《数据结构哈夫曼树编码译码实验报告（2020年7月整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构哈夫曼树编码译码实验报告（2020年7月整理）.pdf（14页珍藏版）》请在金锄头文库上搜索。
1、 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:
2、 HuffmanTree(); HuffmanTree(); void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在 Node中。 让用户从两 种建立哈夫曼树的方法中选择： 1.从键盘读入源码字符集个数， 每个字符， 和每个字符的权 重，建立哈夫曼树， 并将哈夫曼树写入文件 hfmTree 中。 2.从文件 hfmTree 中读 入哈夫曼树信息，建立哈夫曼树*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼树（如
3、果不在内存，则从文件 hfmTree 中读入 并建立内存里的哈夫曼树） ， 对文件 ToBeTran 中的正文进行编码， 并将码文写入文件 CodeFile 中。 ToBeTran 的内容可以用记事本等程序编辑产生。*/ void Decoder(); /*待译码的码文存放在文件 CodeFile 中，使用建立好的哈夫曼树（如 果不在内存， 则从文件 hfmTree 中读入并建立内存里的哈夫曼树）将码文译码， 得到的源文写入文件 TextFile 中，并同时输出到屏幕上。*/ void PrintCodeFile(); /*将码文文件 CodeFile 显示在屏幕上*/ void PrintH
4、uffmanTree(); /*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其 他树形表示法）显示在屏幕上， 同时写入文件 TreePrintFile 中*/ void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法显示哈夫曼树，由 2 PrintHuffmanTree()调用*/ ; /HuffmanTree. cpp #include #include /为使用整型最大值 #includeHuffmanTree.h using namespace std; /* HuffmanTree:HuffmanTree() Node=NULL;
5、 /* HuffmanTree:HuffmanTree() deleteNode; /* void HuffmanTree:CreateHuffmanTree() char Choose; coutChoose; if(Choose=2) /键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard(); /choose=2 else /从哈夫曼树文件 hfmTree.dat 中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); /* void HuffmanTree:CreateHuffmanTreeFromKeyboard() int N
6、um; coutNum; if (Num=1) cout无法建立少于 2 个叶子结点的哈夫曼树。nn; return; LeafNum=Num; Node=new HuffmanNode2*Num-1; 3 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.
7、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.weightmax2) max2=Nodej.weight; pos2=j; Nod
8、epos1.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 4 else ofstream fop; fop.open(hfmTree.dat,ios:out|ios:binary|ios:trunc); /打开文件 if(fop.
9、fail() coutn 哈夫曼树文件打开失败，无法将哈夫曼树写入 hfmTree.dat 文 件。n; return; fop.write(char*) /先写入哈夫曼树的叶子结点个数 for(i=0;iNum;i+) /再写入源文字符集的所有字符（存储在 Info中） fop.write(char*) flush(cout); for(i=0;i2*Num-1;i+) /最后写入哈夫曼树的各个结点（存储在 Node中） fop.write(char*) flush(cout); fop.close(); /关闭文件 coutn 哈夫曼树已成功写入 hfmTree.dat 文件。n; /*
10、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(); return; Info=new charLeafNum; 5 Node=new HuffmanN
11、ode2*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 (LeafNum=1) cout内存无哈夫曼树。操作撤销。nn; return; /if char
12、*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+; /第一次读文件只统计文件中有多少个字符，将字符 数存入 k fip1.close(); SourceText=new chark+1; /申请存放源文的字符数
13、组空间 ifstream fip2(ToBeTran.txt);/第二次读源文文件， 把内容写入 SourceText k=0; while(fip2.get(ch) SourceTextk+=ch; 6 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;
