C Tutorial (배열이용 Heaptree)

HeapTree.c

 배열을 사용하여 Heap tree를 구현해 봅시다.
최대 Heap tree로 구현합니다.

/*==========================================================================================*/
                                                                                                                                                                        
/*                              §       Heap tree  §                                                                                                                            
                                                                                                                                                                                        */
/*              - 배열을 이용해 트리를 구현.
                - 최대히프 트리의 조건을 만족시키는 트리 구현. (최대트리+완전 트리)                                        */
/*               (최대 트리: 각 노드의 키 값이 그 자식의 키값보다 큰 트리)
                 (완전 트리: 마지막 레벨을 제외한 나머지 레벨이 꽉 차있는 트리)                                          */
/*                                                                                                                                                              
                                                                                                                                                                                        */      

/*==========================================================================================*/
#include<stdio.h>
#include<stdlib.h>

#define MAX_ELEMENTS 200                // 최대 히프 크기+1
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)
#define END 0
#define CONTINUE 1

typedef struct {
        int key;
} element;
element heap[MAX_ELEMENTS];


void heapsort(element list[MAX_ELEMENTS],int n);
void insert_max_heap(element item,int *n);
element delete_max_heap(int *n);
int find_heap(int item);
void adjust(element list[MAX_ELEMENTS],int root ,int n);


int main(void){
        int ch,c;
        int item,after;
        int n=0;
        int i=0;
        int k=CONTINUE;
        element temp; 
        puts(" ┌────────────────────────────────┐");
        puts(" │                                                                │");
        puts(" │       § Heap Tree Program §                                  │");
        puts(" │                                                                │");
        puts(" │      ▶ 원하는 메뉴를 입력하세요.                              │");
        puts(" │                                                                │");
        puts(" │      ▶ 1.삽입 2.삭제 3.변환 4.출력 5.종료                     │");
        puts(" │                                                                │");
        puts(" └────────────────────────────────┘");
        puts("");
        while(k!=END){
                printf("\n숫자를 입력하시오(1~5):");
                ch = c = 0;
                while((c=getchar())!='\n')
                        ch=c;
                switch(ch){
                case '1':                       //삽입
                        while(item!=EOF){
                                printf("힙 트리에 삽입할 데이터를 입력하시오.(종료:ctrl+z): ");
                                scanf("%d",&item);
                                temp->key=item;
                                insert_max_heap(temp,&n);
                        }
                        break;
                case '2':
                        printf("삭제되었습니다.: ");
                        delete_max_heap(&n);
                        break;
                
                case '3':
                        printf("변환할 데이터를 입력하시오.: ");
                        scanf("&d",&itemp);
                        printf("변환될 데이터를 입력하시오.: ");
                        scanf("&d",&after);
                        i=find_heap(item);
                        heap[i]->key=after;
                        heapsort(heap,n);
                        break;
                case '4':
                        for(i=1;i<=n;i++)
                                printf("%d ",list[i]->key);
                        break;
                case '5':
                        k=END;
                        printf("이용해 주셔서 감사합니다.");
                        break;
                }
                getchar();
        }
        return 0;
}

                        
                        
void heapsort(element list[MAX_ELEMENTS],int n)
{
        int i,j;
        element temp;
        for (i=n/2; i>0 ; i--)
                adjust(list,i,n);
        for (i=n-1;i>0;i--){
                temp=list[1];
                list[1]=list[i+1];
                list[i+1]=temp;
                adjust(list,1,i);
        }
}

int find_heap(int item)
{
        int i=1;
        while(i<=n)
        {
                if(heap[i].key==item)
                        break;
        }
        return i;
}

void adjust(element list[MAX_ELEMENTS],int root ,int n)
{
        int child, rootkey;
        element temp;
        temp=list[root];
        rootkey = list[root].key;
        child=2*root;
        while(child<=n){
                if((child < n) && (list[child].key < list[child+1].key))
                        child++;
                if(rootkey > list[child].key)
                        break;
                else
                {
                        list[child/2] = list[child];
                        child*=2;
                }
        }
        list[child/2]=temp;
}


void insert_max_heap(element item,int *n)
{
        /* n개의 원소를 갖는 최대 히프에 item을 삽입한다. */
        int i;
        if(HEAP_FULL(*n)){
                fprint(stderr, "The heap is full.\n");
                exit(1);
        }
        i = ++(*n);
        while( (i!=1) && (item.key > heap[i/2].key))
        {
                heap[i]=heap[i/2];
                i/=2;
        }
        heap[i]=item;
}


element delete_max_heap(int *n)
{
        int parent, child;
        element item, temp;
        if(HEAP_EMPTY(*n)){
                fprint(stderr, "The heap is empty.\n");
                exit(1);
        }
        /*가장 큰 값을 저장*/
        item= heap[1];
        /*히프를 재구성하기 위해 마지막 원소를 이용. */
        temp=heap[(*n)--];
        parent = 1;
        child = 2;
        while(child<=*n)
        {
                /*현  parent의 가장 큰 자식을 탐색 */
                if((child<*n) && (heap[child].key < heap[child+1].key))
                        child++;
                if(temp.key>=heap[child].key)
                        break;
                /*아래 단계로 이동.*/
                heap[parent] = heap[child];
                parent = child;
                child *= 2;
        }
        heap [parent] = temp;
        return item;
}

이 글은 스프링노트에서 작성되었습니다.