[C언어로 쉽게 풀어쓴 자료구조] 6장 연결 리스트 연습문제 해설

출처 : https://www.booksr.co.kr/product/9788970509716/

1. 2

2. 1

3. 3

4. c

5. p=p->link;

6. q=p;

7. 포인터 p가 마지막 노드인 data 'D'가 담겨있는 노드를 가리킨다.

8. 4

deleteLast 연산을 수행하려면, last가 xn-1 노드를 가리켜야 한다. 즉, DQ부터 xn-1 노드까지 탐색을 진행한 후에 last가 xn-1 노드를 가리킨다.

9.

#include<stdio.h>
#include<stdlib.h>
#define max_list_size 100

typedef int element;

typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	if (*phead == NULL) {
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) {
		new_node->link = *phead;
		*phead = new_node;
	}
	else {
		new_node->link = p->link;
		p->link = new_node;
	}
	return;
}

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 remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
	if (p == NULL)
		*phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);
	return;
}

ListNode* create_node(element data) {
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(new_node));
	new_node->data = data;
	new_node->link = NULL;
	return new_node;
}

void display(ListNode* head) {
	ListNode* p = head;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->link;
	}
	printf("\n");
}

int main(void) {
	ListNode* list1 = {};
	int n, t;
	printf("노드의 개수 : ");
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++) {
		printf("노드 #%d 데이터  : ", i + 1);
		scanf_s("%d", &t);
		insert_node_back(&list1, create_node(t));
	}
	printf("생성된 연결 리스트 : ");
	display(list1);
}

 

10.

int get_count(ListNode* head) {
	int count = 0;
	ListNode* p = head;
	while (p != NULL) {
		count++;
		p = p->link;
	}
	return count;
}

 

11.

int get_sum(ListNode* head) {
	int sum = 0;
	ListNode* p = head;
	while (p != NULL) {
		sum += p->data;
		p = p->link;
	}
	return sum;
}

 

12.

int find_element(ListNode* head, element item) {
	ListNode* p;
	p = head;
	int count = 0;
	while (p != NULL) {
		if (p->data == item)
			count++;
		p = p->link;
	}
	return count;
}

 

13.

void remove_element_node(ListNode** head, element item) {
	ListNode* p = NULL, *removed = *head;
	while (removed->data != item) {
		p = removed;
		removed = removed->link;
	}
	if (p == NULL)
		*head = (*head)->link;
	else
		p->link = removed->link;

	free(removed);
	return;
}

 

14.

typedef struct ListNode {
	char name[20] = {};
	int age = {};
	double heigh = {};
	struct ListNode* link;
}ListNode;

 

15.

int find_max(ListNode* head) {
	ListNode* p = head;
	int ans = MIN;
	while (p != NULL) {
		if (p->data > ans)
			ans = p->data;
		p = p->link;
	}
	return ans;
}

int find_min(ListNode* head) {
	ListNode* p = head;
	int ans = MAX;
	while (p != NULL) {
		if (p->data < ans)
			ans = p->data;
		p = p->link;
	}
	return ans;
}

 

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;
		else
			break;
	}
	return;
}

 

17.

// 시간 복잡도는 연결리스트 A, B의 크기를 a, b라고 한다면 O(a + b) 가 된다.
ListNode* alternate(ListNode* A, ListNode* B) {
	ListNode* p = A, * q = B,  *t = NULL;
	while (p != NULL || q != NULL) {
		if(p != NULL){
			insert_node_back(&t, create_node(p->data));
			p = p->link;
		}
		if (q != NULL) {
			insert_node_back(&t, create_node(q->data));
			q = q->link;
		}
	}
	return t;
}

 

18.

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.

void split(ListNode** A, ListNode** B, ListNode* C) {
	ListNode* p = C;
	bool flag = true;
	while (p != NULL) {
		if (flag) {
			insert_node_back(A, create_node(p->data));
			p = p->link;
			flag = false;
		}
		else {
			insert_node_back(B, create_node(p->data));
			p = p->link;
			flag = true;
		}
	}
	return;
}

 

20.

#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) { // a, b 중 하나라도 NULL이 되면(끝에다다르면) while문이 깨진다.
		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.

int poly_eval(ListHeader* plist, int x) {
	int sum = 0;
	ListNode* a = plist->head;
	while (a) {
		int temp = 1;
		for (int i = 0; i < a->expon; i++)
			temp *= x;
		sum += temp * a->coef;
		a = a->link;
	}
	return sum;
}

 

22.

#include<stdio.h>
#include<stdlib.h>
#define MAX_LIST_SIZE 100

typedef struct {
	int list[MAX_LIST_SIZE];
	int length;
}ArrayListType;

void init(ArrayListType* L) {
	L->length = 0;
}
bool is_empty(ArrayListType* L) {
	return L->length == 0;
}
bool 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.

#include<stdio.h>
#include<stdlib.h>

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

void add_element(ListNode** phead, ListNode* new_node) {
	if (*phead == NULL) {
		new_node->link = NULL;
		*phead = new_node;
	}
	else {
		ListNode* c = NULL;
		ListNode* p = *phead;
		while (p != NULL) {
			if (new_node->data < p->data) {
				if (c == NULL) {
					new_node->link = *phead;
					*phead = new_node;
				}
				else {
					c->link = new_node;
					new_node->link = p;
				}
				break;
			}
			c = p;
			p = p->link;
		}
	}
}

void delete_element(ListNode** head, element item) {
	ListNode* p = NULL, * removed = *head;
	while (removed->data != item) {
		p = removed;
		removed = removed->link;
	}
	if (p == NULL)
		*head = (*head)->link;
	else
		p->link = removed->link;
	return;
}

void clear(ListNode** head) {
	(*head)->link = NULL;
}

bool is_in_list(ListNode* head, element item) {
	ListNode* p = head;
	while (p != NULL) {
		if (p->data == item)
			return true;
		p = p->link;
	}
	return false;
}

int get_length(ListNode* head) {
	int count = 0;
	ListNode* p = head;
	while (p != NULL) {
		count++;
		p = p->link;
	}
	return count;
}

bool is_empty(ListNode* head) {
	return head->link == NULL;
}

ListNode* create_node(element data) {
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(new_node));
	new_node->data = data;
	new_node->link = NULL;
	return new_node;
}

bool is_full(ListNode* head) {
	// 노드가 더이상 만들어지지 않는다면 메모리가 가득찬상태.
	ListNode* N = create_node(0);
	if (N == NULL)
		return true;
	return false;
}

void display(ListNode* head) {
	ListNode* p = head;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->link;
	}
	printf("\n");
}

 

24.

typedef struct element {
	int row;
	int col;
	int value;
};
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

 

관심이 있으신 분들에게 유용한 정보였길 바라며

다음은 7장 핵심정리를 가져오도록 하겠습니다.