数据结构课程设计+哈夫曼编码译码器.docx

1、哈夫曼编码译码器哈夫曼编码译码器a) 需求分析：一个完整的系统应具有以下功能：(l)I:初始化。从终端读入字符集大小 n，及 n 个字符和 n 个权值， 建立哈夫曼树，并将它存于文件 hfmtree 中。(2) C:编码。利用已建好的哈夫曼树(如不在内存，则从文件 hfmtree 中读入)，对文件 tobetrans 中的正文进行编码，然后将结果存入文件codefile 中。(3) D:编码。利用已建好的哈夫曼树将文件 codefile 中的代码进行译码，结果存入文件 textfile 中。(4) P:印代码文件。将文件 codefile 以紧凑格式显示在终端上，每行50 个代码。同时将此字符

2、形式的编码文件写入文件 codeprint 中。(5) T:印哈夫曼树。将已在内存中的哈夫曼树以直观的方式 (树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件 treeprint 中字符 ABCDEFGHIJKLM频度1866423223210321154757153220字符NOPQRSTUVWXYZ频度20561925051553010112212可以根据题目要求把程序划成 5 个模块，设计成菜单方式，每次执行一个模块后返回菜单。除了初始化(I)过程外，在每次执行时都经过一次读取磁盘文件数据。这是为了如果在程序执行后一直没有进行初始化(I)过程，为了能使后面的操作顺利进行，

3、可以通过读取旧的数据来进行工作。比如：如果程序的工作需要的字符集和权值数据是固定的，只要在安装程序时进行一次初始(I)化操作就可以了。在再次运行程序时，不管进行那项操作都可以把需要的数据读入到内存。b) 概要设计本程序主要用到了三个算法。(1) 哈夫曼编码在初始化(I)的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。先将输入的字符和权值存放到一个结构体数组中，建立哈夫曼树，将计算所得的哈夫曼编码存储到另一个结构体数组中。(2) 串的匹配在编码(D)的过程中间，要对已经编码过的代码译码，可利用循环， 将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较，如果相等就回显并存入文件

4、。(3) 二叉树的遍历在印哈夫曼树(T)的中，因为哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出c） 详细设计构造树的方法如下：初始化：每个字符就是一个结点，字符的频度就是结点的权；1、将结点按频度从小到大排序；2、选取频度最小的两个结点，以它们为儿子，构造出一个新的结点； 新结点的权值就是它两个儿子的权值之和；构造之后，从原来的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去；3、如果结点序列里只剩下一个结点，表示构造完毕，退出。否则回到第一步。编码：上面已经生成了树，接着就该对该树进行编码了。可以假定，对某个结点而言，其左孩子在当前阶段的编码为0，右孩子的编码

5、为1。这样就可以通过“树的遍历”的方式来生成字符编码对照表。来到这里，基本上艰苦的已经完成了，对某个具体的字符串编码和解码就只是简单的“查表替换”的工作了。解码：解码也是个简单的查表-替换过程。如果利用该种编码发送字符串，则它的“字符编码”对应表也必须发送过去，不然对方是不知道怎么解码的。对给出的一串编码，从左向右，将编码组合起来并查表，“一旦”找到有匹配的字符，则马上将当前的编码替换为对应的字符。因为该编码是不会出现“某一个字符的编码是另一个字符编码的前缀”这种情况的，也就是不会出现类似于“A00B0010”这样的情况， 所以解码出来的字符串是唯一的，而且就是原来进行编码的那一个。程序如下#

6、include #include #include using namespace std;struct HuffmanNode/定义哈夫曼树各结点int weight;/存放结点的权值，假设只考虑处理权值为整数的情况int parent;/记录结点父亲位置，-1 表示为根结点，否则表示为非根结点int lchild,rchild;/分别存放该结点的左、右孩子的所在单元的编号;class HuffmanTree/建立哈夫曼树类private:HuffmanNode *Node;/哈夫曼树中结点的存储结构char *Info;/用来保存各字符信息int LeafNum;/树中的叶子结点总数pub

7、lic:HuffmanTree();/构造函数HuffmanTree();/析构函数void Initialization(int WeightNum);/初始化函数：根据 WeightNum 个权值建立一棵哈夫曼树void Encoder();/编码函数：利用构造好的哈夫曼树对字符进行编码void Decoder();/译码函数：对二进制串进行译码void Print();/印文件函数：把已保存好的编码文件显示在屏幕void TreePrinting();/印哈夫曼树函数：将已在内存中的哈夫曼树以直观的方式显示在终端上;/程序名：HuffmanTree.cpp/程序功能：实现哈夫曼树类的源文

8、件(并用其来实现编/译码)/构造函数/函数功能：将结点指针初始化为 NULL HuffmanTree:HuffmanTree()Node=NULL;/将树结点初始化为空Info=NULL;/将字符数组初始化为空LeafNum=0;/将叶子数初始化为 0/ 析构函数/ 函数功能：将所有结点的空间释放/ 函数参数：无/ 参数返回值：无HuffmanTree:HuffmanTree()delete Node;/释放结点空间delete Info;/释放字符存储空间/初始化函数/函数功能：从终端读入字符集大小 n，以及 n 个字符和 n 个权值,/建立哈夫曼树,并将它存放在文件 hfmTree 中./

9、函数参数：int WeightNum 表示代码个数/参数返回值：无void HuffmanTree:Initialization(int WeightNum)/初始化int i,j,pos1,pos2,max1,max2;Node=new HuffmanNode2*WeightNum-1;/WeightNum 权值对应的哈夫曼树中的结点总数为 2*WeightNum-1 个Info=new char2*WeightNum-1; for(i=0;iWeightNum;i+)cout请输入第i+1个字符值; getchar();/丢弃字符t与nInfoi=getchar();/输入一个字符,主要是

10、考虑输入空格而采用这种形式的getchar();coutNodei.weight;/输入权值Nodei.parent=-1;/为根结点Nodei.lchild=-1;/无左孩子Nodei.rchild=-1;/无右孩子for(i=WeightNum;i2*WeightNum-1;i+) /表示需做 WeightNum-1 次合并pos1=-1;pos2=-1;/分别用来存放当前最小值和次小值的所在单元编号max1=32767;/32767 为整型数的最大值max2=32767;/分别用来存放当前找到的最小值和次小值for(j=0;ji;j+)/在跟节点中选出权值最小的两个if(Nodej.pa

11、rent=-1)/是否为根结点if(Nodej.weightmax1)/是否比最小值要小max2=max1;/原最小值变为次小值max1=Nodej.weight;/存放最小值pos2=pos1;/修改次小值所在单元编号pos1=j;/修改最小值所在单元编号elseif(Nodej.weightmax2)/比原最小值大但比原次小值要小max2=Nodej.weight;/存放次小值pos2=j;/修改次小值所在的单元编号/forNodepos1.parent=i;/修改父亲位置Nodepos2.parent=i;Nodei.lchild=pos1;/修改儿子位置Nodei.rchild=pos

12、2;Nodei.parent=-1;/表示新结点应该是根结点Nodei.weight=Nodepos1.weight+Nodepos2.weight; /for LeafNum=WeightNum;char ch;coutch;if(ch=y|ch=Y)ofstream fop;/以二进制方式打开 hfmTree.dat 文件，并当重新运行时覆盖原文件fop.open(hfmTree.dat,ios:out|ios:binary|ios:trunc); if(fop.fail()/文件打开失败cout文件打开失败！n;fop.write(char*)&WeightNum,sizeof(Weig

13、htNum);/写入 WeightNum for(i=0;iWeightNum;i+)/把各字符信息写入文件fop.write(char*)&Infoi,sizeof(Infoi); flush(cout);for(i=0;i2*WeightNum-1;i+)/把个节点内容写入文件fop.write(char*)&Nodei,sizeof(Nodei); flush(cout);fop.close();/关闭文件cout哈夫曼树已构造完成。n;/Initialization/编码函数/函数功能：利用已建立好的哈夫曼树（如不在内存，则从文件 hfmTree 中读入），/对文件 ToBeTran

14、中的正文进行编码,然后将结果代码存(传输)到文件CodeFilevoid HuffmanTree:Encoder()if(Node=NULL)/哈夫曼树不在内存，从文件 hfmTree 中读入ifstream fip;/以二进制方式打开 hfmTree.dat 文件fip.open(hfmTree.dat,ios:binary|ios:in); if(fip.fail()/文件打开失败cout文件打开失败！n; return;/结束本函数fip.read(char*)&LeafNum,sizeof(LeafNum);/读取叶子数Info=new charLeafNum;Node=new Huf

15、fmanNode2*LeafNum-1;for(int i=0;iLeafNum;i+)/读取字符信息fip.read(char*)&Infoi,sizeof(Infoi); for(i=0;i2*LeafNum-1;i+)/读取结点信息fip.read(char*)&Nodei,sizeof(Nodei);char *Tree;/用于存储需编码内容int i=0,num;char Choose;/让用户选择读取文件或重新输入需编码内容coutChoose;if(Choose=1)/读取文件 ToBeTran.txtifstream fip1(ToBeTran.txt); if(fip1.fa

16、il()/文件不存在cout文件打开失败!n; return;/结束本函数char ch; int k=0;while(fip1.get(ch)k+;/计算 CodeFile 中代码长度fip1.close();Tree=new chark+1;ifstream fip2(ToBeTran.txt); k=0;while(fip2.get(ch)Treek=ch;/读取文件内容，并存到 Tree 中k+;fip2.close();Treek=0;/结束标志cout 需 编 码 内 容 为 :; coutTreeendl;/if(Choose=1)else/Choose!=1,重新输入strin

17、g tree;/用于输入需编码内容，由于 string 类对象可以输入任意长度，/所以先利用这个对象输入，再转存在 Tree 中cin.ignore();cout请输入需要编码的内容(可输入任意长，结束时请按 2 下回车):n; getline(cin,tree,n);/输入任意长字符串，/getline 以回车(n)作为结束符，第一次按回车表示字符串结束，第二次按回车才开始输出。while(treei!=0) i+;num=i;/计算 tree 长度i=0;Tree=new charnum+1;while(treei!=0)/将 tree 中的字符转存到 Tree 中Treei=treei;

18、 i+;Treei=0;/结束标志符ofstream fop(CodeFile.dat,ios:trunc);/存储编码后的代码,并覆盖原文件i=0;int k=0; char *code;code=new charLeafNum;/为所产生编码分配容量为 LeafNum 的存储空间/因为不等长编码中最长的编码一定不会超过要求编码的字符个数while(Treek!=0)/对每一个字符编码int j,start=0; for(i=0;iLeafNum;i+)if(Infoi=Treek)/求出该文字所在单元的编号break;j=i;while(Nodej.parent!=-1)/结点 j 非树根

19、j=Nodej.parent;/非结点 j 的双亲结点if(Nodej.lchild=i)/是左子树，则生成代码 0 codestart+=0;else/是右子树，则生成代码 1 codestart+=1;i=j;codestart=0;/置串结束符for(i=0;istart/2;i+)/对二进制序列进行逆置j=codei; codei=codestart-i-1; codestart-i-1=j;i=0;while(codei!=0)/存储代码fopcodei; i+;k+;fop.close();cout已编码！且存到文件 CodeFile.dat 中！nn;/Encode/译码函数/函

20、数功能：利用已建好的哈夫曼树,对传输到达的 CodeFile 中的数据代码进行译码,/将译码结果存入文件 TextFile 中. void HuffmanTree:Decoder()int i=0,k=0;int j=LeafNum*2-1-1;/表示从根结点开始往下搜索char* BitStr;ifstream fip1(CodeFile.dat);/利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码if(fip1.fail()/文件打开失败，还未编码cout请先编码！n; return;cout经译码,原内容为:; char ch;while(fip1.get(ch)k+;/计

21、算 CodeFile 中代码长度fip1.close();BitStr=new chark+1; ifstream fip2(CodeFile.dat); k=0;while(fip2.get(ch)BitStrk=ch;/读取文件内容k+;fip2.close();BitStrk=0;/结束标志符if(Node=NULL)/还未建哈夫曼树cout请先编码!n; return;ofstream fop(TextFile.dat);/将字符形式的编码文件写入文件 CodePrin 中while(BitStri!=0)if(BitStri=0)j=Nodej.lchild;/往左走elsej=No

22、dej.rchild;/往右走if(Nodej.rchild=-1)/到达叶子结点coutInfoj;/输出叶子结点对应的字符j=LeafNum*2-1-1;/表示重新从根结点开始往下搜索fopInfoj;/存入文件/if、i+;/while fop.close();coutn 译码成功且已存到文件 TextFile.dat 中！nn;/Decoder/印文件代码函数/函数功能：将文件 CodeFile 以紧凑格式显示在终端上，/每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。/函数参数：无/参数返回值：无void HuffmanTree:Print()char

23、ch; int i=1;ifstream fip(CodeFile.dat);/读取文件ofstream fop(CodePrin.dat);/存储文件if(fip.fail()cout没有文件，请先编码！n; return;while(fip.get(ch)coutch;/读取文件内容fopch;/存到文件中if(i=50)/每行输出 50 个字符coutendl; i=0;i+;coutendl;fip.close();/关闭 CodeFile.dat 文件fop.close();/关闭 CodePrin.dat 文件/显示哈夫曼树函数/函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹

24、入表的形式)显示在终端上，/同时将此字符形式的哈夫曼树写入文件 TreePrint 中。void HuffmanTree:TreePrinting()if(Node=NULL)/未建立哈夫曼树cout请先建立哈夫曼树！n; return;ofstream fop(TreePrint.dat);cout结点位置(权值)编码左孩子编码右孩子(表示叶子)n;fop结点位置(权值)编码左孩子编码LeafNum-1;i-)/输出哈夫曼树couti(Nodei.weight)-1-Nodei.lchild(NodeNodei.lchild.weight)-0-Nodei.rchild(NodeNodei.

25、rchild.weight)endl; fopi(Nodei.weight)-1-Nodei.lchild(NodeNodei.lchild.weight)-0-Nodei.rchild(NodeNodei.rchild.weight)=0;i-)couti:Nodei.weight(Infoi)-n;fopi:Nodei.weight(Infoi)-n;/程序功能：主函数源文件/主函数int main()cout欢迎使用哈夫曼码的编/译码系统!n;cout在此系统中可以进行以下操作:n; cout(1) 初始化(I);n;cout(2) 编码(E);n;cout(3) 译码(D);n;cout(4) 代码文件(P);n;cout(5) 印哈夫曼树(T)n;cout(6) 退出(Q)nn;HuffmanTree huftree;/定义哈夫曼树对象int weight;char Choose;while(1)coutChoose;switch(Choose)case I:case i:coutweight;huftree.Initialization(weight);/初始化哈夫曼树break;case E:case e:huftree.Encoder(); break;case D:case d:huftree.Decoder(); break;case