2011년7월15일_파일의 내용을 읽어와 정렬된 단방향 연결리스트를 만들기. (step3.c)
작성일자: 2011년7월18일
● step2.c 반복문을 사용해 가변적인 입력도 받아 들일 수 있도록 수정.
1: // step2.c(반복문) 110715 수만 2: #include <stdio.h>
3: #include <stdlib.h>
4: #include <string.h> 5: #include <fcntl.h>
6: #include <sys/types.h>
7: #include <sys/stat.h>
8: #include "node.h" 9:
10: int main() 11: {
12: int ifd; 13: int iCnt; 14: int iRet; 15: NODE *stpNode; //st는 struct, p는 포인터 16: NODE *stpHead;
17:
18: ifd = open("a.dat", O_RDONLY); 19:
20: if(0 > ifd) 21: {
22: write(2, "파일열기에러!\n", 14); 23: return -1; 24: }
25:
26: stpHead = 0; //최초 노드 생성인가 확인용. 27: // 구조체를 생성하고 파일을 읽어온 값을 저장하고 이전 구조체와 연결 28: while(1) 29: {
30: stpNode = malloc(sizeof(NODE)); 31:
32: if(0 == stpNode) 33: {
34: write(2, "동적할당에러!\n", 14); 35: return -1; 36: }
37:
38: iRet = read(ifd, stpNode, sizeof(NODE)); 39: stpNode->next = 0;
40:
41: if(0 == iRet) // read()는 EOF일 경우 0을 반환. 42: {
43: free(stpNode); //내가 잘 못 한 부분으로 소스설명참조★ 44: break; //파일의 끝이므로 노드의 생성을 중지한다. 45: }
46:
47: if(0 != stpHead) //최초 노드이면 연결제외 48: {
49: stpNode->next = stpHead; //이전 구조체와 연결 50: }
51:
52: stpHead = stpNode; //새로 생긴 구조체를 헤더로 (백업) 53: }
54:
55: close(ifd);
56:
57: stpNode = stpHead; // 이전 구조체위치 (복원) 58:
59: //연결리스트의 노드들의 데이터를 출력 60: while(0 != stpNode) 61: {
62: printf("%2d -> ", stpNode->iNum); 63: stpNode = stpNode->next;
64: }
65:
66: printf("NULL\n"); 67:
68:
69: //메모리 해제 (반복문사용) 70: for(stpNode = stpHead ; stpNode != 0 ; stpNode = stpHead) 71: {
72: stpHead = stpNode->next;
73: free(stpNode);
74: }
75:
76: return 0; 77: }
|
<실행결과>
<소스설명>
43행 free(stpNode);
이 코드는 마지막에 있는 메모리해제코드가 있어 필요없다고 판단하여 삭제하였으나,
알고 보니 break되면서 연결리스트와 연결이 되지 않는 노드이므로 따로 소멸시켜줘야 하는 것이었다.
7월17일 일요일에 메모리확인 명령어 top과 cat /proc/meminfo를 해서 확인해 봐도,
malloc( )로 할당된 메모리를 free( )할 때와 하지 않을 때의 차이를 알 수 없었다.
할당받은 주소를 찍어봐도 free( )할 때와 하지 않을 때의 차이만 있을 뿐…
기대했던 대로 free( )하지 않을 때 주소값이 증가하지 않고 고정되었다.
어떻게 제대로 운영체제에 메모리를 돌려주었지 확인할 수 있지?
<소스분석>
그림으로 대신하지 하하하
데이터의 수를 10개로 늘려서 확인해 보자.
a.dat에는 10개의 데이터가 들어갔다. 1~10의 정수
a.dat를 b.dat로 바꾸고,
a.dat를 복사해와서 출력하니 10부터 1까지 출력된다.
이로써 반복문을 사용해 가변적인 데이터의 크기의 파일도 다룰 수 있게 되었다.
● 연결리스트의 노드사이에 노드를 삽입할 위치를 찾기위해 필요한 key
1, 2, 3, 4가 저장된 곳과 같이 노드를 찾을 때 쓰는 고유한 정보
1: typedef struct _node
2: {
3: int iNum;
4: struct _node *next;
5: } NODE;
자기참조포인터 next는 다른 노드와 연결할 때 쓰니 검색에 쓰일 수 없고,
iNum은 주민번호와 같이 그 노드를 식별할 수 있는 고유한 정보이다.
인간은 상기와 같은 그림을 그려 3이라는 값이 들어 있는 노드를 어디에 삽입해야 할지 금방 알 수 있으나,
컴퓨터는 한 번에 한 개의 값만 비교하므로 (레지스터) 연결리스트를 다 뒤지지 않고선 알 수 없다. (인간도 그림 그릴 때 다 알아보는군)
그래서 비교할 때 쓸 값이 필요하고 그런 정보를 key라고 한다.
● step3.c 파일에서 읽어와 연결리스트를 구성할 때 부터 정렬하며 삽입하는 함수 insert( )를 만들어 보자.
1: // step3.c 110715 수만 2: #include <stdio.h>
3: #include <stdlib.h>
4: #include <string.h> 5: #include <fcntl.h>
6: #include <sys/types.h>
7: #include <sys/stat.h>
8: #include "node.h" 9:
10: void *insert(NODE *, NODE *); 11:
12: int main() 13: {
14: int ifd; 15: int iCnt; 16: int iRet; 17: NODE *stpNode; //st는 struct, p는 포인터 18: NODE *stpHead = 0;
19:
20: ifd = open("a.dat", O_RDONLY); 21:
22: if(0 > ifd) 23: {
24: write(2, "파일열기에러!\n", 14); 25: return -1; 26: }
27:
28: stpHead = 0; //최초 노드 생성인가 확인용. 29: // 구조체를 생성하고 파일을 읽어온 값을 저장하고 이전 구조체와 연결 30: while(1) 31: {
32: stpNode = malloc(sizeof(NODE)); 33:
34: if(0 == stpNode) 35: {
36: write(2, "동적할당에러!\n", 14); 37: return -1; 38: }
39:
40: iRet = read(ifd, stpNode, sizeof(NODE)); 41: stpNode->next = 0;
42:
43: // read()는 EOF일 경우 0을 반환. 44: if(0 == iRet) 45: {
46: free(stpNode);
47: break; //파일의 끝이므로 노드의 생성을 중지한다. 48: }
49:
50: stpHead = insert(stpHead, stpNode);
51: }
52:
53: close(ifd);
54:
55: stpNode = stpHead; // 이전 구조체위치 (복원) 56: //연결리스트의 노드들의 데이터를 출력 57: while(0 != stpNode) 58: {
59: printf("%2d -> ", stpNode->iNum); 60: stpNode = stpNode->next;
61: }
62: printf("NULL\n"); 63:
64: //메모리 해제 (반복문사용) 65: for(stpNode = stpHead ; stpNode != 0 ; stpNode = stpHead) 66: {
67: stpHead = stpNode->next;
68: free(stpNode);
69: }
70:
71: return 0; 72: }
73:
74: // 노드포인터 최초의 값은 Head가 가지고 있어야함 75: // 프로그램은 일관성있게 리스트의 제일 처음을 리턴. 76: void *insert(NODE *stpHead, NODE *stpNode) 77: {
78: NODE *stpCurrent; //이것만 사용하는 법도 찾아보삼 79: NODE *stpPrev; //두 개 사용해 하는 법 80:
81: if(0 == stpNode) 82: {
83: return stpHead; 84: }
85:
86: if(0 == stpHead) 87: {
88: stpHead = stpNode;
89: stpHead->next = 0; //삽입 노드 90: return stpHead; 91: }
92:
93: //검색 94: stpCurrent = stpHead; //최초위치를 Current가 갖고 검색시작 95: stpPrev = stpCurrent;
96:
97: while(1) //삽입할 위치 찾기 98: {
99: //연결리스트를 끝까지 검색했을 경우 stop 100: if(0 == stpCurrent) 101: {
102: break; 103: }
104:
105: //삽입할 위치를 찾았을 경우 stop 106: if(stpCurrent->iNum > stpNode->iNum) 107: {
108: break; 109: }
110:
111: stpPrev = stpCurrent;
112: stpCurrent = stpCurrent->next; //다음 노드로 이동 113: }
114:
115: //처음 삽입... 116: if(stpHead == stpCurrent) 117: {
118: if(0 != stpCurrent) 119: {
120: stpNode->next = stpHead; //삽입할 구조체와 첫 구조체연결 121: stpHead = stpNode;
122: }
123: else //노드하나짜리 리스트이면 124: {
125: stpHead->next = stpNode; //뒤에 삽입 126: }
127: }
128: else //중간삽입 끝 삽입 129: {
130: stpNode->next = stpCurrent; //뒷 부분연결 131: stpPrev->next = stpNode; //앞 부분연결 132: }
133:
134: return stpHead; 135: }
|
<실행결과>
오름차순으로 정렬된 값들이 출력되었다.
어떻게 정렬되는지 알아보자.
1: if(0 == stpHead) //최초 노드 삽입시
2: {
3: stpHead = stpNode; //헤드는 새로 생성된 노드를 가리킴.
4: stpHead->next = 0; //삽입 노드가 NULL을 가리키도록
5: return stpHead;
6: }
1: while(1) //삽입할 위치 찾기
2: {
3: //연결리스트를 끝까지 검색했을 경우 stop
4: if(0 == stpCurrent)
5: {
6: break;
7: }
8:
9: //삽입할 위치를 찾았을 경우 stop
10: if(stpCurrent->iNum > stpNode->iNum)
11: {
12: break;
13: }
14:
15: stpPrev = stpCurrent;
16: stpCurrent = stpCurrent->next; //다음 노드로 이동
17: }
10행 기존의 데이터 1이 새로 읽어 들인 2보다 작으니,
Current가 Node보다 작으므로 NULL이 될 때까지 반복을 돌고 나온다.
15행은 Prev에 Current가 가리키는 주소를 저장하여 Prev를 한 단계 전진(다음 노드)시키는 것이고,
16행은 Current가 가리키는 노드의 다음노드의 주소를 담아 다음 노드를 가리킨다.
1: //처음 삽입...
2: if(stpHead == stpCurrent)
3: {
4: if(0 != stpCurrent)
5: {
6: stpNode->next = stpHead; //삽입할 구조체와 첫 구조체연결
7: stpHead = stpNode;
8: }
9: else //노드하나짜리 리스트이면
10: {
11: stpHead->next = stpNode; //뒤에 삽입
12: }
13: }
14: else //중간삽입 끝 삽입
15: {
16: stpNode->next = stpCurrent; //뒷 부분연결
17: stpPrev->next = stpNode; //앞 부분연결
18: }
while문에서 Current가 이동하였으므로 절대 if문을 만족하지 않는다.
그러니 else문을 실행하게 되어,
16행 새로 읽어 들인 노드의 다음은 기존 연결리스트 뒤에 연결하고,
17행 이전 노드는 새로 읽어 들인 노드를 가리키도록 한다.
이렇게 나머지 3, 4, 5도 읽어 들이면 아래와 같이 1부터 5까지 오름차순으로 정렬된 연결리스트를 얻게 된다.
데이터 수를 늘리고 정렬되지 않는 데이터를 넣어 출력결과를 확인해 보자.
어떤 순서의 데이터를 넣든 정렬된 연결리스트가 생성되는 것을 알 수 있다.
|
참조(Reference) |
