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

01 (2)

02 (1) 인덱스를 통해 바로 접근할 수 있다

03 (3)

04 (c)

05 p = p->link;

06 q = p;

07 D

08 (4) delete는 insert와 달리 탐색을 한 후 삭제를 해야되기 때문에 DQ부터 Xn까지의 탐색이 필요

09

ListNode* insert_last(ListNode* head,element item){
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = item;
	newnode->link = NULL;
	ListNode* p = head;
	if(p==NULL) head = newnode;
	else {
		while(p->link !=NULL){
			p = p->link;
		}
		p->link = newnode;
	}
	return head;
}

int main(void){
	ListNode *head = NULL;
	element item;
	int num;
	printf("노드의 개수: ");
	scanf("%d",&num);
	for(int i=0; i<num; i++){
		printf("노드 #%d의 데이터: ",i+1);
		scanf("%d",&item);
		head = insert_last(head,item);
		print_list(head);
	}
	return 0;
}

10, 11, 12

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

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

int how_many(ListNode* head, element item){  //12번
	int count=0;
	for(ListNode* p = head; p!=NULL; p = p->link){
		if(p->data == item) count++;
	}
	return count;
}

int main(void){
	ListNode *head = NULL;
	head = insert_first(head,1);
	head = insert_first(head,2);
	head = insert_first(head,2);
	head = insert_first(head,3);
	
	printf("노드의 개수는 %d\n",get_count(head));
	printf("노드들의 데이터 합은 %d\n",get_sum(head));
	printf("2는 연결리스트에서 %d번 나타난다.\n",how_many(head,2));
	return 0;
}

13

ListNode* delete_element(ListNode* head,element item){
	ListNode* p =head;
	ListNode* pre = head;
	ListNode* removed;
	
	while(p->data != item) p = p->link;
	removed = p;
	while(pre->link != p) pre = pre->link; //삭제하려는 노드의 이전노드 포인터를 찾아서
	pre->link = removed->link; // 링크 필드를 삭제하는 노드가 연결하던 노드로 옮긴다.
	free(removed);
	return head;
}



int main(void){
	ListNode *head = NULL;
	head = insert_first(head,1);
	head = insert_first(head,2);
	head = insert_first(head,3);
	head = insert_first(head,4);
	
	head = delete_element(head,3);
	print_list(head);
	
	return 0;
}

14

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


typedef struct PersonNode{
	char Name[20];
	int Age;
	float Height;
}PersonNode;

typedef struct ListNode{
	PersonNode pe;
	struct ListNode *link;
}ListNode;

ListNode* insert_first(ListNode *head, char name[], int age,float height){
	ListNode *p = (ListNode*)malloc(sizeof(ListNode));
	strcpy(p->pe.Name,name);
	p->pe.Age = age;
	p->pe.Height = height;
	p->link = head;
	head = p;
	return head;
}

void print_list(ListNode* head){
	for(ListNode *p = head;p!=NULL;p=p->link){
		printf("Name:%s  Age:%d  Height:%f ->\n", p->pe.Name,p->pe.Age,p->pe.Height);
	}
	printf("NULL\n");
}

int main(void){
	ListNode *head = NULL;
	head = insert_first(head,"choi",30,1.3);
	head = insert_first(head,"lee",48,1.4);
	head = insert_first(head,"park",27,1.2);
	head = insert_first(head,"Kim",34,1.7);

	print_list(head);
	
	return 0;
}

string을 매개변수로 받고싶을 때 strcpy와 ", ' 쌍따옴표 구분에 주의

 

15

int main(void){
	ListNode *head = NULL;
	element item;
	int num;
	printf("노드의 개수: ");
	scanf("%d",&num);
	for(int i=0; i<num; i++){
		printf("노드 #%d의 데이터: ",i+1);
		scanf("%d",&item);
		head = insert_last(head,item);
	}
	
	int max=0;
	int min = 999999;
	for(ListNode *p=head; p!=NULL; p = p->link){
		if(max<p->data){
			max=p->data;
		}
		else if(min>p->data){
			min = p->data;
		}
	}
	printf("최대값은 %d, 최소값은 %d\n",max,min);
	return 0;	
}

9번 코드에서 main 함수 변경

 

16

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

ListNode* delete_odd(ListNode* head){
	ListNode* removed;
	ListNode* itr;
	
	int num=get_count(head);
	if(head==NULL) return NULL;
	removed = head;
	head = removed->link;
	free(removed);
	itr = head; // head 삭제
	
	for(int i=0;i<(num-1)/2;i++){
		removed = itr ->link;
		itr->link = removed->link;
		free(removed);
		itr = itr->link;
	} // for문으로 남은 홀수번째 노드들 삭제
	
	return head;
	
}

int main(void){
	ListNode *head = NULL;
	for(int i=0;i<6;i++){
		head =insert_first(head,i);
	}
	print_list(head);
	head = delete_odd(head);
	print_list(head);
}

17

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

typedef int element;
typedef struct ListNode{
	element data;
	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, element data){
	ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
	if(temp == NULL) error("메모리 할당 에러");
	temp->data = data;
	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;
	
	for(; p; p = p->link){
		printf("%d-> ",p->data);
	}
	printf("NULL\n");
}

void alternate(ListType* head1, ListType* head2, ListType* head3){
	ListNode* p = head1->head;
	ListNode* q = head2->head;
	
	while(p&&q){ // p와 q가 null이 아닌동안
		insert_last(head3,p->data);
		p=p->link;
		insert_last(head3,q->data);
		q=q->link;
	}
	
	for(; p!=NULL; p= p->link){
		insert_last(head3, p->data);
	}
	for(; q!=NULL; q = q->link){
		insert_last(head3, q->data);
	}
}



int main(void){
	ListType *list1, *list2, *list3;
	
	list1 = create();
	list2 = create();
	list3 = create();
	
	insert_last(list1,10);
	insert_last(list1,20);
	insert_last(list1,30);
	
	insert_last(list2,1);
	insert_last(list2,2);
	insert_last(list2,3);
	
	alternate(list1,list2,list3);
	poly_print(list3);
	
	free(list1);
	free(list2);
	free(list3);
}

18

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

typedef int element;
typedef struct ListNode{
	element data;
	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, element data){
	ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
	if(temp == NULL) error("메모리 할당 에러");
	temp->data = data;
	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;
	
	for(; p; p = p->link){
		printf("%d-> ",p->data);
	}
	printf("NULL\n");
}

void insert(ListNode* pre, element data){
	ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
	if(temp == NULL) error("메모리 오류");
	temp->data = data;
	temp->link = pre->link;
	pre->link = temp;
}



void merge(ListType* list1, ListType* list2, ListType* list3){
	ListNode* a =list1->head;
	ListNode* b =list2->head;
	while(a&&b){
		if(a->data >= b->data){
			if(list3->tail ==NULL){
				insert_last(list3,b->data);
				b=b->link;
				insert_last(list3,a->data);
				a=a->link;
				poly_print(list3);
			}
			else{
				ListNode *p =list3->head; // 이 밖에 선언하면 head가 NULL로 읽힘
				if(list3->tail->data < b->data){// list3안 데이터들이 삽입할 데이터보다 작음
					insert_last(list3,b->data);
					b=b->link;
					insert_last(list3,a->data);
					a=a->link;
					poly_print(list3);
				}
				else{
					//p를 통해 삽입할 데이터보다 작은 노드에 접근
					while(p->data <= b->data && p->link != NULL){
						p=p->link;
					}
					//pre를 통해 p이전의 노드를 가리킴
					ListNode* pre = list3->head;
					while(pre->link != p){
						pre = pre->link;
					}
					insert(pre,b->data);
					b=b->link;
					insert_last(list3,a->data);
					a=a->link;
					poly_print(list3);
				}
			}
		}
		else{
			if(list3->tail ==NULL){
				insert_last(list3,a->data);
				a=a->link;
				insert_last(list3,b->data);
				b=b->link;
			}
			else{
				ListNode *p =list3->head;
				if(list3->tail->data < a->data){
					insert_last(list3,a->data);
					a=a->link;
					insert_last(list3,b->data);
					b=b->link;
				}
				else{
					while(p->data <= a->data && p->link != NULL){
						p=p->link;
					}
					ListNode* pre = list3->head;
					while(pre->link != p){
						pre = pre->link;
					}
					insert(pre,a->data);
					a=a->link;
					insert_last(list3,b->data);
					b=b->link;
				}
			}
		}
	}
}



int main(void){
	ListType *list1, *list2, *list3;
	
	list1 = create();
	list2 = create();
	list3 = create();
	
	insert_last(list1,10);
	insert_last(list1,20);
	insert_last(list1,30);
	
	insert_last(list2,1);
	insert_last(list2,2);
	insert_last(list2,34);
	
	merge(list1,list2,list3);
	poly_print(list3);
	
	free(list1);
	free(list2);
	free(list3);
}

19

void split(ListType* list1,ListType* list2,ListType* list3){
	ListNode* p = list3->head;
	int num = list3->size;
	if(num%2!=0){
		for(int i=0;i<(num-1)/2;i++){
			insert_last(list1,p->data);
			p=p->link;
			insert_last(list2,p->data);
			p=p->link;
		}
		insert_last(list1,p->data);
	}
	else{
		for(int i=0;i<(num/2)-1;i++){
			insert_last(list1,p->data);
			p=p->link;
			insert_last(list2,p->data);
			p=p->link;
		}
		insert_last(list1,p->data);
		p=p->link;
		insert_last(list2,p->data);
	}
}


int main(void){
	ListType *list1, *list2, *list3;
	
	list1 = create();
	list2 = create();
	list3 = create();
	
	insert_last(list3,10);
	insert_last(list3,20);
	insert_last(list3,30);
	insert_last(list3,40);
	insert_last(list3,50);
	insert_last(list3,60);
	
	split(list1,list2,list3);
	poly_print(list1);
	poly_print(list2);
	poly_print(list3);
	
	free(list1);
	free(list2);
	free(list3);
}

20, 21

int poly_eval(ListType* plist,element x){ //21
	ListNode* p = plist->head;
	int sum=0;
	for(; p; p = p->link){
		int coef,exp;
		int mult=1;
		coef = p->coef;
		exp = p->expon;
		for(int i=0;i<exp;i++){
			mult *=x;
		}
		sum += (coef)*mult;
	}
	return sum;
}



int main(void){
	ListType *list1, *list2, *list3;
	
	list1 = create();
	list2 = create();
	list3 = create();
	
	insert_last(list1,3,6);
	insert_last(list1,7,3);
	insert_last(list1,-2,2);
	insert_last(list1,-9,0);
	
	insert_last(list2,-2,6);
	insert_last(list2,-4,4);
	insert_last(list2,6,2);
	insert_last(list2,6,1);
	insert_last(list2,1,0);
	
	poly_print(list1);
	poly_print(list2);
	
	poly_add(list1,list2,list3);
	poly_print(list3);
	
	printf("list1에 2를 대입하면 %d\n",poly_eval(list1,2));
	free(list1);
	free(list2);
	free(list3);
}

23

ListNode* insert_ascending(ListNode* head,element data){
	ListNode *temp = (ListNode*)malloc(sizeof(ListNode));
	temp->data = data;
	temp->link = NULL;
	ListNode *p = head;
	if(p == NULL){
		head=temp;
	}
	else{
		if(p->data > data){//뒤에 들어온 노드가 헤드보다 작으면 교체
			temp->link = head;
			head = temp;
		}
		else{
			while(p->data < data && p->link != NULL){
				p=p->link;//현재 p는 들어갈 위치의 post를 가리킴
			}
			if(p->data > data){//post가 입력값보다 크면 pre위치에 넣기
				ListNode* pre = head;
				while(pre->link !=p){
					pre = pre->link;
				}//이중리스트면 llink로 바로 풀텐데..
				temp->link = pre->link;
				pre->link = temp;
			}
			else{
				temp->link = p->link;
				p->link = temp;
			}
		}
	}
	return head;
}



int main(void){
	ListNode *head = NULL;
	head = insert_ascending(head,1);
	print_list(head);
	head = insert_ascending(head,4);
	print_list(head);
	head = insert_ascending(head,2);
	print_list(head);
	head = insert_ascending(head,6);
	print_list(head);
	head = insert_ascending(head,3);
	print_list(head);
	head = insert_ascending(head,5);
	print_list(head);
	
	return 0;
}