数据结构”课程设计报告（哈夫曼编码/译码器的实现）学生姓名： _ 指导教师： _______ 所 在 系： 电 子 信 息 系 __ 所学专业： 计算机科学与技术_ 年 级： 目录1、需求分析 11.1课程设计要求 11.2选题的意义及背景 11.3本组课程设计目标 12、概要分析 22.1输出哈夫曼树 22.2哈夫曼编码 22.3哈夫曼译码 33、详细设计 43．1哈夫曼建树 43.2哈夫曼编码 43.3哈夫曼译码 43.4主函数 54、调试分析 54.1输入要压缩的文件 54.2读文件并计算字符频率 64.3根据字符的频率，利用Huffman编码思想创建Huffman树 64.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩 64.5解码压缩即根据Huffman树进行译码 65、用户手册 86、测试结果 97、总结 108、参考文献 119、小组人员分工 11 1、需求分析1.1课程设计要求基于哈夫曼编码的思想进行文件的压缩处理(1) 能够将一个文件进行编码压缩(2) 能够将压缩的文件解码还原1.2选题的意义及背景锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。
在信息传递时，希望长度能尽可能短，即采用最短码赫夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间1.3本组课程设计目标实现赫夫曼树的建立，赫夫曼编码的对对应的文件进压缩和对压缩文件的进行译码调试程序，最后完成程序设计，完成设计报告，总结经验2、概要分析主要模块及调用关系建立哈夫曼树 根据哈夫曼树解码对二进制文件进行解码统计字符，得出统计出字符的权值n根据哈夫曼树编码对编码进行压缩生成哈夫曼树生成二进制文件生成对应文件2.1输出哈夫曼树求字符结点数const unsigned int n=256; //字符数const unsigned int m=256*2-1; //结点总数用类编码哈夫曼树class HuffmanTree{ //Huffman树 public: void Code(); //编码 void UnCode(); //译码private: HTNode HT[m+1]; //树结点表(HT[1]到HT[m]) char Leaf[n+1]; ｝; //叶结点对应字符(leaf[1]到leaf[n])2.2哈夫曼编码char *HuffmanCode[n+1]; //叶结点对应编码(*HuffmanCode[1]到*HuffmanCode[n]) unsigned int count; //频度大于零的字符数 unsigned int char_index[n]; //字符对应在树结点表的下标(char_index[0]到char_index[n-1]) unsigned long size; //被压缩文件长度 FILE *infp,*outfp; //输入/出文件 Buffer buf; //字符缓冲 void Stat(); //统计字符出现频度并过滤掉频度为零的字符 //在HT[0]~HT[k]中选择parent为-1，树值最小的两个结点s1,s2 void Select(unsigned int k, unsigned int &s1, unsigned int &s2); void Write(unsigned int bit); //向outfp中写入一个比特 void Write(unsigned int num,unsigned int k);//向outfp中写入k个比特 void WriteToOutfp(); //强行写入outfpint NToBits(unsigned int num); //0~num之间的整数用二进位表示所需的最少位数2.3哈夫曼译码void Read(unsigned int &bit); //从infp中读出一个比特void Read(unsigned int &num,unsigned int k);//从infp中读出k个比特int NToBits(unsigned int num); //0~num之间的整数用二进位表示所需的最少位数void CreateFromCodeFile(); //由编码文件中存储的树结构建立Huffman树 void CreateFromSourceFile();//由被压缩文件建立Huffman树,将树结构存入编码文//件的文件头部中,并求每个字符的Huffman编码 3、详细设计3．1哈夫曼建树统计字符得出结果字符的权值，然后建立对应的哈夫曼树。
CreateFromCodeFile();Read(bit);for(i=0;i
void HuffmanTree::Write(unsigned int bit){buf.bits++; buf.ch=(buf.ch<<1)+bit; if(buf.bits==8){fputc(buf.ch,outfp); buf.bits=0; buf.ch=0;} }void HuffmanTree::Write(unsigned int num,unsigned int k){ Stack s; unsigned int i,bit; for(i=1;i<=k;i++){ s.push(num & 1); num=(num>>1);} for(i=1;i<=k;i++){ s.top(bit); Write(bit); s.pop();} }3.4主函数利用switch函数实现选择编码和译码，以实现整个程序的功能while(c!='3') { cout<>c; switch(c){ case '1': hf.Code(); break; case '2': hf.UnCode();break;} } }4、调试分析4.1输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的选项，依次进行，因为各个环节之间有先后顺序。
第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩若打不开，则继续输入4.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率4.3根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点4.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1读取文件，依次将每个字符用他们的编码表示，即完成一次编码 4.5解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点从根结点开始，每读一个字符，指针变化一次（当读取的字符是‘1’时，指针指向当前所指结点的右孩子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。
将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件结束时为止5、用户手册运行后的主界面会提示用户进行想要的操作1）编码（压缩文件）操作若用户想要对某一文件进行压缩，则按主界面的提示按“1”，然后界面提示输入进行压缩操作的文件路径和文件名（文件大小应小于4GB），输入完成后按回车键，此时界面会提示输入压缩后文件的保存路径及其文件名，输入完成后再按回车键，便可完成编码，系统提示用户压缩文件过程结束2）译码（还原文件）操作若用户想对某一压缩文件进行解压操作，则按主界面的提示按“2”，然后界面提示输入进行解压操作的文件路径和文件名，完成输入后按回车键，此时界面会提示输入解压后的文件的保存路径及其文件名，输入完成后再按回车键，便可完成译码，系统提示用户还原文件过程结束3）操作失败后的界面提示，若用户输入的文件路径和文件名错误，则界面会提示用户文件打开失败的信息用户根据需求，在操作过程中按“3”可随时退出系统注意：选择的文件大小应该大于几十KB，不超过4GB文件过小就没有压缩的意义6、测试结果需进行编码译码的文件类型可任意，测试用例有多种选择，所以选G盘里图片1.bmp（大小为576KB）为本课题测试用例。
测试结果为：原文件经编码后，压缩为s.zip（大小为73KB）形式，在译码解压后，将其还原成d.bmp形式，打开后与原文件完成相同故可利用这种有效的数据压缩技术实现节省数据文件的存储空间和计算机网络的传送时间的功能7、总结在当今信息时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术在课程设计过程中，我们选择《哈夫曼编码/译码的实现》这一课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践这样不但有助于我们消化课堂内容，还可以增强我们的独立思考能力和动手能力；通过编写程序代码和调试运行，我们可以逐步积累调试程序的经验，逐渐培养我们的编程能力和利用计算机解决实际问题的能力课程设计为我们提供了一个自己动手实践的平台通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，利用哈夫曼编码的思想方法，熟练掌握哈夫曼编码的过程创建二叉树的方法和二叉树的存储结构，知道压缩文件是如何进行的，解压缩即为它的逆过程程序的模块化结构尤其重要，应掌握各个模块间的逻辑关系和整体程序的结构在此过程中，我们不但独立思考，还借助各种参考文献来帮助我们完成系统。
更为重要的是，小组成员在对问题的认识方面可以交换不同的意见，老师 的悉心指导给了我们极大的鼓励和帮助！8、参考文献[1] 苏仕华编著.数据结构与算法分析.合肥：中国科技大学出版社，2004[2] 苏仕华等著.数据结构课程设计.北京：机械工业出版社，2005[3] 严蔚敏.吴伟民编著,数据结构C语言版.北京：清华大学出版社,2007[4] 刘正安编著.C++及Windows可视化程序设计.北京：清华大学出版社，2003[5] 严蔚敏，陈文博编著.数据结构及应用算法教程.北京：清华大学出版社，20019、小组人员分工写程序时，根据详细设计，陈竹凌（0882041）编写哈夫曼树，周黄金（0882055）编写编码程序，陈静（0882011）编写译码程序，经过整合我们编写的程序后我们一起设计主程序在一起调试程序，观察程序的正确度，分析程序的性能写实验报告时，需求分析、概要分析和详细设计是周黄金（0882055）所写，调试分析、测试结果和总结是陈静（0882011）所写，用户手册、参考文献和附录均为陈竹凌（0882041）写。