제 3 장 선형 리스트 3.1 선형 리스트 3.2 연결 리스트 3.3 다항식.

Presentation on theme: "제 3 장 선형 리스트 3.1 선형 리스트 3.2 연결 리스트 3.3 다항식."— Presentation transcript:

1 제 3 장 선형 리스트 3.1 선형 리스트 3.2 연결 리스트 3.3 다항식

2 3.1 선형 리스트 리스트 : 원소의 집합 선형리스트 선형리스트의 추상화 정의 현실 세계에는 많은 자료들이 서로 관련되어 존재
이들 관련된 자료들이 일정한 순서를 이루어 나열되어 있는 구조 선형리스트 원소들이 연속적으로 기억장치에 저장 데이터 항목의 순서적인 집합 선형리스트의 추상화 정의 n개의 원소가 있다면, 원소 a1, a2, …, an이 순서를 갖고 있으며, 이들 중의 한 원소 ai (1 ≤ i ≤ n)는 ai+1보다 선행되어 존재하고, ai-1이 ai보다 선행되어 존재하는 구조 여기서 ai : 리스트의 원소, 이들은 동일한 구조를 가짐 선형리스트 : A라 하면, A=(a1, a2, …, an-1, an) 원소의 수가 0인 리스트 : 공백 리스트(empty list)

3 선형리스트와 관련된 연산 새로운 리스트의 생성 리스트의 길이 (length) : 선형리스트의 원소 개수
리스트의 i 위치에 데이터의 입력 리스트의 i 위치에 데이터의 출력 리스트의 i 위치에 원소의 검색 리스트의 i 위치에 원소의 갱신 리스트의 i 위치에 원소의 삽입 리스트의 i 위치에 원소의 삭제

4 순차적 사상(sequential mapping)
선형리스트를 구현하는 일반적 방법: 배 열 순차적 사상(sequential mapping) 배열을 이용하여 표현된 순차 구조 리스트의 원소 ai에 대하여 대응하여 저장되는 것 선형 리스트의 배열을 이용한 순차적 저장 방식의 가장 큰 문제점은 초기에 배열의 크기를 설정하기 때문에 그 일부분만 사용하거나 또는 오버플로우(Overflow)가 발생한다는 점이다.

5 3.1.2 선형리스트에서 원소의 삽입과 삭제 선형리스트는 원소의 삽입과 삭제의 빈번한 자료 이동이 요구되므로 자료의 삽입과 삭제가 많이 발생하지 않는 자료구조에 사용 삽입의 경우 * 구성 요소들의 평균 이동 횟수 : mi n : 배열의 길이, k : 데이터가 삽입되는 위치, pk : k번째에 삽입될 확률

6 [그림 3.1] 순차리스트의 원소(25) 삽입 11 13 19 27 29 35 55 77 n=8 이동 삽입(25) 11 13 19 25 27 29 35 55 77 삽입결과 오버플로우

7 (2) 삭제의 경우 n : 배열의 길이, k : 데이터가 삽입되는 위치, pk : k번째에 삽입될 확률

8 [그림 3.2] 순차리스트의 원소(27) 삭제 11 13 19 27 29 35 55 77 n=8 이동 삭제(27) 11 13 19 29 35 55 77 삭제결과

9 3.1.3 순차 리스트의 응용 순차 리스트에서 일반적으로 다항식은 지수들이 내림차순으로 정렬되어 표현되는데 이러한 다항식은 배열을 이용한 선형리스트의 형태로 표현 될 수 있음. 표현 방법 다항식의 차수가 n+1개의 항으로 구성된 다항식 표현 A(x) = anxⁿ+an-1xn-1 +…+a1x+a0, ai : 계수, 0≤i≤n -1

10 [그림 3.3] 다항식의 배열 표현 계수 a0 a1 … an-1 an 차수 0 1 … n-1 n
다항식 A(x)를 배열을 이용하여 표현하는 방법 연산 시 알고리즘을 간단하게 함.

11 [그림 3.4] 희소한 다항식의 표현 3 5 7 20 200 100 50 0이 아닌 계수들만을 취하여 표현하는 방법 배열 A
지수 3 5 7 20 200 100 50 A(x) = 3x200+5x100+7x50+20

12 3.2 연결 리스트 연결리스트의 정의 <정 의> 선형리스트의 문제점 극복
(기억장소 낭비 등의 문제점으로 인한 비효율성) <정 의> 기억장소 내의 인접된 연속 기억공간을 필요하지 않고 어느 위치에나 저장가능 리스트를 구성하는 원소들이 다음에 연결되는 원소들을 가리키는 주소 정보를 기억시킬 수 있어야 함. 다음 원소의 주소를 저장하고 있는 포인터로서 사용될 필드 공간이 요구.링크(link)

13 [그림 3.5] 기억장소내 연결구조의 표현 주소 data link BB 8 AA 1 DD 11 FF ₩ CC 5 EE 7 1
2 3 4 5 6 7 8 9 10 11

14 [그림 3.6] 연결리스트의 개념적 표현 방법 연결구조로 연결되어 있는 구성요소 : 노드(node)
AA BB CC DD EE FF ∖ 연결구조로 연결되어 있는 구성요소 : 노드(node) 한 노드는 데이터를 저장하는 데이터 필드(data filed)와 다음에 연결되는 노드를 가리키는 포인터인 링크 필드(link field)로 구성 됨. 기억장소 내의 연결리스트 표현을 기술하는 방법 연결 필드의 포인터를 화살표를 이용하여 나타내는 [그림 3.6]과 같은 표현을 통상적으로 이용하고, 마지막에 연결되는 노드의 링크필드는 리스트의 끝으로서 더 이상 연결되는 노드가 없음을 나타내기 위하여 널(NULL)의 표현으로 ‘∖’를 사용함.

15 3.2.1 단순 연결 리스트 > 정 의 > 기본연산 리스트를 구성하는 노드들이 한쪽 방향으로 연결된 구조
삽입과 삭제가 용이 기억장소를 낭비하지 않음 삽입과 삭제에 필요한 시간을 절약 > 기본연산 단순 연결 리스트의 생성 단순 연결 리스트의 삽입 단순 연결 리스트의 삭제

16 (1) 단순 연결 리스트의 생성 [노드구조의 정의] struct listnode {
int data ; /* 노드를 구성하는 데이터 필드*/ struct listnode *link ; /* 다음 노드를 가리키는 링크 필드*/ }; struct listnode node_s; /* 정의된 listnode형 노드 구조의 변수 node_s 선언 */

17 연결 리스트 구조 생성(정의된 노드 구조 이용)
* listnode형으로 정의된 노드의 각 멤버들은 아래와 같이 정의 * 연결리스트의 시작 노드를 가리키는 포인터를 head라 선언 struct listnode *head head data link head -> data head -> link

18 struct listnode *getNode() {
[노드의 생성] struct listnode *getNode() { struct listnode *temp; temp = (struct listnode *)malloc(sizeof(node_s); ruturn temp; } getNode()함수: 사용 가능한 기억 공간으로부터 노드 하나를 생성하여, 생성된 노드의 주소를 넘겨지는 함수 free(x) : 연결리스트로부터 삭제연산을 통하여 제거되는 노드 x를 사용가능한 공간으로 반화하는 함수 동적 기억장소할당(dynamic memory allocation) 방법 : malloc()함수를 이용하여 프로그램의 실행 시 필요한 기억공간을 할당하는 것. (ex) getNode()함수

19 [알고리즘] 연결 리스트 생성 struct listnode *list_Create(int value) {
[알고리즘] 연결 리스트 생성 struct listnode *list_Create(int value) { struct listmode *temp; temp = getNode(); temp -> data = value; if(head == NULL) temp → link = NULL; else temp →link = head; head = temp; }

20 [그림3.8] 단순 연결 리스트의 생성 과정 50 40 30 head /* 리스트가 NULL인 경우의 삽입 */
/* data = 40 노드 삽입 */

21 (2) 단순 연결 리스트의 노드 삽입 단순 연결 리스트에 새로운 노드를 삽입하는 방법에는 리스트의 맨 앞에 또는 임의 노드 뒤에 삽입시키는 것이 있다. [알고리즘] 단순 연결 리스트의 노드 삽입 void insertNode(x, int value) struct listnode *x; { struct listmode *temp; temp getNode(); if(temp = getNode(); if(temp == NULL) return(-1); /* 노드의 미생성 */ else if(x == NULL) temp →data = value; temp →link = head; head = temp; } else{ /* 연결 리스트의 임의의 노드 뒤에 삽입 */ temp →link = x → link; x →link = temp;

22 [과정 1] 리스트의 맨 앞에 노드 삽입 W temp = getNode(); /* 새로운 노드의 생성 */
temp ->data = value; /* 새로운 노드의 data 필드에 값 저장 */ temp ->link = hand; /* 새로운 노드의 링크 필드에 head 포인터가 갖고 있는 다음 연결 노드의 주소 저장 */ head = temp; /* head 포인터로 하여금 생성된 노드를 가리키게 함 */ head 20 temp ②10 30 40 W  ④ ①생성 ③ [그림 3.9] 단순 연결 리스트의 맨 앞 노드 삽입 과정

23 [과정 2] 임이 노드 뒤에 새로운 노드 삽입 W temp = getNode(); /* 새로운 노드의 생성 */
temp ->data = value; /* 새로운 노드의 data 필드에 값 저장 */ temp ->link = x->link; /* 새로운 노드의 링크 필드에 임의 노드를 가리 키는 x포인터가 가리키는 노드의 링크 필드 값인 다음 연결 노드의 주소 저장 */ x ->link = temp; /* 임의 노드의 링크 필드에는 삽입 노드의 주소 저장 */ head 20 temp ②35 30 40 W  ④ ①생성 ③ [그림 3.10] 단순 연결 리스트의 임의 노드 뒤에 삽입 과정

24 (3) 단순 연결 리스트의 노드 삭제 가용 공간 리스트는 이미 생성된 노드들이 사용되지 않고 반환되는 경우, 노드들을 포인터로 연결하여 리스트 구조를 유지하는 공간을 말한다. 즉, 더 이상 사용되지 않는 노드들을 리스트로 구성하여 유지함으로써 malloc() 함수를 이용하여 새로이 노드를 생성하지 않고 가용 공간 리스트에 있는 노드를 사용하게 되는 것이다. 이로써 효율적인 공간 활용이 가능하게 된다. 이 경우 앞서 정의한 av 포인터로 연결된 가용공간리스트가 비어 있는 경우 (av == NULL)를 제외하고, getNode()함수 또는 Free()함수와는 다른 특성의 함수가 정의되어 사용된다. 단순 연결 리스트에서 x가 가리키는 노드를 삭제하기 위하여, 삭제하고자 하는 노드의 앞 노드를 가리키는 포인터를 y라 하자. 이 때 삭제하고자 하는 노드가 맨 앞의 노드라면 y는 NULL 값을 갖게 된다.

25 [알고리즘] 단순 연결 리스트의 삭제 void deleteNode(x, y) struct listnode *x, *y; { }
if(y == NULL) /* 단순 연결 리스트의 맨 앞의 노드 삭제 */ head = x -> link; else /* 단순 연결 리스트의 임의 노드 삭제 */ y ->link = x ->link; free(x); }

26 head = x ->link; /* head 포인터에 삭제된 다음 노드의 주소 저장 */
[과정 1] y = = NULL인 경우 head = x ->link; /* head 포인터에 삭제된 다음 노드의 주소 저장 */ head 20 30  \ y x 40 ① [그림 3.1] y = = NULL 일 때 노드의 삭제

27 y ->link = x->link; /* y포인터가 가리키는 링크 필드에 삭제된 다음 노드의 주소 */
[과정 1] y != = Null인 경우 y ->link = x->link; /* y포인터가 가리키는 링크 필드에 삭제된 다음 노드의 주소 */ head 20 30  y x 40 W ① [그림 3.2] y != = Null 일 때 노드의 삭제

28 3.2.2 환형 연결 리스트 단순 연결 리스트는 리스트를 구성하는 마지막 노드의 링크 필드를 NULL 값으로 갖고 있는 구조
[그림 3.13] 환형 연결 리스트의 개념적 표현 head AA BB CC DD EE FF 이 경우 마지막 노드의 링크 필드의 값을 첫 번째 노드의 주소로 저장함으로써 [그림 3.13]과 같이 마지막 노드가 첫 번째 노드를 가리키는 구조가 됨.

29 마지막 노드의 링크 필드를 활용하여 시작노드의 주소를 갖게 함.
노드의 끝을 나타내는 데는 문제가 발생. (마지막 노드에 대한 식별이 어렵다.) 무한 루프에 빠짐 환형 연결 리스트는 마지막 노드와 첫 번째 노드 사이에 head node를 둠. (head node의 데이터 필드는 비어 있게 함) [그림 3.14] 헤드 노드를 갖는 원형 연결 리스트 구조 - 10 20 30 40 50 헤드노드

30 (1) 환형 연결 리스트의 노드 삽입 헤드 노드를 이용하면 노드를 첫 번째 노드 앞에 삽입하는 경우 마지막 노드가 첫 노드를 가리키도록 하기 위하여 마지막 노드를 탐색해야 하는 문제를 해결할 수 있음. [알고리즘] 삽입 알고리즘 void C_insertNode(x, int value) struct listnode *x; { struct listnode *temp; temp = getNode(); /* ① 삽입 노드의 생성 */ temp ->data = value; /* ② 삽입 노드의 데이터 필드에 데이터 값 저장 */ temp ->link = x ->link; /* ③ 삽입 노드의 링크 필드에 다음 노드의 주소 저장 */ x ->link = temp; /* ④ 임의 노드의 링크 필드에 삽입 노드의 주소 저장 */ }

31 [그림 3.15] 헤드 노드만 존재하는 경우의 노드 삽입
- head head ==  (a) 헤드 노드만 존재하는 경우

32 - head head ==  ②1004 ④ ① ③ temp  (b) 환형 연결 리스트의 노드 삽입 과정

33 (2) 환영 연결 리스트의 노드 삭제 환영 연결 리스트에서 노드의 삭제는 헤드 노드를 제외한 삭제할 노드가 존재하는 가에 관하여 조사해 볼 필요가 있음. 만일, 삭제할 노드가 존재하지 않으면 언더플로우(underflow)가 발생함. [알고리즘] 임의 노드의 삭제 int C_deleteNode(x, y, int value) struct listnode *x, *y; /* y가 가리키는 노드 뒤에 x 노드 삭제 알고리즘 */ { if(head->link == head) list_empty(); else{ value = x ->data; /* ① 삭제 노드의 데이터 필드의 값을 value 변수에 저장 */ y ->link = x ->link; /* ② 삭제 노드의 링크 필드 값인 다음 노드의 주소를 y 노드의 링크 필드에 저장 */ free(x); /* ③ 삭제된 노드 반환 */ } return value;

34 환형 연결 리스트의 임의 위치에서 노드가 삭제되는 경우에는 단순 연결 리스트의 삭제 알고리즘과 같은 처리 방법이 활용될 수 있으며, [그림3.16]은 헤드 노드 뒤의 첫 번째 노드가 삭제되는 경우를 보여주고 있음. - head  10 20 30 y x value ① ② [그림 3.16] 첫 번째 노드의 삭제 과정

35 (3) 환형 연결 리스트의 장단점 장 점 단 점 임의의 노드로부터 모든 노드로의 접근이 용이.
리스트에 노드를 삽입하거나 삭제할 때 노드 수에 관계없이 거의 일정한 시간이 소용되므로, 노드의 삽입과 삭제 연산이 편리. 리스트의 결합(combining), 분리(splitting) 작업을 효율적으로 수행. 단 점 리스트를 구성하는 특정 노드를 검색하고자 할 때 잘못하면 무한 루프에 빠질 가능성이 있음. 검색을 끝낼 수 있는 노드가 존재하여야 하며 이를 위해 추가되는 노드가 head node.

36 3.2.3 이중 연결 리스트 이중 연결 리스트(doubly linked list)?
양방향으로의 탐색이 가능하도록 두 개의 링크 필드를 갖는 노드로 구성된 연결구조 어떤 노드의 다음 노드뿐만 아니라 이전 노드까지도 알 수 있음 데이터 필드와 두개의 링크 필드를 갖음 [노드 구조의 정의] struct double_listnode { int data; struct listnode *llink, *rlink; }

37 [그림 3.17] 이중 연결 리스트의 구조 - head llink data rlink 왼쪽 방향의 포인터 데이터필드
오른쪽 방향의 포인터 (a) 노드의 구조 d \ (b) 연결 구조 1 2 3 4

38 3.2.4 이중 연결 환형 리스트 이중 연결 환형 리스트(doubly linked circular list)
이중 연결 리스트의 구조와 환형 연결 리스트 구조가 혼합된 구조 헤드노드를 갖는 리스트 구조 Head node ⇛ 다른 노드의 구조와 같은 구조를 갖고 있으나 데이터 필드는 사용되지 않으며, 왼쪽 링크 필드(llink)는 리스트의 오른쪽끝 노드를 가리키고, 오른쪽 링크 필드(rlink)는 리스트의 왼쪽 끝 노드를 가리킴. Head pointer ⇛ 리스트의 시작 노드를 가리키는 포인터. [head node가 갖고 있는 llink와 rlink 필드는 각 방향으로의 시작 노드를 가리키는 head pointer로서의 역할을 함.

39 이중 연결 환형 리스트의 임의 노드를 가리키는 포인터를 ptr이라 가정하면 다음의 식을 만족하는 성질을 갖음
ptr = = ptr -> rlink -> llink = = ptr -> llink -> rlink - (a) 헤드노드의 빈 이중 연결 환형 리스트 d (b) 헤드노드의 이중 연결 환형 리스트 1 2 3 4

40 (1) 이중 연결 환형 리스트의 노드 삽입 새로운 노드 p를 임의 노드 x의 오른쪽에 삽입하는 알고리즘
[알고리즘] 삽입 알고리즘 Void double_listnode(p, x); Struct double_listnode *p, *x; { p ->llink = x;/*새로운 노드의 왼쪽 링크 필드에 왼쪽 노드의 주소 저장*/ p ->rlink = x ->rlink;/*새로운 노드의 오른쪽 링크 필드에 오른쪽 노드의 주소 저장*/ x ->rlink ->llink = p;/*삽입되는 노드의 오른쪽에 위치하는 노드의 왼쪽 링크 필드에 삽입 노드의 주소 저장*/ x ->rlink = p; ;/*삽입되는 노드의 왼쪽에 위치하는 노드의 오른쪽 링크 필드에 }

41 [알고리즘의 처리 과정을 단계로 설명] p x … [그림3.19] 이중 연결 환형 리스트의 삽입 과정 10 30 50
0 초기 연결 상태 … 40 p x [그림3.19] 이중 연결 환형 리스트의 삽입 과정

42 [그림 3.20] 이중 연결 환형 리스트의 삽입 과정 p x … p x … 10 30 50 40 ① pllink = x; ①
② prlink = x  rlink; ②

43 p x … p x … 10 30 50 40 ③ x  rlink  llink = p; ③ ④ 10 30 50 40
④ x  rlink = p;

44 이중 연결 환형 리스트의 노드 삭제 (리스트 L에서 x 포인터가 가리키는 노드 삭제)
[알고리즘] 삭제 알고리즘 void double_C_deledteNode(x, L) struct double_listnlde *x *N; { if(x = = L) print(“Can’t delete! “); else { x ->llink ->rlink = x ->rlink; /* 삭제되는 노드의 왼쪽 링크 필드가 가리키는 노드 의 오른쪽 링크 필드에 삭제되는 노드 의 오른쪽 노드의 주소 저장 */ x ->rlink ->llink = x ->llink; /* 삭제되는 노드의 오른쪽 링크 필드가 가리키는 노드의 왼쪽 링크 필드에 삭제되는 노드 왼쪽 노드의 주소 저장 */ free(x); }

45 [그림 3.20] 이중 환형 리스트의 삭제 과정 x … x … 10 30 50
① x  llink  rlink = x  rlink; ① ② x  rlink  llink = x  llink; ② 10 30 50 … x

46 3.3 다항식 다항식의 표현 연결리스트를 이용하여 다항식을 표현하는 방법.
다항식을 연결리스트를 이용하여 표현하기 위해서는 세개의 필드를 갖는 노드를 정의 계수 지수 연결 coef exp link [정의] 다항식의노드 정의 struct poly_node{ int coef; int exp; struct poly_node *link; }

47 다항식 A(x) = 5x³+ 6x²+ 7 를 A를 헤더로 이용한 단순 연결 리스트 표현
3 6 2 7 W [그림 3.21] 다항식의 연결 리스트 표현

48 두 개의 변수로 구성되는 이원 다항식이 표현 미지수를 처리하기 위하여 각각의 차수를 저장할 수 있는 필드가 필요
두 개의 변수로 구성되는 이원 다항식이 표현 미지수를 처리하기 위하여 각각의 차수를 저장할 수 있는 필드가 필요 노드의 구조 계수 지 수 연결 coef x_exp y_exp link [정의] 이원 다항식의 노드 정의 struct poly_node{ int coef; int x_exp; int y_exp; struct poly_node *link

49 이원 다항식 F(x, y) = 3x³y + 12x²y³+ 5y⁴+ 7 [그림 3.22] 이원 다항식의 환형 연결 리스트 표현
- F 3 1 12 2 7 5 4 헤드노드

50 (2) 다항식의 덧셈 두 다항식의 합을 계산하기 위하여 두 개의 포인터 사용 다항식 덧셈의 규칙 [예제]
지수를 비교하여 같으면, 계수는 더해진다. 지수가 다르면, 지수가 큰 쪽의 항을 새로운 다항식에 삽입한다. 지수가 0인 경우에는 항이 계수가 된다. 지수가 같은 계수끼리의 합이 0이 되면 그 항은 삭제한다. [예제] A(x) = 5x³+ 8x² +4 +) B(x) = 9x4 - 3x²+ 4x C(x) = 9x³+ 5x³+ 5x²+ 4x+ 4

51 [그림3.23] 단순 연결 리스트로 표현된 다항식(p->exp < q->exp)
5 A 3 8 2 4 \ p 9 B -3 6 1 q

52 [그림3.24] (p->exp > q-> exp)인 경우
5 A 3 8 2 4 \ p 9 B -3 6 1 q C 큰 쪽 노드의 각 필드 값을 새로운 노드를 생성하여 저장한 후 [그림 3.25]와 같이 리스트 C에 추가한다. 그리고 큰 쪽의 노드를 가리키는 p가 다음 노드를 가리키도록 (p = p->link)

53 [그림3.25] p->exp = q-> exp
A 3 8 2 4 \ p 9 B -3 6 1 q C 같은 경우 두 노드의 계수 값을 더한 후 결과와 지수 값을 새로운 노드에 저장한 후 리스트C에 추가한다. 그 후 p와 q의 값을 다음 노드를 가리키도록 변경. 그 결과 [그림 3.26]

54 [그림3.26] p->link < q-> link
5 A 3 8 2 4 \ p 9 B -3 6 1 q C 위 상태에서 p와 q의 값이 NULL이 될 때까지 과정을 반복 수행

55 [그림3.26] 두 다항식이 덧셈 결과 연결 리스트 9 C 4 5 3 2 6 1 \