허프만 코드를 출력하는걸 문제로 주셨는데 출력까지는 했는데 작은순서대로 출력이안되요 <div><div>#include <stdio.h></div> <div>#include <stdlib.h></div> <div><br></div> <div>#define MAX_ELEMENT 100</div> <div><br></div> <div>typedef struct TreeNode{</div> <div><span style="white-space:pre;"> </span>int weight;</div> <div><span style="white-space:pre;"> </span>struct TreeNode *left_child;</div> <div><span style="white-space:pre;"> </span>struct TreeNode *right_child;</div> <div>} TreeNode;</div> <div>typedef struct{</div> <div><span style="white-space:pre;"> </span>TreeNode *ptree;</div> <div><span style="white-space:pre;"> </span>int key;</div> <div>} element;</div> <div>typedef struct{</div> <div><span style="white-space:pre;"> </span>element heap[MAX_ELEMENT];</div> <div><span style="white-space:pre;"> </span>int heap_size;</div> <div>}HeapType;</div> <div><br></div> <div><br></div> <div>//초기화 함수</div> <div>void init(HeapType *h){</div> <div><span style="white-space:pre;"> </span>h->heap_size=0;</div> <div>}</div> <div>// 노드 출력</div> <div>void print_tree(TreeNode *r, int n, char* code){</div> <div><span style="white-space:pre;"> </span>if(r){</div> <div><span style="white-space:pre;"> </span>n++;</div> <div><span style="white-space:pre;"> </span>code[n]='1';</div> <div><span style="white-space:pre;"> </span>print_tree(r->left_child,n,code);</div> <div><span style="white-space:pre;"> </span>code[n]='0';</div> <div><span style="white-space:pre;"> </span>print_tree(r->right_child,n,code);</div> <div><span style="white-space:pre;"> </span>code[n]='\0';</div> <div><span style="white-space:pre;"> </span>if(r->left_child==NULL || r->right_child == NULL)</div> <div><span style="white-space:pre;"> </span>printf("%d\t=%s\n",r->weight, code);</div> <div><span style="white-space:pre;"> </span>}</div> <div>}</div> <div>//삽입 함수</div> <div>void insert_min_heap(HeapType *h, element item){</div> <div><span style="white-space:pre;"> </span>int i;</div> <div><span style="white-space:pre;"> </span>i=++(h->heap_size);</div> <div><span style="white-space:pre;"> </span>//트리를 거슬러 올라가면서 부모 노드와 비교하는 과정</div> <div><span style="white-space:pre;"> </span>while((i!=1)&&(item.key < h->heap[i/2].key)){</div> <div><span style="white-space:pre;"> </span>h->heap[i] = h->heap[i/2];</div> <div><span style="white-space:pre;"> </span>i/=2;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>h->heap[i]=item; //새로운 노드 삽입</div> <div>}</div> <div>//삭제 함수</div> <div>element delete_min_heap(HeapType *h){</div> <div><span style="white-space:pre;"> </span>int parent, child;</div> <div><span style="white-space:pre;"> </span>element item, temp;</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>item=h->heap[1];</div> <div><span style="white-space:pre;"> </span>temp=h->heap[(h->heap_size)--];<span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>parent=1;</div> <div><span style="white-space:pre;"> </span>child=2;</div> <div><span style="white-space:pre;"> </span>while(child <= h->heap_size){</div> <div><span style="white-space:pre;"> </span>//현재 노드의 자식 노드 중 더 작은 자식 노드를 찾는다.</div> <div><span style="white-space:pre;"> </span>if((child < h->heap_size) && (h->heap[child].key) > h->heap[child+1].key)</div> <div><span style="white-space:pre;"> </span>child++;</div> <div><span style="white-space:pre;"> </span>if(temp.key <= h->heap[child].key) break;</div> <div><span style="white-space:pre;"> </span>//한단계 아래로 이동</div> <div><span style="white-space:pre;"> </span>h->heap[parent] = h->heap[child];</div> <div><span style="white-space:pre;"> </span>parent=child;</div> <div><span style="white-space:pre;"> </span>child*=2;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>h->heap[parent]=temp;</div> <div><span style="white-space:pre;"> </span>return item;</div> <div>}</div> <div>//이진 트리 생성 함수</div> <div>TreeNode *make_tree(TreeNode *left, TreeNode *right){</div> <div><span style="white-space:pre;"> </span>TreeNode *node=(TreeNode *)malloc(sizeof(TreeNode));</div> <div><span style="white-space:pre;"> </span>if(node==NULL){</div> <div><span style="white-space:pre;"> </span>fprintf(stderr,"메모리 에러\n");</div> <div><span style="white-space:pre;"> </span>exit(1);</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>node->left_child=left;</div> <div><span style="white-space:pre;"> </span>node->right_child=right;</div> <div><span style="white-space:pre;"> </span>return node;</div> <div>}</div> <div>//이진 트리 제거 함수</div> <div>void destroy_tree(TreeNode *root){</div> <div><span style="white-space:pre;"> </span>if(root==NULL) return;</div> <div><span style="white-space:pre;"> </span>destroy_tree(root->left_child);</div> <div><span style="white-space:pre;"> </span>destroy_tree(root->right_child);</div> <div><span style="white-space:pre;"> </span>free(root);</div> <div>}</div> <div>//허프만 코드 생성 함수</div> <div>void huffman_tree(int freq[], int n){</div> <div><span style="white-space:pre;"> </span>int i;</div> <div><span style="white-space:pre;"> </span>TreeNode *node, *x;</div> <div><span style="white-space:pre;"> </span>HeapType heap;</div> <div><span style="white-space:pre;"> </span>element e, e1, e2;</div> <div><span style="white-space:pre;"> </span>char* code=(char *)malloc(sizeof(char));</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>init(&heap);</div> <div><span style="white-space:pre;"> </span>for(i=0;i<n;i++){</div> <div><span style="white-space:pre;"> </span>node=make_tree(NULL,NULL);</div> <div><span style="white-space:pre;"> </span>e.key=node->weight = freq[i];</div> <div><span style="white-space:pre;"> </span>e.ptree=node;</div> <div><span style="white-space:pre;"> </span>insert_min_heap(&heap,e);</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>for(i=1;i<n;i++){</div> <div><span style="white-space:pre;"> </span>//최솟값을 가지는 두 개의 노드를 삭제</div> <div><span style="white-space:pre;"> </span>e1=delete_min_heap(&heap);</div> <div><span style="white-space:pre;"> </span>e2=delete_min_heap(&heap);</div> <div><span style="white-space:pre;"> </span>//두 개의 노드를 합친다.</div> <div><span style="white-space:pre;"> </span>x=make_tree(e1.ptree, e2.ptree);</div> <div><span style="white-space:pre;"> </span>e.key=x->weight=e1.key+e2.key;</div> <div><span style="white-space:pre;"> </span>e.ptree=x;</div> <div><span style="white-space:pre;"> </span>insert_min_heap(&heap,e);</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>e=delete_min_heap(&heap); //최종 트리</div> <div><span style="white-space:pre;"> </span>print_tree(e.ptree,-1,code);</div> <div><span style="white-space:pre;"> </span>destroy_tree(e.ptree);</div> <div>}</div> <div><br></div> <div>int main(void) {</div> <div><span style="white-space:pre;"> </span>int x,num,n=0, freq[MAX_ELEMENT];</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>while(1){</div> <div><span style="white-space:pre;"> </span>printf("1.입력 2.허프만 실행 3.종료\n");</div> <div><span style="white-space:pre;"> </span>scanf("%d",&x);</div> <div><span style="white-space:pre;"> </span>switch(x){</div> <div><span style="white-space:pre;"> </span>case 1:</div> <div><span style="white-space:pre;"> </span>printf("추가 : ");</div> <div><span style="white-space:pre;"> </span>scanf("%d",&num);</div> <div><span style="white-space:pre;"> </span>printf("%d\n",num);</div> <div><span style="white-space:pre;"> </span>freq[n]=num;</div> <div><span style="white-space:pre;"> </span>n++;</div> <div><span style="white-space:pre;"> </span>break;</div> <div><span style="white-space:pre;"> </span>case 2:</div> <div><span style="white-space:pre;"> </span>huffman_tree(freq,n);</div> <div><span style="white-space:pre;"> </span>case 3:</div> <div><span style="white-space:pre;"> </span>printf("종료");</div> <div><span style="white-space:pre;"> </span>return 0;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div>}</div></div> <div><br></div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.