2011년7월11일_연결리스트(Linked list)구조를 만드는 이유와 이중연결리스트(double linked list)
| ● CM선생님의 말씀 Q. 이 소스코드의 주제는? A. 구조체배열식 자료구조 + 포인터를 이용한 연결 = 연결리스트 Q. 버블정렬에서 5개의 원소들을 정렬하는데 걸리는 시간? A. 4 + 3 + 2 + 1 = 10번 Q. 데이터, 정보, IT란? A. 정보를 구분하려면 기준이 필요하다. 정보는 사실 + 가치 = 가치있는 검증된 사실이다. (사실들은 데이터이겠군.) Q. 변수, 배열, 구조체가 필요한 이유? A. 자료 = 데이터 변수는 데이터를 저장하기 위한 메모리 ex) for문에선 반복횟수를 정하는 변수가 있다. 모든 프로그램의 변수들은 자료를 저장. int x, y, z; 변수에 어떤 값을 넣을지 프로그래머가 의미를 부여하면 정보가 됨. 배열은 이런 데이터의 집합을 관리하기 위한 자료구조의 하나로 모두 같은 자료형이 여러 개 모인 형태이다. 구조체는 여러 자료형의 데이터를 효율적으로 관리하기 위한 자료구조 중 하나. Q. 연결리스트(linked list)를 만드는 이유? A. 연결리스트는 자료를 저장하기 위한 자료구조로 자료를 찾기 쉽도록 만든 자료구조이다. 배열의 경우 자료를 순차적으로 넣은 뒤 새로운 자료가 들어 왔을 때 다른 자료의 위치까지 바꿔야 하는 문제가 있어 자료를 관리하기 힘들다. 그래서 각 자료마다 포인터로 다음 자료를 가리키게 연결한 구조가 연결리스트이고, 연결리스트는 가상으로 자료를 정렬한다. 실제 구조체의 데이터가 이동하는 것이 아니라, 포인터가 가리키는 곳의 위치만 변경이 되어 화면에 출력시 정렬된 형태로 출력이 된다. 이 때까지 배운 변수, 배열, 구조체의 자료구조 보다 검색의 효율이 높으나, 실제 자료외에 포인터변수가 필요하므로 메모리가 낭비된다. 이렇게 데이터외의 포인터변수들을 오버헤드라고 한다.
|
//도식과 설명추가할 것.
● node.h
1: #ifndef __NODE_H__
2: #define __NODE_H__ 3: #if 0 4: typedef struct _node 5: {
6: int iNum; 7: struct _node *next; 8: } NODE;
9: #else 10: typedef struct _node 11: {
12: int iNum; 13: struct _node *prev; 14: struct _node *next; 15: } NODE;
16: #endif 17: #endif //__NODE_H__ |
● test.c
1: /* 2: * 구조체배열을 선언한 뒤 초기화하고, 3: * 각 배열의 링크드리스트를 만든 뒤에, 4: * 오름차순정렬과 내림차순정렬을 하여 출력. 5: * 6: * 작성일자: 2011년 7월 8일 금요일 7: * 수정일자: 2011년 7월 11일 월요일 8: * 소 속: 내장형하드웨어 9: * 작 성 자: 김수만 10: */ 11:
12: #include <stdio.h>
13: #include "node.h" //NODE구조체로 Linked List를 사용할 시 꼭 추가할 것. 14:
15: int main() 16: {
17: NODE array[5]; //구조체배열의 선언 18: NODE *head; //구조체포인터의 선언 (자동화용) 19:
20: //구조체배열 멤버의 초기화 5, 1, 4, 2, 3(?) 21: array[0].iNum = 5;
22: array[1].iNum = 1;
23: array[2].iNum = 4;
24: array[3].iNum = 2;
25: array[4].iNum = 3;
26:
27: //최초 링크 ----------------------------------------------------- 28: array[0].prev = 0; //끝 29: array[0].next = &array[1];
30:
31: array[1].prev = &array[0];
32: array[1].next = &array[2];
33:
34: array[2].prev = &array[1];
35: array[2].next = &array[3];
36:
37: array[3].prev = &array[2];
38: array[3].next = &array[4];
39:
40: array[4].prev = &array[3];
41: array[4].next = 0; //끝 42:
43: //문제. 최초의 값 출력 44: printf("\n최초의 값\n"); 45: head = array;
46: while(NULL != head) 47: {
48: printf("%d -> ", head->iNum); 49: head = head->next;
50: }
51: printf("NULL\n"); 52:
53: //역순 출력 3,2,4,1,5 ------------------------------------------ 54: printf("\n역순(while문)\n"); 55: head = &array[4];
56: while(NULL != head) 57: {
58: printf("%d -> ", head->iNum); 59: head = head->prev;
60: }
61: printf("NULL\n"); 62:
63: //오름차순정렬 1,2,3,4,5 --------------------------------------- 64: printf("\n오름차순정렬(?)\n"); 65: array[0].prev = &array[2];
66: array[0].next = 0;
67:
68: array[1].prev = 0;
69: array[1].next = &array[3];
70:
71: array[2].prev = &array[4];
72: array[2].next = &array[0];
73:
74: array[3].prev = &array[1];
75: array[3].next = &array[4];
76:
77: array[4].prev = &array[3];
78: array[4].next = &array[2];
79:
80: head = &array[1];
81: while(NULL != head) 82: {
83: printf("%d -> ", head->iNum); 84: head = head->next;
85: }
86: printf("NULL\n"); 87:
88:
89: //내림차순출력 5,4,3,2,1 ----------------------------------------- 90: printf("\n내림차순정렬(?)\n"); 91:
92: head = &array[0];
93: while(NULL != head) 94: {
95: printf("%d -> ", head->iNum); 96: head = head->prev;
97: }
98: printf("NULL\n"); 99:
100: putchar('\n'); 101:
102: return 0; 103: }
|
<실행결과>
