PowerPoint 프레젠테이션

Size: px
Start display at page:

Download "PowerPoint 프레젠테이션"

Transcription

1 트리 10 장. 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색, 삽입, 삭제코드를이해한다. 이진탐색트리의균형에따른효율의차이를이해한다. 1

2 트리 Section 01 트리개요 - 트리 계층구조를표현 : 디렉터리구조, 기업구조도, 족보, 결정트리 [ 그림 10-1] 디렉터리계층구조 [ 그림 10-2] 결정트리의예 2

3 트리관련용어 [ 그림 10-3] 일반트리 트리의구성요소에해당하는 A, B, C,..., F 를노드라함. B 의바로아래있는 E, F 를 B 의자식노드라함. B 는 E, F 의부모노드이고, A 는 B, C, D 의부모노드임. 같은부모아래자식사이에서로를자매노드라함. B, C, D 는서로자매노드이며, E, F 도서로자매노드임. 주어진노드의상위에있는노드들을조상노드라함. B, A 는 F 의조상노드임. 어떤노드의하위에있는노드를후손노드라함. B, E, F, C, D 는 A 의후손노드임. 부모가없는노드즉, 원조격인노드를루트노드라함. C, D, E, F 처럼자식이없는노드를리프노드라함. 리프노드를터미널노드라함. 리프노드를제외한모든노드를내부노드라함. 주어진트리의부분집합을이루는트리를서브트리라함. 이는임의의노드와그노드에달린모든후손노드를합한것임. 주어진트리에는여러개의서브트리가존재할수있음. 그림의 B, E, F 가하나의서브트리이며, 또 C 자체로서하나의서브트리임. 둘이상의자식노드를가질수있는트리를일반트리라함. 최대두개까지의자식노드를가질수있는트리를이진트리라함 3

4 계산식트리 [ 그림 10-4] 계산트리 계산식트리 컴파일작업에이용, 식 (a * (c - d)) + k를평가하기위한것연산자는내부노드에, 피연산자는리프노드에위치연산의우선순위가트리모습자체에내장됨 (c - d) 가먼저계산되어야 (a * (c - d)) 가계산된다 4

5 일반트리의이진트리변환 [ 그림 10-4] 계산트리 [ 그림 10-5] 일반트리 일반트리 이진트리로바꾸어표현가능일반트리의자식노드수는가변. 따라서확정적인자료구조로선언불가부모노드가무조건첫자식노드를가리키게자식노드로부터일렬로자매노드들을이으면이진트리 5

6 재귀적정의 첫째, 아무런노드가없거나, 이진트리정의 둘째, 가운데노드를중심으로좌우로나뉘되, 좌우서브트리모두이진트리다. [ 그림 10-6] 이진트리의정의 6

7 트리의레벨, 높이트리의레벨 루트노드를레벨 0으로하고아래로내려오면서증가트리의높이는최대레벨과일치루트만있는트리의높이는 0 비어있는트리의높이는 -1 [ 그림 10-7] 트리의레벨, 높이 7

8 재귀적정의 트리의높이 트리의높이 = 1 + Max( 왼쪽서브트리의높이, 오른쪽서브트리의높이 ) [ 그림 10-8] 트리의높이 8

9 포화이진트리포화이진트리 ( 飽和, Full Binary Tree) 높이 h인이진트리에서모든리프노드가레벨 h에있는트리리프노드위쪽의모든노드는반드시두개의자식노드를거느려야함. 시각적으로볼때포화될정도로다차들어간모습 [ 그림 10-9] 포화이진트리 (FULL) 9

10 완전이진트리완전이진트리 ( 完全, Complete Binary Tree) 레벨 (h-1) 까지는포화이진트리마지막레벨 h에서왼쪽에서오른쪽으로가면서리프노드가채워짐하나라도건너뛰고채워지면안됨포화이진트리이면완전이진트리. 그러나역은성립안됨 [ 그림 10-10] 완전이진트리 (COMPLETE) 10

11 균형 (Balance) 트리의균형 루트노드를기준으로왼쪽서브트리와오른쪽서브트리간의높이차이 균형트리 (Height Balanced Tree) 왼쪽, 오른쪽서브트리높이가차이가 1 이하 완전균형트리 (Completely Height-Balanced Tree) 왼쪽, 오른쪽서브트리높이가완전히일치하는트리를말한다. 11

12 Section 02 추상자료형트리 - 추상자료형트리작업 Create: 새로운트리를만들기 Destroy: 사용되던트리를파기하기 Insert: 트리에새로운노드를삽입하기 Delete: 트리의특정노드를삭제하기 Search: 주어진키를가진노드레코드를검색하기 IsEmpty: 빈트리인지를확인하기 CopyTree: 주어진트리를복사하기 Traverse: 트리내부노드를하나씩순회하기 12

13 Section 03 배열에의한이진트리구현 - 배열에의한이진트리 #define MAXNODE 100 최대노드수 typedef struct 배열요소는구조체 { char Name[ ]; 성명필드 int LChild; 왼쪽자식 int RChild; 오른쪽자식 node; typedef node treetype[maxnode]; treetype은구조체배열타입 [ 그림 10-11] 트리예시 Index Structure Name LChild RChild 0 Park Kim Seo Lee Cho UnUsed 6 UnUsed 7 UnUsed [ 표 10-1] 배열에의한트리구현 13

14 인덱스 배열에의한이진트리 Park 의 Lchild = 1 이라는것은 LChild 인 Kim 이인덱스 1 번에있음을의미인덱스 -1 은빈트리 (Empty Tree) 를의미 Lee 삭제데이터필드에서 Lee 를찾아서해당엔트리를 Unused 로표시나중에그공간을재사용할수있도록함. 빈공간을관리하기위해서는삭제된첫노드를가리키는인덱스를저장하고, 첫노드의 RChild 필드가두번째삭제된노드를가리키도록체인을형성 Lee 삭제부모노드인 Kim 의 Rchild 도 -1 로부모노드를찾기위해서는 Lee 의인덱스 3 을가지고배열전체를뒤져야함. 시간면에서너무비효율적임. 배열에의한이진트리는거의사용안함 ( 예외 : 완전이진트리 ) 14

15 완전이진트리와배열 완전이진트리와배열 노트필기순으로배열에저장인덱스 K 에있는노드의왼쪽자식은 (2K + 1) 에오른쪽자식은 (2K + 2) 에인덱스 K 에있는노드의부모노드는 (K - 1) / 2 에있다 규칙존재이유 완전이진트리의정의 [ 그림 10-12] 완전이진트리의배열인덱스 15

16 Section 04 포인터에의한이진트리구현 - 포인터에의한이진트리구현 typedef struct { char Name[ ]; 성명필드 node* LChild; 왼쪽자식을가리키는포인터 node* RChild; 오른쪽자식을가리키는포인터 node; 노드는구조체타입 typedef node* Nptr; 노드를가리키는포인터를 Nptr 타입으로명명 [ 그림 10-13] 노드구조 16

17 트리구성이유 삽입, 삭제, 검색이를위해서는순회 (Traversal) 가필요트리정의가재귀적. 따라서순회도재귀적 코드 10-1: 트리순회 Traverse(T) { if (T is Empty) { else { Traverse(Left Subtree of T); Traverse(Right Subtree of T); 왼쪽서브트리와오른쪽서브트리로나누어서재귀호출 베이스케이스 처음부터빈트리를의미하는널. 이진트리순회의기본 재귀호출에의해서브트리를따라내려가리프노드의왼쪽오른쪽서브트리인 LChild 와 RChild 포인터값이널. 17

18 코드 10-2: 전위순회 전위순회 void PreOrder(Nptr T) { if (T!= NULL) { Visit(T->Name); 전위, 아래재귀호출보다앞위치 PreOrder(T->LChild); 왼쪽재귀호출 PreOrder(T->RChild); 오른쪽재귀호출 [ 그림 10-14] 이진트리의순회 18

19 방문순서 : G, C, A, E, L 전위순회 호출함수가루트노드 G 를가리키는포인터 R 을넘김 R 이복사되어 T = T1 으로들어감데이터 G 를일단찍고, G 의 LChild 를넘기며재귀호출이번에는 G 의 LChild 가 T = T2 로들어감값호출에의해포인터복사본이넘겨짐이경우에는읽기만하는작업이므로사실상참조호출이필요없음 [ 그림 10-14] 이진트리의순회 19

20 방문의위치 중위순회, 후위순회 방문 ( 데이터처리 ) 명령의위치에따라서중위순회 ( 中位, In-order Traversal), 후위순회 ( 後位, Post-order Traversal) 로구분. 전위, 중위, 후위라는용어는재귀호출의상대적인위치 전위, 중위, 후위모두각노드를단한번씩만방문. 따라서효율은 O(N) 코드 10-3: 중위순회 void InOrder(Nptr T) { if (T!= NULL) { InOrder(T->LChild); Visit(T->Name); InOrder(T->RChild); 코드 10-4: 후위순회 void PostOrder(Nptr T) { if (T!= NULL) { PostOrder(T->LChild); PostOrder(T->RChild); Visit(T->Name); [ 표 10-2] 중위순회와후위순회 20

21 트리 중위순회결과 : A, C, E, G, L 후위순회결과 : A, E, C, L, G 전위, 중위, 후위표기 계산식트리전위표기 : 전위순회하면 + * a - c d k 중위표기 : 중위순회하면 a * c - d + k 프로그래머가사용후위표기 : 후위순회하면 a c d - * k + 컴파일러번역결과 [ 그림 10-14] 이진트리의순회 [ 그림 10-4] 계산트리 21

22 레벨순회코드 10-5: 레벨순회 void LevelOrder (Nptr T) { Q.Create( ); 새로운큐를만들고 Q.Add(T); 트리의루트포인터를큐에삽입 while (! Q.IsEmpty( )) 큐가비지않을때까지 { Nptr Current = Q.GetFront( ); 프런트포인터를꺼내 Visit(Current->Name); 가리키는노드를방문하고 if (Current->LChild!= NULL) 왼쪽자식이있으면 Q.Add(Current->LChild); 포인터를큐에삽입 if (Current->RChild!= NULL) 오른쪽자식도있으면 Q.Add(Current->RChild); 포인터를큐에삽입 22

23 Section 05 스택과스레드이진트리 - 스택에의한전위순회 코드 10-6: 스택에의한전위순회 IterativePreorder (Nptr p) 루트를가리키는포인터 p { S.create( ); 새로운스택을만들기 if (p!= NULL) 빈트리가아니면 { S.Push(p); 루트를스택에푸쉬 while (! S.IsEmpty( )) 스택이비지않을때까지 { p = S.Pop( ); 스택탑을꺼내서 Visit(p); 일단방문하고 if (p->rchild!= NULL) 오른쪽자식이있으면 S.Push(p->RChild); 스택에넣고 if (p->lchild!= NULL) 왼쪽자식도있으면 S.Push(p->LChild); 스택에넣는다. 스택사용시스템스택이건사용자스택이건스택공간과함께, 푸쉬팝을위한실행시간이요구됨스택의사용을완전히배제함으로써효율성을추구할수는없는가. 23

24 중위순회의예 스레드이진트리 노드마다추가로중위순회선행자, 중위순회후속자포인터추가이러한포인터를스레드 ( 실, Thread) 라함. 실제로는중위순회후속자만있으면되고, 또 Rchild 가널일경우만중위순회후속자가필요. 따라서 Rchild 필드를스레드로대용. 재귀호출이나사용자스택없이중위순회스택팝에의해이전노드로되돌아가는대신이전포인터를트리에내장스레드트리는전위순회나후위순회에도이용 [ 그림 10-15] 선행자 / 후속자스레드 [ 그림 10-16] 후속자스레드 24

25 코드 10-7: 스레드에의한중위순회 ThreadInorder (Nptr p) { if (p!= NULL) 스레드이진트리 { while (p->lchild!= NULL) p = p->lchild; 트리의가장왼쪽자식으로 while (p!= NULL) 더이상순회할곳이없을때까지 { Visit(p); 일단방문하고 Prev = p; 현재노드를 Prev에저장 p = p->rchild; 오른쪽자식노드또는중위후속자로이동 if (p!= NULL && Prev->IsThread = = FALSE) 오른쪽자식노드라면 while (p->lchild!= NULL) 다시가장왼쪽자식으로 p = p->lchild; 중위순회에서가장먼저방문해야할것은가장왼쪽자식두번째 while 루프 p 는현재 Q 를가리키고있으므로 p = p->rchild 에의해서중위후속자인 G 를가리킴. 그림의경우에는 Q 의 RChild 가스레드로사용. 따라서중위후속자인 G 를향해순회만약에이것이스레드가아니라면현재 p 가가리키는것이 G 가아니라 Q 의오른쪽자식노드임을의미. 이자식노드가널이아니라면다시그자식노드로부터가장왼쪽자식으로가서거기서부터방문을다시시작 25

26 Section 06 이진트리의복사 - 이진트리의복사 코드 10-8: 이진트리의복사 Nptr CopyTree(Nptr T) T 는원본의루트포인터 { if (T = = NULL) 원본포인터가가리키는노드가더이상없다면 return NULL; 복사할노드포인터도널로세팅 else 원본포인터에매달린노드가있다면 { Nptr T1 = (node *)malloc(sizeof(node)); 새로운노드를만들고 T1->Name = T->Name; 데이터를복사한다. T1->LChild = CopyTree(T->LChild); 서브트리의루트포인터를할당 T1->RChild = CopyTree(T->RChild); 서브트리의루트포인터를할당 return T1; 서브트리의루트포인터를리턴 전위순회를이용 26

27 Section 07 이진탐색트리 - 이진탐색트리 typedef struct { int Key; 학번 char Name[12]; 성명 char Address[200] 주소 datatype; typedef struct { datatype Data; 데이터는하나의구조체 node* LChild; 왼쪽자식을가리키는포인터 node* RChild; 오른쪽자식을가리키는포인터 node; 구조체타입노드 27

28 이진탐색트리 탐색에유리. 노드위치는키값을기준으로결정 모든노두 N 에대하여, N 의왼쪽서브트리에있는노드는모두 N 보다작고, N 의오른쪽서브트리에있는노드는모두 N 보다크다 N 의왼쪽서브트리와 N 의오른쪽서브트리도이진탐색트리다 약하게정렬되어있다 루트를중심으로왼쪽서브트리는작은것, 오른쪽서브트리는큰것쾌속정렬의파티션과유사. 루트노드는일종의피벗에해당피벗 (Pivot) 을중심으로작은것은모두왼쪽, 큰것은모두오른쪽서브트리만놓고볼때도다시파티션된상태이다 [ 그림 10-17] 이진탐색트리의예 28

29 이진탐색트리의탐색 코드 10-9: 이진탐색트리의탐색 Nptr Search(Nptr T, int Key) { if (T = = NULL) printf("no Such Node"); else if (T->Data.Key = = Key) return T; else if (T->Data.Key > Key) return Search(T->LChild, Key); else return Search(T->RChild, Key); 오류처리후빠져나옴찾아낸노드포인터를리턴 Call by Value로전달 Call by Value로전달 29

30 이진탐색트리의삽입 Nptr Insert(Nptr T, int Key) { if (T = = NULL) 리프노드의 Child 포인터 { T = (node*)malloc(sizeof(node)); 삽입할새노드를만들기 T->Data.Key = Key; 필요시나머지데이터필드복사 T->LChild = NULL; T->RChild = NULL; 리프노드이므로자식노드를널로 else if (T->Data.Key > Key) T->LChild = Insert(T->LChild, Key); 왼쪽서브트리로재귀호출 else T->RChild = Insert(T->RChild, Key); 오른쪽서브트리로재귀호출 return T; 현재서브트리의루트포인터 [ 그림 10-18] 이진탐색트리의삽입 30

31 이진탐색트리의삽입참조호출효과 재귀호출에서되돌아오면서트리자체의자식노드포인터값이바뀜베이스케이스에서 T3가호출함수에리턴호출함수에서는그값을 C의 LChild에할당같은방식으로 T2가 G의 LChild로할당된다. 같은방식으로 T1이 R에되돌려지면, 결국 R은 G를가리킴리프노드 C를제외한나머지포인터값은원래의값그대로를재할당 31

32 이진탐색트리의삭제첫째, 삭제할노드가리프노드인경우 자식이없어서간단함. 예를들어키 A인노드를삭제하려면부모노드인 B의 LChild를널로마찬가지로노드 K를삭제하려면노드 H의 RChild를널로놓으면된다 [ 그림 10-19] 이진탐색트리의삭제 32

33 이진탐색트리의삭제 둘째, 삭제할노드가하나의자식노드를거느린경우 왼쪽자식또는오른쪽자식. 역시간단함. 노드 F 를삭제하려면 F 의부모노드가 F 의자식노드를가리키면됨. 마찬가지로노드 L 을삭제하려면 G 의 RChild 가 H 를가리키면됨. 이렇게하더라도이진탐색트리의특성은유지 L, H, K 모두 G 보다크기때문에 G 의오른쪽서브트리에존재 L 이삭제되고 H 가 G 의오른쪽서브트리에붙어도이진탐색트리의크기관계는유지됨 [ 그림 10-19] 이진탐색트리의삭제 33

34 이진탐색트리의삭제 셋째, 삭제할노드가두개의자식노드를거느린경우 가장복잡한경우노드 B 를삭제. B 의부모인 F 의 LChild 가동시에 A 와 D 를가리키게 D 가 B 로복사. 원래의 D 를삭제이진탐색트리의키크기관계는유지 B 의자리를 B 보다큰 D 가차지하더라도, B 보다작았던 A 가불만할수없음 A < B < D 관계이므로 B 가없어지면당연히 A < D 이고따라서 A 는그대로 D 의왼쪽에있어야한다 [ 그림 10-20] 자식이둘인노드의삭제 34

35 이진탐색트리의삭제 G 를삭제하면 G 의자리로복사되어가야할것은? 이진탐색트리를중위순회 (In-order Traversal) 하면정렬된결과 A, B, D, F, G, H, K, L. 크기면에서 A < B < D < F < G < H < K < L G 가삭제된후대로정렬된순서를그대로유지하려면 G 의자리에는 G 의바로오른쪽 H 나, 아니면 G 의바로왼쪽 F 가들어가야함. G 바로다음에나오는 H 를 G 의중위후속자 (In-order Successor, 後續者 ) 라하고, G 바로직전에나오는 F 를 G 의중위선행자 (In-order Predecessor, 先行者 ) 라고함. [ 그림 10-21] 자식이둘인노드의삭제 ( 일반적 ) 35

36 이진탐색트리의삭제 void BSTclass::Delete(Nptr& T, int Key) { if (T = = NULL) 삭제할노드못찾고리프노드의널까지오면 printf("no Record with Such Key"); 오류처리 else if (T->Data.Key > Key) 삭제키가현재노드의키보다작으면 Delete(T->LChild, Key); 왼쪽서브트리로가서삭제 else if (T->Data.Key < Key) 삭제키가현태노드의키보다크면 Delete(T->RChild, Key); 오른쪽서브트리로가서삭제 else if (T->Data.Key = = Key) 현재 T가가리키는노드가삭제할노드 { if ((T->LChild = = NULL) && (T->RChild = = NULL)) 자식이없는경우 { Nptr Temp = T; T = NULL; Delete Temp; T에널값을할당 else if (T->LChild = = NULL) 오른쪽자식만있는경우 { Nptr Temp = T; T = T->RChild; Delete Temp; 부모를오른쪽자식에 else if (T->RChild = = NULL) 왼쪽자식만있는경우 { Nptr Temp = T; T = T->LChild; Delete Temp; 부모를왼쪽자식에연결 else 자식이둘인경우 SuccessorCopy(T->RChild, T->Data); 오른쪽자식노드포인터와 현재노드의레코드를넘김 36

37 이진탐색트리의삭제 void BSTclass::SuccessorCopy(Nptr& T, datatype& DelNodeData) { if (T->LChild = = NULL) 중위후속자이라면 { DelNodeData.Key = T->Key; 후속자레코드를넘어온레코드에복사 Nptr Temp = T; else T = T->RChild; delete Temp; 후속자의부모와자식을연결 SuccessorCopy(T->LChild, DelNodeData); 후속자찾아서왼쪽으로이동 후속자는자식이없거나자식이하나임 후속자의 Lchild 는항상널이기때문 만약널이아니면후속자가아님 37

38 키 Lee 인노드를찾기 이진탐색트리의효율 Park, Kim, Lee( 왼쪽트리 ) 대 Cho, Kim, Lee( 오른쪽트리 ) 키 Yoo 인노드찾기 Park, Seo, Yoo: ( 왼쪽트리 ) 대 Cho, Kim, Lee, Park, Seo, Yoo ( 오른쪽트리 ) 균형왼쪽트리는완전한균형. 오른쪽트리는왼쪽서브트리의높이가 -1( 빈트리 ), 오른쪽서브트리의높이가 4 로서균형이무너짐. 최악의경우탐색은리프노드까지왼쪽트리는최악의경우에도높이가 2. 오른쪽트리는최악의경우높이 5 를모두타고내려와야함. 오른쪽트리는연결리스트 (Linked List) 에가까움. 연결이한쪽으로일직선으로 (Linear Structure) 진행하는트리 = 편향이진트리 [ 그림 10-22] 이진탐색트리의균형 38

39 균형이잘잡혀있는경우 이진탐색트리의효율 높이는 lgn 에가까움. 높이만큼키비교를요함. 효율 O(lgN) [ 그림 10-23] 이진탐색트리의비교경로 균형이무너진경우최악의경우연결리스트에가까움효율 O(N) 39

40 자료구조별탐색효율비교 자료구조별탐색효율비교 최악의경우 평균적경우 탐색 삽입 삭제 탐색 삽입 삭제 정렬된배열 lgn N N lgn N/2 N/2 정렬안된연결리스트 N 1 1 N/2 1 1 이진탐색트리 N N N lgn lgn N 1/2 [ 표 10-3] 자료구조별효율비교 40

41 Thank you 41

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 10 장. 트리 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색,

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드

More information

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경

More information

08장.트리

08장.트리 ---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조

More information

제 1 장 기본 개념

제 1 장 기본 개념 이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)

More information

7장

7장 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트

More information

Microsoft PowerPoint - lec07_tree [호환 모드]

Microsoft PowerPoint - lec07_tree [호환 모드] Tree 2008학년도 2학기 kkman@sangji.ac.krac kr -1- 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2- 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만

More information

05_tree

05_tree Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소

More information

chap 5: Trees

chap 5: Trees Chapter 5. TREES 목차 1. Introduction 2. 이진트리 (Binary Trees) 3. 이진트리의순회 (Binary Tree Traversals) 4. 이진트리의추가연산 5. 스레드이진트리 (Threaded Binary Trees) 6. 히프 (Heaps) 7. 이진탐색트리 (Binary Search Trees) 8. 선택트리 (Selection

More information

Microsoft PowerPoint - chap10_tree

Microsoft PowerPoint - chap10_tree Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 7. 트리 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 트리의개념 트리 (Tree) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 정의 (1) 하나의루트 (root) 노드 (2) 다수의서브트리 (subtree) 트리는부모-자식관계의노드들로이루어짐

More information

입학사정관제도

입학사정관제도 자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)

More information

Ch.1 Introduction

Ch.1 Introduction Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?

More information

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures 단일연결리스트 (Singly Linked List) 신찬수 연결리스트 (linked list)? tail 서울부산수원용인 null item next 구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct

More information

Chapter 4. LISTS

Chapter 4. LISTS C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or

More information

Chapter 08. 트리(Tree)

Chapter 08. 트리(Tree) 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예

More information

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600 균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at

More information

Microsoft PowerPoint - 제8장-트리.pptx

Microsoft PowerPoint - 제8장-트리.pptx 제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,

More information

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드,

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드, Tree & Heap SANGJI University Kwangman Ko kkman@sangji.ac.kr - 1 - o 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 - 2 - o 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조.

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular

More information

Lab 3. 실습문제 (Single linked list)_해답.hwp

Lab 3. 실습문제 (Single linked list)_해답.hwp Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.

More information

제 11 장 다원 탐색 트리

제 11 장 다원 탐색 트리 제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다.

More information

슬라이드 1

슬라이드 1 6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,

More information

Microsoft PowerPoint - 자료구조2008Chap07

Microsoft PowerPoint - 자료구조2008Chap07 제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint

More information

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우

More information

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100 2015-1 프로그래밍언어 9. 연결형리스트, Stack, Queue 2015 년 5 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 연결리스트 (Linked List) 연결리스트연산 Stack

More information

06장.리스트

06장.리스트 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :

More information

Microsoft PowerPoint - 6장 탐색.pptx

Microsoft PowerPoint - 6장 탐색.pptx 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential

More information

1장. 리스트

1장. 리스트 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 13 장. 균형탐색트리 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1 균형 균형 2 AVL G. M. Adelson-Velskii and

More information

11장 포인터

11장 포인터 Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함

More information

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-chap06-Queue.ppt / 큐 (QUEUE) Chapter 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 큐 Ticket ox Dongwon Jeong djeong@kunsan.ac.kr Department of Kunsan National University 전단 () 후단 () 학습목표 큐 DT 큐의개념및추상데이터타입에대한이해

More information

03_queue

03_queue Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,

More information

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2 제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 균형탐색트리 13 장. 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1 Section 01 AVL 트리 - 균형 균형 2 AVL G.

More information

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Lab 5. 실습문제 (Double linked list)-1_해답.hwp Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.

More information

Microsoft PowerPoint - 08-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In

More information

슬라이드 1

슬라이드 1 CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

Microsoft PowerPoint - 07-chap05-Stack.ppt

Microsoft PowerPoint - 07-chap05-Stack.ppt / 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감.

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음

More information

e-비즈니스 전략 수립

e-비즈니스 전략 수립 트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104 1. 트리 트리 (tree) 원소들간에 1:

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터

More information

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

리스트 (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 한글자음의모임 : (

More information

1장. 리스트

1장. 리스트 01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 리스트 5 장. 리스트 목록이나도표처럼여러데이터를관리할수있는자료형을추상화 데이터삽입, 삭제, 검색등필요작업을가함스택과큐는리스트의특수한경우에해당 학습목표 추상자료형리스트개념과필요작업을이해한다. 배열로구현하는방법, 연결리스트로구현하는방법을숙지한다. C로구현할때와 C++ 로구현할때의차이점을이해한다. 자료구조로서배열과연결리스트의장단점을이해한다. 1 Section 01

More information

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - 스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입

More information

C 언어 강의노트

C 언어 강의노트 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

More information

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]

More information

슬라이드 1

슬라이드 1 CHAP 5 : 스택 yicho@gachon.ac.kr 1 5.1 스택추상데이터타입 스택 (stack) 이란?: 쌓아놓은더미 2 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 3 스택의구조 요소 (element) 스택에저장되는것 C 스택상단 (top) : 스택에서입출력이이루어지는부분

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070> /* */ /* LZWIN.C : Lempel-Ziv compression using Sliding Window */ /* */ #include "stdafx.h" #include "Lempel-Ziv.h" 1 /* 큐를초기화 */ void LZ::init_queue(void) front = rear = 0; /* 큐가꽉찼으면 1 을되돌림 */ int LZ::queue_full(void)

More information

Chapter 4. LISTS

Chapter 4. LISTS 6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 5 장. 리스트 리스트 목록이나도표처럼여러데이터를관리할수있는자료형을추상화 데이터삽입, 삭제, 검색등필요작업을가함 스택과큐는리스트의특수한경우에해당 학습목표 추상자료형리스트개념과필요작업을이해한다. 배열로구현하는방법, 연결리스트로구현하는방법을숙지한다. C 로구현할때와 C++ 로구현할때의차이점을이해한다. 자료구조로서배열과연결리스트의장단점을이해한다. 1 목록 ( 도표

More information

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조

More information

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 Data structure: Assignment 1 Seung-Hoon Na October 1, 018 1 1.1 Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 multiline으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될

More information

1장. 리스트

1장. 리스트 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 05. AVL 트리 06. B- 트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리,

More information

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를 리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 3. 트리 3.1 트리의개요 3.2 이진트리 3.3 트리의운행 3.1 트리의개요 트리 : 그래프의일종 데이터 : 노드 순환적정의 T = {R, T 1,T 2, T n } R : 루트 T i : 서브-트리 ( 트리 ) 3.1 트리의개요 1. 노드 2. 근노드 3. 서브트리 4. 차수 5. 단노드 6. 간노드 (nonterminal node) 7. 부-노드,

More information

Microsoft PowerPoint - 제9장-트리의응용.pptx

Microsoft PowerPoint - 제9장-트리의응용.pptx 제 9 강의. 트리의탐색 1. 이진트리탐색알고리즘 2. 쓰레드 (Threaded) 이진트리 3. 이진트리를다루는알고리즘 1 1. 이진트리탐색알고리즘 트리의탐색 (traversal) 은트리의각노드를방문하는작업을말한다. ( 왜방문할까요?) 다음과같은방법들을생각해볼수있다. 방법 1) 레벨순 : 레벨이낮은순으로방문 A B C D E F G H 3가지다른방법이나올수있다.

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 7 장. 큐 스택, 큐 리스트작업은시간과무관하게정의 스택과큐의작업은시간을기준으로정의 큐는가장먼저삽입된데이터가먼저삭제되는특성의자료형을추상화 학습목표 추상자료형큐의기본개념을스택과대조하여이해한다. 추상자료형큐를구현하기위한세가지방법을이해한다. 원형배열이필요한이유와동작원리를이해한다. 큐의응용예를구체적으로명확하게이해한다. 1 큐 큐 = 대기열 2 큐 대기열을모델링 선입선출,

More information

슬라이드 1

슬라이드 1 -Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E > 제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 스택, 큐 6 장. 스택 리스트작업은시간과무관하게정의스택과큐의작업은시간을기준으로정의스택은가장나중삽입된데이터가먼저삭제되는특성의자료형을추상화 학습목표 추상자료형스택의개념을이해한다. 배열과연결리스트로구현할때의차이점을이해한다. 추상자료형리스트로구현하는방법을명확히이해한다. 스택의응용예, 특히깊이우선탐색방법을이해한다. 스택과재귀호출의연관성을이해한다. 1 Section

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 6 장. 스택 스택, 큐 리스트작업은시간과무관하게정의 스택과큐의작업은시간을기준으로정의 스택은가장나중삽입된데이터가먼저삭제되는특성의자료형을추상화 학습목표 추상자료형스택의개념을이해한다. 배열과연결리스트로구현할때의차이점을이해한다. 추상자료형리스트로구현하는방법을명확히이해한다. 스택의응용예, 특히깊이우선탐색방법을이해한다. 스택과재귀호출의연관성을이해한다. 1 스택 스택

More information

Microsoft PowerPoint - Chap5 [호환 모드]

Microsoft PowerPoint - Chap5 [호환 모드] 데이터구조 (hapter 5: Trees) 2011 년봄학기 숙명여자대학교정보과학부멀티미디어과학전공박영호 Index hapter 01: asic oncepts hapter 02: rrays and Structures hapter 03: Stacks and Queues hapter 04: Lists hapter 05: Trees hapter 06: Graphs

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 스택, 큐 7 장. 큐 리스트작업은시간과무관하게정의스택과큐의작업은시간을기준으로정의큐는가장먼저삽입된데이터가먼저삭제되는특성의자료형을추상화 학습목표 추상자료형큐의기본개념을스택과대조하여이해한다. 추상자료형큐를구현하기위한세가지방법을이해한다. 원형배열이필요한이유와동작원리를이해한다. 큐의응용예를구체적으로명확하게이해한다. 1 Section 01 큐개념 - 큐 큐 = 대기열

More information

Algorithms

Algorithms 자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 선형리스트 연결리스트 2 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것

More information

4.1 관계

4.1 관계 5 장트리 트리 (tree) 정보의항목들이가지 (branch) 로연결될수있게데이터가조직되는것, 예 ) 그림 5.1 정의 : 트리는 1 개이상의노드로이루어진유한집합으로서 1 root node 2 나머지노드들은 n( 0) 개의분리집합 (disjoint set) T 1, T 2,, T n 으로분리, T i 는각각트리로서 subtree 노드 : 정보항목 + 다른노드로뻗어진가지

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 System Software Experiment 1 Lecture 5 - Array Spring 2019 Hwansoo Han (hhan@skku.edu) Advanced Research on Compilers and Systems, ARCS LAB Sungkyunkwan University http://arcs.skku.edu/ 1 배열 (Array) 동일한타입의데이터가여러개저장되어있는저장장소

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)

More information

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D> 연결자료구조 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 내용 배열연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다.

More information

Microsoft PowerPoint - 자료구조2008Chap06

Microsoft PowerPoint - 자료구조2008Chap06 제 6 장연결리스트 연결리스트개요 2 일정한순서를가지는데이터요소들을표현하는방법중의하나이다. 배열과다르게데이터요소들의논리적인순서만유지되고기억장소내에서는각데이터요소들은논리적인순서와는상관없는임의의위치를가지도록하는자료구조이다. 연결리스트에서는각데이터요소들이기억장소내의어떤위치에어떤항목이있는지를표시해주어야한다. 이를위해데이터요소에는데이터값 (value) 뿐만아니라위치정보

More information

02장.배열과 클래스

02장.배열과 클래스 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 배열과구조체 1/20 많은자료의처리? 배열 (array), 구조체 (struct) 성적처리프로그램에서 45 명의성적을저장하는방법 주소록프로그램에서친구들의다양한정보 ( 이름, 전화번호, 주소, 이메일등 ) 를통합하여저장하는방법 홍길동 이름 :

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템

More information

Microsoft PowerPoint - chap11-포인터의활용.pptx

Microsoft PowerPoint - chap11-포인터의활용.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 포인터를 사용하는 다양한 방법에

More information

ABC 10장

ABC 10장 10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;

More information

슬라이드 1

슬라이드 1 컬렉션프레임워크 (Collection Framework) 의정의 - 다수의데이터를쉽게처리할수있는표준화된방법을제공하는클래스들 - 데이터의집합을다루고표현하기위한단일화된구조 (architecture) - JDK 1.2 이전까지는 Vector, Hashtable, Properties와같은컬렉션클래스로서로다른각자의방식으로처리 - 컬렉션프레임워크는다수의데이터를다루는데필요한다양하고풍부한클래스들을제공하므로프로그래머의부담을상당부분덜어준다.

More information

(Microsoft Word - \301\337\260\243\260\355\273\347.docx)

(Microsoft Word - \301\337\260\243\260\355\273\347.docx) 내장형시스템공학 (NH466) 중간고사 학번 : 이름 : 문제 배점 점수 1 20 2 20 3 20 4 20 5 10 6 10 7 15 8 20 9 15 합계 150 1. (20 점 ) 다음용어에대해서설명하시오. (1) 정보은닉 (Information Hiding) (2) 캡슐화 (Encapsulation) (3) 오버로딩 (Overloading) (4) 생성자

More information

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조 q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입

More information

03장.스택

03장.스택 ---------------- DT STRUCTURES USING C ---------------- CHPTER 스택 1/30 스택이란? 스택 (stack): 쌓아놓은더미 후입선출 (LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감 2/30 스택의구조 스택상단 : top 스택하단 : 불필요 요소, 항목 공백상태, 포화상태 삽입, 삭제연산

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];

More information

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning C Programming Practice (II) Contents 배열 문자와문자열 구조체 포인터와메모리관리 구조체 2/17 배열 (Array) (1/2) 배열 동일한자료형을가지고있으며같은이름으로참조되는변수들의집합 배열의크기는반드시상수이어야한다. type var_name[size]; 예 ) int myarray[5] 배열의원소는원소의번호를 0 부터시작하는색인을사용

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임

More information

14장.탐색

14장.탐색 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 탐색 1/28 탐색 (search) 이란? 여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열,

More information

Chapter 4. LISTS

Chapter 4. LISTS 연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는

More information

Chap 6: Graphs

Chap 6: Graphs 5. 작업네트워크 (Activity Networks) 작업 (Activity) 부분프로젝트 (divide and conquer) 각각의작업들이완료되어야전체프로젝트가성공적으로완료 두가지종류의네트워크 Activity on Vertex (AOV) Networks Activity on Edge (AOE) Networks 6 장. 그래프 (Page 1) 5.1 AOV

More information

Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레

Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레 Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레드 블랙 트리를 구현하고자 한다. 1.1 2-3트리와 동등한 레드 블랙 트리 2-3트리와 동등한

More information

쉽게 배우는 알고리즘 강의노트

쉽게 배우는 알고리즘 강의노트 쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,

More information

쉽게배우는알고리즘 5 장. 검색트리 IT COOKBOOK 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 한빛미디어 1

쉽게배우는알고리즘 5 장. 검색트리   IT COOKBOOK 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 한빛미디어 1 쉽게배우는알고리즘 5 장. 검색트리 htt://academy.hanb.co.k 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 - 2 - 한빛미디어 1 학습목표 검색에서레코드와키의역할을구분한다. 이진검색트리에서의검색 삽입 삭제작업의원리를이해한다. 이진검색트리의균형이작업의효율성에미치는영향을이해하고, 레드블랙트리의삽입

More information

Microsoft PowerPoint - chap04-연산자.pptx

Microsoft PowerPoint - chap04-연산자.pptx int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); } 1 학습목표 수식의 개념과 연산자, 피연산자에 대해서 알아본다. C의 를 알아본다. 연산자의 우선 순위와 결합 방향에

More information

금오공대 컴퓨터공학전공 강의자료

금오공대 컴퓨터공학전공 강의자료 C 프로그래밍프로젝트 Chap 14. 포인터와함수에대한이해 2013.10.09. 오병우 컴퓨터공학과 14-1 함수의인자로배열전달 기본적인인자의전달방식 값의복사에의한전달 val 10 a 10 11 Department of Computer Engineering 2 14-1 함수의인자로배열전달 배열의함수인자전달방식 배열이름 ( 배열주소, 포인터 ) 에의한전달 #include

More information

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Function) 1. 함수의개념 입력에대해적절한출력을발생시켜주는것 내가 ( 프로그래머 ) 작성한명령문을연산, 처리, 실행해주는부분 ( 모듈 ) 자체적으로실행되지않으며,

More information

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7> 제14장 동적 메모리 할당 Dynamic Allocation void * malloc(sizeof(char)*256) void * calloc(sizeof(char), 256) void * realloc(void *, size_t); Self-Referece NODE struct selfref { int n; struct selfref *next; }; Linked

More information

4장

4장 CHAP 5: 스택 스택이란? 스택 (stack): 쌓아놓은더미 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 스택의구조 요소 (element) C 스택상단 (top) B A 스택하단 (bottom) 스택추상데이터타입 (ADT) 객체 : n개의 element형의요소들의선형리스트

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070> 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include "QuickSort.h" 7 using namespace std; 8 9 10 Node* Queue[100]; // 추가입력된데이터를저장하기위한 Queue

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 대표적인분할정복알고리즘 4 장. 재귀호출 학습목표 재귀호출이라는개념자체를명확히이해한다. 재귀호출함수의내부구조를이해한다. 재귀호출에내재하는효율성에대해이해한다. 1 Section 01 상징적의미 - 도미노 도미노 2 도미노 100 번째것이반드시쓰러진다는사실을증명하라. 수학적귀납법 (Mathematical Induction) 처음것 (K=1) 은반드시쓰러진다. K

More information

EA0015: 컴파일러

EA0015: 컴파일러 5 Context-Free Grammar 무엇을공부하나? 앞에서배운 " 정규식 " 은언어의 " 어휘 (lexeme)" 를표현하는도구로사용되었다. 언어의 " 구문 (syntax)" 은 " 정규언어 " 의범위를벗어나기때문에 " 정규식 " 으로표현이불가능하다. 본장에서배우는 " 문맥자유문법 " 은언어의 " 구문 (syntax)" 을표현할수있는도구이다. 어떤 " 문맥자유문법

More information

01_List

01_List List Data Structures and Algorithms 목차 추상자료형 (ADT) 배열을이용한리스트의구현 연결리스트의개념적이해 연결리스트의 ADT 구현 원형연결리스트 이중연결리스트 Data Structures and Algorithms 2 추상자료형 Abstract Data Type Data Structures and Algorithms 3 추상자료형

More information