数据结构哈夫曼树编码译码实验报告

1、【详细设计】具体代码实现如下：/Haffma nTree.h#in clude<iostream>#in clude<fstream>#in clude<stri ng>struct Huffma nN ode /哈夫曼树的一个结点int weight;int pare nt;int lchild,rchild;class Huffma nTree / 哈夫曼树private:Huffma nN ode *Node; /Node存放哈夫曼树char *Info; /In fo存放源文用到的字符源码，如 a','b','c

2、9;,'d','e'，此内容可以放入结点中，不单独设数组存放int LeafNum; /哈夫曼树的叶子个数，也是源码个数public:Huffma nTree();void CreateHuffma nTree(); /*种建立哈夫曼树的方法中选择：重，建立哈夫曼树，入哈夫曼树信息，建立哈夫曼树Huffma nTree();在内存中建立哈夫曼树，存放在Node中。 让用户从两1.从键盘读入源码字符集个数，每个字符，和每个字符的权并将哈夫曼树写入文件 hfmTree中。2.从文件hfmTree中读*/ void CreateHuffma nTreeFromKeyb

3、oard();void CreateHuffma nTreeFromFile();void Encoder(); /*使用建立好的哈夫曼树(如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树)，对文件ToBeTran中的正文进行编码，并将码文写入文件 CodeFile中。 ToBeTra n的内容可以用记事本等程序编辑产生。*/void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树(如果不在内存，void Prin tCodeFile(); /* void Prin tHuffma nTree(); /* 他树形表示法)显示在屏幕上,则

4、从文件hfmTree中读入并建立内存里的哈夫曼树)将码文译码， 得到的源文写入文件 TextFile 中，并同时输出到屏幕上。*/将码文文件CodeFile显示在屏幕上*/将哈夫曼树以直观的形式(凹入表示法，或广义表，或其同时写入文件 TreePri ntFile中*/void PrintHuffmanTree_aoru(int T,int layer=1);/* 凹入表示法 显示哈夫曼树，由PrintHuffmanTree()调用 */；/Huffma nTree.cpp#in clude<stri ng>#i nclude<limits> /为使用整型最大值#in

5、clude"Huffma nTree.h"using n amespace std;/*Huffma nTree:Huffma nTree()Node=NULL;/*Huffma nTree:Huffma nTree()deleteNode;/*void Huffma nTree:CreateHuffma nTree()char Choose;cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2) ？"cin> >Choose;if(Choose=2) /键盘输入建立哈夫曼树CreateHuffma nTr

6、eeFromKeyboard();/choose='2'else /从哈夫曼树文件 hfmTree.dat中读入信息并建立哈夫曼树CreateHuffma nTreeFromFile();/*void Huffma nTree:CreateHuffma nTreeFromKeyboard()int Num;cout<<"n请输入源码字符集个数："cin»Num;if (Num<=1)cout<<"无法建立少于2个叶子结点的哈夫曼树。nn"return;LeafNum=Num;Node=new Huf

7、fma nN ode2*Num-1;Info=new char2*Num-1;for(i nt i=0;i<Num;i+) /读入哈夫曼树的叶子结点信息cout<<"请输入第"<<i+1<<"个字符值"getchar();In foi=getchar(); /源文的字符存入字符数组In fogetchar();cout<<"请输入该字符的权值或频度"cin >>Nodei.weight; /源文的字符权重存入Node.weightNodei.pare nt=-1;Nod

8、ei.lchild=-1;Nodei.rchild=-1;for(i=Num;i<2*Num-1;i+)/循环建立哈夫曼树内部结点int pos1=-1,pos2=-1;int max 仁32767,max2=32767;for(i nt j=O;j<i;j+)在根节点中选出权值最小的两个if(Nodej.pare nt=-1) 是否为根结点 if(Nodej.weight<max1)max2=max1;max1=Nodej.weight;pos2=pos1;pos1=j;elseif(Nodej.weight<max2)max2=Nodej.weight;pos2=j

9、;Nodepos1.pare nt=i;Nodepos2.pare nt=i;Nodei.lchild=pos1;Nodei.rchild=pos2;Nodei.pare nt=-1; Nodei.weight=Nodepos1.weight+Nodepos2.weight; /forcout<<"哈夫曼树已成功构造完成。n"II把建立好的哈夫曼树写入文件hfmTree.datchar ch;cout<<"是否要替换原来的哈夫曼树文件(Y/N):"cin> >ch;if (ch!='y'&&am

10、p;ch!='Y') return;else ofstream fop;fop.ope n("hfmTree.dat",ios:out|ios:b in ary|ios:tr unc); /打开文件if(fop.fail()cout<<"n哈夫曼树文件打开失败，无法将哈夫曼树写入 hfmTree.dat文件。n"return;fop.write(char*)&Num,sizeof(Num); / for(i=0;i<Num;i+) /再写入源文字符集的所有字符(存储在 fop.write(char*)&I

11、n foi,sizeof(l nfoi); flush(cout);for(i=0;i<2*Num-1;i+) /最后写入哈夫曼树的各个结点(存储在先写入哈夫曼树的叶子结点个数Info 中)Node 中)/*fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);fop.close(); / 关闭文件cout<<"n 哈夫曼树已成功写入hfmTree.dat 文件。n"*void Huffma nTree:CreateHuffma nTreeFromFile() ifstream fip;fip.ope n

12、("hfmTree.dat",ios:b in ary|ios:i n); if(fip.fail()cout<<"哈夫曼树文件hfmTree.dat 打开失败，无法建立哈夫曼树。n"return;fip.read(char*)&LeafNum,sizeof(LeafNum);if (LeafNum<=1)cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。n"fip.close();return;lnfo=new charLeafNum;Node=new Huffma

13、 nN ode2*LeafNum-1;for(i nt i=O;i<LeafNum;i+)fip.read(char*)&In foi,sizeof(l nfoi);for(i=0;i<2*LeafNum-1;i+)fip.read(char*)&Nodei,sizeof(Nodei);fip.close();cout<<"哈夫曼树已成功构造完成。n"*void Huffma nTree:E ncoder()if(Node=NULL)内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffm

14、a nTreeFromFile();if (LeafNum<=1)cout<<"内存无哈夫曼树。操作撤销。nn"return;/ifchar *SourceText; / 字符串数组，用于存放源文/让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入char Choose;cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2) ？"cin> >Choose;if(Choose='1')ifstream fip1("ToBeTra n.txt"

15、);if(fip1.fail()cout<<"源文文件打开失败！无法继续执行。n"return;char ch;int k=0;数存入kwhile(fip1.get(ch) k+; /第一次读文件只统计文件中有多少个字符，将字符fip1.close();SourceText=new chark+1; II申请存放源文的字符数组空间ifstream fip2("ToBeTran.txt");II第二次读源文文件，把内容写入 SourceTextk=0;while(fip2.get(ch) SourceTextk+=ch;fip2.close()

16、;SourceTextk='0：cout<<"需编码的源文为："cout<<SourceText<<e ndl; else /从键盘输入源文stri ng SourceBuff;cin .ig nore();cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):n"getl in e(c in, SourceBuff,'、n');int k=0;while(SourceBuffk!='0')k+;SourceText=new chark+1;k=0;whi

17、le(SourceBuffk!='0')SourceTextk=SourceBuffk;k+;SourceTextk='0'cout<<"覆盖已有的编码原文件？( Y/N)"char ch;cin> >ch;if(ch='y'|ch='Y')ofstream fip2;fip2.ope n("ToBeTra n. txt");if(!fip2)cerr<<"文件打开失败！"<<endl;abort();fip2<<

18、;SourceText<<e ndl;fip2.close();cout<<"需编码的源文已写入ToBeTran.txt中"<<endl;/开始编码ofstream fop("CodeFile.dat",ios:tru nc); /打开码文存放文件char *code;code=new charLeafNum; /存放一个源文字符的编码int k=0;while(SourceTextk!='0') /源文串中从第一个字符开始逐个编码int star=0;char ch=SourceTextk;for(i

19、 nt i=O;i<LeafNum;i+)if(ln foi=ch)求出该文字所在的单元编号break;int j=i;while(Nodej.pare nt!=-1)j=Nodej.pare nt;if(InfoNodej.lchild=Infoi) codestar+='0'else codestar+='1'i=j;codestar='0'for(i=0;i<star/2;i+)int j=codei;codei=codestar-i-1;codestar-i-1=j;i=0; /将源文的当前字符的对应编码写入码文文件while

20、(codei!='0')fop<<codei;i+;k+; /源文串中的字符后移一个fop.close();cout<<"已完成编码，码文已写入文件CodeFile.dat 中。nn"*void Huffma nTree:Decoder()中读入信息并建立哈夫曼树II如果内存没有哈夫曼树，则从哈夫曼树文件 hfmTree.datif(Node=NULL)CreateHuffma nTreeFromFile();if (LeafNum<=1)cout<<"内存无哈夫曼树。操作撤销。nn"return

21、;/将码文从文件CodeFile.dat 中读入CodeStrifstream fip1("CodeFile.dat");if(fip1.fail()cout<<"没有码文，无法译码。n"return;char* CodeStr;int k=0;char ch;while(fip1.get(ch)k+;fip1.close();CodeStr= new chark+1;ifstream fip2("CodeFile.dat");k=0;while(fip2.get(ch) CodeStrk+=ch;fip2.close()

22、;CodeStrk='0'cout<<"经译码得到的源文为："ofstream fop("TextFile.dat");int j=LeafNum*2-1-1; /j指向哈夫曼树的根int i=0; /码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子while(CodeStri!='0') /下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符if(CodeStri='0') j=Nodejchild;else j=Nodej.rchild; if(No

23、dej.rchild=-1) cout< <ln foj; fop<<l nfoj; j=LeafNum*2-1-1; i+;fop.close();cout<<"n译码成功且已存到文件TextFile.dat 中。nn"/*void Huffma nTree:Pri ntCodeFile()char ch;int i=1;ifstream fip("CodeFile.dat");ofstream fop("CodePri n. dat");if(fip.fail()cout<<&quo

24、t;没有码文文件，无法显示码文文件内容。n"return;while(fip.get(ch)cout<<ch;fop<<ch;if(i=50)cout<<e ndl;fop<<e ndl;i=0;i+;cout<<e ndl;fop<<e ndl;fip.close();fop.close();*void Huffma nTree:Pri ntHuffma nTree()如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树if(Node=NULL)CreateHuffma nTre

25、eFromFile();if (LeafNum<=1)cout<<"内存无哈夫曼树。操作撤销。nn"return;ofstream fop("TreePri nt.dat",ios_base:tr un c);fop.close();Prin tHuffma nTree_aoru(2*LeafNum-1-1,0); return;*void Huffma nTree:Pri ntHuffma nTree_aoru(i nt T,i nt layer)for(i nt i=O;i<layer;i+) cout<<&quo

26、t;"cout<<NodeT.weight<<e ndl;if(NodeT.lchild!=-1) PrintHuffmanTree_aoru(NodeT.lchild,+layer); if(NodeT.rchild!=-1) PrintHuffmanTree_aoru(NodeT.rchild,layer-);/mai n.cpp#in clude<stri ng.h>#in clude<stdlib.h>using n amespace std;int mai n()Huffma nTree huftree;char Choose

27、;while(1)cout<<"您可以进行以下操作:"<<endl;cout<<"1建立哈夫曼树3译码（码文已在文件CodeFile 中)5显示哈夫曼树"<<endl;退出cout<<"2 "<<e ndl;编码（源文已在文件ToBeTran中，或键盘输入）4显示码文 6cout<<"nn*欢迎使用哈夫曼编码/译码系统*"<<e ndl;cout<<"请选择一个操作："；cin> &

28、gt;Choose;switch(Choose)case '1':huftree.CreateHuffma nTree(); break;case 2:huftree.E ncoder(); break;case 3:huftree.Decoder(); break;case '4':huftree.Pri ntCodeFile(); break;case '5':huftree.Pri ntHuffma nTree(); break;case '6':cout<<"n*感谢使 用 本 系统!* nn"system("pause");return 0;"/switch/while/mai n【用户手册】进入哈弗曼树系统，出现以下界面：1建立弗曼树2 、编码（源文中读入，键盘输入）3、译码4、显示码文 5 、显示哈弗曼树 6 、退出用户根据该提示，选择前面数字，就能进入各个功能函数，实现 函数功能。【运 行 结 果】 截 图 一：截图三;*水*和卡疳*常*帝氓迎逹 十"| /:吁嗚$工I*碍系统冶*常水當*i：*4r*+*Mn|:*常*君 籃可以进行以下操作:锂立哙夫曼树3译码（码文已