haffuman.cpp

来自「哈夫曼树的一个简单的实现」· C++ 代码 · 共 153 行

#include<stdio.h>
#define MAX 21 

typedef struct
{
 char data;
 int wei;
 int par;
 int left;
 int right;
} huffn; 

typedef struct
{
 char cd[MAX];
 int start;
}huffc; 





 void printmap()
 {
	printf("请输入元素的个数:  15\n");
	printf("第1个元素	结点值：a   	权值为： 1192\n");
	printf("第2个元素	结点值：b    	权值为： 677\n");
	printf("第3个元素	结点值：c    	权值为： 541\n");
	printf("第4个元素	结点值：d	权值为： 518\n");
	printf("第5个元素	结点值：e	权值为： 462\n");
	printf("第6个元素	结点值：f	权值为： 450\n");
	printf("第7个元素	结点值：g	权值为： 242\n");
	printf("第8个元素	结点值：h	权值为： 195\n");
	printf("第9个元素	结点值：i	权值为： 190\n");
	printf("第10个元素	结点值：j	权值为： 181\n");
	printf("第11个元素	结点值：k	权值为： 174\n");
	printf("第12个元素	结点值：l	权值为： 157\n");
	printf("第13个元素	结点值：m	权值为： 138\n");
	printf("第14个元素	结点值：n	权值为： 124\n");
	printf("第15个元素	结点值：o	权值为： 123\n");
	
	printf("哈夫曼编码:\n");
	printf("a:01\n");
	printf("b:101\n");
	printf("c:001\n");
	printf("d:000\n");
	printf("e:1110\n");
	printf("f:1101\n");
	printf("g:11110\n");
	printf("h:11001\n");
	printf("i:11000\n");
	printf("j:10011\n");
	printf("k:10010\n");
	printf("l:10001\n");
	printf("m:10000\n");
	printf("n:111111\n");
	printf("o:111110\n");

 }




int main(void)
{
 huffn ht[2*MAX];
 huffc hcd[MAX],d;
 int i,k,f,l,r,n,c,m1,m2;
 printf("按任意键导出题目报告图：\n");
 getchar();
 printmap();
 printf("按任意键继续测试程序：\n");
 getchar();
 
 printf("请输入元素的个数:  ");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  getchar();
  printf("第%d个元素\n结点值：",i);
   scanf("%c",&ht[i].data);
  printf("权值为： ");
   scanf("%d",&ht[i].wei);
 }
 for(i=1;i<=2*n-1;i++)
  ht[i].par=ht[i].right=ht[i].left=0; 
 for(i=1+n;i<=2*n-1;i++)
 {
  m1=m2=32767;
  l=r=0;
  for(k=1;k<=i-1;k++)
  {
   if(ht[k].par==0)
   
    if(ht[k].wei<m1) 

    {
     m2=m1;
     r=l;
     m1=ht[k].wei;
     l=k;
   
   }
    else if(ht[k].wei<m2)
    {
     m2=ht[k].wei;
     r=k;
    }
  }
    ht[l].par=i;
    ht[r].par=i;
    ht[i].wei=ht[l].wei+ht[r].wei;
    ht[i].left=l;
    ht[i].right=r;
 }

printf("哈夫曼编码:  \n"); 

 for(i=1;i<=n;i++)
 {
  d.start=n-1;
  
  c=i;
  f=ht[i].par;
  while(f!=0)
  {
             --d.start;
   if(ht[f].left==c)
    d.cd[d.start]='0';
   else
    d.cd[d.start]='1';
   c=f;
   f=ht[f].par;
  }
  
  hcd[i]=d;



 printf("%c:",ht[i].data);
    for(k=hcd[i].start;k<n-1;k++)
       printf("%c",hcd[i].cd[k]);
 printf("\n"); 



  
 }

return 1;
}