단일연결리스트 (Singly Linked List) 신찬수
연결리스트 (linked list)? tail 서울부산수원용인 null item next
구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct name_card * p = &a; // 구조체의포인터변수선언 p->name 또는 p->date // 구조체포인터변수를통한멤버접근 typedef struct name_card * ptr_card; // typedef을이용한선언 ptr_card p = &a;
정수자료값을저장한연결리스트 연결리스트는노드 (node) 들이링크 (link) 에의해연결된기차형태의자료구조 하나의노드는자료가저장되며, 동시에다음노드를가르키는링크도저장되어야한다 구조체사용! item : 정수자료값저장 next : 다음노드로의링크 typedef struct node_elm* node; struct node_elm { }; int item; node next; 20 item next
세개의노드를갖는연결리스트 20 33 56 null
헤드에새로운노드삽입 (insert) 20 33 56 null 78 20 33 56 null
헤드에새로운노드삽입 new_node 78 20 33 56 null node insertathead( node, int value ) { node new_node = (node)malloc( sizeof(struct node_elm) ); new_node->item = value; new_node->next = ; return new_node; }
헤드노드를연결리스트에서삭제 78 20 33 56 null node deletefromhead( node, int *item ) { // 새로운헤드리턴 if (!= null ) { node old = ; = ->next; *item = old->item; free(old); return ; } else printf( List is empty.\n );
연결리스트로구현한스택 typedef struct linkedstack* Lstack; struct linkedstack { node top; int size; }; Lstack createstack( void ){ Lstack S = (Lstack) malloc( sizeof(struct linkedstack) ); S->top = null; S->size = 0; return S; }
연결리스트로구현한스택 int stacksize( Lstack S ) { return S->size; } int stackempty( Lstack S ) { return ( S->size == 0 ); }
연결리스트로구현한스택 void push ( Lstack S, int value ) { 52 S->top = S->size++; } top 52 33 56 null
연결리스트로구현한스택 top int pop( Lstack S ) { int value; S->top = S->size--; return value; } 52 33 56 null top 52 33 56 null
연결리스트로구현한큐? 연결리스트로큐를구현하기위해선, 꼬리 (tail) 노드를삭제하는함수 ( 연산 ) 가필요하다 deletefromtail( ) 어떤값을파라미터로넘겨줘야하나? 리턴해야할내용은무엇인가? 노드만알고있는데, 어떻게 tail 노드를알아야하나? tail 노드를알게되었다면, 주위의노드들의링크를어떻게변경해야하나? ( 그림으로그려확인해볼것!) 특별한경우 예 : 빈리스트인경우에는어떻게처리할것인가?
tail 노드를삭제하는연산 tail 78 20 33 56 null tail 78 20 33 null
변경되어야할노드의링크들 78 20 33 56 null 78 20 33 null
deletefromtail 78 20 33 56 null tail의노드의직전노드 (prev) 를어떻게찾나? node tail, prev = null; if ( == null ) { printf( List is empty\n ); return null; } for ( tail = ; tail->next!= null ; tail = tail->next ) prev = tail;
deletefromtail prev tail 78 20 33 56 null prev->next = tail->next; free(tail);
deletefromtail node deletefromtail( node, int *value) { // return node tail, prev = null; if ( == null ) { printf( List is empty.\n ); return null; } for ( tail = ; tail->next!= null ; tail = tail->next ) prev = tail; if (prev!= null) prev->next = tail->next; *value = tail->item; free(tail); if (prev == null) return null; } else return ;
특정노드삭제하기 prev x tail 78 20 33 56 null tail 78 20 56
특정값을저장한노드삭제하기 node search( node, int value ); value 값이저장된노드가있다면찾아리턴하고, 없으면 null 리턴 node x; int item; x = search(, value ); deletenode(, x, &item );
deletenode node deletenode( node, node x, int *item) { node tail, prev; if ( == null x == null ) return ; if ( x == ) return deletefromhead(, item ); if ( x->next == null ) return deletefromtail(, item ); // x == tail for ( prev = ; prev->next!= x; ) // prev->next == x가되도록 prev = prev->next; prev->next = x->next; *item = x->item; free(x); return ; // 가바뀌지않는다. 왜? }
원형리스트 (Circular list) 78 tail 20 33 56 null tail dummy 노드가항상 tail 노드가되도록함. - dummy 노드의 값은 INT_MAX 로표현. tail 78 20 33
insertatfront( node tail, int value ) tail 20 33 56 tail 78 20 33 56
deletenode deletenode( node tail, node x, node px ); 어떻게?
원형리스트를이용한 Josephus 문제 People sit around a round table. From a person, count the people in clockwise order, kill the k-th person, and then the person is out from the table. Who is the last survivor?
Josephus problem (k = 3) 8 9 1 2 8 9 1 2 7 3 7 3 6 5 4 6 5
Josephus problem (k = 3) 7 9 1 7 9 1 7 1 2 6 2 6 2 6 5 5 1 3 1 2 7 5 1 2 7 5 1 2