자료구조: CHAP 4 리스트 (2) 2017. 4. 11 순천향대학교 컴퓨터공학과 하 상 호.

Presentation on theme: "자료구조: CHAP 4 리스트 (2) 2017. 4. 11 순천향대학교 컴퓨터공학과 하 상 호."— Presentation transcript:

1 자료구조: CHAP 4 리스트 (2) 순천향대학교 컴퓨터공학과 하 상 호

2 내용 리스트 추상 데이터 타입 배열로 구현된 리스트 단순 연결 리스트 삭제 기타 연산 응용: 다항식 원형 연결 리스트
표현 삽입 삭제 기타 연산 응용: 다항식 원형 연결 리스트 이중 연결 리스트

3 삭제 연산 prev가 NULL인 경우 (첫번째 노드 삭제) prev가 NULL이 아닌 경우
10 20 30 prev after removed prev가 NULL인 경우 (첫번째 노드 삭제) prev가 NULL이 아닌 경우 head head procedure delete_node(list, prev, removed: nodeptr) // list: 헤드 포인터 // prev: 삭제될 위치의 선행 노드 // removed: 삭제될 노드

4 삭제 연산 prev가 NULL인 경우 prev가 NULL이 아닌 경우 head removed prev head NULL

5 삭제 연산 알고리즘 procedure delete_node(list, prev, removed: nodeptr)
end delete_node

6 삭제 연산 알고리즘 procedure delete_first(list: nodeptr) // list: 헤드 포인터
end delete_first

7 삭제 연산 알고리즘 procedure delete_last(list: nodeptr) // list: 헤드 포인터
고려사항: 마지막 노드를 삭제하려면? 마지막 노드 인식 그리고 ? 알고리즘 procedure delete_last(list: nodeptr) // list: 헤드 포인터 end delete_last

8 리스트 탐색 탐색 연산: 특정한 데이터값을 갖는 노드를 찾는 연산
head NULL p procedure search(list: nodeptr, val: integer) // list: 헤드 포인터 // val: 탐색 데이터 // val을 포함하는 노드나 null을 반환 end search

9 리스트 합병 합병 연산: 2개의 리스트를 합하는 연산 procedure concat(list1, list2: nodeptr)
head1 NULL head2 procedure concat(list1, list2: nodeptr) // list1, list2: 헤드 포인터 // 연결된 리스트를 반환 end concat

10 리스트 역순 리스트의 노드들을 역순으로 재배치하는 알고리즘을 작성하라. list NULL NULL list

11 리스트 역순 리스트의 노드들을 역순으로 재배치 procedure reverse(list: nodeptr)
NULL q p procedure reverse(list: nodeptr) // list: 헤드 포인터 // 역순 리스트 반환 p, q, r: nodeptr p <- list; // p: 역순으로 변환될 리스트 q <- NULL; // q: 역순된 리스트 while p ≠ NULL do repeat return q;

12 리스트 역순 알고리즘 구성 NULL … NULL NULL NULL r p q NULL … NULL NULL NULL q p r

13 C 코딩: 리스트 연산 다음 연산에 대한 C 함수를 작성하라.
typedef int element; typedef struct node node; typedef node* nodeptr; typedef struct node { element data; nodeptr link; } node; 다음 연산에 대한 C 함수를 작성하라. procedure add_first(list: nodeptr, item: element) // list: 헤드 포인터 // item: 새로 삽입될 항목 end add_first

14 C 코딩: 연결 리스트 다음 연산에 대한 C 함수를 작성하라.
typedef int element; typedef struct node node; typedef node* nodeptr; typedef struct node { element data; nodeptr link; } node; 다음 연산에 대한 C 함수를 작성하라. procedure add_last(list nodeptr,item: element) // list: 헤드 포인터 // item: 새로 삽입될 항목 end add_last

15 리스트 응용: 다항식 3장에서 다룬 다항식을 단순 연결 리스트로 표현하려면? Ex. A=3x12+2x8+1

16 응용: 다항식 다항식을 단순 연결 리스트로 표현하면? Ex. A=3x12+2x8+1 자료 구조
NULL typedef struct node { int coef; int expo; struct node* link; } node; typedef struct node node; typedef node* nodeptr; typedef struct node { int coef; int expo; nodeptr link; } node;

17 응용: 다항식 다음 다항식을 구성하는 알고리즘을 작성하라 A=3x12+2x8+1 A 3 12 2 8 1 NULL

18 응용: 다항식 다음 2개의 다항식을 더하는 알고리듬을 작성하라. A= 3x12+2x8+1 B= 8x12+3x10+10x6 A
6 NULL 11 12 3 10 2 8 10 6 1 c NULL

19 응용: 다항식 다음 2개의 다항식을 더하라. A= 3x12+2x8+1 B= 8x12+3x10+10x6
A, B의 다항식을 더하는 add_poly()를 작성하라. p q 3 12 2 8 10 1 6 NULL add_poly(list1, list2: nodeptr) p, q, r: nodeptr; return r; end add_poly

20 poly_add2(): 알고리즘 Recall procedure poly_add2(p, q: poly) r: poly;
pf <- 0; qf<- 0; rf <-0; // 다항식의 현재 항 인덱스 설정 while pf < p.num and qf < q.num do if p[pf].terms.expo = q[qf].terms.expo then r[rf].terms.coef <- p[pf].terms.coef + q[qf].terms.coef; r[rf].terms.expo <- p[pf].terms.expo; rf <- rf +1; pf <- pf+1; qf <- qf+1; // 인덱스 갱신 else if p[pf].terms.expo > q[qf].terms.expo then r[rf].terms.coef <- p[pf].terms.coef; rf <- rf +1; pf <- pf+1; else r[rf].terms.coef <- p[qf].terms.coef; r[rf].terms.expo <- p[qf].terms.expo; rf <- rf +1; qf <- qf+1; end if repeat // 어느 한 쪽이 먼저 소진된 경우 처리 if pf < p.num then // p의 나머지 항들을 r로 이동 else if qf < q.num then // q의 나머지 항들을 r로 이동 endif end poly_add2 Recall

21 poly_add3: 연결리스트 표현 다항식을 단순연결리스트로 표현하고, 두 다항식에 대해서 덧셈을 수행하는 알고리즘 poly_add3(p1, p2: nodeptr)을 작성하라. 다음 함수 이용할 것: Insert_node_last(list: nodeptr, coef, expo: integer) (coef, expo)를 포함하는 노드를 생성하여 list의 맨 끝에 삽입 add_last(list, node: nodeptr) 이용할 것

22 헤더 노드 사용: 연결 리스트 헤더 노드를 사용하여 다항식을 표현하면? 헤더 노드는 2개의 포인터 head, tail을 포함
리스트에 포함된 노드의 개수를 나타내는 length를 가질 수 있다. 리스트 끝에 노드 추가할 때 편리 header length head tail 3 12 2 8 1 NULL

23 헤더 노드 사용: 삽입 연산 알고리즘 procedure add_last_header(header, new: nodeptr)
if 리스트가 비어 있으면 then else endif end add_last

24 헤더 노드 사용: 다항식 poly_add3()를 헤더 노드를 사용하여 다시 작성하라
Insert_node_last()를 적절하게 수정할 것 교재 프로그램 4.19 참고