2015년 5월 4일

(1)

9. 연결형 리스트, Stack, Queue

2015-1 프로그래밍언어

2015년 5월 4일

교수 김 영 탁

(2)

Advanced Networking Tech. Lab.

Yeungnam University (yuANTL) Programming Language

Prof. Young-Tak Kim 9 - 2

Outline



연결리스트 (Linked List)



연결리스트 연산

 Stack

 Queue



응용

(3)

연결 리스트



배열(array)

 장점: 구현이 간단하고 빠르다

 단점: 크기가 고정된다.

 중간에서 삽입, 삭제가 어렵다.



연결 리스트(linked list)

 각각의 원소가 포인터를 사용하여 다음 원소의 위치를 가리킨다.

0 0 11

2 2 33

4 4 55

6 6 77

8 8 99

(4)

연결 리스트의 장단점



중간에 데이터를 삽입, 삭제하는 경우



데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가



구현이 어렵고 오류가 나기 쉽다.



중간에 있는 데이터를 빠르게 가져올 수 없다.

데이터 삽입 B

A C D

E N

데이터 삭제 B

A C D

E

(5)

연결 리스트의 구조



노드(node) = 데이터 필드(data field)+ 링크 필드(link field)

data link

연결 리스트의 노드는 데이터 필드와 링크 필드로 이루어집니다.

(6)

연결 리스트의 구조



헤드 포인터(head pointer): 첫번째 노드를 가리키는 포인터

10 20 30NULL 40NULL 50NULLNULL

plist

첫번째 노드를 가리키 는 포인터를 헤드포인 터라고 하고 맨 마지 막 노드의 링크 필드

는 NULL입니다.

(7)

노드 생성



노드들은 동적으로 생성된다.

(8)

자기 참조 구조체



자기 참조 구조체(self-referential structure)는 특별한 구조체로서 구성 멤버 중에 같은 타입의 구조체를

가리키는 포인터가 존재하는 구조체

typedef struct NODE { int data;

struct NODE *link;

} NODE;

(9)

간단한 연결 리스트 생성

NODE *p1;

p1 = (NODE *)malloc(sizeof(NODE));

p1->data = 10;

p1->link = NULL;

NODE *p2;

p2 = (NODE *)malloc(sizeof(NODE));

p2->data = 20;

p2->link = NULL;

p1->link = p2;

free(p1);

free(p2);

p1

10 ^NULL p1

p1 10 20 ^NULL

(10)

연결 리스트의 응용



소장하고 있는 책의 목록을 관리하는 프로그램을 작성

 연결 리스트를 사용하여서 작성

(11)

연결 리스트를 이용한 프로그램

(12)

(13)

(14)

(15)

실행 결과

(16)

Linked List에서의 Node 삽입 (1)

NODE *insert_NODE(NODE *plist, NODE *pPrev, DATA item);

1. 리스트의 처음에 삽입하는 경우

pNew->link = pList;

pList = pNew;

2. 리스트의 중간에 삽입하는 경우

pNew->link = pPrev->link;// ① pPrev->link = pNew;// ②

plist 10

pnew

20 30 NULL

5

plist 10

pnew

20 30 NULL

5 pprev

② ①

(17)

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 {

// 연결 리스트의 중간에 삽입

(18)

Linked List에서의 노드 삭제 (1)

NODE delete_node(NODE pList, NODE pPrev, NODE pCurr);

1. 리스트의 처음 노드를 삭제하는 경우

pList = pCurr->link;

free(pCurr);

2. 리스트의 중간 노드를 삭제하는 경우

pPrev->link = pCurr->link;

free(pCurr

);

plist 10 20 30 NULL

pcurr

plist 10 20 30

pcurr

40 NULL

pprev

(19)

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;

}

(20)

Print, Count, Sum Nodes in Linked List

void print_list(NODE *pList)

{ NODE *p;

int count = 0;

int sum = 0;

p = 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);

}

10 plist

20 30 90 NULL

p

...

p p p

(21)

Doubly-Linked List를 이용한 Galaxy of Stars 구성

 Header Files

typedef struct Star { char name[16];

int id;

double distance;

double luminosity;

double mass;

double radius;

int age;

} Star;

typedef struct Galaxy { ListNode *pFirst;

ListNode *pLast;

typedef struct ListNode {

Star *pS;

ListNode *pPrev;

ListNode *pNext;

} ListNode;

(22)

pStar pPrev pNext

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. . . pStar

pPrev pNext

pStar pPrev pNext

Galaxy

pGlx

pFirst pLast numStars

ListNode

Star[ ]

(23)

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;

(24)

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);

} }

(25)

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;

(26)

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;

elsebreak;

} // end if-else } // end for

} else {

printf("Error in excessive number of stars (NUM_STARS: %d)₩n", NUM_STARS);

} }

(27)

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;

}

(28)

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++;

} }

(29)

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);

(30)

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);

}

(31)



실행결과

2015년 5월 4일

9. 연결형 리스트, Stack, Queue