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;
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.