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

1、WORD格式【详细设计】具体代码实现如下：专业资料整理WORD格式/HaffmanTree.h#include<iostream>#include<fstream>#include<string>struct HuffmanNode /int weight;int parent;int lchild,rchild;哈夫曼树的一个结点专业资料整理WORD格式class HuffmanTree /哈夫曼树private:HuffmanNode *Node; /Node存放哈夫曼树char *Info;/Info存放源文用到的字符源码，如'a',&

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

3、/void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();专业资料整理WORD格式void Encoder();/*使用建立好的哈夫曼树如果不在内存，那么从文件并建立内存里的哈夫曼树，对文件 ToBeTran 中的正文进展编码， 并将码文写入文件hfmTree 中读入CodeFile中。专业资料整理WORD格式voidDecoder();/*ToBeTran的内容可以用记事本等程序编辑产生。*/待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树如专业资料整理WORD格式果不在内存，那么从文件hfmT

4、ree 中读入并建立内存里的哈夫曼树将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上。*/专业资料整理WORD格式void PrintCodeFile();/*将码文文件CodeFile显示在屏幕上 */void PrintHuffmanTree(); /*将哈夫曼树以直观的形式凹入表示法，或广义表，或其他树形表示法显示在屏幕上，专业资料整理WORD格式同时写入文件TreePrintFile中 */专业资料整理WORD格式voidPrintHuffmanTree_aoru(int T,int layer=1);PrintHuffmanTree()调用 */;/*凹入表示法显

5、示哈夫曼树，由专业资料整理WORD格式/HuffmanTree.cpp#include<string>#include<limits> /为使用整型最大值专业资料整理WORD格式#include"HuffmanTree.h"using namespace std;/*HuffmanTree:HuffmanTree()Node=NULL;/*HuffmanTree:HuffmanTree()deleteNode;/*void HuffmanTree:CreateHuffmanTree()专业资料整理WORD格式char Choose;cout<&

6、lt;" 你要从文件中读入哈夫曼树( 按 1) ，还是从键盘输入哈夫曼树cin>>Choose;if(Choose='2') /键盘输入建立哈夫曼树CreateHuffmanTreeFromKeyboard();/choose='2'( 按2)？"专业资料整理WORD格式else /从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树专业资料整理WORD格式CreateHuffmanTreeFromFile();/*void HuffmanTree:CreateHuffmanTreeFromKeyboard()int Nu

7、m;cout<<"n请输入源码字符集个数："cin>>Num;if (Num<=1)专业资料整理WORD格式cout<<"无法建立少于2 个叶子结点的哈夫曼树。nn"专业资料整理WORD格式return;专业资料整理WORD格式LeafNum=Num;Node=new HuffmanNode2*Num-1;Info=new char2*Num-1;for(int i=0;i<Num;i+) /读入哈夫曼树的叶子结点信息cout<<" 请输入第 "<<i+1<

8、<" 个字符值 "getchar();Infoi=getchar(); /源文的字符存入字符数组Infogetchar();专业资料整理WORD格式cout<<" 请输入该字符的权值或频度"cin>>Nodei.weight; /源文的字符权重存入Nodei.parent=-1;Nodei.lchild=-1;Node.weight专业资料整理WORD格式Nodei.rchild=-1;for(i=Num;i<2*Num-1;i+)/循环建立哈夫曼树内部结点int pos1=-1,pos2=-1;int max1=32

9、767,max2=32767;for(int j=0;j<i;j+)/在根节点中选出权值最小的两个if(Nodej.parent=-1)/是否为根结点if(Nodej.weight<max1)max2=max1;max1=Nodej.weight;pos2=pos1;pos1=j;elseif(Nodej.weight<max2)max2=Nodej.weight;pos2=j;Nodepos1.parent=i;Nodepos2.parent=i;Nodei.lchild=pos1;Nodei.rchild=pos2;Nodei.parent=-1;Nodei.weight

10、=Nodepos1.weight+Nodepos2.weight; /forcout<<" 哈夫曼树已成功构造完成。n"专业资料整理WORD格式/ 把建立好的哈夫曼树写入文件hfmTree.datchar ch;cout<<" 是否要替换原来的哈夫曼树文件(Y/N):"cin>>ch;if (ch!='y'&&ch!='Y') return;elseofstream fop;fop.open("hfmTree.dat",ios:out|ios:bina

11、ry|ios:trunc); / 翻开文件 if(fop.fail()cout<<"n哈夫曼树文件翻开失败，无法将哈夫曼树写入hfmTree.dat文件。 n"return;专业资料整理WORD格式fop.write(char*)&Num,sizeof(Num); /for(i=0;i<Num;i+)先写入哈夫曼树的叶子结点个数专业资料整理WORD格式 /再写入源文字符集的所有字符存储在Info中专业资料整理WORD格式fop.write(char*)&Infoi,sizeof(Infoi);flush(cout);for(i=0;i<

12、;2*Num-1;i+)专业资料整理WORD格式 /最后写入哈夫曼树的各个结点存储在Node中专业资料整理WORD格式fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);专业资料整理WORD格式fop.close(); /关闭文件cout<<"n哈夫曼树已成功写入hfmTree.dat文件。 n"专业资料整理WORD格式/*void HuffmanTree:CreateHuffmanTreeFromFile()ifstream fip;fip.open("hfmTree.dat",ios:

13、binary|ios:in);if(fip.fail()cout<<" 哈夫曼树文件 hfmTree.dat 翻开失败，无法建立哈夫曼树。 n" return;fip.read(char*)&LeafNum,sizeof(LeafNum);if (LeafNum<=1)专业资料整理WORD格式cout<<" 哈夫曼树文件中的数据有误，叶子结点个数少于2 个，无法建立哈夫曼树。n"fip.close();return;Info=new charLeafNum;Node=new HuffmanNode2*LeafNum-

14、1;for(int i=0;i<LeafNum;i+)fip.read(char*)&Infoi,sizeof(Infoi);for(i=0;i<2*LeafNum-1;i+)fip.read(char*)&Nodei,sizeof(Nodei);fip.close();cout<<" 哈夫曼树已成功构造完成。n"/*void HuffmanTree:Encoder()if(Node=NULL)/内存没有哈夫曼树，那么从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(

15、);if (LeafNum<=1)cout<<" 内存无哈夫曼树。操作撤销。nn"return;/if专业资料整理WORD格式char *SourceText; /字符串数组，用于存放源文专业资料整理WORD格式/ 让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入专业资料整理WORD格式char Choose;专业资料整理WORD格式cout<<" 你要从文件中读入源文( 按 1) ，还是从键盘输入源文( 按 2) ？ "cin>>Choose;if(Choose='1')

16、ifstream fip1("ToBeTran.txt");if(fip1.fail()cout<<" 源文文件翻开失败! 无法继续执行。n"return;char ch;int k=0;专业资料整理WORD格式while(fip1.get(ch) k+; /第一次读文件只统计文件中有多少个字符，将字符数存入 kfip1.close();专业资料整理WORD格式SourceText=new chark+1; / ifstream fip2("ToBeTran.txt");/申请存放源文的字符数组空间第二次读源文文件， 把内

17、容写入SourceText专业资料整理WORD格式k=0;while(fip2.get(ch) SourceTextk+=ch;fip2.close();SourceTextk='0'cout<<" 需编码的源文为："cout<<SourceText<<endl;else / 从键盘输入源文 string SourceBuff;cin.ignore();cout<<" 请输入需要编码的源文( 可输入任意长，按回车键完毕):n"getline(cin,SourceBuff,'n'

18、;);int k=0;while(SourceBuffk!='0')k+;SourceText=new chark+1;k=0;while(SourceBuffk!='0')SourceTextk=SourceBuffk;k+;SourceTextk='0'cout<<" 覆盖已有的编码原文件" Y/N "char ch;cin>>ch;if(ch='y'|ch='Y')ofstream fip2;fip2.open("ToBeTran.txt&quo

19、t;);if(!fip2)cerr<<" 文件翻开失败！"<<endl;abort();fip2<<SourceText<<endl;fip2.close();专业资料整理WORD格式cout<<" 需编码的源文已写入ToBeTran.txt中 "<<endl;/ 开场编码ofstream fop("CodeFile.dat",ios:trunc); /翻开码文存放文件char *code;专业资料整理WORD格式code=new charLeafNum;/存放一

20、个源文字符的编码专业资料整理WORD格式int k=0;while(SourceTextk!='0')/源文串中从第一个字符开场逐个编码int star=0;char ch=SourceTextk;for(int i=0;i<LeafNum;i+)if(Infoi=ch)/求出该文字所在的单元编号break;int j=i;while(Nodej.parent!=-1)j=Nodej.parent;if(InfoNodej.lchild=Infoi) codestar+='0'else codestar+='1'i=j;codestar=&

21、#39;0'for(i=0;i<star/2;i+)int j=codei;codei=codestar-i-1;codestar-i-1=j;i=0; /将源文的当前字符的对应编码写入码文文件while(codei!='0')fop<<codei;i+;k+; /源文串中的字符后移一个fop.close();cout<<" 已完成编码，码文已写入文件CodeFile.dat中。 nn"专业资料整理WORD格式/*void HuffmanTree:Decoder()/ 如果内存没有哈夫曼树， 那么从哈夫曼树文件 hfmT

22、ree.dat 中读入信息并建立哈夫曼树if(Node=NULL)CreateHuffmanTreeFromFile();if (LeafNum<=1)cout<<" 内存无哈夫曼树。操作撤销。nn"return;/ 将码文从文件 CodeFile.dat 中读入 CodeStr ifstream fip1("CodeFile.dat");if(fip1.fail()cout<<" 没有码文，无法译码。 n" return;char* CodeStr;int k=0;char ch;while(fip1.

23、get(ch)k+;fip1.close();CodeStr=new chark+1;ifstream fip2("CodeFile.dat");k=0;while(fip2.get(ch) CodeStrk+=ch;fip2.close();CodeStrk='0'cout<<" 经译码得到的源文为："ofstream fop("TextFile.dat");专业资料整理WORD格式int j=LeafNum*2-1-1; /j指向哈夫曼树的根专业资料整理WORD格式inti=0; /码文从第一个符号开场

24、，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子while(CodeStri!='0') / 下行到哈夫曼树的叶子结点处，那么译出叶子结点对应的源文字符 if(CodeStri='0') j=Nodej.lchild;else j=Nodej.rchild;if(Nodej.rchild=-1)cout<<Infoj;fop<<Infoj;j=LeafNum*2-1-1;i+;fop.close();cout<<"n译码成功且已存到文件TextFile.dat中。 nn"/*void Hu

25、ffmanTree:PrintCodeFile()char ch;int i=1;ifstream fip("CodeFile.dat");ofstream fop("CodePrin.dat");if(fip.fail()cout<<" 没有码文文件，无法显示码文文件内容。n"return;while(fip.get(ch)cout<<ch;fop<<ch;if(i=50)cout<<endl;fop<<endl;i=0;i+;cout<<endl;专业资料整理

26、WORD格式fop<<endl;fip.close();fop.close();/*void HuffmanTree:PrintHuffmanTree()/ 如果内存没有哈夫曼树， 那么从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树if(Node=NULL)CreateHuffmanTreeFromFile();if (LeafNum<=1)cout<<" 内存无哈夫曼树。操作撤销。nn"return;ofstream fop("TreePrint.dat",ios_base:trunc);fop.clos

27、e();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);return;/*void HuffmanTree:PrintHuffmanTree_aoru(int T,int layer)for(int i=0;i<layer;i+) cout<<"_"cout<<NodeT.weight<<endl;if(NodeT.lchild!=-1) PrintHuffmanTree_aoru(NodeT.lchild,+layer);if(NodeT.rchild!=-1) PrintHuffmanTree_ao

28、ru(NodeT.rchild,layer-);/main.cpp#include<string.h>#include<stdlib.h>using namespace std;int main()HuffmanTree huftree;char Choose;while(1)专业资料整理WORD格式cout<<"nn*欢迎使用哈夫曼编码/译码系统*"<<endl;cout<<" 您可以进展以下操作 :"<<endl;cout<<"1建立哈夫曼树3译码 ( 码文已在文件CodeFile 中 )5显示哈夫曼树 "<<endl;cout<<"2编码 ( 源文已在文件ToBeTran 中，或键盘输入 )4显示码文6退出&quo