2015-1 프로그래밍언어 9. 연결형리스트, Stack, Queue 2015 년 5 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr)
연결리스트 (Linked List) 연결리스트연산 Stack Queue 응용 Outline 9-2
연결리스트 배열 (array) 장점 : 구현이간단하고빠르다 단점 : 크기가고정된다. 중간에서삽입, 삭제가어렵다. 0 1 2 3 4 5 6 7 8 9 연결리스트 (linked list) 각각의원소가포인터를사용하여다음원소의위치를가리킨다. A C D E B 메인메모리 9-3
연결리스트의장단점 중간에데이터를삽입, 삭제하는경우 N A C D E A C D E B B 데이터삽입 데이터삭제 데이터를저장할공간이필요할때마다동적으로공간을만들어서쉽게추가 구현이어렵고오류가나기쉽다. 중간에있는데이터를빠르게가져올수없다. 9-4
연결리스트의구조 노드 (node) = 데이터필드 (data field)+ 링크필드 (link field) 연결리스트의노드는데이터필드와링크필드로이루어집니다. data link 9-5
연결리스트의구조 헤드포인터 (head pointer): 첫번째노드를가리키는포인터 첫번째노드를가리키는포인터를헤드포인터라고하고맨마지막노드의링크필드는 NULL 입니다. plist 10 20 30 NULL NULL 40 NULL 50 NULL 9-6
노드생성 노드들은동적으로생성된다. 9-7
자기참조구조체 자기참조구조체 (self-referential structure) 는특별한구조체로서구성멤버중에같은타입의구조체를가리키는포인터가존재하는구조체 typedef struct NODE int data; struct NODE *link; NODE; 9-8
간단한연결리스트생성 NODE *p1; p1 = (NODE *)malloc(sizeof(node)); p1->data = 10; p1->link = NULL; NODE *p2; p2 = (NODE *)malloc(sizeof(node)); p2->data = 20; p1 p1 10 NULL p2->link = NULL; p1->link = p2; free(p1); free(p2); p1 10 20 NULL p1 10 20 NULL 9-9
연결리스트의응용 소장하고있는책의목록을관리하는프로그램을작성 연결리스트를사용하여서작성 9-10
연결리스트를이용한프로그램 9-11
9-12
9-13
9-14
실행결과 9-15
Linked List 에서의 Node 삽입 (1) NODE *insert_node(node *plist, NODE *pprev, DATA item); 1. 리스트의처음에삽입하는경우 pnew->link = plist; plist 10 20 30 NULL plist = pnew; pnew 5 2. 리스트의중간에삽입하는경우 pprev pnew->link = pprev->link;// 1 pprev->link = pnew;// 2 plist 10 20 30 NULL 2 1 pnew 5 9-16
Linked List 에서의 Node 삽입 (2) NODE *insert_node(node *plist, NODE *pprev, DATA item) NODE *pnew = NULL; if (!(pnew = (NODE *)malloc(sizeof(node))) ) printf(" 메모리동적할당오류 n"); exit(1); pnew->data = item; if( pprev == NULL ) // 연결리스트의처음에삽입 pnew->link = plist; plist = pnew; else // 연결리스트의중간에삽입 pnew->link = pprev->link; pprev->link = pnew; return plist; 9-17
Linked List 에서의노드삭제 (1) NODE *delete_node(node *plist, NODE *pprev, NODE *pcurr); 1. 리스트의처음노드를삭제하는경우 plist = pcurr->link; free(pcurr); plist 10 20 30 NULL pcurr 2. 리스트의중간노드를삭제하는경우 pprev->link = pcurr->link; plist 10 20 30 40 NULL free(pcurr); pprev pcurr 9-18
Linked List 에서의노드삭제 (2) NODE *delete_node(node *plist, NODE *pprev, NODE *pcurr) if( pprev == NULL ) // First node plist = pcurr->link; else pprev->link = pcurr->link; free(pcurr); return plist; 9-19
Print, Count, Sum Nodes in Linked List void print_list(node *plist) NODE *p; int count = 0; int sum = 0; p = plist; plist while( p!= NULL ) printf("%d, ", p->data); count++; sum += p->data; p = p->link; printf( n ); printf( Length of list: %d n, count); printf( Sum of list: %d n, sum); p 10 20 30... 90 NULL p p p 9-20
Header Files Doubly-Linked List 를이용한 Galaxy of Stars 구성 typedef struct Star char name[16]; int id; double distance; double luminosity; double mass; double radius; int age; Star; typedef struct ListNode Star *ps; ListNode *pprev; ListNode *pnext; ListNode; typedef struct Galaxy ListNode *pfirst; ListNode *plast; int num_star; Galaxy; 9-21
Galaxy pglx numstars pfirst plast ListNode pprev pprev pprev pprev pprev pprev pnext pnext pnext pnext pnext pnext pstar pstar pstar pstar pstar pstar Star[ ] Star[0] -name -id... Star[1] -name -id... Star[2] -name -id... Star[i] -name -id... Star[ j] -name -id... Star[k] -name -id... Star[N-1] -name -id... 9-22
Star* genstar(int starid) Star *pnew; int name_len; pnew = (Star *)malloc(sizeof(star)); name_len = rand() % 6 + 5; pnew->name[0] = rand() % 26 + 'A'; for (int i = 1; i<name_len; i++) pnew->name[i] = rand() % 26 + 'a'; pnew->name[name_len] = ' 0'; pnew->id = starid; pnew->distance = (double)(rand() % 10000 + 10.0); pnew->luminosity = (double)(rand() % 10000 + 10.0); pnew->mass = (double)(rand() % 10000 + 10.0); pnew->radius = (double)(rand() % 10000 + 10.0); pnew->age = rand() % 10000 + 10; return pnew; 9-23
void insertnodeattail(galaxy *pglx, Star *pstar) ListNode *pnew; pnew = (ListNode *)malloc(sizeof(listnode)); pnew->pnext = pnew->pprev = NULL; pnew->ps = pstar; if (pglx->num_star == 0) pglx->pfirst = pglx->plast = pnew; pglx->num_star++; else if (pglx->num_star < NUM_STARS) pnew->pprev = pglx->plast; pglx->plast->pnext = pnew; pglx->plast = pnew; pnew->pnext = NULL; pglx->num_star++; else printf("error in excessive number of stars (NUM_STARS: %d) n", NUM_STARS); 9-24
void insertnodeinorder(galaxy *pglx, Star *pstar) ListNode *pnew, *pln; pnew = (ListNode *)malloc(sizeof(listnode)); pnew->pnext = pnew->pprev = NULL; pnew->ps = pstar; if (pglx->num_star == 0) pglx->pfirst = pglx->plast = pnew; pnew->pnext = NULL; pnew->pprev = NULL; pglx->num_star++; else if (pglx->num_star < NUM_STARS) for (pln = pglx->pfirst; pln!= NULL;) if (pnew->ps->id < pln->ps->id) pnew->pnext = pln; pnew->pprev = pln->pprev; if (pln!= pglx->pfirst) if (pln->pprev!= NULL) pln->pprev->pnext = pnew; pln->pprev = pnew; 9-25
else // ps == pglx->pfirst pglx->pfirst = pnew; pnew->pprev = NULL; pln->pprev = pnew; pglx->num_star++; break; else if ((pln == pglx->plast) && (pnew->ps->id >= pln->ps->id)) pnew->pprev = pln; pln->pnext = pnew; pglx->plast = pnew; pnew->pnext = NULL; pglx->num_star++; break; else if (pln!= pglx->plast) pln = pln->pnext; else break; // end if-else // end for else printf("error in excessive number of stars (NUM_STARS: %d) n", NUM_STARS); 9-26
Star * removefromhead(galaxy *pglx) ListNode *pln; Star *ps; if (pglx->num_star > 0) pln = pglx->pfirst; ps = pln->ps; pglx->pfirst = pglx->pfirst->pnext; if (pglx->pfirst!= NULL) pglx->pfirst->pprev = NULL; pglx->num_star--; free(pln); return ps; else printf("error in removefromhead: Linked List is empty n"); return NULL; 9-27
Star * getfromhead(galaxy *pglx) if (pglx->num_star > 0) return pglx->pfirst->ps; else return NULL; void printgalaxy(galaxy *pglx) ListNode *pln; int count; printf(" Number of stars: %d n", pglx->num_star); pln = pglx->pfirst; count = 0; while ((pln!= NULL) && (count <NUM_STARS)) printf(" Star_ID (%3d), Name (%s) n", pln->ps->id, pln->ps->name); pln = pln->pnext; count++; 9-28
void main() Galaxy *pglx; Star *ps; int *starid, i; pglx = (Galaxy *)malloc(sizeof Galaxy); pglx->pfirst = NULL; pglx->plast = NULL; pglx->num_star = 0; starid = new int[num_stars]; genbigrandarray(starid, NUM_STARS); printf("inserting Stars into Galaxy using insertnodeinorder()... n"); for (i = 0; i<num_stars; i++) ps = genstar(starid[i]); insertnodeinorder(pglx, ps); printf(" Galaxy after insertnodeinorder(%d) n", ps->id); printgalaxy(pglx); 9-29
printf(" ndeleting Stars from Galaxy using removefromhead()... n"); for (i = 0; i<num_stars; i++) ps = removefromhead(pglx); if (ps!= NULL) printf(" Galaxy after node (id: %d) remove from head of the linked list: n", ps->id); printgalaxy(pglx); free(ps); ps = getfromhead(pglx); if (ps!= NULL) printf(" New head in list of Galaxy: %d n", ps->id); free(pglx); 9-30
실행결과 9-31