자료구조 (26) 썸네일형 리스트형 병합 정렬 구현 (분열) #1 병합 정렬을 구현해 보자 병합 정렬의 개념은 다음과 같다. 1. 데이터를 쪼갤수 없을 때 까지 계속 쪼갠다. 2. 쪼개진 데이터를 병합하면서 정렬한다. 우선 1번 개념을 살펴 보자 데이터를 쪼갤 수 없을 떄 까지 쪼갠다는 것을 다음 그림을 보면 이해가 쉽다. 마지막 red box 를 보면 index 가 더이상 쪼개질 수 없을 만금 쪼개졌다 (배열에 오직 1개의 데이터만 있음) 위 처럼 쪼개는 코드를 구현 해보자 아래 그림과 같은 Parameter와 재귀 함수를 사용하면 쉽게 구현 할 수 있다. start Index : 배열의 시작 인덱스 Mid: 배열의 중간 인덱스 ((Start Index + End Index) / 2) End Index: 배열의 마지막 인덱스 start Index와 End Index는.. 힙(Heap)정렬 구현 Heap 정렬 구현은 쉽다. kjt9109.tistory.com/entry/%ED%9E%99%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-%EA%B5%AC%ED%98%84-1 힙(우선순위 큐) 구현 #1 힙 구현은 곧 우선순위 큐의 완성으로 이어진다. 일반적으로 큐는 FIFO 이다. 하지만 우선순위 큐의 OUT은 들어간 순서 상관 없이 우선순위에 따라 나온다. 힙(Heap)이란? 1. 힙은 '이진트리' 이되 '완 kjt9109.tistory.com 이전에 공부했던 힙을 살펴보면 힙에 데이터를 추가하여 완성 하였을 때 Root노드에는 우선순위가 가장 큰 데이터가 오게된다. 따라서 힙 구조에 Root 노드 데이터만 빼서 뺀 순서대로 정렬하면 데이터를 자연스럽게 정렬 된다.. 힙(우선순위 큐) 구현 #2 실행소스:github.com/KJT9109/Data_Structure/tree/master/Heap_ProrityQueue 앞서 설계한 구조를 가지고 설계를 해보자 우선 힙 구조체 선언은 다음과 같다. Heap Data Structure 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #define MAXIMUM_SIZE 255 typedef char HData; typedef int HNode; typedef HData (*HPriorityCompare)(HData, HData); typedef struct { int heapNode; HPriorityCompare HPriorityFunc; HData heapData[MAXIMUM_SIZE]; }HeapStruct; Colored.. 힙(우선순위 큐) 구현 #1 힙 구현은 곧 우선순위 큐의 완성으로 이어진다. 일반적으로 큐는 FIFO 이다. 하지만 우선순위 큐의 OUT은 들어간 순서 상관 없이 우선순위에 따라 나온다. 힙(Heap)이란? 1. 힙은 '이진트리' 이되 '완전 이진트리'이다 2. 모든 노드에 저장된 값은 자식 노드에 저장된 값도가 크거나 같아야한다. 3. 같은 노드 사이는 상관 없다. 힙은 최대 힙(Max Heap) 과 최소 힙(Min Heap)이 있는데 루트노드로 올라갈수록 저장된 값이 작아지면 최소 힙, 커지면 최대 힙이라고 한다. 힙에서 데이터 저장 과정 위 그림처럼 힙이 있다고 하자 여기에 9라는 데이터를 저장한다고 하면 일단 완전 이진트리를 만든다. 부모노드와 우선순위를 비교해서 높으면 부모노드와 바꿔 준다. 부모노드가 우선순위 클때까지 9.. 수식트리의 구현 #2 구현 코드 URL:github.com/KJT9109/Data_Structure 앞서 설명했던 부분을 코드로 구현해보자 후기표현법변환은 이전 Stack 공부 할때 설명했으므로 생략 후기표현법에서 수식트리로 변환하는 함수이다. PostfixToTree함수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 void PostfixToTree(BTreeNode *curNode, int *char_arr) { BTreeNode *changeN.. 수식트리의 구현 #1 공부한 이진트리로 수식트린을 구현해보자 앞서 공부했던 계산기에서 후위변환법을 가지고 온 다음 그 식을 가지고 TREE로 구현한다. 책에서는 다시 스택을 활용해서 만드는데 그냥 다 트리에 넣어서 만들어보았다. 트리로 변환 할 식 ->51-8/(3*4-4)-20 우선 위 식을 후위변환표현으로 변경한다. ->51 8 3 4 * 4 - / - 20 - 여기서 포인터는 마지막 연산자인 -를 가리키고 있다. 이제 트리에 다 집어 넣는다 트리에 집어 넣을 때 다음과 같은 규칙을 지키며 집어 넣는다. 1. 연산자가 나오면 왼쪽에 피 연산자가 나오면 오른쪽에 넣는다. 2. 피 연산자노드는 자식 노드를 생성 할 수 없다. 위 규칙을 지키며 트리를 만들면 다음과 같은 트리가 만들어진다. 51 8 3 4 * 4 - / - 2.. 이진트리 구현 열혈 C 자료구조를 통해 공부한 내용을 가지고 계산기를 이진트리를 직접 구현 해보자 CPU 입장에서는 이진트리나 양방향 리스트로 똑같은 거 같다. 노드: node 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 구성요소 간선: edge 노드와 노드를 연결하는 연결선 루트 노드: root node 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드: terminal node 아래로 또 다른 노드가 연결되어 있지 않은 D, E, F 내부 노드: internal node 단말 노드를 제외한 모든 노드로 A, B와 같은 노드 이진트리 구조체 typedef int BTData; typedef struct _bTreeNode { BTData data; struct _bTreeNode *lef.. Queue - LinkedList로 구현 Queue를 리스트로 구현해보자 다음과 같이 그림을 그린 후 코드로 구현했다. 초기화 코드 구현 typedef struct __LinkedList { int data; struct __LinkedList *next; }LinkedList; typedef struct __Queue { LinkedList *front; LinkedList *rear; LinkedList *body; } LQueue_Struct; void LQueue_init(LQueue_Struct *lqueue) { lqueue->body = (LinkedList*) malloc(sizeof(LinkedList)); lqueue->body->data = '\0'; lqueue->front = lqueue->body; lqueue->rea.. 이전 1 2 3 4 다음
