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

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

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

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

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

4 삭제 연산 Head 포인터가 NULL이면? prev가 NULL인 경우 prev가 NULL이 아닌 경우 head removed

5 삭제 연산 알고리즘 procedure delete_node(list, prev, removed: nodeptr)
list, prev의 NULL 유무 고려 procedure delete_node(list, prev, removed: nodeptr) // list: 헤드 포인터 // prev: 삭제될 위치의 선행 노드 // removed: 삭제될 노드 end delete_node

6 삭제 연산 알고리즘 procedure delete_first(list: nodeptr) // list: 헤드 포인터
고려사항: List에 포함된 노드 개수가 0인 경우 한 개인 경우 두 개 이상인 경우 알고리즘 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 리스트 방문 리스트에 포함된 모든 노드를 순차적으로 방문 procedure display(list: nodeptr)
end display

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

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

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

12 리스트 역순 리스트의 노드들을 역순으로 재배치 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;

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

14 연결 리스트 표현 Recall: (data, link)의 레코드로 표현 자체 참조변수 type nodeptr = ↑node
type node record data: integer; link: nodeptr; end; list: nodetpr; list↑.data <- 10; list↑.link <- NULL;

15 C 표현: 연결 리스트 (data, link)의 레코드로 표현 C의 구조체 type nodeptr = ↑node
type node record data: integer; link: nodeptr; end; data link C의 구조체 typedef int element; typedef struct node { element data; struct node *link; } node; typedef int element; typedef struct node node; typedef node* nodeptr; typedef struct node { element data; nodeptr link; } node;

16 C 표현: 연결 리스트 노드의 생성(in C) typedef int element;
typedef struct node node; typedef node* nodeptr; typedef struct node { element data; nodeptr link; } node; typedef int element; typedef struct node { element data; struct node *link; } node; node *p; p = (node *) malloc(sizeof(node)); nodeptr p; p = (nodeptr) malloc(sizeof(node)); p data link

17 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

18 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

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

20 응용: 다항식 다항식을 단순 연결 리스트로 표현하면? 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;

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

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

23 응용: 다항식 다음 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

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

25 Recall: poly_add2() 분석 구분 내용 I p, q: poly
p = (np, (coefi, expoi)), i=1, 2, …, np q = (nq, (coefj, expoj)), j=1, 2, …, nq O r: poly r = (nr, (coefk, expok)), i=1, 2, …, nr P 0<= r.nr <= p.np + q.nq r.(coefk, expok) = (p.coefi+q.coefj, p.expoi) if э i, j s.t. expok = p.expoi and expok = q.expoj (p.coefi, p.expoi) if э i s.t. expok = p.expoi and ¬э j s.t. expok = q.expoj (q.coefj, q.expoj) if ¬э i s.t. expok = p.expoi and э j s.t. expok = q.expoj E 분석

26 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

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

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

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