A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

Size: px

Start display at page:

Download "A Hierarchical Approach to Interactive Motion Editing for Human-like Figures"

서형 한
4 years ago
Views:

1 단일연결리스트 (Singly Linked List) 신찬수

2 연결리스트 (linked list)? tail 서울부산수원용인 null item next

$구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.$

3 구조체복습 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;

$item : 정수자료값저장 next : 다음노드로의링크 typedef struct node_elm* node; struct node_elm { }; int item; node next; 20$

4 정수자료값을저장한연결리스트 연결리스트는노드 (node) 들이링크 (link) 에의해연결된기차형태의자료구조 하나의노드는자료가저장되며, 동시에다음노드를가르키는링크도저장되어야한다 구조체사용! item : 정수자료값저장 next : 다음노드로의링크 typedef struct node_elm* node; struct node_elm { }; int item; node next; 20 item next

5 세개의노드를갖는연결리스트 null

6 헤드에새로운노드삽입 (insert) null null

7 헤드에새로운노드삽입 new_node 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; }

8 헤드노드를연결리스트에서삭제 null node deletefromhead( node, int *item ) { // 새로운헤드리턴 if (!= null ) { node old = ; = ->next; *item = old->item; free(old); return ; } else printf( List is empty.\n );

9 연결리스트로구현한스택 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; }

10 연결리스트로구현한스택 int stacksize( Lstack S ) { return S->size; } int stackempty( Lstack S ) { return ( S->size == 0 ); }

11 연결리스트로구현한스택 void push ( Lstack S, int value ) { 52 S->top = S->size++; } top null

12 연결리스트로구현한스택 top int pop( Lstack S ) { int value; S->top = S->size--; return value; } null top null

13 연결리스트로구현한큐? 연결리스트로큐를구현하기위해선, 꼬리 (tail) 노드를삭제하는함수 ( 연산 ) 가필요하다 deletefromtail( ) 어떤값을파라미터로넘겨줘야하나? 리턴해야할내용은무엇인가? 노드만알고있는데, 어떻게 tail 노드를알아야하나? tail 노드를알게되었다면, 주위의노드들의링크를어떻게변경해야하나? ( 그림으로그려확인해볼것!) 특별한경우 예 : 빈리스트인경우에는어떻게처리할것인가?

14 tail 노드를삭제하는연산 tail null tail null

15 변경되어야할노드의링크들 null null

16 deletefromtail 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;

17 deletefromtail prev tail null prev->next = tail->next; free(tail);

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

19 특정노드삭제하기 prev x tail null tail

20 특정값을저장한노드삭제하기 node search( node, int value ); value 값이저장된노드가있다면찾아리턴하고, 없으면 null 리턴 node x; int item; x = search(, value ); deletenode(, x, &item );

21 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 ; // 가바뀌지않는다. 왜? }

22 원형리스트 (Circular list) 78 tail null tail dummy 노드가항상 tail 노드가되도록함. - dummy 노드의 값은 INT_MAX 로표현. tail

23 insertatfront( node tail, int value ) tail tail

24 deletenode deletenode( node tail, node x, node px ); 어떻게?

25 원형리스트를이용한 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?

26 Josephus problem (k = 3)

27 Josephus problem (k = 3)

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100 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