Algorithms

Transcription

1 자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok

2 목 차 선형리스트 연결리스트 2

3 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3

4 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것 가족이름리스트 좋아하는음식리스트 오늘의할일리스트 서두옥 김치찌개 자료구조수업 이승희 크림스파게티 보고서작성 서하은 불고기피자 드라마시청 서영은 잡채 청소하기

5 선형리스트개념 (cont d) 선형리스트 (Linear List) 순서리스트 (Ordered List) 리스트에서나열한원소들간에순서를가지고있는리스트 원소들간의논리적인순서와물리적인순서가같은구조 ( 순차자료구조 ) 가족이름리스트좋아하는음식리스트오늘의할일리스트 1 서두옥 1 김치찌개 1 자료구조수업 2 이승희 2 크림스파게티 2 보고서작성 3 서하은 3 불고기피자 3 드라마시청 4 서영은 4 잡채 4 청소하기 5

6 선형리스트개념 (cont d) 선형리스트 (cont d) 선형리스트에서의원소삽입 원소삽입전 원소삽입후 원소 30 삽입 6

7 선형리스트개념 (cont d) 선형리스트 (cont d) 선형리스트에서의원소삭제 원소삭제전 원소삭제후 원소 30 삭제

8 1 차원배열의순차표현 선형리스트의구현 1 차원배열은인덱스를하나만사용하는배열 과목국어영어수학총점 점수 arr int arr[4] = {70, 80, 90, 240}; [0] [1] [2] [3] x0012ff70 0x0012ff74 0x0012ff78 0x0012ff7b [ 학생성적의선형리스트의논리구조 ] [ 학생성적의선형리스트의물리구조 ] 8

9 선형리스트의구현 (cont d) 2 차원배열의순차표현 행과열의구조로나타내는배열 메모리에저장될때에는 1 차원의순서로저장 학생 과목 국어영어수학총점 int score[3][4] = { }; {70, 80, 90}, {50, 60, 70}, {60, 70, 80} 9

10 연결리스트 선형리스트 연결리스트 연결자료구조 단순연결리스트 원형연결리스트 이중연결리스트 10

11 연결자료구조 순차선형리스트의문제점 리스트가순서를유지해야하므로원소들의삽입과삭제가 어렵다. 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을 이동시키는추가적인작업과시간이소요된다. 원소들의이동작업으로인한오버헤드가발생 원소의개수가많고삽입과삭제연산이많이발생하는경우더많이발생한다. 메모리사용의비효율성 최대한의크기를가진배열을처음부터준비해두어야하기때문에기억장소의 낭비를초래할수있다. 11

12 연결리스트 (Linked List) 연결자료구조 (cont d) 순차자료구조에서의연산시간에대한문제와저장공간에대한 문제를개선한자료표현방법 연결자료구조 (Linked Data Structure) t 비순차자료구조 (Nonsequential Data Structure) 데이터아이템을줄줄이엮은 (Link, Chain) 것 노드 (Node) : < 원소, 주소 > 단위로저장 데이터필드 (data field) : 원소의값을저장 링크필드 (link field) : 노드의주소를저장 data 데이터 link 링크 12

13 자기참조구조체 연결자료구조 (cont d) 자신의구조체자료형을가리키는포인터멤버를가질수있다. struct { }; char int float _score struct _score name[12]; kor, eng, math, tot; ave; *link; typedef struct _score SCORE; link 멤버는자신과같은구조의구조체주소를저장하고있다가필요시저장된주소의구조체에접근하는것을목표로한다. 13

14 연결자료구조 (cont d) 자기참조구조체 (cont d) 구조체노드의생성 SCORE *head, *new_node; // struct score *head, *new_node; head = NULL; // SCORE 크기의메모리할당 new_node = (SCORE *)malloc(sizeof(score)); if(new_node == NULL) { printf( 메모리할당실패!!! \n ); exit(100); } new_node name kor eng math tot ave NULL 14

15 단순연결리스트 단순연결리스트 (Singly linked List) 연결리스트 선형연결리스트 (linear linked list) 단순연결선형리스트 (i (singly linked likdlinear list) typedef struct _node { int data; struct _node *link; }NODE; NODE *head; head NULL 15

16 단순연결리스트 (cont d) 단순연결리스트삽입알고리즘 리스트의첫번째노드삽입알고리즘 insertfirstnode(head, data) new_node makenode(data); // 삽입할노드의메모리할당및초기화 new_node.link = head; head new_node; end insertfistnode() 번지 2000 번지 3000 번지 head X NULL 번지 new_node 9000 data NULL 16

17 단순연결리스트 (cont d) 단순연결리스트삽입알고리즘 (cont d) 리스트의중간노드삽입알고리즘 head NULL insertmiddlenode(head, pre, data) 9000 new_node makenode(data); if (head = NULL) then new_node 번지 data NULL head new; else { new_node.link pre.link; pre.link new_node; } end insertmiddlenode() 17

18 단순연결리스트 (cont d) 단순연결리스트삽입알고리즘 (cont d) 중간노드로삽입하는과정 : 리스트가빈리스트가아닐때... 1) 리스트에서새로운노드 (new_node) 가삽입될이전노드 (pre) 의위치를탐색 2) 각노드의링크필드수정 head 번지 2000 번지 3000 번지 X 3000 NULL pre 9000 번지 new_node 9000 data NULL

19 단순연결리스트 (cont d) 단순연결리스트삽입알고리즘 (cont d) 리스트의마지막노드삽입알고리즘 insertlastnode(head, data) new_node makenode(data); if (head = NULL) then else { head new_node; temp head; while (temp.link!= NULL) do temp temp.link; } end insertlastnode() temp.link new_node; 19

20 단순연결리스트 (cont d) 단순연결리스트삽입알고리즘 (cont d) 마지막노드로삽입하는과정 : 리스트가빈리스트가아닐때... 1) 리스트의마지막노드를탐색 2) 리스트의마지막노드 (temp) 가새로운노드 (new_node) 를가리키게한다. 번지 2000 번지 3000 번지 head NULL 9000 temp temp 번지 new_node 9000 data NULL 20

21 단순연결리스트 (cont d) 단순연결리스트삭제알고리즘 리스트에서조건을만족하는노드삭제알고리즘 deletenode(head, data) if (head = NULL) then error; else { temp head; while (temp!= NULL) { if (temp.data = data) then { if (temp = head) then deletefirstnode(); else if (temp = NULL) then deletelastnode(); tn d else deletemiddlenode(); } pre temp; temp temp.link; } } end deletenode() 21

22 단순연결리스트 (cont d) 단순연결리스트삭제알고리즘 (cont d) 리스트의첫번째노드를삭제 삭제할노드 (old) 의다음노드 (old.link) 를 head 로연결한다. 번지 2000 번지 3000 번지 4000 번지 head X NULL 2000 메모리해제 temp 22

23 단순연결리스트 (cont d) 단순연결리스트삭제알고리즘 (cont d) 리스트의중간노드를삭제 삭제할노드 (old) 탐색후다음노드 (old.link) 를이전노드 (pre) 의다음노드 (pre.link) 로연결한다. 번지 2000 번지 3000 번지 4000 번지 head X 4000 NULL 4000 메모리해제 temp temp 3000 pre

24 단순연결리스트 (cont d) 단순연결리스트삭제알고리즘 (cont d) 리스트의마지막노드를삭제 삭제할노드 (old) 탐색후이전노드 (pre) 의링크필드 (pre.link) 를 NULL 로만든다. 번지 2000 번지 3000 번지 4000 번지 head NULL X NULL 메모리해제 temp temp 4000 pre

25 단순연결리스트 (cont d) 단순연결리스트탐색알고리즘 리스트에서조건을만족하는데이터를가진노드탐색알고리즘 searchnode(head, data) temp head; while (temp!= NULL) do { } if (temp.data = data) then return temp; temp temp.link; if (temp = NULL) then return NULL; end searchnode() 25

26 원형연결리스트 원형연결리스트 (Circular linked List) 단순연결리스트에서마지막노드가리스트의첫번째노드를가리키게하여구조를원형으로만든연결리스트 번지 2000 번지 3000 번지 4000 번지 head

27 이중연결리스트 이중연결리스트 (Doubly linked List) 원형연결리스트의문제점 현재노드의바로이전노드를접근하려면전체리스트를한바퀴순회해야한다. typedef struct _dnode { struct _dnode int struct _dnode }DNODE; *Llink; data; *Rlink; DNODE *head; head NULL NULL 27

28 이중연결리스트 (cont d) 이중연결리스트삽입알고리즘 리스트의첫번째노드로삽입 insertfirstnode(head, data) new_node makenode(data); head NULL 번지 if (head = NULL) then head = new_node; new_node 9000 NULL data NULL else { head.llink = new_node; new_node.rlink = head; head = new_node; } end insertfirstnode() 28

29 이중연결리스트 (cont d) 이중연결리스트삽입알고리즘 (cont d) 리스트의첫번째노드로삽입 : 빈리스트가아닐경우 번지 2000 번지 3000 번지 head X NULL NULL 번지 new_node 9000 NULL data NULL 29

30 이중연결리스트 (cont d) 이중연결리스트삽입알고리즘 (cont d) 리스트의중간노드로삽입 insertmiddlenode(head, temp, data) new_node makenode(data); if (head = NULL) then head = new_node; else { new_ Node.Llink = temp.llink; new_node.rlink = temp; temp.llink.rlink = new_node; temp.link = new_node; } end insertmiddlenode() 30

31 이중연결리스트 (cont d) 이중연결리스트삽입알고리즘 (cont d) 리스트의중간노드로삽입 : 빈리스트가아닐경우... head 번지 번지 3000번지 NULL 2000 X X NULL 2000 temp 9000 번지 new_node 9000 NULL data NULL

32 이중연결리스트 (cont d) 이중연결리스트삽입알고리즘 (cont d) 리스트의중간노드로삽입 : 빈리스트가아닐경우... 번지 2000 번지 3000 번지 head NULL NULL temp 9000 번지 new_node 9000 NULL data NULL 32

33 이중연결리스트 (cont d) 이중연결리스트삽입알고리즘 (cont d) 리스트의마지막노드로삽입 insertlastnode(head, data) new_node makenode(data); if (head = NULL) then head = new_node; else { temp = head; while (temp.rlink!= NULL) temp = temp.rlink; temp.rlink = new_node; new_node.llink = temp; } end insertlastnode() 33

34 이중연결리스트 (cont d) 이중연결리스트삽입알고리즘 (cont d) 리스트의마지막노드로삽입 번지 2000 번지 3000 번지 9000 head NULL NULL temp temp 번지 new_node 9000 NULL data NULL

35 이중연결리스트 (cont d) 이중연결리스트삭제알고리즘 리스트에서조건을만족하는노드삭제알고리즘 deletenode(head, data) if (head = NULL) then error; else { temp head; while (temp!= NULL) { if (temp.data = data) then break; temp temp.link; } if (temp = head) then deletefirstnode(); else if (temp = NULL) then deletelastnode(); else deletemiddlenode(); } end deletenode() 35

36 이중연결리스트 (cont d) 이중연결리스트삭제알고리즘 (cont d) 리스트의첫번째노드를삭제 head 번지 2000 번지 3000 번지 NULL NULL NULL 메모리해제 temp 36

37 이중연결리스트 (cont d) 이중연결리스트삭제알고리즘 (cont d) 리스트의중간노드를삭제 번지 2000번지 3000번지 head NULL NULL 3000 메모리해제 temp temp

38 이중연결리스트 (cont d) 이중연결리스트삭제알고리즘 (cont d) 리스트의마지막노드를삭제 번지 2000번지 3000번지 head NULL NULL NULL 메모리해제 temp temp

39 이중연결리스트 (cont d) 이중연결리스트탐색알고리즘 리스트에서조건을만족하는데이터를가진노드탐색알고리즘 searchnode(head, data) temp head; while (temp!= NULL) do { } if (temp.data = data) then return temp; temp temp.rlink; if (temp = NULL) then return NULL; end searchnode() 39

40 참고문헌 [1] 이지영, C 로배우는쉬운자료구조, 한빛미디어, [2] 주우석, CᆞC++ 로배우는자료구조론, 한빛미디어, [3] 천인국, C C 언어로쉽게풀어쓴자료구조, 생능출판사, [4] 이재규, C 로배우는알고리즘 : 개념과기본알고리즘, 도서출판세화, [5] 문병로, 쉽게배우는알고리즘 : 관계중심의사고법, 한빛미디어, [6] 카사이아사오, 진명조역, C 언어로배우는알고리즘입문, 한빛미디어, [7] Kyle Loudon, 허욱역, Algorithms with C : C 로구현한알고리즘, 한빛미디어, 2006 [8] Wikipedia, 이강의자료는저작권법에따라보호받는저작물이므로무단전제와무단복제를금지하며, 내용의전부또는일부를이용하려면반드시저작권자의서면동의를받아야합니다. Copyright Clickseo.com. All rights reserved. 40