C언어 (CSE2035) (15-1 Lists) Linear list 의구성, Insertion, deletion 윤용운, Ph.D. Dept. of Computer Science and Engineering Sogang University Seoul, Korea Tel: 010-3204-6811 Email : yuyoon0@sogang.ac.kr 2018-01-11 1
1-2 강의목표 연결 List 의기본개념소개 STACK 의기본개념소개 Queue 의기본개념소개 Tree structure 에대한기본개념소개 Graph 에대한기본개념소개
3 Lists List 는연관된 data 들의 collection 이다. 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace, 2,3,,King) 핸드폰의문자메시지리스트
1-4 Lists LISTS 의연산 새로운항목을리스트의끝, 처음, 중간에추가한다. 기존의항목을리스트의임의의위치에서삭제한다. 모든항목을삭제한다. 기존의항목을수정하고, 대치한다. 리스트가특정한항목을가지고있는지를살핀다. 리스트의특정위치의항목을반환한다. 리스트안의항목의개수를센다. 리스트가비었는지, 꽉찼는지를체크한다. 리스트안의모든항목을표시한다. Ex ) what-to-do 일정에대하여필요한것들은??? 일정의추가, 삭제, 검색, 대치
List Implementations 배열을이용하는방법 장점 : 원소의 Searching 이쉽고구현이간단 단점 : 원소의삽입및삭제가쉽지않다. 항목의개수제한 Linked list( 연결리스트 ) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 리스트 ADT 배열을이용한구현 a b c a b c 연결리스트를이용한구현 a b c 1-5
List Implementations ( 배열구현 ) 1 차원배열에항목들을순서대로저장 L=(A, B, C, D, E) 0 1 2 3 4 5 6 7 8 9 A B C D E 삽입연산 : 삽입위치다음의항목들을이동하여야함. N 0 1 2 3 4 5 6 7 8 9 A B C D E 삭제연산 : 삭제위치다음의항목들을이동함 C 0 1 2 3 4 5 6 7 8 9 A B D E 1-6
List Implementations (Linked List) Linked list 표현 리스트의항목들을노드 (node) 라고하는곳에분산하여저장 다음항목을가리키는주소도같이저장 노드 (node) : < 항목, 주소 > pair 노드는데이타필드와링크필드로구성 데이타필드 : 리스트의원소, 즉데이타값을저장하는곳 링크필드 : 다른노드의주소값을저장하는장소 ( 포인터 ) 메모리안에서의노드의물리적순서가리스트의논리적순서와일치할필요없음 A C D E B 메인메모리 1-7
8 List Implementations (Linked List) Linked list 를이용한구현
1-9 List Implementations (Linked List) 장점 삽입, 삭제가보다용이하다. 연속된메모리공간이필요없다. 크기제한이없다. A N C D E 삽입연산 단점 구현이어렵다. 오류가발생하기쉽다. B 메인메모리 삭제연산 A C D E B 메인메모리
1-10 연결리스트의종류 헤드포인터 단순연결리스트 헤드포인터 원형연결리스트 헤드포인터 이중연결리스트
Linked List 의구조 노드 = 데이터 fields + 링크 fields 헤드포인터 (head pointer): 리스트의첫번째노드를가리키는변수 data link 헤드포인터 노드의생성 : 필요할때마다동적메모리생성이용하여노드를생성 운영체제 요구 동적생성 헤드포인터 1-11
1-12 List Implementations Linked List Node Structures Nodes 연결 List의구현을위한 elements 2가지 parts를가지는 Structure임 Data parts : 리스트의원소, 즉데이타값을저장하는곳 Link parts : 다른노드의주소값을저장하는장소 ( 포인터 )
13 List Implementations Linked List 는항상 head pointer 를가진다. 어느용도로 list 를사용하느냐에따라 pointer 를더사용할수도있다.
14 Linked List Structure Linked list : 다음정보 (node) 를가리키는포인터를가지고있는 data 구성방식의한형태이다. 포인터로마치체인과같이연결되어있는 list 라고해서 linked list 라한다. Linked list 의 node 는 data 부분과 link 부분의두 parts 로구성된다. Node 의추가와삭제가자유로워메모리를효율적으로활용할수있어서, 데이터의추가삭제가빈번히발생하거나, 크기가정해지지않은경우유용하다. DATA LINK DATA LINK
15 Linked List Structures List 의첫번째 node 를가리키는포인터를헤드포인터라고한다. linked list 의 node 는다음 node 를가리킨다. 마지막 node 의포인터는 값을가진다. HEAD DATA LINK DATA LINK DATA LINK < Linked list 시작과끝 >
1-16 단순연결리스트 하나의링크필드를이용하여연결 마지막노드의링크값은 헤드포인터 10 30 40 50 60 삽입연산 before after 10 30 before after 10 30 new 20 new 20 insert_node(l,before,new) if L = then L new else new.link before.link before.link new
17 Linked List Structures Linked list 를 C 언어로표현하면다음과같다. typedef struct _NODE { DATATYPE DATA; struct _NODE *LINK; }NODE; DATA LINK? 만약 data 가 integer 하나인 linked list 를만든다면, node 와헤드포인터는다음과같이표현된다. typedef struct _NODE { int Data; struct _NODE *Link; }NODE; NODE *HEAD;
18 Linked List Structures chap15-1.c typedef struct _NODE{ int Data; struct _NODE *Link; }NODE; NODE *HEAD = ; 위 node 를가지고정수 3, 4 순서대로저장하는 Linked list 를동적으로생성해보자. HEAD = (NODE*)malloc(sizeof(NODE)); HEAD->data = 3; HEAD->Link = (NODE*)malloc(sizeof(NODE)); HEAD->Link->data = 4; HEAD->Link->Link = ; HEAD 3 Link 4 Link
19 Insert a Node Linear 리스트에 node 삽입하기 새로운 node 를위해메모리를할당한다. 삽입할위치를선택 : 정확한위치를알기위해삽입할위치의이전 node 의위치를파악 새로삽입된 node 가삽입된위치뒤의 node 를가리키도록한다. 새로삽입된 node 이전의 node 가새로운 node 를가리키도록한다.
Insert into Empty List 빈 list 에 node 삽입하기 비어있는 list 에서 HEAD 는 을가리키고있다. 새로운 node pnew 를생성한후, HEAD 가 pnew 를가리키게만든다. < 생성전 > HEAD NODE *pnew; < 새로운 node 생성 > pnew 7 LINK pnew = (NODE*)malloc(sizeof(NODE)); pnew->link = ; pnew->data = 7; <HEAD 가새로운 node 를가리키게변경 > HEAD 7 LINK HEAD = pnew; pnew 20
21 Insert at Beginning List 의처음에 node 삽입하기 이미존재하는 list 는유지한채처음, 즉 HEAD 가가리키는 node 를새로생성하는 node 로교체하는방법이다. 새로운 node 는이전의첫 node 를가리키도록한다. < 원래 list> HEAD 3 LINK NODE *pnew; < 데이터가 1인새로운 node 생성 > HEAD 3 LINK pnew 1 LINK <head를새로운 node로이동 > HEAD 1 LINK 3 LINK pnew =(NODE*) malloc(sizeof(node)); pnew->data = 1; pnew->link = HEAD; HEAD = pnew;
22 Insert at Middle list 의중간에 node 삽입하기 HEAD 특정위치에 node를삽입하기위해서는현재위치를가리키는 node ( 즉바로전 node) 를알고있어야한다. 새로운 node를생성한후생성된 node의링크를전 node의링크로하고, 전node의링크를새로운 node로바꾼다. < 원래 list> HEAD 3 LINK 3 LINK 11 LINK < 이전 node(3) 을기억하고새로운 node 를생성 > pprev 11 LINK pnew < 이전 node 의 link 를새로운 node 로변경 > 7 LINK NODE *pnew, *pprev; HEAD 3 LINK 7 LINK 11 LINK pprev = HEAD ; while(pprev!= && pprev->data!= 3) pprev = pprev->link; pnew = (NODE*) malloc(sizeof(node)); pnew->link = pprev->link; pnew->data = 7; pprev->link = pnew; pprev pnew
Insert a Node chap15-3.c NODE* insertnode(node*plist, Node*pPre, DATA item) plist : list 의 head pointer ppre : 삽입하고자하는 node 의바로이전 node 인를가리키는포인터, 새로운 node 의 data 인 item 을입력받아서새로운노드를 plist 에삽입한다. 1. NODE* insertnode(node *plist, NODE *ppre, int item)) { 2. NODE * pnew; 3. if (!pnew =(NODE*)malloc(sizeof(NODE))) { 4. printf( \nmemory overflow in insert\n ); 5. exit(100); } / 6. pnew->data = item; 7. if (plist==) { 8. pnew->link = ; // plist의값이 임 9. plist = pnew; 10. } else if (ppre==) { 11. pnew->link = plist; 12. plist=pnew; 13. } else { 14. pnew->link = ppre->link; 15. ppre->link = pnew; 16. } // end if 17. return plist; 1-23 18. } plist 의 head 가 인빈 List 에노드를삽입하는경우이다. 삽입할 node 의이전 node 가 인경우는가장처음에새로운 node 를삽입할경우이다. 두노드사이에삽입하는경우임. 호출한프로그램의 head 에새롭게만들어진 plist 반환
24 Delete a Node Linear List 로부터 node 삭제하기 삭제할위치를선택 : 정확한위치를알기위해삭제할 node 와이전 node 의위치를파악 삭제할 node 의이전 node 가삭제할 node 의다음 node 를가리키도록한다. 삭제된 node 는 free 시킨다.
Delete a Node List 의처음 node 삭제하기 첫 node 가리스트로부터삭제되면헤더가가리키는 node 가변경되어야한다. 헤더가가리키는 node 는첫 node 가가리킨 node, 즉리스트에서두번째 node 가된다. ( 만약존재하지않는다면자연히 이된다.) < 원래 list> HEAD 3 LINK 11 LINK <head 가가리키는 node 가변경, 삭제될 node 는따로기억 > ptr 3 LINK HEAD < 삭제된 node free > HEAD 11 LINK 11 LINK NODE *ptr; ptr = HEAD; HEAD =HEAD->LINK; free(ptr); 25
Delete a Node 일반적인 list 에서 node 삭제하기 삭제될 node 를가리키는 node, 즉삭제될 node 의이전 node 를기억한다. 이전 node 의 LINK 를삭제될 node 의 LINK 로대체한다. < 원래 list> 원래 List 에서 11 을찾아서삭제 HEAD 3 LINK 11 LINK < 이전 node(3) 의 LINK 를변경 > HEAD 3 LINK pprev 11 LINK pcur < 삭제된 node free > HEAD 3 LINK pprev 26 NODE *pprev, *pcur; pcur = pprev = HEAD; if(pcur == ){ printf( The list is empty\n ); }else{ while(pcur->link!= && pcur->data!= 11) { pprev = pcur; pcur = pcur->link; } pprev->link = pcur->link; free(pcur); }
27 Delete a Node chap15-4.c NODE* deletenode(node *plist, Node*pPre, Node* pcur) plist 로부터하나의 node 를삭제하는함수로해당 node 가삭제된 list 를 return Parameter: plist 는 list 의 head 를가리키는포인터 ppre 는삭제하려는 node 의이전 node 를가리키는포인터 pcur 은삭제하려는 node 를가리키는포인터 맨처음 node 를삭제할경우 맨처음 node 가아닌 node 를삭제할경우
Traversing linked lists Linked list 를탐색하는방법 배열의경우 index 가존재해서이를이용하여데이터를탐색한다. Linked list 의경우헤드에서부터순차적으로 link 를따라가탐색한다. 선임자의 Node 와현재의 Node 를알려주어야, 다음에 insertion, deletion 등의처리가가능 HEAD 3 LINK 11 LINK 22 LINK ptr 위예제에서 data 가 22 인 node 를찾고싶다면아래와같이동작한다. NODE *ptr; ptr = head; while(ptr!= ) { if(ptr->data == 22) break; ptr = ptr->link; } 28
29 Search a Node in a Linear List 선임자의 Node 와현재의 Node 를알려주어야, 다음에 insertion, deletion 등의처리가가능 Target 를찾은경우, 찾지못한경우
30 Search a Node in a Linear List target target target target target target
1-31 Search a Node in a Linear List
1-32 질문 실습과제 #11