数据结构-哈夫曼编码

《数据结构-哈夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实训班级：计科101 姓名： 学号：完成日期：2012/6/28题目：哈夫曼编码一、问题描述设某编码系统共有n个字符，使用频率分别为{w1,w2,…,wn}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。二、基本要求(1)在文件中存储一系列字符代码；(2)编写程序分析文件中各个字符以及每个字符出现的频率；(3)将各个字符及其频率分析成结点以及结点的权值，构造哈弗曼树。(4)分析构造的哈夫曼树，列出相应的哈弗曼编码(5)把生成的编码替换原文件中的字符，并将结果存储到文件中三、实验描述设有10个字符，使用频率分别为10%、5%、7%、8%、15%、6%、18%、5%、3

2、%、13%，这10个结点的权值分别为10、5、7、8、15、6、18、5、3、13、让后构造一颗有10个叶子节点的二叉树四、实验程序#include#include#includeintm,s1,s2;typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar*HuffmanCode;//动态分配数组存储哈夫曼编码表voidSelect(HuffmanTreeHT,i

3、ntn){inti,j;for(i=1;i<=n;i++)if(!HT[i].parent){s1=i;break;}for(j=i+1;j<=n;j++)if(!HT[j].parent){s2=j;break;}for(i=1;i<=n;i++)if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;for(j=1;j<=n;j++)if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;}voidHuffmanCoding(HuffmanT

4、ree&HT,HuffmanCodeHC[],int*w,intn){//w存放n个字符的权值(均>0)，构造哈夫曼树HT，//并求出n个字符的哈夫曼编码HCinti,j;char*cd;intp;intcdlen;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1;i<=n;i++){//初始化HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;i++){//

5、初始化HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}puts("哈夫曼树的构造过程如下所示：");printf("HT初态:结点weightparentlchildrchild");for(i=1;i<=m;i++)printf("%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf("按任意键，继续...");getchar();for(i=n+1;i<=m;i++){//建哈夫曼树//在HT

6、[1..i-1]中选择parent为0且weight最小的两个结点，//其序号分别为s1和s2。Select(HT,i-1);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;printf("select:s1=%ds2=%d",s1,s2);printf("结点weightparentlchildrchild");for(j=1;j<=i;j++)printf("%4d%8d%8d%8d%8d",j,HT[j].

7、weight,HT[j].parent,HT[j].lchild,HT[j].rchild);printf("按任意键，继续...");getchar();}//------无栈非递归遍历哈夫曼树，求哈夫曼编码cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间p=m;cdlen=0;for(i=1;i<=m;++i)//遍历哈夫曼树时用作结点状态标志HT[i].weight=0;while(p){if(HT[p].w