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

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

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

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

3 리스트란? 순서를 가진 항목들의 모임 리스트의 예 집합과의 차이점은? 자료를 정리하는 방법을 제공 장보기 리스트
오늘 만날 사람들의 리스트 핸드폰의 문자 메시지 리스트 …

4 리스트의 연산 새로운 항목을 리스트의 끝, 처음, 중간에 추가한다. 기존의 항목을 리스트의 임의의 위치에서 삭제한다.
모든 항목을 삭제한다. 기존의 항목을 대치한다. 리스트가 특정한 항목을 가지고 있는지를 조사한다. 리스트의 특정위치의 항목을 반환한다. 리스트안의 항목의 개수를 센다. 리스트가 비어 있는지 또는 꽉 차 있는지를 체크한다. 리스트안의 모든 항목을 디스플레이한다.

5 리스트 ADT ∙객체: n개의 요소로 구성된 순서 있는 모임 ∙연산:
∙연산:   ▪ addLast(list, item) ::= 맨끝에 item을 추가한다.  ▪ addFirst(list, item) ::= 맨앞에 item을 추가한다.  ▪ add(list, pos, item) ::= pos 위치에 item을 추가한다.  ▪ delete(list, pos) ::= pos 위치의 요소를 제거한다.  ▪ clear(list) ::= 리스트의 모든 요소를 제거한다.  ▪ replace(list, pos, item) ::= pos 위치의 요소를 item로 바꾼다.  ▪ isInList(list, item) ::= item이 리스트안에 있는지를 검사한다.  ▪ getItem(list, pos) ::= pos 위치의 요소를 반환한다.  ▪ getLength(list) ::= 리스트의 길이를 구한다.  ▪ isEmpty(list) ::= 리스트가 비어 있는지를 검사한다.  ▪ isFull(list) ::= 리스트가 꽉 차있는지를 검사한다.  ▪ display(list) ::= 리스트의 모든 요소를 디스플레이한다.

6 예제 다음 각 연산의 결과는 무엇인가? (항목의 위치는 0부터 시작한다고 가정) list addLast(list, a);
addLast(list b); add(list, 2, c); add(list, 1, d); delete(list, 2); replace(list, 1, e): (a)

7 예제 #2 main() { int i, n; ListType list2; // 리스트 생성 // 리스트 연산 수행
addLast(list2,"마요네즈”); addLast(list2,"빵”); addLast(list2,"치즈”); addLast(list2,"우유”); // 리스트 출력 display(list2); n = getLength(list2); printf("쇼핑해야할 항목수는 %d입니다.\n", n); for(i=0;i<n;i++) printf("%d항목은 %s입니다.¡°,i, getItem(list2,i)); }

8 리스트 구현 방법 배열 vs 연결 리스트 평가 기준 구현이 용이한가? 삽입, 삭제 연산이 효율적인가?
리스트의 크기가 제한되는가? a b c NULL 배열을 이용한 구현 연결리스트를 이용한 구현

9 리스트 구현: 배열 다음과 같이 리스트를 1차원 배열로 구현 삽입연산: 삭제 연산 L=(A, B, C, D, E)
N의 항목을 리스트의 3번째 항목으로 삽입하는 경우 삭제 연산 리스트의 3번째 항목을 삭제하는 경우 A B C D E 1 2 3 4 5 6 7 8 9

10 리스트 구현: 배열 리스트 표현 … 리스트의 현재 크기 list length type list_type = record
list: array [1.. MAX_LIST_SIZE] of integer; length: integer; end; typedef struct { int list[MAX_LIST_SIZE]; int length; } ArrayListType;

11 리스트 연산 삽입 연산 (알고리즘) addFirst(), addLast()를 구현하라.
typedef struct { int list[MAX_LIST_SIZE]; int length; } ArrayListType; 삽입 연산 (알고리즘) addFirst(), addLast()를 구현하라. A B C D E 1 2 3 4 5 N add(in out ArrayListType list, in int pos, in int item) // pos 위치에 item을 삽입 { } // 배열이 꽉 차 있고, pos가 올바른 범위에 있는지 검사

12 리스트 연산 삭제 연산 deleteFirst(), deleteLast()를 구현하라.
B C D E 1 2 3 4 5 int delete(in out ArrayListType list, in int pos) // pos 위치 값을 삭제하고, 삭제된 값을 반환 { } // pos가 올바른 범위에 있는지 검사

13 리스트 연산 isEmpty() 연산 isFull()을 구현하라.
boolean isEmpty(in ArrayListType list) // 리스트가 비어 있으면 true, 그렇지 않으면 // flase를 반환 { }

14 리스트 연산 display() 연산 display(in ArrayListType list)
// 리스트에 포함된 모든 항목을 출력 { }

15 예제 typedef struct { int list[MAX_LIST_SIZE]; int length;
} ArrayListType; main() { ArrayListType list // 리스트 생성 // ArrayListType *list로 선언하면? // 리스트 연산 수행 init(&list); addFirst(&list,10); add(&list, 0, 20); add(&list, 0, 30); // 리스트 출력 display(list); }

16 연결 리스트란? 노드들의 연결된 표현 노드는 (데이터, 링크)로 구성 링크는 노드를 연결하는데 사용(주소로 표현)
노드는 분산되어 저장 가능(순차적으로 배치될 필요 없음) 메인 메모리 A B C D E data link

17 연결 리스트란? 삽입, 삭제 연산이 용이한가? 알고리즘 복잡도는? 리스트 크기에 제한을 두는가? 구현이 용이한가? 삽입 연산
메인 메모리 A B C D E N 메인 메모리 A B C D E

18 연결 리스트의 구조 노드 헤드 포인터 (데이터, 링크) 리스트의 첫번째 노드를 가리키는 변수 NULL 헤드 포인터 data
link NULL 헤드 포인터

19 연결 리스트의 유형 헤드 포인터 단순 연결 리스트 원형 연결 리스트 이중 연결 리스트 NULL

20 단순 연결 리스트 하나의 링크 필드를 이용하여 연결 마지막 노드의 링크 값은 NULL link 헤드포인터 NULL 10 20
30 50 40

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

22 삽입 연산 헤드 포인터가 NULL인 경우 prev가 NULL인 경우 (첫번째 노드로 삽입)
prev가 NULL이 아닌 경우 (prev 다음에 삽입) 10 30 20 prev after new procedure insertNode(list, prev, new: nodeptr) // list: 헤드 포인터 // prev: 삽입될 위치의 선행 노드 // new: 새로 삽입될 노드

23 삽입연산 (1) head가 NULL인 경우 (2) prev가 NULL인 경우 head NULL new_node head

24 삽입연산 (3) prev가 NULL이 아닌 경우 new_node NULL prev head

25 삽입 연산 알고리즘 procedure insertNode(list, prev, new: nodeptr)
list, prev의 NULL 유무 고려 알고리즘 procedure insertNode(list, prev, new: nodeptr) // list: 헤드 포인터 // prev: 삽입될 위치의 선행 노드 // new: 새로 삽입될 노드 { return list; }

26 삽입 연산 알고리즘 procedure addFirst(list, new: nodeptr) // list: 헤드 포인터
첫번째 노드로 삽입 현재의 첫 노드를 어떻게 아는가? procedure addFirst(list, new: nodeptr) // list: 헤드 포인터 // new: 새로 삽입될 노드 { return list; }

27 삽입 연산 알고리즘 procedure addLast(list, new: nodeptr) // list: 헤드 포인터
마지막 노드로 삽입 현재의 마지막 노드를 어떻게 아는가? procedure addLast(list, new: nodeptr) // list: 헤드 포인터 // new: 새로 삽입될 노드 { return list; }

28 리스트 방문 리스트에 포함된 모든 노드를 순차적으로 방문 procedure display(list: nodeptr)
end display

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

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

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

32 Review: C의 포인터 포인터: 다른 변수의 주소를 가지고 있는 변수 포인터가 가리키는 내용의 변경: * 연산자 사용 주소
26 ‘A’ 변수 a 주소 포인터 p 포인터: 다른 변수의 주소를 가지고 있는 변수 char a='A'; char *p; p = &a; 포인터가 가리키는 내용의 변경: * 연산자 사용 26 ‘B’ 변수 a 주소 포인터 p *p= 'B';

33 Review: C의 포인터 다음 C 코드의 각 문장 의미는 무엇인가? int a = 10, b = 20; // a)
int *q, *r, *p; q = &a; // b) r = &b; *r = *q; // c) printf(“%p\t%d”, r, *r); // d) p = (int *)malloc(sizeof(int)*3); *p = *r; *(p+1) = a; *(p+2) = b; printf((%p: %d, %p: %d, %p: %d\n”, p, *p, (p+1), *(p+1), (p+2), *(p+2));

34 포인터 용도: 참조-호출 표현 함수의 매개변수를 포인터로 전달 void swap(int* px, int* py) {
int tmp; tmp = *px; *px = *py; *py = tmp; } main() int a=1,b=2; printf("swap을 호출하기 전: a=%d, b=%d\n", a,b); swap(&a, &b); printf("swap을 호출한 다음: a=%d, b=%d\n", a,b);

35 포인터 용도: 동적 메모리 할당 전형적인 동적 메모리 할당 코드 동적 메모리 할당 관련 라이브러리 함수
main() { int* pi; pi = (int *)malloc(sizeof(int)); // 동적 메모리 할당 ... … // 동적 메모리 사용 free(pi); // 동적 메모리 반납 } 동적 메모리 할당 관련 라이브러리 함수 void * malloc(size_t size) // 메모리 할당 free(void * ptr) // ptr이 가리키는 메모리 반환 sizeof(var) // 변수나 타입의 크기 반환(바이트 단위) stdlib.h 상에 정의

36 Test 다음 각 C 문장의 의미는? int a, b; Int *p; a = 10; p = &a; b = *p;

37 Test 다음 각 C 문장의 의미는? int a, b; Int *p, *q; a = 10; p = &a; q = &b;
*q = *p + 10;

38 Test 다음 각 C 문장의 의미는? int a, b, c; Int *p, *q; a = 10; p = &a; q = &b;
*q = *p + 10; q = p c = *p + *q

39 Test 다음 각 C 문장의 의미는? int a; Int *p; a = 10;
p = (int *)malloc(sizeof(int)); *p = a;

40 Test 다음 각 C 문장의 의미는? int a; Int *p; a = 10;
p = (int *)malloc(sizeof(int)*3); *p = a; *(p+1) = a + 20; *(p+2) = *p + 30;

41 Test 다음 각 C 문장의 의미는? struct node p; p.data = 10; p.link = NULL;
int data; struct node *link; } 다음 각 C 문장의 의미는? struct node p; p.data = 10; p.link = NULL;

42 Test 다음 각 C 문장의 의미는? struct node p; struct node *list; p.data = 10;
int data; struct node *link; } 다음 각 C 문장의 의미는? struct node p; struct node *list; p.data = 10; p.link = NULL; list = (struct node *)malloc(sizeof(struct node)); (*list).data = 20; list->link = NULL;

43 Test 다음 각 C 문장의 의미는? struct node p; struct node *list; p.data = 10;
int data; struct node *link; } 다음 각 C 문장의 의미는? struct node p; struct node *list; p.data = 10; p.Link = NULL; list = (struct node *)malloc(sizeof(struct node)); (*list).data = 20; list->link = &p;

44 Test 다음에서 새로운 노드 q(data=30)를 생성하여 list 앞에서 삽입하려면? struct node p;
int data; struct node *link; } Test 다음에서 새로운 노드 q(data=30)를 생성하여 list 앞에서 삽입하려면? struct node p; struct node *list, *q; p.data = 10; p.link = NULL; list = (struct node *)malloc(sizeof(struct node)); (*list).data = 20; list->link = &p;

45 Test 다음에서 새로운 노드 r을 생성하여 list에서 두번째 노드로 삽입하려면? struct node p;
int data; struct node *link; } Test 다음에서 새로운 노드 r을 생성하여 list에서 두번째 노드로 삽입하려면? struct node p; struct node *list, *q, *r; p.data = 10; p.link = NULL; list = (struct node *)malloc(sizeof(struct node)); (*list).data = 20; list->link = &p; q = (struct node *)malloc(sizeof(struct node)); q->data = 20; q->link = list; list = q

46 C 구현: 삽입 연산 알고리즘 procedure insertNode(list, prev, new: nodeptr)
list, prev의 NULL 유무 고려 알고리즘 procedure insertNode(list, prev, new: nodeptr) // list: 헤드 포인터 // prev: 삽입될 위치의 선행 노드 // new: 새로 삽입될 노드 { return list; }

47 C 구현: 리스트 방문 리스트에 포함된 모든 노드를 순차적으로 방문 procedure display(list: nodeptr)
end display