资源描述:
《数据结构-哈夫曼编码》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构实训班级:计科101 姓名: 学号:完成日期:2012/6/28题目:哈夫曼编码一、问题描述设某编码系统共有n个字符,使用频率分别为{w1,w2,…,wn},设计一个不等长的编码方案,使得该编码系统的空间效率最好。二、基本要求(1)在文件中存储一系列字符代码;(2)编写程序分析文件中各个字符以及每个字符出现的频率;(3)将各个字符及其频率分析成结点以及结点的权值,构造哈弗曼树。(4)分析构造的哈夫曼树,列出相应的哈弗曼编码(5)把生成的编码替换原文件中的字符,并将结果存储到文件中三、实验描述设有10个字符,使用频率分别为10%、5%、7%、8%、15%、6
2、%、18%、5%、3%、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;//动态分配数组存储哈夫曼编码表voidSe
3、lect(HuffmanTreeHT,intn){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
4、=j;}voidHuffmanCoding(HuffmanTree&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=
5、0;HT[i].rchild=0;}for(i=n+1;i<=m;i++){//初始化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("按任意键,
6、继续...");getchar();for(i=n+1;i<=m;i++){//建哈夫曼树//在HT[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("结点weightparentlchildr
7、child");for(j=1;j<=i;j++)printf("%4d%8d%8d%8d%8d",j,HT[j].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
8、[p].w