-5강
1. 연결 리스트
1) 단일 링크드 리스트 (단일 연결 리스트)
단일 연결리스트는 노드와 노드를 하나의 포인터 멤버로 연결하는 구조이다.
-
필요할 때마다 구조체 자료형의 크기만큼 Heap 영역의 메모리 공간을 할당하면서 다음 구조체 노드의 주소를 next 멤버에 저장한다. 이와 같이 긴 리스트를 형성하면서 필요한 데이터의 개수만큼만 메모리 공간을 사용한다.
-
각 구조체 노드는 자신의 다음 노드를 가리키는 포인터를 포함하며, 마지막 노드의 포인터 필드는 이 링크드 리스트에 더 이상 노드가 없다는 것을 나타내기 위해 NULL로 설정될 것이다.
코드 예시
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 struct EMPLOYEE { 6 char name[20]; 7 int salary; 8 float height; 9 char comAddr[50]; 10 struct EMPLOYEE *next; 11 }; 12 13 int main() 14 { 15 struct EMPLOYEE *ptr; 16 struct EMPLOYEE *head, *tail, *frptr; 17 18 head=tail=frptr=NULL; 19 20 while(1) 21 { 22 ptr=(struct EMPLOYEE*)malloc(sizeof(struct EMPLOYEE)); 23 if(ptr==NULL) 24 { 25 perror("Error "); 26 exit(1); 27 } 28 29 printf("\nname ? (quit:end) "); 30 gets(ptr->name); //kim[enter] 31 32 if(strcmp(ptr->name, "end")==0) 33 break; 34 35 printf("salary ? "); 36 scanf("%d",&ptr->salary); //1000[enter] 37 38 printf("height ? "); 39 scanf("%f%*c",&ptr->height); //173.2[enter] 40 41 42 printf("comAddr ? "); 43 gets(ptr->comAddr); // seoul ...[enter] 44 45 ptr->next=NULL; 46 47 if(head==NULL) 48 head=tail=ptr; 49 else 50 { 51 tail->next = ptr; 52 tail = ptr; 53 } 54 printf("%s, %d, %.2f, %s \n", ptr->name, ptr->salary, 55 ptr->height, ptr->comAddr); 56 57 } //while(1) end 58 free(ptr); 59 ptr = head; 60 while(ptr) 61 { 62 printf("%s, %d, %.2f, %s \n", ptr->name, ptr->salary, 63 ptr->height, ptr->comAddr ); 64 frptr = ptr; 65 ptr = ptr->next; 66 free(frptr); 67 } 68 return 0; 69 }
2) 이중 링크드 리스트(이중 연결 리스트)
이중 링크드 리스트란 각 노드는 전 노드의 주소와 다음 노드의 주소를 포함하는 구조이다. 이때 첫번째 노드는 이전 노드가 없으므로 before는 NULL이 되어야 하며, 마지막 노드도 다음 노드가 없으므로 next는 NULL이 되어야 한다.
코드 예시
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 struct EMPLOYEE { 6 char name[20]; 7 int salary; 8 float height; 9 char comAddr[50]; 10 struct EMPLOYEE *before; 11 struct EMPLOYEE *next; 12 }; 13 14 int main() 15 { 16 struct EMPLOYEE *ptr; 17 struct EMPLOYEE *head, *tail, *frptr; 18 19 head=tail=frptr=NULL; 20 21 while(1) 22 { 23 ptr=(struct EMPLOYEE*)malloc(sizeof(struct EMPLOYEE)); 24 if(ptr==NULL) 25 { 26 perror("Error "); 27 exit(1); 28 } 29 30 printf("\nname ? (quit:end) "); 31 gets(ptr->name); //kim[enter] 32 33 if(strcmp(ptr->name, "end")==0) 34 break; 35 36 printf("salary ? "); 37 scanf("%d",&ptr->salary); //1000[enter] 38 39 printf("height ? "); 40 scanf("%f%*c",&ptr->height); //173.2[enter] 41 42 43 printf("comAddr ? "); 44 gets(ptr->comAddr); // seoul ...[enter] 45 46 ptr->before=NULL; 47 ptr->next=NULL; 48 49 if(head==NULL) 50 head=tail=ptr; 51 else 52 { 53 ptr->before = tail; 54 tail->next = ptr; 55 tail = ptr; 56 } 57 printf("%s, %d, %.2f, %s \n", ptr->name, ptr->salary, 58 ptr->height, ptr->comAddr); 59 60 } //while(1) end 61 free(ptr); 62 /* 63 printf("head->tail \n"); 64 ptr = head; 65 while(ptr) 66 { 67 printf("%s, %d, %.2f, %s \n", ptr->name, ptr->salary, 68 ptr->height, ptr->comAddr ); 69 frptr = ptr; 70 ptr = ptr->next; 71 free(frptr); 72 } 73 */ 74 printf("tail->head \n"); 75 ptr = tail; 76 while(ptr) 77 { 78 printf("%s, %d, %.2f, %s \n", ptr->name, ptr->salary, 79 ptr->height, ptr->comAddr ); 80 frptr = ptr; 81 ptr = ptr->before; 82 free(frptr); 83 } 84 return 0; 85 }
3) 특정 멤버 동적할당
구조체 노드 멤버 중 특정 멤버가 포인터를 갖는 멤버로 구성할 수 있다.
- 내용의 크기에 맞춰서 조절할 수 있다.
- 메모리를 해제할 때 해당 멤버또한 해제해 줘야한다.
4) 연결리스트 정렬하기
어떤 노드가 순서 있는 값을 가지고 있다면 그 값을 기준으로 순서 있는 단일 링크드 리스트를 구성할 수 있다.
링크드 리스트와 달리 head만 지정해준다.
(NULL로 된 0번 구조체를 쓰면 head 없이 정렬할 수 있다..)
2. 스택과 큐
1) 스택(Stack)
스택은 밑이 막힌 상자와 같다. 밑이 막힌 공간에 무언가를 넣고 뺀다는 의미이다. 이때 입구와 출구가 같기 때문에 먼저 들어간 자료는 상자의 밑에 있게 되고, 나중에 들어간 자료는 상자의 위에 쌓이게 된다. 따라서 상자에서 자료를 꺼내면 나중에 들어간 자료, 즉 가장 위의 자료가 먼저 나온다. 그래서 스택을 LIFO(Last In Frist Out) 또는 FILO(First In Last Out) 이라고 한다.
코드예시
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 5 typedef struct _node 6 { 7 int id; 8 char name[20]; 9 struct _node *next; 10 } node; 11 12 void init_stack(void); 13 int push(void); 14 void pop(void); 15 void stack_print(void); 16 void clear_stack(void); 17 18 node *top; 19 20 int main() 21 { 22 int stop =1; 23 char ch; 24 25 init_stack(); 26 27 while(stop) 28 { 29 printf("\n1. Stack push .. \n"); 30 printf("2. Stack print.. \n"); 31 printf("3. Stack pop .. \n"); 32 printf("4. clear stack .. \n"); 33 printf("5. quit .. \n"); 34 printf("\n select ... ? "); 35 36 ch=getchar(); 37 fflush(stdin); 38 39 switch(ch) 40 { 41 case '1' : push(); 42 break; 43 case '2' : stack_print(); 44 break; 45 case '3' : pop(); 46 break; 47 case '4' : clear_stack(); 48 break; 49 case '5' : stop=0; 50 } 51 } 52 return 0; 53 } 54 55 void init_stack(void) 56 { 57 top=NULL; 58 } 59 60 61 int push(void) 62 { 63 node *temp; 64 65 while(1) 66 { 67 68 if ((temp = (node*)malloc(sizeof(node))) == NULL) 69 { 70 printf("memory allocation error...\n"); 71 return -1; 72 } 73 74 printf("\nID ? (quit:-1) "); 75 scanf("%d%*c", &temp->id); 76 //fflush(stdin); 77 if(temp->id==-1) 78 break; 79 printf("NAME ? "); 80 gets(temp->name); 81 82 temp->next=top; 83 top=temp; 84 } 85 free(temp); 86 87 return 1; 88 } 89 90 void stack_print(void) 91 { 92 node *temp; 93 94 temp=top; 95 printf("\nStack list : Top -> Buttom\n"); 96 97 while(temp) 98 { 99 printf("%d, %s \n", temp->id, temp->name); 100 temp=temp->next; 101 } 102 } 103 104 void pop(void) 105 { 106 node *x; 107 108 if (top == NULL) // if empty 109 { 110 printf("Stack underflow... \n"); 111 return ; 112 } 113 114 printf("\nGet node -> id: %d, name: %s \n ",top->id, top->name); 115 //node 주소연결 및 삭제 116 x=top; 117 top=top->next; 118 free(x); 119 } 120 121 void clear_stack(void) 122 { 123 node *x; 124 125 while (top) 126 { 127 x = top; 128 top = top->next; 129 free(x); 130 } 131 }
배열을 이용한 스택
- 스택의 상자를 배열로 정의하고 스택의 상단을 top이라는 인덱스를 통하여 유지한다.
1차원 배열 stack[n]을 이용한 순차 표현
스택을 표현하는 가장 간단한 방법이다.
n은 스택에 저장할 수 있는 최대 원소수이다.
스택의 i번째 원소는 Stack[i-1]에 저장한다.
변수 top은 스택의 top 원소를 가리킨다. (초기 : top = -1)
배열을 이용하여 구현한 스택은 다음과 같다.
구조체를 이용한 스택
- 링크드 리스트를 이용해서 스택을 구현할 때의 장점은 현재 스택에 저장되어 있는 자료 크기만큼 메모리를 사용한다는 것이다. 스택은 입구와 출구가 하나이기 때문에 단일 링크드 리스트도 쉽게 구현할 수 있다.
먼저 링크드 리스트의 스택 구조를 살펴보자. 먼저 스택 초기화는 top 구조체 변수를 NULL로 두어 빈 스택임을 알린다. 그리고 노드가 삽입될 때마다 top 포인터를 변경하여 마지막 노드의 주소를 갖게 한다. 노드가 제거될 때는 값을 반환하고 top 포인터를 이전 노드의 주소로 변경한 후 제거한다.
스택의 특징
-
스택의 링크드 리스트를 이용한 방법은 포인터를 사용하기 때문에 프로그래밍에서 부담이 될 수 있으며, 잘못하면 심각한 논리 오류에 빠질 수 있다. 따라서 정확한 포인터의 활용이 요구된다. 그러나 스택의 자료 개수만큼 노드가 메모리를 차지하고 스택의 크기가 정해져 있지 않아도 메모리의 한계까지 스택의 구조를 늘릴 수 있다는 장점도 있다.
-
스택의 개념은 시스템 내부에서부터 고급 알고리즘까지 매우 다양한 방법으로 사용되고 있으며, 스택의 주 용도는 자료의 임시 저장 장소이다. 시스템 내부에서는 스택이라고 해서 함수의 호출이나 인터럽트 처리시 현재의 주소나 상태를 임시로 저장해 두는데 사용된다. 그리고 고급 알고리즘으로는 산술식의 계산이라든지 재귀 호출 등의 개념에서 사용될 수 있다.
2) 큐
큐의 개념은 입구와 출구가 서로 다른 2개의 통로 구조를 갖는다. 따라서 입구에서는 자료를 넣고, 출구에서는 자료를 꺼낼 수 있다. 즉, 큐는 먼저 들어온 것이 먼저 꺼내진다. 그래서 큐를 LILO(Last In Last Out) 또는 FIFO(First In First Out)이라고 한다.
