资源描述：
《数据结构第6章实验报告哈弗曼.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构实验报告第六章实验名称：文件压缩实验类型：综合性实验班级：学号：姓名：实验日期：2014年6月14日1.问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。l统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。l根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.t
2、xt文件中。l压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。l解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。2.数据结构设计在实验中数据结构设为：typedefstruct{chardata;//存放字符unsignedintweight;//权重unsignedintparent,lchild,rchild;//左孩子标号，右孩子标号}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表3.算法设计程序分为以下几个部分：（1）统计数据文件
3、里字符以及出现的次数int*w;//存放每个字符的频数inti;//用于各种计数//***********************************************************//统计1.txt中文件字符以及频数ifstreamfin("d:\1.txt",ios::in);//从1.txt中读取字符if(!fin){cout<<"Fileopenerror!";return0;}inttongji[256];intaa;//字符对应的asciicharcc;//用来读取文件里的字符for(intii=0;ii<256;ii++)//初始化{tongji[ii
4、]=0;}while((cc=fin.get())!=EOF)//从文件读取字符，并建立字符统计数组{aa=int(cc);tongji[aa]++;}fin.close();//关闭文件//**************************************//用于建立哈弗曼树的统计变量unsignedintn=0;for(intii=0;ii<256;ii++){if(tongji[ii]!=0){n++;}}unsignedintpinshu[n];//每个字符的频数charzifu[n];//文件中出现的字符intn1=0;//范围从0--n-1，用于出现过字符的赋值for(
5、intii=0;ii<256;ii++){if(tongji[ii]!=0){pinshu[n1]=tongji[ii];zifu[n1]=char(ii);++n1;}}（1）依据字符出现的频率建立哈弗曼树voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn,charzi[]){//w存放n个字符的权值(均>0),zi[]存放n字符，6构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCintm,i,s1,s2,start;unsignedc,f;HuffmanTreep;char*cd;if(n<=1)return;m=2*n-
6、1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(p=HT+1,i=1;i<=n;++i,++p,++w,++zi)//初始化哈弗曼树{(*p).weight=*w;(*p).data=*zi;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i<=m;++i,++p)//非叶子节点的父亲为0(*p).parent=0;for(i=n+1;i<=m;++i)//建赫夫曼树{//在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2selec
7、t(HT,i-1,s1,s2);HT[s1].parent=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*));//分配n个字符编码的头指针向量([0]不用
