C 언어 하프 만 트 리 구현

본 논문 의 사례 는 C 언어 가 하프 만 트 리 를 실현 하 는 구체 적 인 코드 를 공유 하여 여러분 께 참고 하 시기 바 랍 니 다.구체 적 인 내용 은 다음 과 같 습 니 다.

//    C    
#include <stdio.h>
#include <stdlib.h>
typedef struct HuffmanNode
{
 char letter;//     ,      ,     #
 struct HuffmanNode *parent;//    
 int code;//           ,  0,    1
}HuffmanNode;
typedef struct HeapNode
{
 int rate;//    
 HuffmanNode *node;//           
}HeapNode;
/*------------------    ----------------------*/
int heapSize;//   
int num;//      
HeapNode *heap;//   
char *letter;//    
int *rate;//      
HuffmanNode **array; //        ,                 
char ch;
/*----------------------    -------------------------*/
void init(int numOfLetters);//     
void input();//    
int parent(int i);//    
int left(int i);//    
int right(int i);//    
void swap(int i,int j);//    
void heapIfy(int i,int localHeapSize);//       ,              
void buildHeap();//    
HeapNode* extractMin();//            
void heapInsert(int rate,HuffmanNode *p);//       (  :      )
HuffmanNode* buildTree();//      
void display();//    
void backPrint(HuffmanNode *p,HuffmanNode *root);//          code
/*----------------------    -------------------------*/
void init(int numOfLetters)
{
 heapSize=numOfLetters;//          
 num=numOfLetters;//      
 heap=(HeapNode*)malloc((numOfLetters+1)*sizeof(HeapNode));//     ,          ,           ,    
 letter=(char*)malloc((numOfLetters+1)*sizeof(char));//      
 rate=(int *)malloc((numOfLetters+1)*sizeof(int));//          
 array=(HuffmanNode **)malloc((numOfLetters+1)*sizeof(HuffmanNode));//        ,                 
 
}
void input()
{
 int i=1;
 while(i<=heapSize)
 {
  printf("   %d   
",i); scanf("%c",&letter[i]);ch=getchar(); printf(" %d
",i); scanf("%d",&rate[i]);ch=getchar(); // heap[i].rate=rate[i]; heap[i].node=(HuffmanNode *)malloc(sizeof(HuffmanNode)); array[i]=heap[i].node; heap[i].node->parent=NULL; heap[i].node->letter=letter[i]; i++; } } int parent(int i) { return i/2; } int left(int i) { return 2*i; } int right(int i) { return 2*i+1; } void swap(int i,int j) // , { int rate; HuffmanNode *p; rate=heap[i].rate; p=heap[i].node; heap[i].rate=heap[j].rate; heap[i].node=heap[j].node; heap[j].rate=rate; heap[j].node=p; } void heapIfy(int i,int localHeapSize)// , { int l=left(i); int r=right(i); int least=i; // heap rate i,left(i),right(i) if(l<=localHeapSize&&heap[least].rate>heap[l].rate) { least=l; } if(r<=localHeapSize&&heap[least].rate>heap[r].rate) { least=r; } if(least!=i) { swap(i,least); heapIfy(least,localHeapSize); } } void buildHeap()// { int i=0; for(i=heapSize/2;i>=1;i--) { heapIfy(i,heapSize); } } HeapNode* extractMin() { if(heapSize>=1) { HeapNode *min; swap(1,heapSize); min=&heap[heapSize]; --heapSize; heapIfy(1,heapSize); return min; } else { printf(" "); return NULL; } } void heapInsert(int rate,HuffmanNode *p) { ++heapSize; int i=heapSize; while(i>1&&heap[parent(i)].rate>rate) { heap[i].rate=heap[parent(i)].rate; heap[i].node=heap[parent(i)].node; i=parent(i); } heap[i].rate=rate; heap[i].node=p; } HuffmanNode* buildTree() { buildHeap();// HeapNode *p;// HeapNode *q;// int count=heapSize; int i; for(i=1;i<=count-1;i++) { HuffmanNode *tree=(HuffmanNode*)malloc(sizeof(HuffmanNode));// tree->letter='#';// #, p=extractMin(); q=extractMin(); p->node->parent=tree; p->node->code=0; q->node->parent=tree; q->node->code=1; //printf("%c:%d",p->node->letter,p->node->code); //printf("
"); printf("%c:%d",q->node->letter,q->node->code); printf("
");// heapInsert(p->rate+q->rate,tree);// } return extractMin()->node; } void display() { HuffmanNode*p=buildTree();//// int i=1; while(i<=num) { printf("%c:",array[i]->letter); backPrint(array[i],p); printf("
"); i++; } } void backPrint(HuffmanNode *p,HuffmanNode *root) { if(p!=root) { backPrint(p->parent,root); printf("%d",p->code);//printf("++++");// } } int main(int argc ,char* argv[]) { int number; printf(" :
"); scanf("%d",&number); ch=getchar(); init(number); input(); display(); system("PAUSE"); return 0; }
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.

좋은 웹페이지 즐겨찾기