e-비즈니스 전략 수립
|
|
|
- 재포 낭
- 5 years ago
- Views:
Transcription
1 트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 )
2 Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104
3 1. 트리 트리 (tree) 원소들간에 1: 多관계를가지는비선형자료구조 원소들간에계층관계를가지는계층형자료구조 상위원소에서하위원소로내려가면서확장되는트리 ( 나무 ) 모양의구조 하나의줄기에서가지로뻗어나가면서 확장되는구조 하나의그루터기에서뿌리로뻗어나가면서 확장되는구조 3/104
4 1. 트리 트리자료구조의예 가계도 가계도의자료 : 가족구성원 자료를연결하는선 : 부모 - 자식관계표현 4/104
5 1. 트리 철수의자식 성호, 영주, 진호 성호, 영주, 진호의부모 철수 같은부모의자식들끼리는형제관계 성호, 영주, 진호는형제관계 조상 현재위치에서연결된선을따라올라가면서만나는사람들 수영의조상 : 승완, 성호, 철수 자손 - 현재위치에서연결된선을따라내려가면서만나는사람들 성호의자손 : 승우, 승완, 수영, 수철 선을따라내려가면서다음세대로확장 가족구성원누구든지자기의가족을데리고분가하여독립된가계를이룰수있다. 5/104
6 1. 트리 트리 A 6/104
7 1. 트리 트리 A 노드 (node) 트리의원소 트리 A 의노드 - A,B,C,D,E,F,G,H,I,J,K,L 루트노드 (root node) 트리의시작노드 트리 A 의루트노드 - A 간선 (edge) 노드를연결하는선. 부모노드와자식노드를연결 형제노드 (sibling node) 같은부모노드의자식노드들 B,C,D 는형제노드 조상노드 간선을따라루트노드까지이르는경로에있는모든노드들 K 의조상노드 : F, B, A 서브트리 (subtree) 부노노드와연결된간선을끊었을때생성되는트리 각노드는자식노드의개수만큼서브트리를가진다. 자손노드 서브트리에있는하위레벨의노드들 B 의자손노드 E,F,K,L 7/104
8 1. 트리 트리 A 차수 (degree) 노드의차수 : 노드에연결된자식노드의수. A 의차수 =3, B 의차수 =2, C 의차수 =1 트리의차수 : 트리에있는노드의차수중에서가장큰값 트리 A 의차수 =3 단말노드 ( 리프노드 ) : 차수가 0 인노드. 자식노드가없는노드 높이 노드의높이 : 루트에서노드에이르는간선의수. 노드의레벨 B 의높이 =1, F 의높이 =2 트리의높이 : 트리에있는노드의높이중에서가장큰값. 최대레벨 트리 A 의높이 =3 8/104
9 1. 트리 포리스트 (forest) : 서브트리의집합 트리 A 에서노드 A 를제거하면, A 의자식노드 B, C, D 에대한서브트리가생기고, 이들의집합은포리스트가된다. A 루트루트루트 B C D E F G H I J K L 트리 1 트리 2 트리 3 9/104
10 2. 이진트리 이진트리 트리의노드구조를일정하게정의하여트리의구현과연산이쉽도록정의한트리 이진트리의모든노드는왼쪽자식노드와오른쪽자식노드만을가진다. 부모노드와자식노드수와의관계 1:2 공백노드도자식노드로취급한다. 0 노드의차수 2 10/104
11 2. 이진트리 이진트리는순환적구성 노드의왼쪽자식노드를루트로하는왼쪽서브트리도이진트리 노드의오른쪽자식노드를루트로하는오른쪽서브트리도이진트리 루트 A 의왼쪽서브트리 루트 B A A 의오른쪽서브트리 루트 C B 의왼쪽서브트리 B 의오른쪽서브트리 C 의왼쪽서브트리 C 의오른쪽서브트리 D E F G H I J K L 11/104
12 2. 이진트리 추상자료형이진트리 ADT BinaryTree 데이터 : 공백이거나루트노드, 왼쪽서브트리, 오른쪽서브트리로구성된노드들의유한집합연산 : bt, bt1, bt2 BinaryTree; item Element; createbt() = create an empty binary tree; // 공백이진트리를생성하는연산 isempty(bt) = if (bt is empty) then return true else return false; // 이진트리가공백인지아닌지를확인하는연산 makebt(bt1, item, bt2) = return {item 을루트로하고 bt1 을왼쪽서브트리, bt2 를오른쪽서브트리로하는이진트리 } // 두개의이진서브트리를연결하여하나의이진트리를만드는연산 leftsubtree(bt) = if (isempty(bt)) then return null else return left subtree of bt; // 이진트리의왼쪽서브트리를구하는연산 rightsubtree(bt) = if (isempty(bt)) then return null else return right subtree of bt; // 이진트리의오른쪽서브트리를구하는연산 data(bt) = if (isempty(bt)) then return null else return the item in the root node of bt; // 이진트리에서루트노드의데이터 (item) 를구하는연산 End BinaryTree 12/104
13 2. 이진트리 이진트리의특성 정의 1) n 개의노드를가진이진트리는항상 (n-1) 개의간선을가진다. 루트를제외한 (n-1) 개의노드가부모노드와연결되는한개의간선을가짐 정의 2) 높이가 h 인이진트리가가질수있는노드의최소개수는 (h+1) 개가되며, 최대개수는 (2 h+1-1) 개가된다. 이진트리의높이가 h 가되려면한레벨에최소한한개의노드가있어야하므로 높이가 h 인이진트리의최소노드의개수는 (h+1) 개 하나의노드는최대 2 개의자식노드를가질수있으므로레벨 i 에서의노드의 최대개수는 2 i 개이므로높이가 h 인이진트리전체의노드개수는 2 i = 2 h+1-1 개 13/104
14 2. 이진트리 이진트리의특성 높이가 3 이면서최소의노드를갖는이진트리와최대의노드를갖는이진트리 14/104
15 2. 이진트리 이진트리의종류 포화이진트리 (Full Binary Tree) 모든레벨에노드가포화상태로차있는이진트리 높이가 h 일때, 최대의노드개수인 (2 h+1-1) 의노드를가진이진트리 루트를 1 번으로하여 2 h+1-1 까지정해진위치에대한노드번호를가짐 15/104
16 2. 이진트리 완전이진트리 (Complete Binary Tree) 높이가 h 이고노드수가 n 개일때 ( 단, h+1 n < 2 h+1-1 ), 포화이진트리의노드번호 1 번부터 n 번까지빈자리가없는이진트리 예 ) 노드가 12 개인완전이진트리 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 I 10 J 11 K 12 L /104
17 2. 이진트리 편향이진트리 (Skewed Binary Tree) 높이 h 에대한최소개수의노드를가지면서한쪽방향의자식노드만을가진이진트리 왼쪽편향이진트리 모든노드가왼쪽자식노드만을가진편향이진트리 오른쪽편향이진트리 모든노드가오른쪽자식노드만을가진편향이진트리 17/104
18 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 순차자료구조를이용한이진트리의구현 1 차원배열의순차자료구조사용 높이가 h 인포화이진트리의노드번호를배열의인덱스로사용 인덱스 0 번 : 실제로사용하지않고비워둠. 인덱스 1 번 : 루트저장 18/104
19 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 완전이진트리의 1 차원배열표현 1 A 2 3 B C D E F G H I J K L [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] A B C D E F G H I J K L 19/104
20 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 왼쪽편향이진트리의 1 차원배열표현 20/104
![3. 이진트리구현 : 순차자료구조를이용한이진트리구현 이진트리의 1 차원배열에서의인덱스관계 [0] 1 A [1] [2] A B 부모노드의인덱스 = 2 2 B 3 C [3] [4] [5] C D E 4 5 6](/docs-images/100/143848124/images/21-1.jpg "7 D E F G 8 9 10 11 12 H I J K L [6] [7] [8] [9] [10] F G H I J 왼쪽자식노드의인덱스 = 10 [11] [12] K L 오른쪽자식노드의인덱스 = 11")
21 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 이진트리의 1 차원배열에서의인덱스관계 [0] 1 A [1] [2] A B 부모노드의인덱스 = 2 2 B 3 C [3] [4] [5] C D E D E F G H I J K L [6] [7] [8] [9] [10] F G H I J 왼쪽자식노드의인덱스 = 10 [11] [12] K L 오른쪽자식노드의인덱스 = 11 21/104
22 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 이진트리의순차자료구조표현의단점 편향이진트리의경우에사용하지않는배열원소에대한메모리공간낭비발생 트리의원소삽입 / 삭제에대한배열의크기변경어려움 22/104
23 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 연결자료구조를이용한이진트리의구현 단순연결리스트를사용하여구현 이진트리의모든노드는최대 2 개의자식노드를가지므로일정한구조의 단순연결리스트노드를사용하여구현 이진트리의노드구조에대한 C 구조체정의 typedef struct treenode { char data; struct treenode *left; struct treenode *right; } treenode; 23/104
24 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 완전이진트리의단순연결리스트표현 24/104
25 3. 이진트리구현 : 순차자료구조를이용한이진트리구현 왼쪽편향이진트리의단순연결리스트표현 25/104
26 4. 이진트리의순회 이진트리의순회 (traversal) 계층적구조로저장되어있는트리의모든노드를방문하여데이터를처리하는연산 순회를위해수행할수있는작업정의 ⑴ 현재노드를방문하여데이터를읽는작업 D ⑵ 현재노드의왼쪽서브트리로이동하는작업 L ⑶ 현재노드의오른쪽서브트리로이동하는작업 R 현재노드 노드의데이터읽기 : 작업 D 왼쪽서브트리로이동하기 : 작업 L 오른쪽서브트리로이동하기 : 작업 R 26/104
27 4. 이진트리의순회 이진트리가순환적으로정의되어구성되어있으므로, 순회작업도서브트리에대해서순환적으로반복하여완성한다. 왼쪽서브트리에대한순회를오른쪽서브트리보다먼저수행한다. 순회의종류 전위순회 중위순회 후위순회 27/104
28 4. 이진트리의순회 전위순회 (preorder traversal) 수행방법 1 현재노드 n을방문하여처리한다. : D 2 현재노드 n의왼쪽서브트리로이동한다. : L 3 현재노드 n의오른쪽서브트리로이동한다. : R 전위순회알고리즘 28/104
29 4. 이진트리의순회 전위순회의예 29/104
30 4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K 30/104
31 4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K 31/104
32 4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K 32/104
33 4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K A B C D E F G H I J K 33/104
34 4. 이진트리의순회 수식이진트리에대한전위순회 수식을이진트리로구성한수식이진트리를전위순회하면, 수식에대한전위표기식을구할수있다. [ 그림 8-15] 의수식이진트리의전위순회경로 >> -*AB/CD 34/104
35 4. 이진트리의순회 중위순회 (inorder traversal) 수행방법 1 현재노드 n의왼쪽서브트리로이동한다. : L 2 현재노드 n을방문하여처리한다. : D 3 현재노드 n의오른쪽서브트리로이동한다. : R 중위순회알고리즘 35/104
36 4. 이진트리의순회 중위순회의예 36/104
37 4. 이진트리의순회 중위순회과정 >> H-D-B-I-E-J-A-F-C-G-K A B C D E F G H I J K 37/104
38 4. 이진트리의순회 38/104
39 4. 이진트리의순회 39/104
40 4. 이진트리의순회 40/104
41 4. 이진트리의순회 수식이진트리에대한중위순회 수식이진트리를중위순회하면, 수식에대한중위표기식을구할수있다. [ 그림 8-15] 의수식이진트리의중위순회경로 >> A*B-C/D 41/104
42 4. 이진트리의순회 후위순회 (postorder traversal) 수행방법 1 현재노드 n의왼쪽서브트리로이동한다. : L 2 현재노드 n의오른쪽서브트리로이동한다. : R 3 현재노드 n을방문하여처리한다. : D 후위순회알고리즘 42/104
43 4. 이진트리의순회 후위순회의예 43/104
44 4. 이진트리의순회 후위순회과정 >> H-D-I-J-E-B-F-K-G-C-A A B C D E F G H I J K 44/104
45 4. 이진트리의순회 45/104
46 4. 이진트리의순회 46/104
47 4. 이진트리의순회 47/104
48 4. 이진트리의순회 수식이진트리에대한후위순회 수식이진트리를후위순회하면, 수식에대한후위표기식을구할수있다. [ 그림 8-15] 의수식이진트리의후위순회경로 >> AB*CD/- 48/104
![4. 이진트리의순회 : [ 예제 8-1] 연결자료구조로구현한이진트리에서의순회 C 프로그램 수식 (A*B-C/D)](/docs-images/100/143848124/images/49-1.jpg "에대한수식이진트리를단순연결리스트로구현 전위순회, 중위순회, 후위순회를차례로수행하면서순회경로를출력하는프로그램 실행결과 >")
49 4. 이진트리의순회 : [ 예제 8-1] 연결자료구조로구현한이진트리에서의순회 C 프로그램 수식 (A*B-C/D) 에대한수식이진트리를단순연결리스트로구현 전위순회, 중위순회, 후위순회를차례로수행하면서순회경로를출력하는프로그램 실행결과 > 49/104
50 4. 이진트리의순회 : [ 예제 8-1] 01 #include <stdio.h> 02 #include <stdlib.h> 03 #include <memory.h> typedef struct treenode{ // 연결자료구조로구성하기위해트리의노드정의 06 char data; 07 struct treenode *left; // 왼쪽서브트리에대한링크필드 08 struct treenode *right; // 오른쪽서브트리에대한링크필드 09 } treenode; treenode* makerootnode(char data, treenode* leftnode, treenode* rightnode) 12 { //data 를루트노드로하여왼쪽서브트리와오른쪽서브트리를연결하는연산 13 treenode* root = (treenode *)malloc(sizeof(treenode)); 14 root->data = data; 15 root->left = leftnode; 16 root->right = rightnode; 17 return root; 18 } void preorder(treenode* root) // 이진트리에대한전위순회연산 21 { 22 if(root){ 23 printf("%c", root->data); 24 preorder(root->left); 25 preorder(root->right); 26 } 27 } 50/104
51 4. 이진트리의순회 : [ 예제 8-1] void inorder(treenode* root) // 이진트리에대한중위순회연산 30 { 31 if(root){ 32 inorder(root->left); 33 printf("%c", root->data); 34 inorder(root->right); 35 } 36 } void postorder(treenode* root) // 이진트리에대한후위순회연산 39 { 40 if(root){ 41 postorder(root->left); 42 postorder(root->right); 43 printf("%c", root->data); 44 } 45 } 46 51/104
52 4. 이진트리의순회 : [ 예제 8-1] 47 void main() 48 { 49 treenode* n7 = makerootnode('d', NULL, NULL); 50 treenode* n6 = makerootnode('c', NULL, NULL); 51 treenode* n5 = makerootnode('b', NULL, NULL); 52 treenode* n4 = makerootnode('a', NULL, NULL); 53 treenode* n3 = makerootnode('/', n6, n7); 54 treenode* n2 = makerootnode('*', n4, n5); 55 treenode* n1 = makerootnode('-', n2, n3); printf("\n preorder : "); 58 preorder(n1); printf("\n inorder : "); 61 inorder(n1); printf("\n postorder : "); 64 postorder(n1); getchar(); 67 } 52/104
53 4. 이진트리의순회 : [ 예제 8-2] 폴더계산 C 프로그램 컴퓨터의폴더구조가이진트리구조인경우에이진트리순회를응용하여폴더의용량을계산하는프로그램 폴더의이진트리구조 53/104
54 4. 이진트리의순회 : [ 예제 8-2] 하위폴더의용량을계산하여상위폴더의용량과더해서전체용량을계산해야하므로후위순회를이용 프로그램폴더의전체용량 = 프로그램폴더 (2M) + 하위폴더의용량 {C 프로그램폴더 (200M) + Java 프로그램폴더 (100M)} = 302M C:\ 의전체용량 = C:\ 의용량 (0M) + 하위폴더의용량 { 프로그램폴더의전체용량 (302M) + 자료폴더 (15M)} = 317M 그림폴더의전체용량 = 그림폴더 (68M) + 하위폴더의용량 { 사진폴더 (55M) + 동영상폴더 (120M)} = 243M D:\ 의전체용량 = D:\ 의용량 (10M) + 하위폴더의용량 { 음악폴더의용량 (40M) + 그림폴더의전체용량 (243M)} = 293M 내컴퓨터의전체용량 = 내컴퓨터의용량 (0M) + 하위폴더의용량 {C:\ 폴더의전체용량 (317M) + D:\ 폴더의전체용량 (293M)} = 610M 54/104
55 4. 이진트리의순회 : [ 예제 8-2] 01 #include <stdio.h> 02 #include <stdlib.h> 03 #include <memory.h> typedef struct treenode{ // 트리의노드구조정의 06 int size; // 데이터필드 07 struct treenode *left; // 왼쪽서브트리에대한링크필드 08 struct treenode *right; // 오른쪽서브트리에대한링크필드 09 } treenode; int FolderSize=0; 12 // size 를루트노드의데이터필드로하여왼쪽서브트리와오른쪽서브트리를 // 연결하는연산 13 treenode* makerootnode(int size, treenode* leftnode,treenode* rightnode) 14 { 15 treenode* root = (treenode *)malloc(sizeof(treenode)); 16 root->size = size; 17 root->left = leftnode; 18 root->right = rightnode; 19 return root; 20 } 55/104
56 4. 이진트리의순회 : [ 예제 8-2] 21 // 각폴더의크기계산을위한후위순회연산 22 int postorder_foldersize(treenode* root) 23 { 24 if(root){ 25 postorder_foldersize(root->left); 26 postorder_foldersize(root->right); 27 FolderSize += root ->size; 28 } 29 return FolderSize; 30 } 31 56/104
57 4. 이진트리의순회 : [ 예제 8-2] 32 void main() 33 { 34 treenode* F11 = makerootnode(120, NULL, NULL); 35 treenode* F10 = makerootnode(55, NULL, NULL); 36 treenode* F9 = makerootnode(100, NULL, NULL); 37 treenode* F8 = makerootnode(200, NULL, NULL); 38 treenode* F7 = makerootnode(68, F10, F11); 39 treenode* F6 = makerootnode(40, NULL, NULL); 40 treenode* F5 = makerootnode(15, NULL, NULL); 41 treenode* F4 = makerootnode(2, F8, F9); 42 treenode* F3 = makerootnode(10, F6, F7); 43 treenode* F2 = makerootnode(0, F4, F5); 44 treenode* F1 = makerootnode(0, F2, F3); printf("\n C:\\ 의용량 : %d M \n", postorder_foldersize(f2)); FolderSize=0; 49 printf("\n D:\\ 의용량 : %d M \n", postorder_foldersize(f3)); FolderSize=0; 52 printf("\n 내컴퓨터의전체용량 : %d M \n", postorder_foldersize(f1)); getchar(); 55 } 57/104
58 4. 이진트리의순회 : [ 예제 8-2] 실행결과 > 58/104
59 5. 이진탐색트리 이진탐색트리 (binary search tree) 이진트리에탐색을위한조건을추가하여정의한자료구조 이진탐색트리의정의 ⑴ 모든원소는서로다른유일한키를갖는다. ⑵ 왼쪽서브트리에있는원소의키들은그루트의키보다작다. ⑶ 오른쪽서브트리에있는원소의키들은그루트의키보다크다. ⑷ 왼쪽서브트리와오른쪽서브트리도이진탐색트리다. 59/104
60 5. 이진탐색트리 이진탐색트리의탐색연산 루트에서시작한다. 탐색할킷값 x를루트노드의킷값과비교한다. ( 킷값 x = 루트노드의킷값 ) 인경우 : 원하는원소를찾았으므로탐색연산성공 ( 킷값 x < 루트노드의킷값 ) 인경우 : 루트노드의왼쪽서브트리에대해서탐색연산수행 ( 킷값 x > 루트노드의킷값 ) 인경우 : 루트노드의오른쪽서브트리에대해서탐색연산수행 서브트리에대해서순환적으로탐색연산을반복한다. 60/104
61 5. 이진탐색트리 탐색연산알고리즘 61/104
62 5. 이진탐색트리 탐색연산예 ) 원소 11 탐색하기 1 찾는킷값 11 을루트노드의킷값 8 과비교 ( 찾는킷값 11 > 노드의킷값 8) 이므로오른쪽서브트리를탐색 2 ( 찾는킷값 11 > 노드의킷값 10) 이므로, 다시오른쪽서브트리를탐색 3 ( 찾는킷값 11 < 노드의킷값 14) 이므로, 왼쪽서브트리를탐색 4 ( 찾는킷값 11 = 노드의킷값 11) 이므로, 탐색성공! ( 연산종료 ) 62/104
63 5. 이진탐색트리 이진탐색트리의삽입연산 1) 먼저탐색연산을수행 삽입할원소와같은원소가트리에있으면삽입할수없으므로, 같은원소가트리에있는지탐색하여확인한다. 탐색에서탐색실패가결정되는위치가삽입위치가된다. 2) 탐색실패한위치에원소를삽입한다. 63/104
64 5. 이진탐색트리 이진탐색트리에서의 삽입할자리탐색 삽입할노드만들기 탐색한자리에노드연결 64/104
65 5. 이진탐색트리 이진탐색트리에서의삽입연산예 ) 원소 4 삽입하기 1 찾는킷값 4 를루트노드의킷값 8 과비교하여, ( 찾는킷값 4 < 노드의킷값 8) 이므로, 왼쪽서브트리를탐색한다. 2 ( 찾는킷값 4 > 노드의킷값 3) 이므로, 오른쪽서브트리를탐색한다. 3 ( 찾는킷값 4 < 노드의킷값 5) 이므로, 왼쪽서브트리를탐색해야하는데왼쪽자식노드가없으므로탐색실패! 이때, 탐색실패가결정된위치즉, 왼쪽자식노드의위치가삽입위치가된다. 4 탐색작업으로찾은자리즉, 노드 5 의왼쪽자식노드자리에노드 4 를삽입한다. 65/104
66 5. 이진탐색트리 단순연결리스트로표현한이진트리에서의원소 4 삽입하기 q q 탐색실패! q 66/104
67 5. 이진탐색트리 이진탐색트리의삭제연산 1) 먼저탐색연산을수행 삭제할노드의위치를알아야하므로트리를탐색한다. 2) 탐색하여찾은노드를삭제한다. 노드의삭제후에도이진탐색트리를유지해야하므로삭제노드의경우에대한후속처리 ( 이진탐색트리의재구성작업 ) 가필요하다. 삭제할노드의경우 삭제할노드가단말노드인경우 : 차수가 0 인경우 삭제할노드가하나의자식노드를가진경우 : 차수가 1 인경우 삭제할노드가두개의자식노드를가진경우 : 차수가 2 인경우 67/104
68 5. 이진탐색트리 단말노드의삭제연산 노드 4 를삭제하는경우 68/104
69 5. 이진탐색트리 노드 4 를삭제하는경우에대한단순연결리스트표현 노드를삭제하고, 삭제한노드의부모노드의링크필드에 null 설정 69/104
70 5. 이진탐색트리 자식노드가하나인노드, 즉차수가 1 인노드의삭제연산 노드를삭제하면, 자식노드는트리에서연결이끊어져서고아가된다. 후속처리 : 이진탐색트리의재구성 삭제한부모노드의자리를자식노드에게물려준다. 예 ) 노드 10 을삭제하는경우 탐색시작 > = 10 자식노드이동 14 1 단계 : 삭제할노드탐색 2 단계 : 탐색한노드삭제 3 단계 : 후속처리 /104
71 5. 이진탐색트리 예 ) 노드 10 을삭제하는경우 71/104
72 5. 이진탐색트리 노드 10 을삭제하는경우에대한단순연결리스트표현 72/104
73 5. 이진탐색트리 자식노드가둘인노드, 즉차수가 2 인노드의삭제연산 노드를삭제하면, 자식노드들은트리에서연결이끊어져서고아가된다. 후속처리 : 이진탐색트리의재구성 삭제한노드의자리를자손노드들중에서선택한후계자에게물려준다. 후계자선택방법방법 1) 왼쪽서브트리에서가장큰자손노드선택 왼쪽서브트리의오른쪽링크를따라계속이동하여오른쪽링크필드가 NULL 인노 드즉, 가장오른쪽에있는노드가후계자가된다. 방법 2) 오른쪽서브트리에서가장작은자손노드선택 오른쪽서브트리에서왼쪽링크를따라계속이동하여왼쪽링크필드가 NULL 인노 드즉, 가장왼쪽에있는노드가후계자가된다. 73/104
74 5. 이진탐색트리 삭제한노드의자리를물려받을수있는후계자노드 74/104
75 5. 이진탐색트리 예 ) 노드 8 을삭제하는경우 75/104
76 5. 이진탐색트리 노드 5 를후계자로선택한경우 1 후계자노드 5 를원래자리에서삭제하여, 삭제노드 8 의자리를물려준다. 2 후계자노드 5 의원래자리는자식노드 4 에게물려주어이진탐색트리를재구성한다. ( 자식노드가하나인노드삭제연산의후속처리수행!) 노드 10 을후계자로선택한경우 1 후계자노드 10 을원래자리에서삭제하여, 삭제노드 8 의자리를물려준다. 2 후계자노드 10 의원래자리는자식노드 14 에게물려주어이진탐색트리를재구성한다. ( 자식노드가하나인노드삭제연산의후속처리수행!) 76/104
77 5. 이진탐색트리 노드 5 를후계자로선택한경우 1 단계 : 노드삭제 노드삭제 8 2 단계 : 삭제한노드의자리를후계자에게물려주기 3 단계 : 후계자노드의원래자리를자식노드에게물려주기 /104
78 5. 이진탐색트리 노드 8 을후계자로선택한경우 1 단계 : 노드삭제 노드삭제 8 2 단계 : 삭제한노드의자리를후계자에게물려주기 3 단계 : 후계자노드의원래자리를자식노드에게물려주기 /104
79 5. 이진탐색트리 이진탐색트리에서의삭제연산알고리즘 79/104
80 5. 이진탐색트리 이진탐색트리에서의삭제연산알고리즘 80/104
81 5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 연결자료구조를이용한이진탐색의 C 프로그램 이진탐색트리를단순연결리스트로구현하고, 탐색연산을수행하는프로그램 실행결과 > 81/104
82 5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 001 #include<stdio.h> 002 #include<stdlib.h> typedef struct treenode { 005 char key; // 데이터필드 006 struct treenode* left; // 왼쪽서브트리링크필드 007 struct treenode* right; // 오른쪽서브트리링크필드 008 } treenode; typedef char element; // char을이진탐색트리 element의자료형으로정의 treenode* insertnode(treenode *p, char x) 013 { // 포인터 p가가리키는노드와비교하여노드 x를삽입하는연산 014 treenode *newnode; 015 if (p == NULL){ 016 newnode = (treenode*)malloc(sizeof(treenode)); 017 newnode->key = x; 018 newnode->left = NULL; 019 newnode->right = NULL; 020 return newnode; 021 } 022 else if (x < p->key) p->left = insertnode(p->left, x); 023 else if (x > p->key) p->right = insertnode(p->right, x); 024 else printf("\n 이미같은키가있습니다! \n"); return p; 027 } 82/104
83 5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 029 void deletenode(treenode *root, element key) 030 { // root 노드부터탐색하여 key 값과같은노드를찾아삭제하는연산 031 treenode *parent, *p, *succ, *succ_parent; 032 treenode *child; parent=null; 035 p=root; 036 while((p!= NULL) && (p->key!= key)){ // 삭제할노드의위치탐색 037 parent=p; 038 if(key < p->key) p=p->left; 039 else p=p->right; 040 } 041 if(p == NULL){ // 삭제할노드가없는경우 042 printf("\n 찾는키가이진트리에없습니다!!"); 043 return; 044 } // 삭제할노드가단말노드인경우 047 if((p->left == NULL) && (p->right == NULL)){ 048 if(parent!= NULL){ 049 if(parent->left == p) parent->left=null; 050 else parent->right=null; 051 } 052 else root=null; 053 } /104
84 5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 055 // 삭제할노드가한개의자식노드를가진경우 056 else if((p->left == NULL) (p->right == NULL)){ 057 if(p->left!= NULL) child=p->left; 058 else child=p->right; if(parent!= NULL){ 061 if(parent->left == p) parent->left=child; 062 else parent->right=child; 063 } 064 else root=child; 065 } // 삭제할노드가두개의자식노드를가진경우 068 else{ 069 succ_parent=p; 070 succ=p->left; 071 while(succ->right!= NULL){ 072 succ_parent=succ; 073 succ=succ->right; 074 } 075 if(succ_parent->left == succ) succ_parent->left=succ->left; 076 else succ_parent->right=succ->left; 077 p->key=succ->key; 078 p=succ; 079 } 080 free(p); 081 } /104
85 5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 083 treenode* searchbst(treenode* root, char x) 084 { // 이진탐색트리에서키값이 x인노드의위치를탐색하는연산 085 treenode* p; 086 p = root; 087 while (p!= NULL){ 088 if (x < p->key) p = p->left; 089 else if (x == p->key) return p; 090 else p = p->right; 091 } 092 printf("\n 찾는키가없습니다!"); 093 return p; 094 } void displayinorder(treenode* root) 097 { // 이진탐색트리를중위순회하면서출력하는연산 098 if(root){ 099 displayinorder(root->left); 100 printf("%c_", root->key); 101 displayinorder(root->right); 102 } 103 } void menu() 106 { 107 printf("\n* *"); 108 printf("\n\t1 : 트리출력 "); 109 printf("\n\t2 : 문자삽입 ); 85/104
86 5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 110 printf("\n\t3 : 문자삭제 "); 111 printf("\n\t4 : 문자검색 "); 112 printf("\n\t5 : 종료 "); 113 printf("\n* *"); 114 printf("\n메뉴입력 >> "); 115 } int main() 118 { 119 treenode* root = NULL; 120 treenode* foundednode = NULL; 121 char choice, key; root=insertnode(root, 'G'); // 트리만들기 124 insertnode(root, 'I'); 125 insertnode(root, 'H'); 126 insertnode(root, 'D'); 127 insertnode(root, 'B'); 128 insertnode(root, 'M'); 129 insertnode(root, 'N'); 130 insertnode(root, 'A'); 131 insertnode(root, 'J'); 132 insertnode(root, 'E'); 133 insertnode(root, 'Q'); while(1){ 136 menu(); 137 choice = getchar(); getchar(); 86/104
87 5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 139 switch(choice){ 140 case 1 : printf("\t[ 이진트리출력 ] "); 141 displayinorder(root); printf("\n"); 142 break; case 2 : printf(" 삽입할문자를입력하세요 : "); 145 key = getchar(); getchar(); 146 insertnode(root, key); 147 break; case 3 : printf(" 삭제할문자를입력하세요 : "); 150 key = getchar(); getchar(); 151 deletenode(root, key); 152 break; case 4 : printf(" 찾을문자를입력하세요 : "); 155 key = getchar(); getchar(); 156 foundednode = searchbst(root, key); 157 if (foundednode!= NULL) 158 printf("\n %c 를찾았습니다! \n", foundednode->key); 159 else printf("\n 문자를찾지못했습니다. \n"); 160 break; case 5 : return 0; 163 default : printf(" 없는메뉴입니다. 메뉴를다시선택하세요! \n"); 164 break; 165 } 166 } 167 } 87/104
88 6. 히프 히프 (heap) 완전이진트리에있는노드중에서킷값이가장큰노드나킷값이가장작은노드를찾기위해서만든자료구조 최대히프 (max heap) 킷값이가장큰노드를찾기위한완전이진트리 { 부모노드의킷값 자식노드의킷값 } 루트노드 : 킷값이가장큰노드 최소히프 (min heap) 킷값이가장작은노드를찾기위한완전이진트리 { 부모노드의킷값 자식노드의킷값 } 루트노드 : 킷값이가장작은노드 88/104
89 6. 히프 히프의예 89/104
90 6. 히프 히프가아닌이진트리의예 90/104
91 6. 히프 히프의추상자료형 ADT Heap 데이터 : n개의원소로구성된완전이진트리로서각노드의킷값은그의자식노드의킷값보다크거나같다. ( 부모노드의킷값 자식노드의킷값 ) 연산 : heap Heap; item Element; createheap() = create an empty heap; // 공백히프의생성연산 isempty(heap) = if (heap is empty) then return true; else return false; // 히프가공백인지를검사하는연산 insertheap(heap, item) = insert item into heap; // 히프의적당한위치에원소 (item) 를삽입하는연산 deleteheap(heap) = if (isempty(heap)) then return error; else { item 히프에서가장큰원소 ; remove { 히프에서가장큰원소 }; return item; } // 히프에서킷값이가장큰원소를삭제하고반환하는연산 End Heap() 91/104
92 6. 히프 히프에서의삽입연산 1 단계 : 완전이진트리를유지하면서확장한노드에삽입할원소를임시저장 노드가 n 개인완전이진트리에서다음노드의확장자리는 n+1 번의노드가된다. n+1 번자리에노드를확장하고, 그자리에삽입할원소를임시저장한다. 2 단계 : 만들어진완전이진트리내에서삽입원소의제자리를찾는다. 현재위치에서부모노드와비교하여크기관계를확인한다. { 현재부모노드의킷값 삽입원소의킷값 } 의관계가성립하지않으면, 현재부모노드의원소와삽입원소의자리를서로바꾼다. 92/104
93 6. 히프 히프에서의삽입연산예 1) 17 을삽입하는경우 노드를확장하여임시로저장한위치에서의부모노드와크기를비교하여히프의크기관계가성립하므로, 현재위치를삽입원소의자리로확정 93/104
94 6. 히프 히프에서의삽입연산예 2) 23 을삽입하는경우 94/104
95 6. 히프 히프에서의삽입연산알고리즘 95/104
96 6. 히프 1 현재히프의크기를하나증가시켜서노드위치를확장하고, 확장한노드번호가현재의삽입위치 i 가된다. 2 삽입할원소 item 과부모노드 heap[ i/2 ] 를비교하여 item 이부모노드보다작거나같으면현재의삽입위치 i 를삽입원소의위치로확정한다. 3 만약삽입할원소 item 이부모노드보다크면, 부모노드와자식노드의자리를바꾸어최대히프의관계를만들어야하므로부모노드 heap[ i/2 ] 를현재의삽입위치 heap[i] 에저장하고, 4 i/2 를삽입위치 i 로하여, 2~4 를반복하면서 item 을삽입할위치를찾는다. 5 찾은위치에삽입할노드 item 을저장하면, 최대히프의재구성작업이완성되므로삽입연산을종료한다. 96/104
97 6. 히프 히프에서의삭제연산 히프에서는루트노드의원소만을삭제할수있다. 1단계 : 루트노드의원소를삭제하여반환한다. 2 단계 : 원소의개수가 n-1 개로줄었으므로, 노드의수가 n-1 인완전이진트리로조정한다. 노드가 n 개인완전이진트리에서노드수 n-1 개의완전이진트리가되기위해서마지막노드, 즉 n 번노드를삭제한다. 삭제된 n 번노드에있던원소는비어있는루트노드에임시저장한다. 3 단계 : 완전이진트리내에서루트에임시저장된원소의제자리를 찾는다. 현재위치에서자식노드와비교하여크기관계를확인한다. { 임시저장원소의킷값 현재자식노드의킷값 } 의관계가성립하지않으면, 현재자식노드의원소와임시저장원소의자리를서로바꾼다. 97/104
98 6. 히프 히프에서의삭제연산예 98/104
99 6. 히프 히프에서의삭제연산알고리즘 99/104
100 6. 히프 히프에서의삭제연산알고리즘 1 루트노드 heap[1] 을변수 item 에저장하고, 2 마지막노드의원소 heap[n] 을변수 temp 에임시저장한후에, 3 마지막노드를삭제하고히프배열의원소개수를하나감소한다. 4 마지막노드의원소였던 temp 의임시저장위치 i 는루트노드의자리인 1 번이된다. 5 현재저장위치에서왼쪽자식노드 heap[j] 와오른쪽자식노드 heap[j+1] 이있을때, 둘중에서킷값이큰자식노드의킷값과 temp 를비교하여, temp 가크거나같으면현재위치가 temp 의자리로확정된다. 6 만약 temp 가자식노드보다작으면, 자식노드와자리를바꾸고다시 5~ 6 을반복하면서 temp 의자리를찾는다. 7 찾은위치에 temp 를저장하여최대히프의재구성작업을완성하고 8 루트노드를저장한 item 을반환하는것으로삭제연산을종료한다. 100/104
101 6. 히프 순차자료구조를이용한히프의구현 부모노드와자식노드를찾기쉬운 1 차원배열의순차자료구조이용 1 차원배열을이용한히프의표현예 101/104
![6. 히프 : [ 예제 8-4] 순차자료구조를이용한히프프로그램 순차자료구조를이용한히프 C 프로그램 공백히프에원소 10, 45, 19, 11, 96 을차례로삽입하면서최대히프를구성하고,](/docs-images/100/143848124/images/102-1.jpg "삭제연산을수행하여삭제된원소를출력하는프로그램 최대히프의루트노드는히프에서가장큰노드가되므로, 원소개수만큼 삭제연산을수행하면서출력하면큰값부터작은값의내림차순으로출력 되는것을확인할수있다.")
102 6. 히프 : [ 예제 8-4] 순차자료구조를이용한히프프로그램 순차자료구조를이용한히프 C 프로그램 공백히프에원소 10, 45, 19, 11, 96 을차례로삽입하면서최대히프를구성하고, 삭제연산을수행하여삭제된원소를출력하는프로그램 최대히프의루트노드는히프에서가장큰노드가되므로, 원소개수만큼 삭제연산을수행하면서출력하면큰값부터작은값의내림차순으로출력 되는것을확인할수있다. 실행결과 > 102/104
103 6. 히프 : [ 예제 8-4] 순차자료구조를이용한히프프로그램 01 #include <stdio.h> 02 #include <stdlib.h> 03 #define MAX_ELEMENT typedef struct { // 히프에대한 1 차원배열과히프원소의갯수를구조체로묶어서선언 05 int heap[max_element]; 06 int heap_size; 07 } heaptype; heaptype* createheap() // 공백히프를생성하는연산 10 { 11 heaptype *h = (heaptype *)malloc(sizeof(heaptype)); 12 h->heap_size=0; 13 return h; 14 } void insertheap(heaptype *h, int item) // 히프에 item 을삽입하는연산 17 { 18 int i; 19 h->heap_size = h->heap_size +1; 20 i = h->heap_size; 21 while((i!=1) && (item > h->heap[i/2])){ 22 h->heap[i] = h->heap[i/2]; 23 i/=2; 24 } 25 h->heap[i] = item; 26 } 103/104
104 6. 히프 : [ 예제 8-4] 순차자료구조를이용한히프프로그램 28 int deleteheap(heaptype *h) // 히프의루트를삭제하여반환하는연산 29 { 30 int parent, child; 31 int item, temp; 32 item = h->heap[1]; 33 temp = h->heap[h->heap_size]; 34 h->heap_size = h->heap_size -1; 35 parent = 1; 36 child = 2; 37 while(child <= h->heap_size) { 38 if((child < h->heap_size) && (h->heap[child]) < h->heap[child+1]) 39 child++; 40 if (temp >= h->heap[child]) break; 41 else { 42 h->heap[parent] = h->heap[child]; 43 parent = child; 44 child = child*2; 45 } 46 } 47 h->heap[parent] = temp; 48 return item; 49 } printheap(heaptype *h) // 1차원배열히프의내용을출력하는연산 52 { 53 int i; 54 printf("heap : "); 104/104
105 6. 히프 : [ 예제 8-4] 순차자료구조를이용한히프프로그램 55 for(i=1; i<= h->heap_size; i++) 56 printf("[%d] ", h->heap[i]); 57 } void main() 60 { 61 int i, n, item; 62 heaptype *heap = createheap(); 63 insertheap(heap, 10); 64 insertheap(heap, 45); 65 insertheap(heap, 19); 66 insertheap(heap, 11); 67 insertheap(heap, 96); printheap(heap); n= heap->heap_size; 72 for(i=1; i<=n; i++){ 73 item = deleteheap(heap); 74 printf("\n delete : [%d] ", item); 75 } getchar(); 78 } 105/104
106 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 )
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. 부-노드,
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 를가리키도록변경
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
7장
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트
슬라이드 1
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드
08장.트리
---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조
슬라이드 1
CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소
슬라이드 1
Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음
슬라이드 1
Data Structure Chapter 7. 트리 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 트리의개념 트리 (Tree) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 정의 (1) 하나의루트 (root) 노드 (2) 다수의서브트리 (subtree) 트리는부모-자식관계의노드들로이루어짐
슬라이드 1
CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터
Microsoft PowerPoint - chap10_tree
Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-
슬라이드 1
CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산
Microsoft PowerPoint - lec07_tree [호환 모드]
![Microsoft PowerPoint - lec07_tree [호환 모드]](/thumbs/82/84829941.jpg "Microsoft PowerPoint - lec07_tree [호환 모드]")
Tree 2008학년도 2학기 kkman@sangji.ac.krac kr -1- 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2- 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만
입학사정관제도
자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)
Ch.1 Introduction
Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?
05_tree
Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical
제 11 장 다원 탐색 트리
제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다.
슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)
슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템
Microsoft PowerPoint - 제8장-트리.pptx
제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,
제 1 장 기본 개념
이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)
Microsoft PowerPoint - 자료구조2008Chap07
제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint
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
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 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조.
06장.리스트
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :
Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74
큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조
11장 포인터
Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함
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
Lab 3. 실습문제 (Single linked list)_해답.hwp
Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.
슬라이드 1
6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,
<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>
연결자료구조 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 내용 배열연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다.
Lab 4. 실습문제 (Circular singly linked list)_해답.hwp
Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular
Chapter 08. 트리(Tree)
윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예
이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2
제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.
Algorithms
자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 선형리스트 연결리스트 2 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것
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
리스트 (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 한글자음의모임 : (
1장. 리스트
01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef
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 노드 : 정보항목 + 다른노드로뻗어진가지
Microsoft PowerPoint - Chap5 [호환 모드]
![Microsoft PowerPoint - Chap5 [호환 모드]](/thumbs/98/135324412.jpg "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
슬라이드 1
CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element
정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2
13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우
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
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 관계성립
1장. 리스트
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential
Microsoft PowerPoint - 제9장-트리의응용.pptx
제 9 강의. 트리의탐색 1. 이진트리탐색알고리즘 2. 쓰레드 (Threaded) 이진트리 3. 이진트리를다루는알고리즘 1 1. 이진트리탐색알고리즘 트리의탐색 (traversal) 은트리의각노드를방문하는작업을말한다. ( 왜방문할까요?) 다음과같은방법들을생각해볼수있다. 방법 1) 레벨순 : 레벨이낮은순으로방문 A B C D E F G H 3가지다른방법이나올수있다.
Microsoft PowerPoint - 6장 탐색.pptx
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential
ABC 10장
10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;
<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >
제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다
원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를
리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은
학습목차 2.1 다차원배열이란 차원배열의주소와값의참조
- Part2- 제 2 장다차원배열이란무엇인가 학습목차 2.1 다차원배열이란 2. 2 2 차원배열의주소와값의참조 2.1 다차원배열이란 2.1 다차원배열이란 (1/14) 다차원배열 : 2 차원이상의배열을의미 1 차원배열과다차원배열의비교 1 차원배열 int array [12] 행 2 차원배열 int array [4][3] 행 열 3 차원배열 int array [2][2][3]
Microsoft PowerPoint - ch07 - 포인터 pm0415
2015-1 프로그래밍언어 7. 포인터 (Pointer), 동적메모리할당 2015 년 4 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline 포인터 (pointer) 란? 간접참조연산자
<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>
한국방송통신대학교컴퓨터과학과 2 학년자료구조 제 1 장기본개념 자료와정보 3 알고리즘 4 자료 data : 현실세계에서관찰이나측정을통해수집된값 value 이나사실 fact 특정한일을수행하는명령어들의유한집합 정보 information : 자료를처리 / 추출 process 해서얻어진유용한결과 입 출 력 : 외부에서제공되는자료가있을수있다력 : 적어도한가지결과를생성한다
<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
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
PowerPoint 프레젠테이션
10 장. 트리 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색,
5 장 트 리
5 장 트리 Copyright 2007 DBLAB, Seoul National University 트리구조 Copyright 2007 DBLAB, Seoul National University 2 트리 트리 : 하나이상의노드 (node) 로이루어진유한집합 1 하나의루트 (root) 노드 2 나머지노드들은 n( 0) 개의분리집합 T 1, T 2,, T n 으로분할
PowerPoint 프레젠테이션
C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];
슬라이드 1
-Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역
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,
Lab 5. 실습문제 (Double linked list)-1_해답.hwp
Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.
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) 동일한타입의데이터가여러개저장되어있는저장장소
Microsoft PowerPoint - 07-chap05-Stack.ppt
/ 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감.
q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2
연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조 q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입
03장.스택.key
---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1 ? (stack): (LIFO:Last-In First-Out) 2 : top : ( index -1 ),,, 3 : ( ) ( ) -> ->. ->.... 4 Stack ADT : (LIFO) : init():. is_empty():
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 학습목표 포인터를 사용하는 다양한 방법에
슬라이드 1
CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element
03장.스택
---------------- DT STRUCTURES USING C ---------------- CHPTER 스택 1/30 스택이란? 스택 (stack): 쌓아놓은더미 후입선출 (LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감 2/30 스택의구조 스택상단 : top 스택하단 : 불필요 요소, 항목 공백상태, 포화상태 삽입, 삭제연산
PowerPoint 프레젠테이션
트리 10 장. 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색,
슬라이드 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) : 스택에서입출력이이루어지는부분
Chapter 4. LISTS
연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는
o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -
스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입
<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>
쉽게풀어쓴 C 언어 Express 제 17 장동적메모리와연결리스트 이번장에서학습할내용 동적메모리할당의이해 동적메모리할당관련함수 연결리스트 동적메모리할당에대한개념을이해하고응용으로연결리스트를학습합니다. 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것
슬라이드 제목 없음
Chapter 5: TREES Trees Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each
<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>
연습문제해답 5 4 3 2 1 0 함수의반환값 =15 5 4 3 2 1 0 함수의반환값 =95 10 7 4 1-2 함수의반환값 =3 1 2 3 4 5 연습문제해답 1. C 언어에서의배열에대하여다음중맞는것은? (1) 3차원이상의배열은불가능하다. (2) 배열의이름은포인터와같은역할을한다. (3) 배열의인덱스는 1에서부터시작한다. (4) 선언한다음, 실행도중에배열의크기를변경하는것이가능하다.
Microsoft PowerPoint - 08-Queue.ppt
Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In
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 큐의개념및추상데이터타입에대한이해
제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.
제 11 장포인터 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습합니다.
Microsoft PowerPoint - Chap5 [호환 모드]
![Microsoft PowerPoint - Chap5 [호환 모드]](/thumbs/83/87488276.jpg "Microsoft PowerPoint - Chap5 [호환 모드]")
5.3 Binary Tree Traversal Tree 의각 node 를한번씩방문하는알고리즘 각 node 와그 node 의 subtree 들을동등하게취급하면 6 개의 traversal 조합이있다. (L: Left 로움직임, V: 노드를 visiting, R: Right 로움직임 ) (1) LVR, (2) LRV, (3) VLR, (4) VRL, (5) RVL,
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 #define _CRT_SECURE_NO_WARNINGS #include #include main() { char ch; printf(" 문자 1개를입력하시오 : "); scanf("%c", &ch); if (isalpha(ch))
<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>
#include "stdafx.h" #include "Huffman.h" 1 /* 비트의부분을뽑아내는함수 */ unsigned HF::bits(unsigned x, int k, int j) return (x >> k) & ~(~0
OCW_C언어 기초
초보프로그래머를위한 C 언어기초 4 장 : 연산자 2012 년 이은주 학습목표 수식의개념과연산자및피연산자에대한학습 C 의알아보기 연산자의우선순위와결합방향에대하여알아보기 2 목차 연산자의기본개념 수식 연산자와피연산자 산술연산자 / 증감연산자 관계연산자 / 논리연산자 비트연산자 / 대입연산자연산자의우선순위와결합방향 조건연산자 / 형변환연산자 연산자의우선순위 연산자의결합방향
비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2
비트연산자 1 1 비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 진수법! 2, 10, 16, 8! 2 : 0~1 ( )! 10 : 0~9 ( )! 16 : 0~9, 9 a, b,
리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센
Linked List 2014 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트
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]
슬라이드 1
Linked List 2015 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트
슬라이드 1
Data Structure Chapter 4. 리스트 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 리스트추상데이터타입 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 :
1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ
Linked List 2010 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트
리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li
Linked List 2011 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트
Microsoft PowerPoint - 제11장 포인터(강의)
쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조
untitled
if( ) ; if( sales > 2000 ) bonus = 200; if( score >= 60 ) printf(".\n"); if( height >= 130 && age >= 10 ) printf(".\n"); if ( temperature < 0 ) printf(".\n"); // printf(" %.\n \n", temperature); // if(
1장. 리스트
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 05. AVL 트리 06. B- 트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리,
Microsoft PowerPoint - chap4_list
Chap. 4 : 리스트 (list) 2007 학년도 2 학기 리스트 1. 리스트개념 ~ 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 ~ 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 ~ 요일 : ( 일요일, 월요일,, 토요일 ) ~ 한글자음의모임 : (ᆨ,ᆫ,,ᄒ) ~ 핸드폰의문자메시지리스트
02장.배열과 클래스
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 배열과구조체 1/20 많은자료의처리? 배열 (array), 구조체 (struct) 성적처리프로그램에서 45 명의성적을저장하는방법 주소록프로그램에서친구들의다양한정보 ( 이름, 전화번호, 주소, 이메일등 ) 를통합하여저장하는방법 홍길동 이름 :
슬라이드 1
CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임
Microsoft PowerPoint - chap-11.pptx
쉽게풀어쓴 C 언어 Express 제 11 장포인터 컴퓨터프로그래밍기초 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 컴퓨터프로그래밍기초 2 포인터란? 포인터 (pointer): 주소를가지고있는변수 컴퓨터프로그래밍기초 3 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다.
중간고사
중간고사 예제 1 사용자로부터받은두개의숫자 x, y 중에서큰수를찾는알고리즘을의사코드로작성하시오. Step 1: Input x, y Step 2: if (x > y) then MAX
슬라이드 1
CHAP 4 : 리스트 조영임 yicho@gachon.ac.kr 1 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item0, item1,..., itemn 1) 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace,
슬라이드 1
자료구조 (Data Structures), 4 장. 리스트 담당교수 : 조미경 이번장에서학습할내용 * 리스트란? * 배열로리스트구현 * 연결리스트로리스트구현 * 연결리스트종류 * 연결리스트응용 : 다항식구현 2/63 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L ( item 0,
슬라이드 1
CHAP 4: 리스트 리스트란? 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 : (Ace, 2,3,,King) 핸드폰의문자메시지리스트 L ( item0, item1,..., itemn 1) 리스트의연산