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

上传人:深夜****等你... 文档编号:84229431 上传时间:2023-04-04 格式:PDF 页数:15 大小:554.33KB
返回 下载 相关 举报
数据结构哈夫曼树编码译码实验报告.pdf_第1页
第1页 / 共15页
数据结构哈夫曼树编码译码实验报告.pdf_第2页
第2页 / 共15页
点击查看更多>>
资源描述

《数据结构哈夫曼树编码译码实验报告.pdf》由会员分享,可在线阅读,更多相关《数据结构哈夫曼树编码译码实验报告.pdf(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。

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;/哈夫曼树的叶子个数,也是源码个数 public:HuffmanTree();HuffmanT

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

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

4、上,同时写入文件 TreePrintFile 中*/欢迎下载 2 void PrintHuffmanTree_aoru(int T,int layer=1);/*凹入表示法显示哈夫曼树,由PrintHuffmanTree()调用*/;/HuffmanTree.cpp#include#include/为使用整型最大值#includeHuffmanTree.h using namespace std;/*HuffmanTree:HuffmanTree()Node=NULL;/*HuffmanTree:HuffmanTree()deleteNode;/*void HuffmanTree:Create

5、HuffmanTree()char Choose;coutChoose;if(Choose=2)/键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard();/choose=2 else /从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile();/*void HuffmanTree:CreateHuffmanTreeFromKeyboard()int Num;coutNum;if(Num=1)cout无法建立少于 2 个叶子结点的哈夫曼树。nn;return;欢迎下载 3 LeafNum=Num;Nod

6、e=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;/源文的字符权重存入 Node.weight Nodei.parent=-1;Nodei.lchild=-1;Nodei.rchild=-1;for(i=Num;i2*Num-1;i+)/循环建立哈夫曼树内部结点 int pos1=-1,pos2=-1;int m

7、ax1=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.weightmax2)max2=Nodej.weight;pos2=j;Nodepos1.parent=i;Nodepos2.parent=i;Nodei.lchild=pos1;Nodei.rchild=pos2;Nodei.parent=-1;Nodei.weight=No

8、depos1.weight+Nodepos2.weight;/for cout哈夫曼树已成功构造完成。n;欢迎下载 4 /把建立好的哈夫曼树写入文件 hfmTree.dat char ch;coutch;if(ch!=y&ch!=Y)return;else ofstream fop;fop.open(hfmTree.dat,ios:out|ios:binary|ios:trunc);/打开文件 if(fop.fail()coutn 哈夫曼树文件打开失败,无法将哈夫曼树写入 hfmTree.dat 文件。n;return;fop.write(char*)&Num,sizeof(Num);/先写入

9、哈夫曼树的叶子结点个数 for(i=0;iNum;i+)/再写入源文字符集的所有字符(存储在 Info中)fop.write(char*)&Infoi,sizeof(Infoi);flush(cout);for(i=0;i2*Num-1;i+)/最后写入哈夫曼树的各个结点(存储在 Node中)fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);fop.close();/关闭文件 coutn 哈夫曼树已成功写入 hfmTree.dat 文件。n;/*void HuffmanTree:CreateHuffmanTreeFromFile()ifstrea

10、m fip;fip.open(hfmTree.dat,ios:binary|ios:in);if(fip.fail()cout哈夫曼树文件 hfmTree.dat 打开失败,无法建立哈夫曼树。n;return;fip.read(char*)&LeafNum,sizeof(LeafNum);if(LeafNum=1)欢迎下载 5 cout哈夫曼树文件中的数据有误,叶子结点个数少于 2 个,无法建立哈夫曼树。n;fip.close();return;Info=new charLeafNum;Node=new HuffmanNode2*LeafNum-1;for(int i=0;iLeafNum;i

11、+)fip.read(char*)&Infoi,sizeof(Infoi);for(i=0;i2*LeafNum-1;i+)fip.read(char*)&Nodei,sizeof(Nodei);fip.close();cout哈夫曼树已成功构造完成。n;/*void HuffmanTree:Encoder()if(Node=NULL)/内存没有哈夫曼树,则从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile();if(LeafNum=1)cout内存无哈夫曼树。操作撤销。nn;return;/if char*SourceText

12、;/字符串数组,用于存放源文 /让用户选择源文是从键盘输入,还是从源文文件 ToBeTran.txt 中读入 char Choose;coutChoose;if(Choose=1)ifstream fip1(ToBeTran.txt);if(fip1.fail()cout源文文件打开失败!无法继续执行。n;return;char ch;int k=0;欢迎下载 6 while(fip1.get(ch)k+;/第一次读文件只统计文件中有多少个字符,将字符数存入 k fip1.close();SourceText=new chark+1;/申请存放源文的字符数组空间 ifstream fip2(T

13、oBeTran.txt);/第二次读源文文件,把内容写入 SourceText k=0;while(fip2.get(ch)SourceTextk+=ch;fip2.close();SourceTextk=0;cout需编码的源文为:;coutSourceTextendl;else /从键盘输入源文 string SourceBuff;cin.ignore();cout请输入需要编码的源文(可输入任意长,按回车键结束):n;getline(cin,SourceBuff,n);int k=0;while(SourceBuffk!=0)k+;SourceText=new chark+1;k=0;w

14、hile(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();欢迎下载 7 cout需编码的源文已写入 ToBeTran.txt 中endl;/开始编码 ofstream fop(CodeFile.dat,ios:trunc);/打开码文存放文件 char*code;code=new char

15、LeafNum;/存放一个源文字符的编码 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(Nodej.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=code

16、i;codei=codestar-i-1;codestar-i-1=j;i=0;/将源文的当前字符的对应编码写入码文文件 while(codei!=0)fopcodei;i+;k+;/源文串中的字符后移一个 fop.close();cout已完成编码,码文已写入文件 CodeFile.dat 中。nn;欢迎下载 8 /*void HuffmanTree:Decoder()/如果内存没有哈夫曼树,则从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 if(Node=NULL)CreateHuffmanTreeFromFile();if(LeafNum=1)cout内存无哈夫曼树。操

17、作撤销。nn;return;/将码文从文件 CodeFile.dat 中读入 CodeStr ifstream 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();CodeStrk=0;cout经译码得到的源文为:;ofs

18、tream fop(TextFile.dat);int j=LeafNum*2-1-1;/j 指向哈夫曼树的根 欢迎下载 9 int i=0;/码文从第一个符号开始,顺着哈夫曼树由根下行,按码文的当前符号决定下行到左孩子还是右孩子 while(CodeStri!=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 译码成功且已存到文件 T

19、extFile.dat 中。nn;/*void HuffmanTree:PrintCodeFile()char 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)coutendl;fopendl;i=0;i+;coutendl;欢迎下载 10 fopendl;fip.close();fop.close();/*void HuffmanTree:Print

20、HuffmanTree()/如果内存没有哈夫曼树,则从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 if(Node=NULL)CreateHuffmanTreeFromFile();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)fo

21、r(int i=0;ilayer;i+)cout_;coutNodeT.weightendl;if(NodeT.lchild!=-1)PrintHuffmanTree_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)欢迎下载 11 coutnn*欢 迎 使 用 哈 夫 曼 编

22、码/译 码 系 统*endl;cout您可以进行以下操作:endl;cout1 建立哈夫曼树 3 译码(码文已在文件 CodeFile 中)5 显示哈夫曼树endl;cout2 编码(源文已在文件 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;ca

23、se 5:huftree.PrintHuffmanTree();break;case 6:coutn*感谢使用本系统!*nn;system(pause);return 0;/switch /while/main 欢迎下载 12【用户手册】进入哈弗曼树系统,出现以下界面:1 建立弗曼树 2、编码(源文中读入,键盘输入)3、译码 4、显示码文 5、显示哈弗曼树 6、退出 用户根据该提示,选择前面数字,就能进入各个功能函数,实现函数功能。【运行结果】截图一:截图二:欢迎下载 13 截图三:截图四:欢迎下载 14 【心得体会】本实验是搜集相关资料,然后自己增加功能函数的代码实现的。因此,在完成未完成的功能函数之前还必须要细心阅读所给出代码,整体观察各个部分之前的联系,搞清楚已给出和未完成的代码功能之后,才根据算法,设计出该功能的函数代码。在完成实验时,有发现代码也有纰漏的地方,如在源文件读入的时候,多出了一个值,得要增加下表减这个代码来去掉。还有就是在译码的时候,由于变量定义的混淆,在编译的时候通过,但执行时却出现意料不到的结果,在自己细心观察、思考之前也还没找出错误之处。后来通过请教老师,在和老师讨论检查之后才知道了错误之所在,最后改正错误。实验成功完成。欢迎下载 15【参考文献】数据结构与算法(课本)C+语言基础

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 小学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知得利文库网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号-8 |  经营许可证:黑B2-20190332号 |   黑公网安备:91230400333293403D

© 2020-2023 www.deliwenku.com 得利文库. All Rights Reserved 黑龙江转换宝科技有限公司 

黑龙江省互联网违法和不良信息举报
举报电话:0468-3380021 邮箱:hgswwxb@163.com