(完整word版)数据结构哈夫曼树编码译码实验报告

1、 【详细设计】 具体代码实现如下： /HaffmanTree.h #include #include #include struct HuffmanNode / 哈夫曼树的一个结点 int weight; int parent; int lchild,rchild; ; class HuffmanTree /哈夫曼树 private: HuffmanNode *Node; /Node 存放哈夫曼树 char *Info; /Info 存放源文用到的字符源码，如 a,b,c,d,e ，此内 容可以放入结点中，不单独设数组存放 int LeafNum; /哈夫曼树的叶子个数，也是源码个数 publ

2、ic: HuffmanTree(); void CreateHuffmanTree(); /* 种建立哈夫曼树的方法中选择： 重，建立哈夫曼树， 入哈夫曼树信息，建立哈夫曼树 HuffmanTree(); 在内存中建立哈夫曼树，存放在 Node 中。 让用户从两 1. 从键盘读入源码字符集个数， 每个字符， 和每个字符的权 并将哈夫曼树写入文件 hfmTree 中。2. 从文件 hfmTree 中读 */ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好

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

4、le 中，并同时输出到屏幕上。 */ 将码文文件 CodeFile 显示在屏幕上 */ 将哈夫曼树以直观的形式(凹入表示法，或广义表，或其 同时写入文件 TreePrintFile 中 */void PrintHuffmanTree_aoru(int T,int layer=1); PrintHuffmanTree() 调用 */ ; /* 凹入表示法 显示哈夫曼树， /HuffmanTree. cpp #include #include / 为使用整型最大值 #includeHuffmanTree.h using namespace std; /* HuffmanTree:HuffmanTr

5、ee() Node=NULL; /* HuffmanTree:HuffmanTree() deleteNode; /* void HuffmanTree:CreateHuffmanTree() char Choose; coutChoose; if(Choose=2) / 键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard(); /choose=2 else / 从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); /* void HuffmanTree:CreateHuffmanTreeFro

6、mKeyboard() int Num; coutNum; if (Num=1) (按 2) ？ cout 无法建立少于 2 个叶子结点的哈夫曼树。 nn; return; LeafNum=Num; Node=new HuffmanNode2*Num-1; Info=new char2*Num-1; for(int i=0;iNum;i+) / 读入哈夫曼树的叶子结点信息 cout 请输入第 i+1 个字符值 ; getchar(); Infoi=getchar(); / 源文的字符存入字符数组 Info getchar(); coutNodei.weight; / 源文的字符权重存入 Nod

7、e.weight Nodei.parent=-1; Nodei.lchild=-1; Nodei.rchild=-1; for(i=Num;i2*Num-1;i+) / 循环建立哈夫曼树内部结点 int pos1=-1,pos2=-1; int max1=32767,max2=32767; for(int j=0;ji;j+)/ 在根节点中选出权值最小的两个 if(Nodej.parent=-1)/ 是否为根结点 if(Nodej.weightmax1) max2=max1; max1=Nodej.weight; pos2=pos1; pos1=j; else if(Nodej.weightm

8、ax2) max2=Nodej.weight; pos2=j; Nodepos1.parent=i; Nodepos2.parent=i; Nodei.lchild=pos1; Nodei.rchild=pos2; Nodei.parent=-1; Nodei.weight=Nodepos1.weight+Nodepos2.weight; /for cout 哈夫曼树已成功构造完成。 n; / 把建立好的哈夫曼树写入文件 hfmTree.dat char ch; coutch; if (ch!=y else ofstream fop; fop.open(hfmTree.dat,ios:out|

9、ios:binary|ios:trunc); / 打开文件 if(fop.fail() coutn 哈夫曼树文件打开失败， 无法将哈夫曼树写入 hfmTree.dat 文 件。 n; return; fop.write(char*) / for(i=0;iNum;i+) / 再写入源文字符集的所有字符(存储在 fop.write(char*) flush(cout); for(i=0;i2*Num-1;i+) / 最后写入哈夫曼树的各个结点(存储在 fop.write(char*) flush(cout); 先写入哈夫曼树的叶子结点个数 Info 中) Node 中) fop.close();

10、 / 关闭文件 coutn 哈夫曼树已成功写入 hfmTree.dat 文件。 n; /* * void HuffmanTree:CreateHuffmanTreeFromFile() ifstream fip; fip.open(hfmTree.dat,ios:binary|ios:in); if(fip.fail() cout 哈夫曼树文件 hfmTree.dat 打开失败，无法建立哈夫曼树。 n; return; fip.read(char*) if (LeafNum=1) cout 哈夫曼树文件中的数据有误， 叶子结点个数少于 2 个，无法建立哈夫曼树。 n; fip.close();

11、 return; Info=new charLeafNum; Node=new HuffmanNode2*LeafNum-1; for(int i=0;iLeafNum;i+) fip.read(char*) for(i=0;i2*LeafNum-1;i+) fip.read(char*) fip.close(); cout 哈夫曼树已成功构造完成。 n; /* void HuffmanTree:Encoder() if(Node=NULL) / 内存没有哈夫曼树，则从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); if

12、 (LeafNum=1) cout 内存无哈夫曼树。操作撤销。 nn; return; /if char *SourceText; /字符串数组，用于存放源文 / 让用户选择源文是从键盘输入，还是从源文文件 ToBeTran.txt 中读入 char Choose; coutChoose; if(Choose=1) ifstream fip1(ToBeTran.txt); if(fip1.fail() cout 源文文件打开失败 ! 无法继续执行。 n; return; char ch; int k=0; while(fip1.get(ch) k+; / 第一次读文件只统计文件中有多少个字符，

13、将字符 数存入 k fip1.close(); SourceText=new chark+1; /申请存放源文的字符数组空间 SourceText ifstream fip2(ToBeTran.txt);/ 第二次读源文文件， 把内容写入 k=0; while(fip2.get(ch) SourceTextk+=ch; fip2.close(); SourceTextk=0; cout 需编码的源文为： ; coutSourceTextendl; else / 从键盘输入源文 string SourceBuff; cin.ignore(); cout 请输入需要编码的源文 ( 可输入任意长，按

14、回车键结束 ):n; getline(cin,SourceBuff,n); int k=0; while(SourceBuffk!=0) k+; SourceText=new chark+1; k=0; while(SourceBuffk!=0) SourceTextk=SourceBuffk; k+; SourceTextk=0; coutch; if(ch=y|ch=Y) ofstream fip2; fip2.open(ToBeTran.txt); if(!fip2) cerr 文件打开失败！ endl; abort(); fip2SourceTextendl; fip2.close()

15、; cout 需编码的源文已写入 ToBeTran.txt 中 endl; / 开始编码 ofstream fop(CodeFile.dat,ios:trunc); / 打开码文存放文件 char *code; code=new charLeafNum; /存放一个源文字符的编码 int k=0; while(SourceTextk!=0) /源文串中从第一个字符开始逐个编码 int star=0; char ch=SourceTextk; for(int i=0;iLeafNum;i+) if(Infoi=ch)/ 求出该文字所在的单元编号 break; int j=i; while(Nod

16、ej.parent!=-1) j=Nodej.parent; if(InfoNodej.lchild=Infoi) codestar+=0; else codestar+=1; i=j; codestar=0; for(i=0;istar/2;i+) int j=codei; codei=codestar-i-1; codestar-i-1=j; i=0; / 将源文的当前字符的对应编码写入码文文件 while(codei!=0) fopcodei; i+; k+; / 源文串中的字符后移一个 fop.close(); cout 已完成编码，码文已写入文件 CodeFile.dat 中。 nn

17、; /* void HuffmanTree:Decoder() 中读入信息并建立哈夫曼树 / 如果内存没有哈夫曼树， 则从哈夫曼树文件 hfmTree.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; ch

18、ar 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(); CodeStrk=0; cout 经译码得到的源文为： ; ofstream fop(TextFile.dat); int j=LeafNum*2-1-1; /j指向哈夫曼树的根 int i=0; / 码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定 下行到左孩子还是右孩子 while(Co

19、deStri!=0) / 下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符 if(CodeStri=0) j=Nodej.lchild; else j=Nodej.rchild; if(Nodej.rchild=-1) coutInfoj; fopInfoj; j=LeafNum*2-1-1; i+; fop.close(); coutn 译码成功且已存到文件 TextFile.dat 中。 nn; /* void HuffmanTree:PrintCodeFile() char ch; int i=1; ifstream fip(CodeFile.dat); ofstream fop

20、(CodePrin.dat); if(fip.fail() cout 没有码文文件，无法显示码文文件内容。 n; return; while(fip.get(ch) coutch; fopch; if(i=50) coutendl; fopendl; i=0; i+; coutendl; fopendl; fip.close(); fop.close(); /* void HuffmanTree:PrintHuffmanTree() / 如果内存没有哈夫曼树， 则从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 if(Node=NULL) CreateHuffmanTreeFr

21、omFile(); if (LeafNum=1) cout 内存无哈夫曼树。操作撤销。 nn; return; ofstream fop(TreePrint.dat,ios_base:trunc); fop.close(); PrintHuffmanTree_aoru(2*LeafNum-1-1,0); return; /* void HuffmanTree:PrintHuffmanTree_aoru(int T,int layer) for(int i=0;ilayer;i+) cout_; coutNodeT.weightendl; if(NodeT.lchild!=-1) PrintHu

22、ffmanTree_aoru(NodeT.lchild,+layer); if(NodeT.rchild!=-1) PrintHuffmanTree_aoru(NodeT.rchild,layer-); /main.cpp #include #include using namespace std; int main() HuffmanTree huftree; char Choose; while(1) cout 您可以进行以下操作 :endl; cout1 建立哈夫曼树 3译码 ( 码文已在文件 CodeFile 中 ) 5 显示哈夫曼树 endl; 退出 cout2 endl; 编码 (

23、 源文已在文件 ToBeTran 中，或键盘输入 ) 4 显示码文 6 * 欢迎使用哈夫曼编码/译码系统 * endl; coutChoose; switch(Choose) case 1: huftree.CreateHuffmanTree(); break; case 2: huftree.Encoder(); break; case 3: huftree.Decoder(); break; case 4: huftree.PrintCodeFile(); break; case 5: huftree.PrintHuffmanTree(); break; case 6: coutn * 感

24、谢使用本系 统 !* *nn; system(pause); return 0; /switch /while /main 【用户手册】 进入哈弗曼树系统，出现以下界面： 1建立弗曼树2 、编码（源文中读入，键盘输入）3、译码 4、显示码文 5、显示哈弗曼树6 、退出 用户根据该提示，选择前面数字，就能进入各个功能函数，实现 函数功能 截 图 卡串丰*半*串*丰爭*串爭术*只欠迎（J用卩台夫曼编马/i睪 码 系 统*挙半*串辛术*率:i：* 您可以进行以下操作： 1建立哈夫曼树3译码（码文己在文件CodeFile中）5显示哈夫曼树 2编码（源文已在文件ToBeTran中，或键盘输入）4显示码文

25、6退出 请选择一牛操作： 搜狗拼音输入法全： ：水*来*5（!*帝水京*冷*来京*好*址*烦迎使 用 哈夫 曼编码/译码系统窗壮水点*水*窗*黑*总*立*来紳蜒 熬可以进行以下操作： 建立哈夫曼树3译码（码文已在文件CodeFile中）5显示哈夫曼树 :编码（源文已在文件ToBeTran中,.或键盘输入）4显示码文 6退出 青选择一个操作：3 岁译码得到的源文为；VVCTVV 荤码成功己疗到文件TextFile.曲t中* ：*紳*牢*半*半*榊 粋*衬半*欢迎 使用哈 夫曼编 码/译 码系统军*林*半枠申*衲半*半*来*卷 冬可以进行以下操作： 建立哈夭曼树3译码（码文己在文件CodeFile中