[C언어로 쉽게 풀어쓴 자료구조] Chapter6. 연결 리스트 I (2)

202~208p LAB

ListNode* search_list(ListNode* head,element x){
	ListNode* p = head;
	while(p !=NULL){
		if(p->data == x) return p;
		p=p->link;
	}
	return NULL;
}

int where_is_x(ListNode* head,element x){
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p = head;
	int count =1;
	ListNode* search = search_list(head,x);
	if(search != NULL){
		while(p!=search){
			count++;
			p=p->link;
		}
		return count;
	}
	else{
		count =0;
		return count;
	}
}

int main(void){
	ListNode *head = NULL;
	
	
	for(int i=0; i<5;i++){
		head= insert_first(head,i);
		print_list(head);
	}
	int pos = where_is_x(head,3); // where_is_x를 pos위치에 바로 넣으면
	                              // 계속 함수를 호출한다. 조심.
	
	if(pos!=0){
		printf("3은 %d번째 노드입니다\n",pos);
	}
	else{
		printf("3은 리스트에 없습니다\n");
	}
	
	
	head= delete_first(head);
	print_list(head); // 지우고 나서 한번 더 확인
	
	pos= where_is_x(head,3);
	if(pos!=0){
		printf("3은 %d번째 노드입니다\n",pos);
	}
	else{
		printf("3은 리스트에 없습니다\n");
	}
	
	return 0;
}

202p search_list와 더불어 탐색하는 값이 몇 번째 노드인지 반환하는 where_is_x를 구현했다.

 

ListNode* concat_list(ListNode* head1,ListNode* head2)
{
	if (head1 == NULL) return head2;
	else if (head2 == NULL) return head1;
	else{
		ListNode* p;
		p=head1;
		while(p->link != NULL)
			p=p->link; 
		p->link = head2;
		return head1;
	}
}



int main(void){
	ListNode *head1 = NULL;
	ListNode *head2 = NULL;
	head1 = insert_first(head1,10);
	head1 = insert_first(head1,20);
	head1 = insert_first(head1,30);
	print_list(head1);
	
	head2 = insert_first(head2,40);
	head2 = insert_first(head2,50);
	print_list(head2);
	
	ListNode* total = concat_list(head1,head2);
	print_list(total);
	
	return 0;
}

204p concat_list 구현

 

ListNode* reverse(ListNode *head){
	ListNode *p, *q, *r;
	p= head; // 역순으로 만들 리스트
	q= NULL; // 역순으로 만들 노드
	while(p != NULL){
		r = q; // 역순으로 된 리스트
		q = p;
		p = p->link;
		q->link = r;
	}
	return q;
}


int main(void){
	ListNode *head1 = NULL;
	ListNode *head2 = NULL;
	
	head1= insert_first(head1,10);
	head1= insert_first(head1,20);
	head1= insert_first(head1,30);
	print_list(head1);
	
	head2= reverse(head1);
	print_list(head2);
	return 0;
}

206p reverse 구현

 

6.6 연결 리스트의 응용: 다항식

typedef struct ListNode{
	int coef;
	int expon;
	struct ListNode *link;
}ListNode;

다항식의 각 항을 하나의 노드로 표현하기 위해 계수(coef), 지수(exp)와 다음 항을 가리키는

링크 필드를 구조체 멤버로 가진다.

 

두 다항식 A와 B를 각각 포인터 p와 q가 가리킬 때,

1. p.expon == q.expon
2. p.expon < q.expon
3. p.expon > q.expon

이렇게 3가지 경우를 구분하여 처리할 수 있다.

case1일 땐 두 계수를 더해서 0이 아니라면 새로운 항을 만들어 다항식 C에 추가한 뒤 p와 q를 이동시킨다.

case2, 3일 땐 각각 q, p 가 지시하는 항을 새로운 항으로 복사하여 다항식 C에 추가한 뒤 각 포인터를 이동시킨다.

 

p나 q 둘 중 하나가 NULL이 된다면 나머지 포인터가 가리키는 다항식의 남아 있는 항들을 전부 C로 가져온다.

 

 

typedef struct ListType{
	int size;
	ListNode *head;
	ListNode *tail;
}ListType;

 

위 그림은 헤더 노드를 통해 리스트를 표현한 것으로, 첫번째 노드를 head에, 마지막 노드를 tail에

포인터를 통해 나타내고, 연결 리스트에 들어 있는 항목들의 개수를 size 변수를 통해 담은 것이다.

 

- tail 포인터 사용시 맨 끝 노드로 바로 접근할 수 있다.

- 연결 리스트를 생성한 후엔 헤더 노드를 초기화시켜주어야 한다.

- 각 다항식의 헤더노드에서 tail 포인터를 유지함으로서 항상 마지막 노드에 접근 가능하게 한다.

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

typedef int element;
typedef struct ListNode{
	int coef;
	int expon;
	struct ListNode *link;
}ListNode;

typedef struct ListType{
	int size;
	ListNode *head;
	ListNode *tail;
}ListType;

ListType *create(){
	ListType *plist = (ListType*)malloc(sizeof(ListType));
	plist -> size = 0;
	plist -> head = plist->tail = NULL;
	return plist;
}

void error(char *message){
	fprintf(stderr,"%s\n",message);
	exit(1);
}

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_add(ListType* a, ListType* b, ListType* c){
	ListNode* p = a->head;
	ListNode* q = b->head;
	int sum;
	
	while(p&&q){ // p와 q가 null이 아닌동안
		if(p->expon == q->expon){ //case1
			sum = p->coef + q -> coef;
			if(sum !=0) insert_last(c,sum,p->expon);
			p = p->link;
			q = q->link;
		}
		else if(p->expon > q->expon){ //case2
			insert_last(c,p->coef,p->expon);
			p = p->link;
		}
		else{ //case3
			insert_last(c,q->coef,q->expon);
			q = q->link;
		}
	}
	
	for(; p!=NULL; p= p->link){
		insert_last(c, p->coef, p->expon);
	}
	for(; q!=NULL; q = q->link){
		insert_last(c, q->coef, q->expon);
	}
}

void poly_print(ListType* plist){
	ListNode* p = plist->head;
	
	printf("polynomial = ");
	for(; p; p = p->link){
		printf("%d^%d + ",p->coef,p->expon);
	}
	printf("\n");
}



int main(void){
	ListType *list1, *list2, *list3;
	
	list1 = create();
	list2 = create();
	list3 = create();
	
	insert_last(list1,3,12);
	insert_last(list1,2,8);
	insert_last(list1,1,0);
	
	insert_last(list2,8,12);
	insert_last(list2,-3,10);
	insert_last(list2,10,6);
	
	poly_print(list1);
	poly_print(list2);
	
	poly_add(list1,list2,list3);
	poly_print(list3);
	
	free(list1);
	free(list2);
	free(list3);
}