DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 5

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 5

C언어로 쉽게 풀어쓴 자료구조

8장 Exercise 문제다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.

<HeapTree.h>

#ifndef __HEAP_TREE_H__
#define __HEAP_TREE_H__
 
#define MAX_ELEMENT 200
 
typedef struct {
    int key;
} element;
typedef struct {
    element heap[MAX_ELEMENT];
    int size;
} HeapType;
 
void Init(HeapType* h);
 
void InsertMinHeap(HeapType* h, element item);
int DeleteMinHeap(HeapType* h);
int PrintMinHeap(HeapType* h);
 
void PrintHeap(HeapType* h);
 
#endif

<HeapTree.cpp>

#include <stdio.h>
#include <math.h>
#include "HeapTree.h"
 
void Init(HeapType* h)
{
    h->size = 0;
}
 
void InsertMinHeap(HeapType* h, element item)
{
    int i;
    i = ++(h->size);
 
    while ((i != 1) && item.key < h->heap[i / 2].key)
    {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = item;
}
 
int DeleteMinHeap(HeapType* h)
{
    int parent, child;
    element min, temp;
 
    min = h->heap[1];
    temp = h->heap[h->size--];
    parent = 1;
    child = 2;
 
    while (child <= h->size)
    {
        if ((child < h->size) && (h->heap[child].key) > h->heap[child + 1].key)
            child++;
        if (temp.key <= h->heap[child].key)
            break;
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    h->heap[parent] = temp;
    return min.key;
}
int PrintMinHeap(HeapType* h)
{
    return h->heap[1].key;
}
 
void PrintHeap(HeapType* h)
{
    for (int i = 1; i <= h->size; i++)
        printf("(%d) ", h->heap[i].key    );
    printf("\n");
}

<main.cpp>

#include <stdio.h>
#include "HeapTree.h"
 
int main(void)
{
    element e1 = { 10 }, e2 = { 5 }, e3 = { 30 }, e4 = { 25 }, e5 = { 45 }, e6 = { 27 };
    HeapType heap;
 
    Init(&heap);
 
    InsertMinHeap(&heap, e1);
    InsertMinHeap(&heap, e2);
    InsertMinHeap(&heap, e3);
    InsertMinHeap(&heap, e4);
    InsertMinHeap(&heap, e5);
    InsertMinHeap(&heap, e6);
    
    printf("<<최소 히프 출력(배열)>>\n");
    PrintHeap(&heap);
    printf("\n최소 히프 삭제 실행 : %d\n\n", DeleteMinHeap((&heap)));
    printf("<<최소 히프 출력(배열)>>\n");
    PrintHeap(&heap);
    printf("\n최소 히프 출력 : %d\n", PrintMinHeap(&heap));
}