哈夫曼编码算法实现完整版.pdf

哈夫曼编码算法实现完整版 ———————————————————————————————— 作者： ———————————————————————————————— 日期： 实验三 树的应用 一.实验题目 ： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时 间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权 值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为 结点的权值， 建立哈夫曼树， 然后对各个字符进行哈夫曼编码， 最后打印输出字 符及对应的哈夫曼编码。 三、程序源代码 : #include iostream.h #include fstream.h #include string.h #include stdlib.h typedef struct{ char data; int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char * * HuffmanCode; void Select(HuffmanTree HT,int n,int m) {HuffmanTree p=HT; int tmp; for(int j=n+1;j=m;j++) {int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x=j-1;x++) { if(p[x].parent==0p[x].weighttag1) { tag1=p[x].weight;s1=x;} } for(int y=1;y=j-1;y++) { if(p[y].parent==0y!=s1p[y].weighttag2) { tag2=p[y].weight;s2=y;} } if(s1s2) // 将选出的两个节点中的序号较小的始终赋给 s1 { tmp=s1; s1=s2; s2=tmp;} p[s1].parent=j; p[s2].parent=j; p[j].lchild=s1; p[j].rchild=s2; p[j].weight=p[s1].weight+p[s2].weight; } } void HuffmanCoding(HuffmanTree HT,int n,char *w1,int*w2) { int m=2*n-1; if(n=1) return; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); HuffmanTree p=HT; for(int i=1;i=n;i++) { p[i].data=w1[i-1]; p[i].weight=w2[i]; p[i].parent=p[i].lchild=p[i].rchild=0; } for(;i=m;i++) { p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0; } Select(HT,n,m); ofstream outfile; //生成