《数据结构哈夫曼编码实验报告》由会员分享，可在线阅读，更多相关《数据结构哈夫曼编码实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、. . 实验报告实验课名称： 数据结构实验实验名称： 文件压缩问题班级： 20132012 学号：时间： 2015-6-9 一、问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度， 提高信道利用率及传输效率。 要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值， 对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。二、数据结构设计首先定义一个结构体：struct head unsigned char b; / 记录字符long count; / 权重int parent,lch,rch; / 定义双亲，左孩子，右孩
2、子char bits256; / 存放哈夫曼编码的数组 header512,tmp; / 头部一要定设置至少512 个,因为结点最多可达256,所有结点数最多可达511 三、算法设计. . 输入要压缩的文件读文件并计算字符频率根据字符的频率，利用Huffman编码思想创建 Huffman 树由创建的 Huffman 树来决定字符对应的编码，进行文件的压缩解码压缩即根据Huffman 树进行译码设计流程图如图 1.1 所示。统计字符，得出统计出字符的权值n 建立哈夫曼树对二进制文件进行解码根据哈夫曼树编码对编码进行压缩根据哈夫曼树解码. . 图 1.1 设计流程图(1)压缩文件输入一个待压缩的文
3、本文件名称(可带路径 )如:D:lulu.txt统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进行编码,生成压缩文件。 压缩文件名称 =文本文件名 .COD 如:D:lulu.COD 压缩文件内容 =哈夫曼树的核心内容 +编码序列for(int i=0;i256;i+) headeri.count=0; / 初始化权重headeri.b=(unsigned char)i; / 初始化字符 ifstream infile(infilename,ios:in|ios:binary); while(infile.peek()!=EOF) 生成二进制文件生成对应文件生成哈夫曼
4、树. . infile.read(char *)&temp,sizeof(unsigned char); / 读入一个字符headertemp.count+; / 统计对应结点字符权重flength+; / 统计文件长度 infile.close(); / 关闭文件for(i=0;i256-1;i+) / 对结点进行冒泡排序,权重大的放在上面，编码时效率高for(int j=0;j256-1-i;j+) if(headerj.countheaderj+1.count) tmp=headerj; headerj=headerj+1; headerj+1=tmp; for(i=0;i256;i+)
5、 if(headeri.count=0) break; leafnum=i; / 取得哈夫曼树中叶子结点数pointnum=2*leafnum-1; / 取得哈夫曼树中总结点数目infile.open(infilename,ios:in|ios:binary); / 打开待压缩的文件infile.clear(); infile.seekg(0); ofstream outfile(outfilename,ios:out|ios:binary); / 打开压缩后将生成. . 的文件outfile.write(char *)&flength,sizeof(long); / 写入原文件长度(2)哈夫
6、曼编码for(i=0;ileafnum;i+) outfile.write(char *)&headeri.b,sizeof(unsigned char); / 写入字符headeri.count=strlen(headeri.bits); / 不再设置其他变量,权值这时已无使用价值 ,可以用相应结点的权值变量记录长度outfile.write(char *)&headeri.count,sizeof(unsigned char); / 写入长度的 ASCII码if(headeri.count%8=0) bytelen=headeri.count/8; else bytelen=headeri
7、.count/8+1; strcat(headeri.bits,0000000); / 在编码后面补 0，使其最后凑满 8 的倍数，/ 超过无妨，可以用bytelen 控制好写入字节的长度 for(int j=0;jbytelen;j+) temp=ctoa(headeri.bits); . . outfile.write(char *)&temp,sizeof(unsigned char); strcpy(headeri.bits,headeri.bits+8); cout 该文件的哈夫曼的编码为 :endl; for(i=0;iflength;i+) coutheaderi.bitsend
8、l; / 此循环结束后就完成了编码对照表的写入(3) 解压文件输入一个待解压的压缩文件名称(可带路径)如:D:lulu.COD 从文件中读出哈夫曼树 ,并利用哈夫曼树将编码序列解码；生成(还原)文本文件。文件文件名称=压缩文件名 +_new.txt 如:D:lulu_new.txt while(1) while(readlen(clength-8)&strlen(buf)=256) / 处理缓冲区，直到少于256 位，再读满它 for(i=0;i=flength) break; / 如果写入达到原文件长度，退出/while if(readlen=(clength-8)/*编码长度 */|wri
9、telen=flength) break; / 如果写入或者读入编码完毕，退出/ 退出此循环后，还有未解码完成的buf / 对 buf 缓冲的善后处理. . while(writelenflength) for(i=0;istrlen(buf);i+) strcpy1(buf1,buf,i+1); if(strcmp1(buf1,header,n,temp)=1) outfile.write(char *)&temp,sizeof(unsigned char); writelen+; strcpy(buf,buf+i+1); break; /for infile.close(); / 关闭文件
10、outfile.close(); 四、界面设计程序包含压缩功能，解压功能，输出功能，帮助，终止程序功能。五、运行测试与分析（1）运行程序，显示提示，如图1.2 所示。. . 图 1.2 启动界面（2）编码操作。图 1.3 在 D 盘中建立一个文本文档，并命名为123.txt 图 1.4 文件压缩，输出哈弗曼编码界面图 1.5 在盘中生成一个 COD 的文档，并且名为12.COD: . . （3）解码操作。根据实验要求输出实验结果。如图1.4 所示。图 1.4 数据结果输出界面(4) 显示数据内容若用户想知道文本输入的内容，可输入“ L”，然后界面提示输入文本文件的路径和文件名，完成输入后按回车键，界面会出现文本的内容。六、实验收获与思考在完成实验的过程中， 使我明白了面向对象与面向对象的差别。在面向对象过程中，类的设计是至关重要的， 类设计好了等于程序就成功了一半，所以这次的课程帮助我复习了这一学期面向对象课程的学习，刚好可以弥补这一学期面向对象学习的不足。 同时，也使我对数据结构与算法的知识有了一定的了解，帮我. . 在大二学习数据结构与算法的课程中奠定了一定的基础，使我以后学习数据结构与算法的时候可以更加轻松。教师评分：教师签字：
