C언어로 쉽게 풀어쓴 자료구조 [연습문제 7장]

1. (3)   ∵ top은 가장 최근에 입력된 자료를 가리키므로, c를 출력하기 위해서는 pop연산이 3번 필요하다.
   
   

2. (1)   ∵ 배열은 삽입, 삭제 시간복잡도가 모두 O(n)으로 가장 오래 걸린다.
   
   

node* search(node* head, element data) {
	if (head->data == data)
		return head;
	else {
		for (node* p = head->link; p != head; p = p->link)
			if (p->data == data)
				return p;
	}
	return NULL;
}

int get_size(node* head) {
	if (head == NULL)
		return 0;

	int c = 0;
	node* p = head;

	do {
		p = p->link;
		c++;
	} while (p != head);
	return c;
}

5. 장점: 어떤 노드의 선행, 후속 노드를 찾기 용이하다.
   단점: 메모리 소비가 크다
   
   

void reverse(node* head) {
	for (node* p = head->llink; p != head; p = p->llink)
		printf("%d → ", p->data);
}

node* search(node* head, element data) {
	for (node* p = head->rlink; p != head; p = p->rlink) {
		if (p->data == data)
			return p;
	}
	return NULL;
}