06장.리스트

Size: px

Start display at page:

Download "06장.리스트"

상모 시
4 years ago
Views:

1 DATA STRUCTURES USING C CHAPTER 리스트 1/28

2 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace, 2,3,,King) 핸드폰의문자메시지리스트 다항식의각항들 2/28

3 리스트의구조 Stack, Queue, Deque 과의공통점과차이점 선형자료구조 자료의접근위치 리스트 ( List) 임의의위치에서도삽입과삭제가가능함 A B C D F 요소위치 : [0] [1] [2] [3] [n-1] 3/28

4 리스트의연산 기본연산 리스트의어떤위치에새로운요소를삽입한다. 리스트의어떤위치에있는요소를삭제한다. 리스트의어떤위치에있는요소를반환한다. 리스트가비었는지를살핀다. 리스트가가득차있는지를체크한다. 고급연산 리스트에어떤요소가있는지를살핀다. 리스트의어떤위치에있는요소를새로운요소로대치한다. 리스트안의요소의개수를센다. 리스트안의모든요소를출력한다. 4/28

5 리스트 ADT 데이터 : 임의의접근방법을제공하는같은타입요소들의순서있는모임연산 : init(): 리스트를초기화한다. insert(pos, item): pos 위치에새로운요소 item을삽입한다. delete(pos): pos 위치에있는요소를삭제한다. get_entry(pos): pos 위치에있는요소를반환한다. is_empty(): 리스트가비어있는지를검사한다. is_full(): 리스트가가득차있는지를검사한다. find(item): 리스트에요소 item이있는지를살핀다. replace(pos, item): pos 위치를새로운요소 item으로바꾼다. size(): 리스트안의요소의개수를반환한다. 5/28

6 리스트구현방법 배열을이용 구현이간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트를이용 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 리스트 ADT 배열을이용한구현 a b c a b c 연결리스트를이용한구현 a b c NULL 6/28

7 배열로구현된리스트 1 차원배열에항목들을순서대로저장 L=(A, B, C) length data[max_list_size] A B C data[0] data[1] data[2] data[3] data[4] data[5] typedef int Element; Element data[max_list_size]; int length = 0; 7/28

8 공백상태 / 포화상태 공백상태 / 포화상태 length length A B C D F [0] [1] [2] [3] [MAX_LIST_SIZE-1] [0] [1] [2] [3] [MAX_LIST_SIZE-1] (a) 공백상태 (b) 포화상태 8/28

9 삽입연산 삽입위치다음의항목들을이동하여야함. N length [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E (a) 삽입전 length void insert( int pos, Element e ) { int i; if(is_full()==0 && pos >= 0 && pos<=length){ for( i=length ; i>pos ; i-- ) data[i] = data[i-1]; [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] A B N C D E (b) 삽입후 data[pos] = e; length++; else error(" 포화상태오류또는삽입위치오류 "); 9/28

10 삭제연산 삭제위치다음의항목들을이동하여야함 length [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E void delete( int pos ) { int i; C (a) 삭제전 length if( is_empty()==0 && 0<=pos && pos<length ) { for(i=pos+1 ; i<length ; i++ ) data[i-1] = data[i]; [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] A B D E (b) 삭제후 length--; else error(" 공백상태오류또는삭제위치오류 "); 10/28

11 전체프로그램 void main() { init_list(); insert(0, 10); insert(0, 20); insert(1, 30); insert(size(), 40); insert(2, 50); print_list(" 배열로구현한 List( 삽입 x5)"); 5 번의 insert() 연산결과 교체연산결과 (2 번항목 ) 3 번 delete () 연산결과 replace(2, 90); print_list(" 배열로구현한 List( 교체 x1)"); delete(2); delete(size() - 1); delete(0); print_list(" 배열로구현한 List( 삭제 x3)"); clear_list(); print_list(" 배열로구현한 List( 정리후 )"); 11/28

12 연결리스트로구현한리스트 단순연결리스트 (simply linked list) 사용 하나의링크필드를이용하여연결 마지막노드의링크값은 NULL Element data[max_list_size] int length; Node* head; data[0] A head A data[2] data[3] B C B data[4] data[5] length C data[6] D NULL 배열을이용한리스트 연결리스트를이용한리스트 12/28

13 데이터 구조체 #define Element int typedef struct LinkedNode { Element data; struct LinkedNode* link; Node; // 데이터필드 // 링크필드 데이터 Node* head; // 헤드포인터 13/28

14 단순한연산들 헤드포인터 head A B C D NULL 최초의 p 는헤드포인터 Node* p = head; p 이후로 link 를따라진행 p = p->link; int size() { Node* p; int count = 0; for (p = head; p!= NULL; p = p->link) count++; return count; Node* get_entry(int pos) { Node* n = head; int i; for (i = 0; i<pos; i++, n = n->link) if (n == NULL) return NULL; return n; 14/28

15 삽입연산 before B C node N (a) 삽입하기전 before B C (2) (1) node N (b) 삽입한후 void insert_next(node *prev, Node *n) { if (n!= NULL) { n->link = prev->link; prev->link = n; void insert(int pos, Element val) { Node *new_node, *prev; new_node = (Node*)malloc(sizeof(Node)); new_node->data = val; new_node->link = NULL; if (head == NULL) head = new_node; else { prev = get_entry(pos - 1); if (prev!= NULL) insert_next(prev, new_node); 15/28

16 삭제연산 before B before removed N (a) 삭제하기전 (1) removed after C after Node* remove_next(node *prev) { Node* removed = prev->link; if (removed!= NULL) prev->link = removed->link; return removed; B N (b) 삭제한후 C void delete(int pos) { Node* prev, *removed; if (pos == 0 && is_empty() == 0) { removed = head; head = head->link; free(removed); else { prev = get_entry(pos - 1); if (prev!= NULL) { removed = remove_next(prev); free(removed); 16/28

$전체프로그램 void main() { init_list( ); insert( 0, 10 ); insert( 0, 20 ); insert( 1, 30 ); insert( size(), 40 ); insert( 2, 50 ); print_list(" 단순연결리스트로구현한 List( 삽입 x5)"); 5 번의 insert() 연산결과 교체연산결과 (2 번항목$

17 전체프로그램 void main() { init_list( ); insert( 0, 10 ); insert( 0, 20 ); insert( 1, 30 ); insert( size(), 40 ); insert( 2, 50 ); print_list(" 단순연결리스트로구현한 List( 삽입 x5)"); 5 번의 insert() 연산결과 교체연산결과 (2 번항목 ) 3 번 delete () 연산결과 replace(2, 90); print_list(" 단순연결리스트로구현한 List( 교체 x1)"); delete( 2 ); delete( size()-1); delete( 0); print_list(" 단순연결리스트로구현한 List( 삽입 x3)"); clear_list( ); print_list(" 단순연결리스트로구현한 List( 정리후 )"); 17/28

18 헤드포인터와헤드노드 헤드포인터 (head) A B C D NULL (a) 헤드포인터를사용하여구현한리스트 헤드노드 (org)? A B C D NULL Node org; 낭비되는데이터필드 실제헤드포인터 = org.link (b) 헤드노드를사용하여구현한리스트 // 헤드노드 org. 실제헤드포인터는 org.link 가됨 헤드노드사용이유는? 18/28

19 원형연결리스트 Circular Linked List 헤드포인터 변형된원형연결리스트 헤드포인터 19/28

20 이중연결리스트 후속노드는쉽게알수있다.( 링크필드 ) 선행노드를알수는없을까? 나의선행노드는? 헤드포인터 NULL 20/28

21 이중연결리스트구조 링크필드 노드구조 선행노드 prev data next 후속노드 typedef struct DblLinkedNode { Element data; struct DblLinkedNode* prev; struct DblLinkedNode* next; Node; 데이터필드 이중연결리스트의구조 헤드포인터 NULL p == p->next->prev == p->prev->next 21/28

22 삽입연산 현재노드 현재노드 this this B C B C (1) (4) ( 3) ( 2) N (a) 현재노드 B 에서새노드 N 을삽입하기전 N (b) 삽입후 void insert_next(node *p, Node *n) { if (n!= NULL) { n->prev = p; n->next = p->next; if (p->next!= NULL) p->next->prev = n; p->next = n; 22/28

23 삭제연산 현재노드 this B N (a) 현재노드 N을삭제하기전현재노드 ( 1) this B N C C void remove_curr(node *n) { if (n->prev!= NULL) n->prev->next = n->next; if (n->next!= NULL) n->next->prev = n->prev; (b) 삭제후 ( 2) 23/28

24 전체프로그램 void main() { init_list(); insert(0, 10); insert(0, 20); insert(1, 30); insert(size(), 40); insert(2, 50); print_list(" 이중연결리스트로구현한 List( 삽입 x5)"); 5 번의 insert() 연산결과 교체연산결과 (2 번항목 ) 3 번 delete () 연산결과 replace(2, 90); print_list(" 이중연결리스트로구현한 List( 교체 x1)"); delete(2); delete(size() - 1); delete(0); print_list(" 이중연결리스트로구현한 List( 삽입 x3)"); clear_list(); print_list(" 이중연결리스트로구현한 List( 정리후 )"); 24/28

25 연결리스트의응용 : 라인편집기 Line Editor Contents Basic Linked list Stack Queue Contents Basic Linked list Stack Queue NULL 문서 문서의내부적인표현 25/28

26 라인편집기기능 (1) 한라인삽입 : 행번호와문자열을입력 (2) 한라인삭제 : 행번호를입력 (3) 한라인변경 : 행번호와문자열을입력 (4) 현재내용출력 : 현재모든행을출력 (5) 파일입력 : 지정된파일읽기 (6) 파일출력 : 지정된파일로저장 typedef struct Line { char str[max_char_per_line]; Line; typedef Line Element; 26/28

27 실행결과 1 0 번줄에삽입 라인추가명령 1 번줄에삽입 2 번줄에삽입 3 번줄에삽입 화면출력명령 내용출력 삭제명령 2 번줄삭제 27/28

28 실행결과 2 내용출력 Test.txt 를읽음 4 번줄을변경 변경메뉴 4 번줄이 typedef 에서 #define 을사용하는문장으로변경됨. 28/28

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

00. 리스트 자료구조 01. 링크드 리스트 02. 더블 링크드 리스트 03. 환형 링크드 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : (