《数据结构》课程设计数学与应用数学一班胡耕岩2012214147一、问题分析和任务定义1.1设计任务采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。

要求（1）运行时的压缩原文件的规模应不小于5K。

（2）提供恢复文件与原文件的相同性对比功能。

1.2问题分析本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。

在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。

哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。

在文本文件中多采用二进制编码。

为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。

设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。

若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。

为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。

哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。

统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。

利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。

则概率越大的节点，路径越短。

哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。

哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。

总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。

其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。

1.3测试用数据本实验的数据是通过读入一个名为huffman.txt的文本文档，文档中内容为字符型数据。

二、概要设计和数据结构的选择以下是在任务分析对题意的理解做出的概要设计和对数据结构的选择：1、数据结构定义//huffman树的结点结构体typedef struct HTnode{long weight; //记录结点的权值int parent; //记录结点的双亲结点位置int lchild; /结点的左孩子int rchild; //结点的右孩子int *code; //记录该结点的huffman编码int codelen; //记录该结点huffman编码的长度//初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode(){weight = MAX;parent = -1;lchild = -1;rchild = -1;codelen = 0;}}HTnode;2、定义huffman数类及其函数class huffmanTree{public:huffmanTree();virtual ~huffmanTree();bool count(char *input); //压缩时统计各字符出现的次数，将其写入对应结点的权值void create(); //压缩时根据各结点的权值构造huffman树void code(); //压缩时利用huffman树计算每个字符的huffman编码void printcode(); //列出每个字符的huffman编码void addbit(int bit); //压缩时对一个未满8个bit的byte中加入一个bitvoid resetbyte(); //将byte清空bool compress(char *input, char *output);//压缩函数,成功返回true 失败falsebool decompress(char *input, char *output); //恢复函数,成功返回true 失败falsevoid compare(char *input, char *output); //将原文件与压缩后的文件比较void compare2(char *input, char *output); //将原文件与恢复后的文件比较private:int root; //记录根结点的位置int leafnum; //记录不同字符的个数HTnode HT[leaf*2-1]; //HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1char byte; //压缩文件时用来缓冲bit的变量int bitsnum; //byte中bit的个数int lacknum; //压缩到最后byte中的bit不满8个时填充的0的个数};3、主程序的流程及模块间关系主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：1:压缩函数bool compress(char *input, char *output)2:恢复函数bool d ecompress(char *input, char *output)3:恢复文件与原文件的对比函数void compare2(char *input, char *output)并可在完成相应功能后安全退出，压缩或恢复的文件在同文件夹下生成。

三、详细设计和编码核心算法----huffman算法：（1）根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一个带权的w1的根据点，其左右子树均空。

（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。

（3）在F中删除这两棵树，同时将所得到的二叉树加入F中。

（4）重复（2）(3),直到F中只含一棵树为止。

这棵树便是Huffman树。

Huffman 树可用于构造代码总长度最短的编码方案。

为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL（树的带权路径长度）不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。

权值越大的结点离根越近的二叉树才是最优二叉树（huffman树）。

按照上面的算法，则可按照下面图的构造过程生成huffman树。

主程序模块:Huffman编码流程Huffman解码流程四、上机调试以下是我在上机过程中遇到的一些问题及解决方案开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就huffman编码是采用等长编码还是采用不等长问题，采用不登长编码要避免译码的二义性或多义性。

假设用0表示字符D,用01表示字符C则当接受到编码串“…01…”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。

因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。

符合此要求的编码叫做前缀编码。

显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。

为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。

因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的huffman 树的问题。

基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些语法错误,修正后编译通过。

运行程序如下图所示图5 程序主菜单压缩：在命令行下输入1对文件进行压缩，根据提示输入刚刚建的文本文件（huffman.txt），和要生成的压缩文件名称，按回车确认进行压缩。

图6 压缩文本成功执行完毕后如下图所示。

图7 压缩完毕恢复：在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称和恢复后的文件名称，按回车确定，成功执行后如下图所示。

图7 文件恢复完毕对比：在命令行下输入3对恢复后的文件和原文件对比，根据提示输入要对比的文件，按回车确认，成功执行后如下图所示。

图8 文件恢复完毕五、测试结果程序功能满足设计要求，测试未发现明显bug，详细可参见五使用说明。

程序如下:// stdafx.h#include <iostream> //输入输出头文件#include <fstream> //文件操作的类和方法#include <queue> //队列容器using namespace std;const int leaf = 256; //最多可能出现的不同字符数const long MAX = 99999999; //表示无穷大//huffman树的结点结构体typedef struct HTnode{long weight; //记录结点的权值int parent; //记录结点的双亲结点位置int lchild; //结点的左孩子int rchild; //结点的右孩子int *code; //记录该结点的huffman编码int codelen; //记录该结点huffman编码的长度//初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode(){weight = MAX;parent = -1;lchild = -1;rchild = -1;codelen = 0;}}HTnode;//##############################################################//huffmanTree.h//huffman树类class huffmanTree{public:huffmanTree();virtual ~huffmanTree();bool count(char *input); //压缩时统计各字符出现的次数，将其写入对应结点的权值void create(); //压缩时根据各结点的权值构造huffman树void code(); //压缩时，利用建好的huffman树计算每个字符的huffman编码void printcode(); //列出每个字符的huffman编码void addbit(int bit); //压缩时对一个未满8个bit的byte中加入一个bitvoid resetbyte(); //将byte清空bool compress(char *input, char *output); //压缩函数成功执行返回true 失败falsebool decompress(char *input, char *output); //恢复函数成功执行返回true 失败falsevoid compare(char *input, char *output); //将原文件与压缩后的文件比较void compare2(char *input, char *output); //将原文件与恢复后的文件比较private:int root; //记录根结点的位置int leafnum; //记录不同字符的个数HTnode HT[leaf*2-1]; //HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1char byte; //压缩文件时用来缓冲bit的变量int bitsnum; //byte中bit的个数int lacknum; //压缩到最后byte中的bit不满8个时填充的0的个数};//##############################################################//huffmanTree.cpp#include "stdafx.h"#include "huffmanTree.h"//////////////////////////////////////////////////////////////////////// Construction/Destruction//////////////////////////////////////////////////////////////////////huffmanTree::huffmanTree(){//初始化成员变量root = 0;leafnum = 0;byte = 0;bitsnum = 0;lacknum = 0;}huffmanTree::~huffmanTree(){for(int i=0; i<leaf; i++){if(HT[i].codelen != 0)delete []HT[i].code;}}//统计各字符出现的次数bool huffmanTree::count(char *input){ifstream ifs;char c;ifs.open(input,ios::binary);if(!ifs){cout << "无法打开文件" << input << '!' << endl;return false;}while(ifs.get(c)){if(HT[c+128].weight==MAX){ //若该字符是第一次出现，先初始化权值HT[c+128].weight = 0;leafnum++;}HT[c+128].weight++; //权值+1}ifs.close();return true;}//选权值最小的两棵树组成新的数void huffmanTree::create(){for(int i=leaf; i<2*leaf-1; i++){int loc1=-1, loc2=-1;for(int j=0; j<i; j++){if(HT[j].parent != -1)continue;if(loc1==-1 || HT[j].weight < HT[loc1].weight){loc2 = loc1;loc1 = j;}else if(loc2==-1 || HT[j].weight < HT[loc2].weight)loc2 = j;}if(HT[loc1].weight==MAX || HT[loc2].weight==MAX || loc2==-1) //只剩一棵树，结束break;HT[i].weight = HT[loc1].weight + HT[loc2].weight;//为了减少压缩文件中需要写入的huffman树的信息，约定小标小的结点做为双亲结点的左孩子HT[i].lchild = loc1>loc2 ? loc2 : loc1;HT[i].rchild = loc1>loc2 ? loc1 : loc2;HT[loc1].parent = i; HT[loc2].parent = i;root = i;}}//列出每个字符的huffman编码void huffmanTree::printcode(){for(int i=0; i<leaf; i++){if(HT[i].codelen!=0){cout << "值为" << i-128 << "的字符的huffman编码：";for(int j=0; j<HT[i].codelen; j++){cout << HT[i].code[j];}cout << endl;}}}//压缩时，利用建好的huffman树计算每个字符的huffman编码void huffmanTree::code(){for(int i=0; i<leaf; i++){int len=0;int loc=i;while(HT[loc].parent!=-1){ //计算huffman编码长度len++;loc = HT[loc].parent;}HT[i].codelen = len;HT[i].code = new int[len];loc = i;for(int j=len-1; j>=0; j--){ //从后往前找，记录结点的huffman编码if(loc==HT[HT[loc].parent].lchild)HT[i].code[j] = 0;elseHT[i].code[j] = 1;loc = HT[loc].parent;}}}//压缩时对一个未满8个bit的byte中加入一个bitvoid huffmanTree::addbit(int bit){if(bit == 0)byte = byte << 1; //若新增的bit为0，则直接将byte按位左移elsebyte = ((byte << 1) | 1); //若新增的bit为1，先将byte按位左移，再与1按位或运算bitsnum++;}//将byte清空void huffmanTree::resetbyte(){byte = 0;bitsnum = 0;}//压缩函数成功执行返回true 失败falsebool huffmanTree::compress(char *input, char *output){if( !count(input) )return false;create();code();ifstream ifs;ofstream ofs;ifs.open(input,ios::binary);ofs.open(output,ios::binary);char c;if(!ifs){cout << "无法打开文件" << input << '!' << endl;return false;}if(!ofs){cout << "无法打开文件" << output << '!' << endl;return false;}ofs.put(0); //预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384); //将根节点的位置-384写入（为使该值不超过char的最大表示范围）for(int i=0; i<leaf*2-1; i++){ //写入每个结点的双亲结点位置if(HT[i].parent==-1) //若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)ofs.put(127);else //否则将双亲结点的位置-384再写入（为使该值不超过char的最大表示范围）ofs.put(HT[i].parent-384);}while(ifs.get(c)){ //将字符的huffman编码并加入byte中int tmp = c+128;for(int i=0; i<HT[tmp].codelen; i++){addbit(HT[tmp].code[i]);if(bitsnum==8){ //若byte已满8位，则输出该byte并将byte清空ofs.put(byte);resetbyte();}}}if(bitsnum!=0){ //处理最后未满8个字符的byte，用0填充并记录填充的个数for(int i=bitsnum; i<8; i++){addbit(0);lacknum++;}ofs.put(byte);resetbyte();}ofs.seekp(0,ios::beg); //将写指针移动到文件开头ofs.put(lacknum); //写入最后一个字节缺失的bit个数ifs.close();ofs.close();return true;}//恢复函数成功执行返回true 失败falsebool huffmanTree::decompress(char *input, char *output){queue<char> q;char c;ifstream ifs;ofstream ofs;ifs.open(input,ios::binary);ofs.open(output,ios::binary);if(!ifs){cout << "无法打开文件" << input << '!' << endl;return true;}if(!ofs){cout << "无法打开文件" << output << '!' << endl;return false;}ifs.get(c);lacknum = c; //读出最后一个字节缺失的bit个数ifs.get(c);root = c+384; //读出根结点的位置for(int i=0; i<leaf*2-1; i++){ //建立各结点之间的双亲孩子关系ifs.get(c);if(c==127)continue;else{HT[i].parent = c+384;if(HT[c+384].lchild==-1)HT[c+384].lchild = i;elseHT[c+384].rchild = i;}}int point = root;//为了方便处理最后一个可能有缺失bit的字节，先将读出的数据放入队列while(ifs.get(c))q.push(c);//还原文件过程while(q.size()>1){ //还未到最后一个字节c = q.front();for(int i=0; i<8; i++){if(int(c&128)==0){point = HT[point].lchild;if(HT[point].lchild==-1 && HT[point].rchild==-1){ofs.put(char(point-128));point = root;}c = c << 1;}else{point = HT[point].rchild;if(HT[point].lchild==-1 && HT[point].rchild==-1){ofs.put(char(point-128));point = root;}c = c << 1;}}q.pop();}c = q.front(); //最后一个字节for(i=0; i<8-lacknum; i++){if(int(c&128)==0){point = HT[point].lchild;if(HT[point].lchild==-1 && HT[point].rchild==-1){ofs.put(char(point-128));point = root;}c = c << 1;}else{point = HT[point].rchild;if(HT[point].lchild==-1 && HT[point].rchild==-1){ofs.put(char(point-128));point = root;}c = c << 1;}}q.pop();ifs.close();ofs.close();return true;}//将原文件与压缩后的文件比较void huffmanTree::compare(char *input, char *output) {ifstream origin, compress;origin.open(input,ios::binary);compress.open(output,ios::binary);if(!origin){cout << "无法打开文件" << input << '!' << endl;return;}if(!compress){cout << "无法打开文件" << output << '!' << endl;return;}double total1=0, total2=0;char c;while(origin.get(c))total1++;while(compress.get(c))total2++;cout << "原文件大小：" << total1 << " Byte" << endl;cout << "压缩后大小：" << total2 << " Byte" << endl;cout << "压缩率：" << total2/total1*100 << '%' << endl;origin.close();compress.close();}//将原文件与恢复后的文件比较void huffmanTree::compare2(char *input, char *output){ifstream origin, decompress;origin.open(input,ios::binary);decompress.open(output,ios::binary);double total1=0, total2=0;char c1, c2;bool dif = false;while(origin.get(c1) && decompress.get(c2)){if(c1!=c2) //依次比较每个字节，不同则将dif标志设为true dif = true;total1++;total2++;}while(origin.get(c1)){ //若原文件还有剩余的数据，将dif设为truedif = true;total1++;}while(decompress.get(c2)){ //若恢复文件还有剩余的数据，将dif设为truedif = true;total2++;}cout << "原文件大小：" << total1 << " Byte" << endl;cout << "恢复文件大小：" << total2 << " Byte" << endl;if(dif==true)cout << "原文件与恢复文件不同!" << endl;elsecout << "原文件与恢复文件相同!" << endl;origin.close();decompress.close();}//############################################################## //huffman.cpp#include "stdafx.h"#include "huffmanTree.h"void main(){int choice = 1;char input[255], output[255];huffmanTree h;while(choice){cout<<" ***************************************************"<<endl;cout<<" * 哈夫曼编码压缩恢复算法*"<<endl;cout<<" * *"<<endl;cout<<" * 1)压缩*"<<endl;cout<<" * *"<<endl;cout<<" * 2) 恢复*"<<endl;cout<<" * *"<<endl;cout<<" * 3) 恢复文件与原文件的对比*"<<endl;cout<<" * *"<<endl;cout<<" * 4) 清屏*"<<endl;cout<<" * *"<<endl;cout<<" * 5) 退出*"<<endl;cout<<" * *"<<endl;cout<<" * 说明：请您输入相应的操作序号进行操作*"<<endl;cout<<" ****************************************************"<<endl;cout<<">";cin >> choice;switch(choice){case 1:{cout << "请输入待压缩的文件名：";cin >> input;cout << "请输入压缩后的文件名：";cin >> output;if( press(input,output)){h.printcode();pare(input,output);cout<<endl<<"文件压缩成功!"<<endl;}else{cout<<endl<<"文件压缩失败!"<<endl;}}break;case 2:{cout << "请输入待恢复的文件名：";cin >> input;cout << "请输入恢复后的文件名：";cin >> output;if (h.decompress(input,output))cout<<endl<<"文件恢复成功!"<<endl;elsecout<<endl<<"文件恢复失败!"<<endl;}break;case 3:{cout << "请输入原文件的文件名：";cin >> input;cout << "请输入恢复文件的文件名：";cin >> output;pare2(input,output);}break;case 4:{//执行清屏命令system("cls");}break;case 5:break;default:cout << "参数错误！请重新输入" << endl;}cout << endl;}}。