C언어로 쉽게 풀어쓴 자료구조
교수님이 안 가르쳐주셔서 독학하는 자료구조 / 6장 연결리스트- 1 / 연습문제 - 2
우럭이안우럭 ・ 2020. 5. 23. 2:43
URL 복사 이웃추가
본문 기타 기능
신고하기
C언어로 쉽게 풀어 쓴 자료구조 / 천인국외 2명/ 생능출판 6장 연습문제
******************************************************
**공부용으로 혼자서 풀어 본것이기 때문에 언제든지 답이 틀릴 수 있습니다. **
******************************************************
14. 다음 그림과 같은 데이터를 저장할 수 있는 단순 연결 리스트를 생성하는 프로그램을 작성해보자.
head
| Name : kim Age : 34 Heigh : 1.7 | Name : park Age : 27 Heigh : 1.2 | Name : lee Age : 48 Heigh : 1.4 | Name : choi Age : 30 Heigh : 1.3 |
| -> | -> | -> | NULL |
typedef struct ListNode {char name[20] = {};int age = {};double heigh = {};struct ListNode* link;}ListNode;
15. 단순 연결 리스트가 정렬되지 않은 정수들의 리스트를 저장하고 있다. 리스트에서 최대값과 최소값을 찾는 프로그램을 작성하라.
#include <stdio.h>#include <stdlib.h>typedef int element;typedef struct ListNode{element data;struct ListNode* link;} ListNode;void insert(ListNode** phead, ListNode* p, ListNode* new_p){if (*phead == NULL){new_p->link = NULL;*phead = new_p;}else{new_p->link = NULL;ListNode* p = *phead;while (p->link != NULL)p = p->link;p->link = new_p;}}ListNode* create_node(element data){ListNode* new_p;new_p = (ListNode*)malloc(sizeof(new_p));new_p->data = data;new_p->link = NULL;return new_p;}void print_list(ListNode* head){for (ListNode* p = head; p != NULL; p = p->link)printf("%d ", p->data);}int Get_Max(ListNode* head){int Max = head->data;for (ListNode* p = head; p != NULL; p = p->link){if (Max < p->data)Max = p->data;}return Max;}int Get_Min(ListNode* head){int Min = head->data;for (ListNode* p = head; p != NULL; p = p->link){if (Min > p->data)Min = p->data;}return Min;}int main(void){int n, num;ListNode* head = NULL;printf("노드의 개수 : ");scanf_s("%d", &n);for (int i = 1; i <= n; i++){printf("노드 #%d 데이터 : ", i);scanf_s("%d", &num);insert(&head, head, create_node(num));}printf("최대값 : %d\n", Get_Max(head));printf("최소값 : %d\n", Get_Min(head));print_list(head);return 0;}
16. 단순 연결 리스트의 헤드 포인터가 주어져 있을 때 첫 번째 노드에서부터 하나씩 건너서 있는 노드를 전부 삭제하는 함수를 작성하라. 즉 홀수번째 있는 노드들이 전부 삭제된다.
void remove_odd_node(ListNode** head) {*head = (*head)->link;ListNode* p = NULL, * removed = *head;while (removed->link != NULL) {p = removed;removed = removed->link;p->link = removed->link;if (removed->link != NULL)removed = removed->link;elsebreak;}return;}
17. 두 개의 단순연결 리스트 A, B가 주어져 있을 경우, alternate함수를 작성하라. alternate 함수는 A와 B로부터 노드를 번갈아 가져와서 새로운 리스트 C를 만드는 연산이다. 만약 입력리스트 중에서 하나가 끝나게 되면 나머지 노드들을 전부 C로 옮긴다. 작성된 함수의 시간복잡도를 구하라.
#include <stdio.h>#include <stdlib.h>typedef int element;typedef struct ListNode{element data;struct ListNode* link;} ListNode;void insert(ListNode** phead, ListNode* p, ListNode* new_p){if (*phead == NULL){new_p->link = NULL;*phead = new_p;}else{new_p->link = NULL;ListNode* p = *phead;while (p->link != NULL)p = p->link;p->link = new_p;}}ListNode* create_node(element data){ListNode* new_p;new_p = (ListNode*)malloc(sizeof(new_p));new_p->data = data;new_p->link = NULL;return new_p;}void print_list(ListNode* head){for (ListNode* p = head; p != NULL; p = p->link)printf("%d ", p->data);}ListNode* alternate(ListNode* head1, ListNode* head2) {ListNode* p = head1;ListNode* q = head2;ListNode* r = NULL;while (p != NULL || q != NULL) {if (p != NULL) {insert(&r, r, create_node(p->data));p = p->link;}if (q != NULL) {insert(&r, r, create_node(q->data));q = q->link;}}return r;}int main(void){int n, num;ListNode* head1 = NULL;ListNode* head2 = NULL;ListNode* result = NULL;printf("리스트 1의 개수 : ");scanf_s("%d", &n);for (int i = 1; i <= n; i++){printf("리스트 1 - 노드 #%d 데이터 : ", i);scanf_s("%d", &num);insert(&head1, head1, create_node(num));}printf("리스트 2의 개수 : ");scanf_s("%d", &n);for (int i = 1; i <= n; i++){printf("리스트 2 - 노드 #%d 데이터 : ", i);scanf_s("%d", &num);insert(&head2, head2, create_node(num));}print_list(alternate(head1, head2));return 0; }//시간 복잡도는 head1과 head2의 노드의 개수 n번씩 반복되기 떄문에 O(n)이 된다.
18. 2개의 단순 연결 리스트를 병합하는 함수를 조금 변경하여 보자. 두 개의 연결리스트 a, b가 데이터값의 오름차순으로 노드들이 정렬되어 있는 경우, 이러한 정렬상태를 유지하면서 합병을 하여 새로운 연결리스트를 만드는 알고리즘 merge를 작성하라. a와 b에 있는 노드들은 전부 새로운 연결 리스트로 옮겨진다. 작성된 알고리즘의 시간복잡도도 구하라.
ListNode* merge(ListNode* A, ListNode* B) {ListNode* p = A, * q = B, * t = NULL;while (p != NULL && q != NULL) {if (p->data < q->data) {insert_node_back(&t, create_node(p->data));p = p->link;}else {insert_node_back(&t, create_node(q->data));q = q->link;}}while (p != NULL) {insert_node_back(&t, create_node(p->data));p = p->link;}while (q != NULL) {insert_node_back(&t, create_node(q->data));q = q->link;}return t;}
19. 단순 연결 리스트 C를 두 개의 단순 연결 리스트 A와 B로 분리하는 함수 split를 작성하여 보자. C의 홀수 번째 노드들을 모두 A로 이동되고 C의 짝수 번째 노드들은 모두 B로 이동된다. 이 함수가 C를 변경하여서는 안된다. 작성된 알고리즘의 시간 복잡도를 구하고 구현하여 수행하여보라.
#include <stdio.h>#include <stdlib.h>typedef int element;typedef struct ListNode{element data;struct ListNode* link;} ListNode;void insert_node_back(ListNode** phead, ListNode* new_node) {if (*phead == NULL) {new_node->link = NULL;*phead = new_node;}else {new_node->link = NULL;ListNode* p = *phead;while (p->link != NULL)p = p->link;p->link = new_node;}}void insert(ListNode** phead, ListNode* p, ListNode* new_p){if (*phead == NULL){new_p->link = NULL;*phead = new_p;}else{new_p->link = NULL;ListNode* p = *phead;while (p->link != NULL)p = p->link;p->link = new_p;}}ListNode* create_node(element data){ListNode* new_p;new_p = (ListNode*)malloc(sizeof(new_p));new_p->data = data;new_p->link = NULL;return new_p;}void print_list(ListNode* head){for (ListNode* p = head; p != NULL; p = p->link)printf("%d ", p->data);}void split(ListNode* C, ListNode** A, ListNode** B) {ListNode* r = C;while (r != NULL) {insert_node_back(A, create_node(r->data));r = r->link;if (r == NULL)break;insert_node_back(B, create_node(r->data));r = r->link;}return;}int main(void){int n, num;ListNode* A = NULL;ListNode* B = NULL;ListNode* C = NULL;printf("리스트 C의 개수 : ");scanf_s("%d", &n);for (int i = 1; i <= n; i++){printf("노드 #%d 데이터 : ", i);scanf_s("%d", &num);insert(&C, C, create_node(num));}split(C, &A, &B);printf("리스트 A : ");print_list(A);printf("\n리스트 B : ");print_list(B);return 0; }// 연결리스트 C의 개수 n개에 따라 이루어지므로 시간복잡도는 O(n)
20. 두개의 다항식이 다음과 같이 주어졌다. 이들을 연결 리스트를 이용하여 나타내고 본문의 프로그램을 이용하여 두 다항식의 합을 구해보시오.
A(x) = 3x^6 + 7x^3 -2x^2 -9 , B(x) = -2x^6 -4x^4 + 6x^2 + 6x +1
#include<stdio.h>#include<stdlib.h>typedef struct ListNode {int coef;int expon;struct ListNode* link;} ListNode;typedef struct ListHeader {int length;ListNode* head;ListNode* tail;}ListHeader;void init(ListHeader* plist) {plist->length = 0;plist->head = plist->tail = NULL;}void insert_node_last(ListHeader* plist, int coef, int expon) {ListNode* temp = (ListNode*)malloc(sizeof(ListNode));temp->coef = coef;temp->expon = expon;temp->link = NULL;if (plist->tail == NULL) {plist->head = plist->tail = temp;}else {plist->tail->link = temp;plist->tail = temp;}plist->length++;}void poly_add(ListHeader* plist1, ListHeader* plist2, ListHeader* plist3){ListNode* a = plist1->head;ListNode* b = plist2->head;int sum;while (a && b) {if (a->expon == b->expon) {sum = a->coef + b->coef;if (sum != 0)insert_node_last(plist3, sum, a->expon);a = a->link; b = b->link;}else if (a->expon > b->expon) {insert_node_last(plist3, a->coef, a->expon);a = a->link;}else {insert_node_last(plist3, b->coef, b->expon);b = b->link;}}while (a) {insert_node_last(plist3, a->coef, a->expon);a = a->link;}while (b) {insert_node_last(plist3, b->coef, b->expon);b = b->link;}}void poly_print(ListHeader* plist) {ListNode* p = plist->head;while (p) {printf("%d %d\n", p->coef, p->expon);p = p->link;}}int main(void) {ListHeader list1, list2, list3;init(&list1); init(&list2); init(&list3);insert_node_last(&list1, 3, 6);insert_node_last(&list1, 7, 3);insert_node_last(&list1, -2, 2);insert_node_last(&list1, -9, 0);insert_node_last(&list2, -2, 6);insert_node_last(&list2, -4, 4);insert_node_last(&list2, 6, 2);insert_node_last(&list2, 6, 1);insert_node_last(&list2, 1, 0);poly_add(&list1, &list2, &list3);poly_print(&list3);}
21. 다항식을 연결 리스트로 표현할 수 있음을 보였다. 다항식이 연결 리스트로 표현되어 있고, p를 다항식을 가리키는 포인터라고 할 때, 어떤 실수 x에 대하여 이 다항식의 값을 계산하는 함수 poly_eval을 작성하라. 즉 다항식이 x^3 + 2x +6이고 x=2이면 2^3 + 2*2 + 6를 계산하는 함수를 작성하여보라.
#include <stdio.h>#include <stdlib.h>typedef struct ListNode {int coef;int expon;struct ListNode* link;} ListNode;typedef struct ListType {int size;ListNode* head;ListNode* tail;} ListType;void error(const char* message){fprintf(stderr, "%s\n", message);exit(1);}ListType* create(){ListType* plist = (ListType*)malloc(sizeof(ListType));plist->size = 0;plist->head = plist->tail = NULL;return plist;}void insert_last(ListType* plist, int coef, int expon){ListNode* temp =(ListNode*)malloc(sizeof(ListNode));if (temp == NULL) error("메모리 할당 에러");temp->coef = coef;temp->expon = expon;temp->link = NULL;if (plist->tail == NULL) {plist->head = plist->tail = temp;}else {plist->tail->link = temp;plist->tail = temp;}plist->size++;}void poly_print(ListType* plist){ListNode* p = plist->head;printf("polynomial = ");for (; p; p = p->link) {printf("%d*x^%d + ", p->coef, p->expon);}printf("\n");}int poly_eval(ListType* plist, int x){ListNode* p = plist->head;int result, eval = 0;for (; p; p = p->link){result = 1;for (int i = 0; i < p->expon; i++)result *= x;result = p->coef * result;eval += result;}return eval;}int main(void){ListType* list;int x = 0;list = create();// 다항식 1을 생성 insert_last(list, 3, 2);insert_last(list, 2, 1);insert_last(list, 1, 0);poly_print(list);printf("미지수 x의 값 : ");scanf_s("%d", &x);printf("다항식의 값 = %d" , poly_eval(list, x));free(list);}
22. 배열을 이용하여 숫자들을 입력 받아 항상 오름차순으로 정렬된 상태로 유지하는 리스트 Sort-edList를 구현하여 보라. 다음의 연산들을 구현하면 된다.
#include<stdio.h>#include<stdlib.h>#define MAX_LIST_SIZE 100typedef struct {int list[MAX_LIST_SIZE];int length;} ArrayListType;void init(ArrayListType* L) {L->length = 0;}void is_empty(ArrayListType* L) {return L->length == 0;}void is_full(ArrayListType* L) {return L->length == MAX_LIST_SIZE;}void add_item(ArrayListType* L, int item) {if (is_full(L)) {printf("이미 배열이 가득찼습니다.\n");return;}int i = 0;for (i = 0; i < L->length; i++) {if (item < L->list[i]) {for (int j = L->length; j > i; j--)L->list[j] = L->list[j - 1];break;}}L->list[i] = item;L->length++;}void delete_item(ArrayListType* L, int item) {int i;for (i = 0; i < L->length; i++) {if (item == L->list[i]) {for (int j = i; j < L->length; j++) {L->list[j] = L->list[j + 1];}}}L->length--;}void clear_list(ArrayListType* L, int item) {L->length = 0;}bool is_in_list(ArrayListType* L, int item){for (int i = 0; i < L->length; i++)if (L->list[i] == item)return true;return false;}int get_length(ArrayListType* L) {return L->length;}void display(ArrayListType* L) {for (int i = 0; i < L->length; i++)printf("%d ", L->list[i]);printf("\n");}
23. 단순 연결 리스트를 이용하여 숫자들을 항상 오름차순으로 정렬된 상태로 유지하는 리스트 SortedList를 구현하여 보라. 앞의 문제의 연산들을 구현하면 된다.
#include<stdio.h>#include<stdlib.h>typedef int element;typedef struct ListNode{element data;struct ListNode* link;} ListNode;void add(ListNode** phead, ListNode* node) {if (*phead == NULL) {node->link = NULL;*phead = node;}else{ListNode* p = NULL;ListNode* q = *phead;for (ListNode* q = *phead; q = q->link; q == NULL){if (node->data < p->data){if (c == NULL){node->link = *phead;*phead = node}else{p->link* node;node->link = q;}break;}}}}void Delete(ListNode * *head, element item){ListNode* p = NULL;ListNode* removed = *head;while (removed->data != item) {p = removed;removed = removed->link;}if (p == NULL)*head = *head->link;elsep->link = removed->link;return;}void clear(ListNode * *head){*head->link = NULL;}void is_in_list(ListNode * head, element item) {ListNode* p = head;while (p != NULL) {if (p->data == item)return 1;p = p->link;}return 0;}int get_length(ListNode * head) {int count = 0;ListNode* p = head;for (ListNode* p = head; p = p->link; p == NULL)count++;return count;}void is_empty(ListNode * head) {return head->link == NULL;}ListNode* create_node(element data) {ListNode* node;node = (ListNode*)malloc(sizeof(new_node));node->data = data;node->link = NULL;return node;}void is_full(ListNode * head) {ListNode* N = create_node(0);if (N == NULL)return 1;return 0;}void display(ListNode* head){ListNode* p = head;while (p != NULL){printf("%d ", p->data);p = p->link;}printf("\n");}
댓글6 이 글에 댓글 단 블로거 열고 닫기
인쇄
