数据结构第6章实验报告哈弗曼

数据结构实验报告第六章实验名称：文件压缩实验类型：综合性实验班级：学号：姓名：实验日期：2014年6月14日1.问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。2.数据结构设计在实验中数据结构设为：typedefstruct{chardata;//存放字符unsignedintweight;//权重unsignedintparent,lchild,rchild;//左孩子标号，右孩子标号}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表3.算法设计程序分为以下几个部分：（1）统计数据文件里字符以及出现的次数int*w;//存放每个字符的频数inti;//用于各种计数//***********************************************************//统计1.txt中文件字符以及频数ifstreamfin(d:\\1.txt,ios::in);//从1.txt中读取字符if(!fin){coutFileopenerror!\n;return0;}inttongji[256];intaa;//字符对应的asciicharcc;//用来读取文件里的字符for(intii=0;ii256;ii++)//初始化{tongji[ii]=0;}while((cc=fin.get())!=EOF)//从文件读取字符，并建立字符统计数组{aa=int(cc);tongji[aa]++;}fin.close();//关闭文件//**************************************//用于建立哈弗曼树的统计变量unsignedintn=0;for(intii=0;ii256;ii++){if(tongji[ii]!=0){n++;}}unsignedintpinshu[n];//每个字符的频数charzifu[n];//文件中出现的字符intn1=0;//范围从0--n-1，用于出现过字符的赋值for(intii=0;ii256;ii++){if(tongji[ii]!=0){pinshu[n1]=tongji[ii];zifu[n1]=char(ii);++n1;}}（2）依据字符出现的频率建立哈弗曼树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-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和s2select(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]不用)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';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC}free(cd);//释放工作空间}intmin(HuffmanTreet,inti){//函数voidselect()调用intj,flag;unsignedintk=UINT_MAX;//取k为不小于可能的值for(j=1;j=i;j++)if(t[j].weightk&&t[j].parent==0)k=t[j].weight,flag=j;t[flag].parent=1;returnflag;}voidselect(HuffmanTreet,inti,int&s1,int&s2){//s1为最小的两个值中序号小的那个intj;s1=min(t,i);s2=min(t,i);if(s1s2){j=s1;s1=s2;s2=j;}}（3）存储哈弗曼树，建立字符与哈弗曼编码的对应关系文件//哈弗曼编码对应表写入fstreamf(d:\\HuffCode.txt,ios::out);//生成哈弗曼编码与字符的对照表for(i=1;i=n;i++)//输出字符与哈弗曼编码对照表{fzifu[i-1]的哈弗曼编码：HC[i]endl;}f.close();fstreamfouthf(d:\\文字翻译到哈弗曼.txt,ios::out);//将翻译后的文字，//写入翻译后的文件ifstreamfin1(d:\\1.txt,ios::in);//从1.txt中逐个字符读取if(!fin1){coutFileopenerror!\n;return0;}while((cc=fin1.get())!=EOF)//从文件读取字符，{for(i=0;in;i++){if(cc==zifu[i])fouthfHC[i+1];//把字符对应哈弗曼编码写入//文件“文字翻译到哈弗曼”}}fin1.close();//关闭文件fouthf.close();（4）根据哈弗曼树对数据文件里的数据进行翻译，得到哈弗曼编码fstreamfouthf(d:\\文字翻译到哈弗曼.txt,ios::out);//将翻译后的文字，写入翻译后的文件ifstreamfin1(d:\\1.txt,ios::in);//从1.txt中逐个字符读取if(!fin1){coutFileopenerror!\n;return0;}while((cc=fin1.get())!=EOF)//从文件读取字符，{for(i=0;in;i++){if(cc==zifu[i])fouthfHC[i+1];//把字符对应哈弗曼编码写入文件“文字翻译到哈弗曼”}}fin1.close();//关闭文件fouthf.close();（5）将哈弗曼编码的8位作为一个字节的8位，以字符形式存进另一文件//把翻译后的哈弗曼存进数组zongchanghafu[]charzongchanghafu[sum];ifstreamfin4(文字翻译到哈弗曼.txt,ios::in);//从文字翻译到哈弗//曼.txt中逐个读取哈弗曼编码if(!fin4){coutFileopenerror!\n;return0;}intjishu=0;while((cc=fin4.get())!=EOF)//从文件读取字符，{zongchanghafu[jishu]=cc;jishu++;}fin4.close();//关闭文件//*******************************************************//取出哈弗曼编码进行压缩存储inthuansum=0;//存放每8为二进制数对应的十进制数，即新的字符对应的ASCII码charlinshicun[9];//存放8位二进制数yasuon=(sum/8)+1;//yasuon是压缩后的字符数charyasuo[yasuon];//创建压缩后的字符数组，存放压缩后的数据ofstreamfout6(d:\\压缩.dat,ios::binary);for(intk=1;k=yasuon;k++){intl=(k-1)*8;linshicun[0]=zongchanghafu[l];linshicun[1]=zongchanghafu[l+1];linshicun[2]=zongchanghafu[l+2];linshicun[3]=zongchanghafu[l+3];linshicun[4]=zongchanghafu[l+4];linshicun[5]=zongchanghafu[l+5];linshicun[6]=zongchanghafu[l+6];linshicun[7]=zongchanghafu[l+7];inti2=1;for(intii=7;ii=0;ii--){huansum=huansum+linshicun[ii]*i2;i2=2*i2;}//*******************************************************//生成压缩文件fout6.write((char*)(&huansum),sizeof(huansum));}//end每八位二进制数转换fout6.close();（6）再根据哈弗曼编码对压缩后的文件进行翻译，得到原文件内容先把压缩后文件中的数据还原为二进制数提取到一个文件中，再对其进行翻译fstreamfout2(d:\\哈弗曼翻译到文字.txt,ios::out);//将翻译后的文字，//写入翻译后的文件ifstreamfin2(文字翻译到哈弗曼.txt,ios::in);//从文字翻译到哈弗//曼.txt中逐个读取哈弗曼编码if(!fin2){coutFileopenerror!\n;return0;}longintsum=0;//翻译后哈弗曼编码的总长度intyasuon;//压缩数组的长度yasuoncc=fin2.get();++sum;intlc,rc,c3;c3=2*n-1;lc=HT[c3].lchild;rc=HT[c3].rchild;do{if(cc=='0')c3=lc;elsec3=rc;lc=HT[c3].lchild;rc=HT[c3].rchild;if(lc==0&&rc==0){fout2HT[c3].data;if((cc=fin2.get())==EOF)break;else{c3=n*2-1;++s