二叉树两种存储结构的应用.doc

数据结构实验实验四二叉树两种存储结构的应用 计算机科学与技术系0901班 日 期：2011年5月5日实验报告2009级 0901班 2011年5月5日实验类型：综合设计型 实验地点：软件实验室三 一 实验题目二叉树两种存储结构的应用二 需求分析本实验需要设计程序，输入叶子结点和权值，建立一颗哈弗曼树，并根据哈弗曼树进行编码和译码操作。键盘中输入或者从文件中读入哈弗曼树；键盘中输入或者从源文件中读入需要编码的源文，然后将源文根据哈弗曼树的权值，译码为二进制代码。最后实现凹入显示法显示哈弗曼树。三 概要设计 本程序由HaffmanTree.h、HaffmanTree.cpp、main.cpp三个文件构成。HaffmanTree.h中定义了哈弗曼树的储存结构体HaffmanNode，里面定义了weight、parent、lchild、rchild四个变量来描述哈弗曼树的储存结构。在HaffmanTree.h中还定义了一个名为HaffmanTree的类，里面定义的是建树、编码、译码和凹入显示哈弗曼树等函数，而相关的实现代码则在HaffmanTree.cpp中给出。main.cpp中主要是实现内部函数与用户界面的对接。void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node中。 让用户从两种建立哈夫曼树的方法中选择： 1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树， 并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）， 对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。 ToBeTran的内容可以用记事本等程序编辑产生。*/ void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码， 得到的源文写入文件TextFile中，并同时输出到屏幕上。*/ void PrintCodeFile(); /*将码文文件CodeFile显示在屏幕上*/ void PrintHuffmanTree(); /*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上， 同时写入文件TreePrintFile中*/ void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/译码建立哈弗曼树从键盘输入从内存中读取哈弗曼树从键盘输入码文从内存中读取码文编码显示哈弗曼树退出四 详细设计建立哈弗曼树void HuffmanTree:CreateHuffmanTreeFromKeyboard()int Num;coutNum;if (Num=1)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; /源文的字符权重存入Node.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;elseif(Nodej.weightmax2)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; /forcout哈夫曼树已成功构造完成。n;/2009100145编码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(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=codei;codei=codestar-i-1;codestar-i-1=j; i=0; /将源文的当前字符的对应编码写入码文文件while(codei!=0) fopcodei;i+;k+; /源文串中的字符后移一个fop.close();cout已完成编码，码文已写入文件CodeFile.dat中。nn; /2009100136译码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经译码得到的源文为：;ofstream fop(TextFile.dat); int j=LeafNum*2-1-1; /j指向哈夫曼树的根 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(); /2009100122显示哈弗曼树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;fopendl;fip.close(); fop.close(); /2009100132五 调试分析在内存中建立哈夫曼树，存放在Node中。 让用户从两种建立哈夫曼树的方法中选择：1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/ 当用键盘建立哈弗曼数时应注意系统无法建立少于2个叶子结点的哈夫曼树先写入哈夫曼树的叶子结点个数再写入源文字符集的所有字符最后写入哈夫曼树的各个结点六 使用说明进入哈弗曼树系统，出现以下界面：1建立弗曼树 2、编码（源文中读入，键盘输入） 3、译码 4、显示码文 5、显示哈弗曼树 6、退出 用户根据该提示，选择前面数字，就能进入各个功能函数，实现函数功能。七 测试结果八 实验总结 1、实验中注意函数的选择和应用，并且考虑多方面的实现结果，使实验的失误减少 2、对于源文的编码和译码的中间转换过程需要侧重练习 3、各个模块之间的连接函数需要反复调试，使程序执行更加流畅九 模块分工2009100145 辛志鹏 建立哈夫曼树2009100136 张发辉 编码2009100122 赵金桃 译码2009100132 田 飞 显示哈夫曼树/HaffmanTree.h#include#include#includestruct 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(); HuffmanTree(); void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node中。 让用户从两种建立哈夫曼树的方法中选择：1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）， 对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。 ToBeTran的内容可以用记事本等程序编辑产生。*/ void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存， 则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码， 得到的源文写入文件TextFile中，并同时输出到屏幕上。*/ void PrintCodeFile(); /*将码文文件CodeFile显示在屏幕上*/ void PrintHuffmanTree(); /*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上， 同时写入文件TreePrintFile中*/ void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/;/HuffmanTree.cpp#include#include /为使用整型最大值#includeHuffmanTree.husing namespace std;/*HuffmanTree:HuffmanTree()Node=NULL;/*HuffmanTree:HuffmanTree()deleteNode;/*void HuffmanTree:CreateHuffmanTree() char Choose; coutChoose;if(Choose=2) /键盘输入建立哈夫曼树CreateHuffmanTreeFromKeyboard();/choose=2else /从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();/*void HuffmanTree:CreateHuffmanTreeFromKeyboard()int Num;coutNum;if (Num=1)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; /源文的字符权重存入Node.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;elseif(Nodej.weightmax2)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; /forcout哈夫曼树已成功构造完成。n;/把建立好的哈夫曼树写入文件hfmTree.datchar ch;coutch;if (ch!=y&ch!=Y) return;elseofstream 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); /先写入哈夫曼树的叶子结点个数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()ifstream 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) cout哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。n;fip.close();return; Info=new charLeafNum; Node=new HuffmanNode2*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);fip.close();cout哈夫曼树已成功构造完成。n;/*void HuffmanTree:Encoder()if(Node=NULL)/内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();if (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+; /第一次读文件只统计文件中有多少个字符，将字符数存入kfip1.close(); SourceText=new chark+1; /申请存放源文的字符数组空间ifstream fip2(ToBeTran.txt);/第二次读源文文件，把内容写入SourceTextk=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;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();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(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=codei;codei=codestar-i-1;codestar-i-1=j; i=0; /将源文的当前字符的对应编码写入码文文件while(codei!=0) fopcodei;i+;k+; /源文串中的字符后移一个fop.close();cout已完成编码，码文已写入文件CodeFile.dat中。nn; /*void HuffmanTree:Decoder()/如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树if(Node=NULL) CreateHuffmanTreeFromFile();if (LeafNum=1)cout内存无哈夫曼树。操作撤销。nn;return;/将码文从文件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(); CodeStrk=0; cout经译码得到的源文为：;ofstream fop(TextFile.dat); int j=LeafNum*2-1-1; /j指向哈夫曼树的根 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译码成功且已存到文件TextFile.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;fopendl;f