数据结构实验报告- 文件压缩

1、专业.专注数据结构与程序设计实验实验报告课程名称数据结构与程序设计实验实验项目名称学号姓名学生所在学院计算机学院实验室名称地点课程编号0906550文件压缩年级专业计算机科学与技术指导教师杨静21B276哈尔滨工程大学实验报告四实验课名称：数据结构与程序设计实验实验名称：文件压缩班级：学号：姓名：时间：2016.04.21一、问题描述哈夫曼编码是一种常用的数据压缩技术,对数据文件进行哈夫曼编码可大大缩短文件的传输长度,提高信道利用率及传输效率。要求采用哈夫曼编码原理,统计文本文件中字符出现的词频,以词频作为权值,对文件进行哈夫曼编码以达到压缩文件的目的,再用哈夫曼编码进行译码解压缩。统计待压缩

2、的文本文件中各字符的词频,以词频为权值建立哈夫曼树,并将该哈夫曼树保存到文件HufTree.dat中。根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码,并将字符编码保存到HufCode.txt文件中。压缩：根据哈夫曼编码,将源文件进行编码得到压缩文件CodeFile.dat。解压：将CodeFile.dat文件利用哈夫曼树译码解压,恢复为源文件。二、数据结构设计由于哈夫曼树中没有度为1的结点,则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点,可以存储在一个大小为2n-1的一维数组中,而且对每个结点而言,即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。

3、1使用结构体数组统计词频，并存储：typedefstructNodeintweight;叶子结点的权值charc;叶子结点intnum;叶子结点的二进制码的长度LeafNodeN;2使用结构体数组存储哈夫曼树：typedefstructunsignedintweight;/权值unsignedintparent,LChild,RChild;HTNode,HuffmanM+1;/huffman树3使用字符指针数组存储哈夫曼编码表：typedefchar*HuffmanCode2*M;/haffman编码表三、算法设计1读取文件,获得字符串voidread_file(charconst*file_

4、name,char*ch)FILE*in_file=Fopen(file_name,r);unsignedintflag=fread(ch,sizeof(char),N,in_file);if(flag=0)printf(%s读取失败门，file_name);fflush(stdout);printf(读入的字符串是:%snn:ch);Fclose(in_file);intlen二strlen(ch);chlen-1=0;2统计叶子结点的字符和权值并存储voidCreateLeaf(charch,int*ch_len,LeafNodeleaves,int*leaf_num)intlen,j,k

5、;inttag;*leaf_num=0;叶子节点个数统计字符出现个数，放入CWfor(len=0;chlen!=0;len+)/遍历字符串chtag=1;for(j=0;jlen;j+)if(chj=chlen)tag=0;break;if(tag)/*leaf_num=0不用leaves+*leaf_num.c二chlen;leaves*leaf_num.weight=1;for(k=len+1;chk!=0;k+)在之后的字符串中累计权值if(chlen=chk)leaves*leaf_num.weight+;权值累加for(i二n+1;i=2*n-1;i+)for(j=1;j=i-1;j

6、+)if(!htj.parent)break;s1=j;找到第一个双亲为零的结点for(;jhtj.weight?j:s1;hts1.parent二i;hti.LChild二s1;for(j=1;j=i-1;j+)if(!htj.parent)break;s2=j;找到第二个双亲为零的结点for(;jhtj.weight?j:s2;hts2.parent二i;hti.RChild=s2;hti.weight二hts1.weight+hts2.weight;/权值累加存储：voidsave_HufTree(Huffmanht,LeafNodele,intln)inti;FILE*HufTree=

7、Fopen(HufTree.dat,a);CreateHuffmanTree(ht,le,丨n);printf(n哈夫曼树门)；printf(编号权值parentLChildRChildn);fputs(编号权值|parent|LChild|RChildn,HufTree);for(i=1;i=2*ln-1;i+)/*打印Huffman树的信息*/printf(%dt%dt%dt%dt%dn,i,(ht)i.weight,(ht)i.parent,(ht)i.LChild,(ht)i.RChild);fprintf(HufTree,%d|%d|%d|%d|%dn,i,(ht)i.weight,

8、(ht)i.parent,(ht)i.LChild,(ht)i.RChild);Fclose(HufTree);printf(哈弗曼树已保存至HufTree.datn);4.读取哈夫曼树至新的结构体数组voidread_HufTree(Huffmanht)记得从1开始存储inti=1,j;FILE*HufTree=Fopen(HufTree.dat,r);while(fscanf(HufTree,%d|%d|%d|%d|%dn,&j,&(ht)i.weight),&(ht)i.parent),&(ht)i丄Child),&(ht)i.RChild)=5)printf(%dt%dt%dt%dn,

9、(ht)i.weight,(ht)i.parent,(ht)i.LChild,(ht)i.RChild);i+;Fclose(HufTree);printf(已从HufTree.dat读取哈弗曼树n);5根据哈夫曼树生成每个叶子结点的编码voidCrtHuffmanNodeCode(Huffmanht,charch,HuffmanCodecode_of_leaf,LeafNodeweight,intm,intn)inti,c,p,start;char*cd;cd=(char*)malloc(n*sizeof(char);cdn-1=0;末尾置0for(i=1;i二n;i+)start二n-1;

10、/cd串每次从末尾开始c=i;p=hti.parent;/p在n+1至2n-1while(p)沿父亲方向遍历,直到为0start-;/依次向前置值if(htp丄Child=c)与左子相同，置0cdstart=O;else否则置1cdstart=1;c=p;p=htp.parent;weighti.num二n-start;二进制码的长度(包含末尾0)code_of_leafi=(char*)malloc(n-start)*sizeof(char);strcpy(code_of_leafi,&cdstart);将二进制字符串拷贝到指针数组code_of_leaf中free(cd);/释放cd内存6

11、保存每个叶子结点的信息voidsave_HufCode(Huffmanht,char*ch,HuffmanCodecode_of_leaf,LeafNodeleaves,intch_len,intleaf_num)inti;FILE*HufCode=Fopen(HufCode.txt,a);CrtHuffmanNodeCode(ht,ch,code_of_leaf,leaves,ch_len,leaf_num);/叶子结点的编码printf(n每个叶子节点的前缀码门);/打印叶子结点的编码for(i=1;i=leaf_num;i+)printf(%c:%sn,leavesi.c,code_of

12、_leafi);fprintf(HufCode,%c:%sn,leavesi.c,code_of_leafi);Fclose(HufCode);printf(每个叶子节点的前缀码已保存至HufCode.txtn);7读取每个叶子节点的信息到新的字符指针数组voidread_HufCode(HuffmanCodecode_of_leaf)inti=1;charc,tem10;FILE*HufCode=Fopen(HufCode.txt,r);while(fscanf(HufCode,%c:%sn,&c,tem)=2)intlen二strlen(tem);code_of_leafi=(char*)

13、malloc(len*sizeof(char);strcpy(code_of_leafi,tem);/printf(%c:%sn,c,code_of_leafi);i+;Fclose(HufCode);printf(已从HufCode.txt读取每个叶子节点信息门)；8生成所有字符的编码voidCrtHuffmanCode(charch,HuffmanCodecode_of_leaf,HuffmanCodecode_of_ch,LeafNodeleaves,intleaf_num,intch_len)inti,k;for(i=0;ich_len;i+)for(k=1;k=leaf_num;k+

14、)/*从weightk.c中查找与chi相等的下标K*/if(chi=leavesk.c)break;code_of_chi=(char*)malloc(leavesk.num)*sizeof(char);strcpy(code_of_chi,code_of_leafk);/拷贝二进制编码9保存字符串的编码信息(压缩)FILE*Fopen(charconst*filename,charconst*mode)FILE*idlist;idlist=fopen(filename,mode);if(idlist=NULL)perror(filename);exit(EXIT_FAILURE);else

15、returnidlist;解码并保存到str2.txtvoidTrsHuffmanTree(Huffmanht,LeafNodew,HuffmanCodehe,intn,intm)inti=0,j,p；FILE*str2=Fopen(str2.txt,a);printf(n经解压得原文件中的字符串：”)；while(im)p=2*n-1;从父亲节点向下遍历直到叶子节点for(j=O;hcij!=O;j+)if(hcij=O)p=htp.LChild;elsep=htp.RChild;printf(%c,wp.c);/*打印原信息*/fputc(wp.c,str2);i+；Fclose(str2

16、);printf(n已将解压得到的字符串保存至str2.txtn);释放huffman编码内存voidFreeHuffmanCode(HuffmanCodehi,HuffmanCodeh2,HuffmanCodehe,intleaf_num,inteh_len)inti;for(i=1;i=leaf_num;i+)释放叶子结点的编码free(h1i);free(h2i);for(i=O;ih.exe文件SJtFl.txt-的字符串是：aaabcbadffafd3统计叶子节点的权值叶子节点的字符与权值a：5b：2c:14根据权值生成哈夫曼树，保存至HufTree.dat,并用新的结构体数组读取哈

17、夫曼树_ntLOW画边158002260031b杪427&053700B383275945B6961913078哈鼎曼树已保仔至HnfTree.dat已JHufTree-触t读取哈劳曼树158011260116027037038315g4|18g61113101710根据CodeFile.dat解压,获得原字符串,并保存至str2.txt经解压得原文件史的字薈串：aaabcbadffafd已熔解庄得轨的子符串葆祥至0tr2.txt11.str2.txt内容typedefchar*HuffmanCode2*M;/haffman编码typedefstructunsignedintweight;/权

18、值unsignedintparent,LChild,RChild;HTNode,HuffmanM+1;/huffman树typedefstructNodeintweight;叶子结点的权值charc;叶子结点intnum;叶子结点的二进制码的长度LeafNodeN;/产生叶子结点的字符和权值voidCreateLeaf(charch,int*ch_len,LeafNodeleaves,int*leaf_num)intlen,j,k;inttag;*leaf_num=0;叶子节点个数统计字符出现个数，放入CWfor(len=0;chlen!=0;len+)/遍历字符串chtag=1;for(j=

19、0;jlen;j+)if(chj=chlen)tag=O;break;if(tag)*leaf_num=0不用leaves+*leaf_num.c二chlen;leaves*leaf_num.weight=1;for(k=len+1;chk!=O;k+)在之后的字符串中累计权值if(chlen=chk)leaves*leaf_num.weight+;权值累加*ch_len=len;字符串长度/创建HuffmanTreevoidCreateHuffmanTree(Huffmanht丄eafNodew,intn)inti,j;ints1,s2;初始化哈夫曼树for(i=1;i二n;i+)if(!h

20、tj.parent)break;s2=j;找到第二个双亲为零的结点for(;jhtj.weight?j:s2;hts2.parent二i;hti.RChild二s2;hti.weight二hts1.weight+hts2.weight;/权值累加/生成每个叶子结点的编码voidCrtHuffmanNodeCode(Huffmanht,charch,HuffmanCodecode_of_leaf,LeafNodeweight,intm,intn)inti,c,p,start;char*cd;cd=(char*)malloc(n*sizeof(char);cdn-1=0;末尾置0for(i=1;i

21、二n;i+)start二n-1;/cd串每次从末尾开始c=i;p=hti.parent;/p在n+1至2n-1while(p)沿父亲方向遍历,直到为0start-;/依次向前置值if(htp.LChild=c)与左子相同，置0cdstart=0;else否则置1cdstart=1;c=p;p=htp.parent;weighti.num二n-start;二进制码的长度(包含末尾0)code_of_leafi=(char*)malloc(n-start)*sizeof(char);strcpy(code_of_leafi,&cdstart);将二进制字符串拷贝到指针数组code_of_leaf中

22、free(cd);/释放cd内存/生成所有字符的编码voidCrtHuffmanCode(charch,HuffmanCodecode_of_leaf,HuffmanCodecode_of_ch,LeafNodeleaves,intleaf_num,intch_len)inti,k;for(i=0;ich_len;i+)for(k=1;k=leaf_num;k+)/*从weightk.c中查找与chi相等的下标K*/if(chi=leavesk.c)break;code_of_chi=(char*)malloc(leavesk.num)*sizeof(char);strcpy(code_of_

23、chi,code_of_leafk);/拷贝二进制编码FILE*Fopen(charconst*filename,charconst*mode)FILE*idlist;idlist=fopen(filename,mode);if(idlist=NULL)perror(filename);exit(EXIT_FAILURE);elsereturnidlist;voidFclose(FILE*file)if(fclose(file)!=0)perror(fclose);exit(EXIT_FAILURE);file=NULL;voidread_file(charconst*file_name,ch

24、ar*ch)FILE*in_file=Fopen(file_name,r);unsignedintflag=fread(ch,sizeof(char),N,in_file);if(flag=0)printf(%s读取失败门，file_name);fflush(stdout);printf(读入的字符串是:%snn:ch);Fclose(in_file);intlen二strlen(ch);chlen-1=0;voidsave_HufTree(Huffmanht,LeafNodele,intln)inti;FILE*HufTree=Fopen(HufTree.dat,a);CreateHuffm

25、anTree(ht,le,ln);printf(n哈夫曼树门)；printf(编号权值parentLChildRChildn);fputs(编号权值|parent|LChild|RChildn,HufTree);for(i=1;i=2*ln-1;i+)/*打印Huffman树的信息*/printf(%dt%dt%dt%dt%dn,i,(ht)i.weight,(ht)i.parent,(ht)i丄Child,(ht)i.RChild);fprintf(HufTree,%d|%d|%d|%d|%dn,i,(ht)i.weight,(ht)i.parent,(ht)i丄Child,(ht)i.RC

26、hild);Fclose(HufTree);printf(哈弗曼树已保存至HufTree.datn);voidread_HufTree(Huffmanht)记得从1开始存储inti=1,j;FILE*HufTree=Fopen(HufTree.dat,r);while(fscanf(HufTree,%d|%d|%d|%d|%dn,&j,&(ht)i.weight),&(ht)i.parent),&(ht)i.LChild),&(ht)i.RChild)=5)/printf(%dt%dt%dt%dn,(ht)i.weight,(ht)i.parent,(ht)i.LChild,(ht)i.RCh

27、ild);i+;Fclose(HufTree);printf(已从HufTree.dat读取哈弗曼树n);voidsave_HufCode(Huffmanht,char*ch,HuffmanCodecode_of_leaf,LeafNodeleaves,intch_len,intleaf_num)inti;FILE*HufCode=Fopen(HufCode.txt,a);CrtHuffmanNodeCode(ht,ch,code_of_leaf,leaves,ch_len,leaf_num);/叶子结点的编码printf(n每个叶子节点的前缀码门);/打印叶子结点的编码for(i=1;i=l

28、eaf_num;i+)printf(%c:%sn,leavesi.c,code_of_leafi);fprintf(HufCode,%c:%sn,leavesi.c,code_of_leafi);Fclose(HufCode);printf(每个叶子节点的前缀码已保存至HufCode.txtn);voidread_HufCode(HuffmanCodecode_of_leaf)inti=1;charc,tem10;FILE*HufCode=Fopen(HufCode.txt,r);while(fscanf(HufCode,%c:%sn,&c,tem)=2)intlen二strlen(tem);

29、code_of_leafi=(char*)malloc(len*sizeof(char);strcpy(code_of_leafi,tem);/printf(%c:%sn,c,code_of_leafi);i+;Fclose(HufCode);printf(已从HufCode.txt读取每个叶子节点信息门)；voidsave_CodeFile(char*ch,HuffmanCodecode_of_leaf,HuffmanCodecode_of_ch,LeafNodeleaves,intleaf_num,intch_len)FILE*CodeFile=Fopen(CodeFile.dat,a);

30、CrtHuffmanCode(ch,code_of_leaf,code_of_ch,leaves,leaf_num,ch_len);/字符串的编码printf(n字符串的编码：);打印字符串的编码inti;for(i=0;ich_len;i+)printf(%s,code_of_chi);fputs(code_of_chi,CodeFile);Fclose(CodeFile);printf(n字符串的哈弗曼编码已保存至CodeFile.datn);解码并保存到str2.txtvoidTrsHuffmanTree(Huffmanht,LeafNodew,HuffmanCodehc,intn,intm)inti=0,j,p;FILE*str2=Fopen(str2.txt,a);printf(n经解压得原文件中的字符串：”)；while(im)p=2*n-1;从父亲节点向下遍历直到叶子节点for(j=O;hcij!=O;j+)if(hcij=0)p=htp丄Child;elsep=htp.RChild;printf(%c,wp.c);/*打印原信息*/fputc(wp.c,str2);i+;Fclose(str2);printf(n已将解压得到的字符串保存至str2.txtn);释放huffman编码内存voidFreeHuffmanCode(