哈夫曼树与哈夫曼编码 一．实验目的 1、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 二．实验内容 [问题描述] 已知 n 个字符在原文中出现的频率，求它们的哈夫曼编码。 [基本要求] 1. 初始化：从键盘读入 n 个字符，以及它们的权值，建立 Huffman 树。 2. 编码：根据建立的 Huffman 树，求每个字符的 Huffman 编码。 3. 译码：对给定的待编码字符序列进行编码。 三．主要实现函数 ○1 .初始化 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, char 构造哈夫曼树 HT ○2 .编码（Encoding） void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, *cha,int n) char *cha,int n) 利用已建好的哈夫曼树，对档进行编码。 ○3 .译码（Decoding )。 void DeCoding(HuffmanTree &HT,HuffmanCode &HC,int n) 利用已建好的哈夫曼树将代码进行译码 四．源程序代码 #include #include #include #define N 100 char ch; unsigned int weight; unsigned int parent,lchild,rchild; 

s1=min(HT,i); s2=min(HT,i); } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, char *cha,int n) { char c; int f,i,start,m,s1,s2; HTNode *p; if(n<=1) return ; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,++p,i=1;i<=n;++i,++p) { }HTNode,*HuffmanTree; typedef char * *HuffmanCode; int min(HuffmanTree &HT,int i) { int j,flag; Char k ; for(j=1;j<=i;j++) if(HT[j].weightch=cha[i]; p->weight=w[i]; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;++i) { Select(HT,i-1,s1,s2); HT[s1].parent=i; 

HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild == c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); printf("字符为%c",HT[i].ch); printf("的编码是%s\n",HC[i]); } free(cd); } void DeCoding(HuffmanTree &HT,HuffmanCode &HC,int n) { char f[N]; printf("请输入字符串:\n"); getchar(); gets(f); int i;int m,k=0; while(f[k]!='\0') for(i=1;i<=n;i++) { m=strlen(HC[i]); if(strncmp(HC[i],f+k,m)==0) { k=k+m; printf("输出%s 的字符是",HC[i]); printf("%c\n",HT[i].ch); } } } main() { HuffmanTree HT; HuffmanCode HC; int n,i; printf("*********哈夫曼树编译码程序*************"); 

printf("\n 输入建哈夫曼树元素的个数："); scanf("%d",&n); int m=2*n-1; char cha[9]; int w[9]; for(i=1;i<=n;i++) { printf("第%d 个元素字母和权值:\n",i); getchar(); scanf("%c %d",&cha[i],&w[i]); } HuffmanCoding(HT,HC,w,cha,n); DeCoding(HT,HC,n); return 0; } 五．运行 （1）运行主界面 （2）输入八个元素及权值，并编码界面 （3）译码界面