哈夫曼树的应用 .pdf

《哈夫曼树的应用 .pdf》由会员分享，可在线阅读，更多相关《哈夫曼树的应用 .pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、哈夫曼树的应用课程设计学生姓名：蔡丽敏学号：6103105003专业班级：计算机科学与技术051 班指导教师：林振荣二 00 八年十二月二十七日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 25 页 - - - - - - - - - 目录1. 课程设计目的,1 2. 课程设计题目设计和要求,1 3. 课程设计报告内容,1 4. 结论 ,255. 参考书目,25名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

2、- 名师精心整理 - - - - - - - 第 2 页，共 25 页 - - - - - - - - - 1. 课程设计目的树型结构是一种应用极为广泛的非线性数据结构, 也是本课程设计的重点内容, 哈夫曼树 (最优二叉树 )是树型结构的典型应用 , 本次课程设计突出了数据结构加操作的程序设计观点, 希望能根据树型结构的非线性特点, 熟悉各种存储结构的特性 , 达到如何应用树型结构的非线性特点, 熟悉各种存储结构的特性 , 达到如何应用树型结构解决具体问题的目的. 2. 课程设计题目描述和要求【问题描述】利用哈夫曼编码进行住处通讯可以大大提高信道利用率, 缩短住处传输时间, 降低成本 , 但是

3、, 这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码( 复原), 对于双向传输信息的信道, 每端都一个完整的编码译码系统, 试为这样的住处收发站写一个哈夫曼友的编码译码系统 . 【基本要求】：一个完整的系统应以下功能: (1) I. 初始化(Initialization)。从终端读入字符集大小n，以及 n 个字符和 n个权值 , 建立哈夫曼树 , 并将它存放在文件hfmTree 中. (2) E. 编码(Encoding) 。利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree 中读入） ， 对文件 ToBeTran中的正文进行编码 , 然

4、后将结果代码存 (传输)到文件 CodeFile 中. (3) D. 译码(Decoding) 。利用已建好的哈夫曼树, 对传输到达的 CodeFile 中的数据代码进行译码 , 将译码结果存入文件TextFile中. (4) P. 印文件代码 (Print)。将文件 CodeFile 以紧凑格式显示在终端上，每行50 个代码。同时将此字符形式的编码文件写入文件CodePrin 中。(5) T. 印哈夫曼树 (TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式 )显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据：(1) 利用下述中的数

5、据调试程序。(2) 用下表给出的字符集和频度的计数据建立哈曼树, 并实现以下报文的编码和译码： “THIS PROGRAM IS MY FAVORITE”. 。字符 A B C D E F G H I J K L 频数 186 64 13 22 32 103 21 15 47 57 1 5 32 字符 M N O P Q R S T U V W X Y Z 频数 20 57 63 15 1 48 51 80 23 8 18 1 16 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

6、 3 页，共 25 页 - - - - - - - - - 3. 课程设计报告内容哈夫曼编码 / 译码( 一) 、 需求分析1、 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编 / 译码系统。本次设计就是为这样的信息收发站写的一个哈夫曼的编/ 译码器。本课程设计要求：2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码3、演示程序以用户与计算机的对话方式执行，

7、即在计算机终端上显示“提示信息” 之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。4、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。5、在本系统中，用户可以对任意长的字符串可进行编码/ 译码。6、程序执行的命令包括：1) 初始化 (I) 2) 编码(E) 3) 译码(D) 4) 印代码文件 (P) 5) 印哈夫曼树 (T) 6) 退出(Q) 7、测试数据：(1) 利用下述中的数据调试程序。(2) 用下表给出的字符集和频度的计数据建立哈曼树, 并实现以下报文的编码和译码： “THIS PROGRAM IS MY FAV

8、ORITE”. 。字符 A B C D E F G H I J K L 频数 186 64 13 22 32 103 21 15 47 57 1 5 32 字符 M N O P Q R S T U V W X Y Z 频数 20 57 63 15 1 48 51 80 23 8 18 1 16 1 ( 二) 、概要设计为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：ADT HuffmanTree 数据对象： D=ai| aiCharSet,i=1,2,n, n0 数据关系： R= ai-1, aiD, ai-1基本操作 P：HuffmanTree

9、(); 构造函数 HuffmanTree(); 析构函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 25 页 - - - - - - - - - Initialization(int WeightNum); 操作结果：构造哈夫曼树。Encoder() 初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。操作结果：对字符串进行编码Decoder(); 初始条件：哈夫曼树已存在且已编码。操作结果：对二进制串进行译码Print() 初始条件：编码文件已存在。操作结果：把已保存

10、好的编码文件显示在屏幕TreePrinting() 初始条件：哈夫曼树已存在。操作结果：将已在内存中的哈夫曼树以直观的方式显示在终端上2. 本程序包含三个模块：1) 主程序模块：void main() 初始化；do 接受命令；处理命令；while(“命令” =”退出” ) 2) 、建树模块实现定义的抽象数据类型3) 、编/ 译码模块实现字符串的编/ 译码各模块之间的调用关系如下：主程序模块建树模块编/ 译码模块程序代码如下/ 程序名： HuffmanTree.h / 程序功能：哈夫曼树类的头文件( 并用其来实现编 / 译码) 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

11、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 25 页 - - - - - - - - - / 作者：蔡丽敏/ 日期： 2008.12.27 / 版本： 1.0 / 对应类实现文件 : HuffmanTree.cpp / 对应主程序文件 : main.cpp 1/ 程序名： HuffmanTree.h 2/ 程序功能：哈夫曼树类的头文件( 并用其来实现编 / 译码) 3 4/ 对应类实现文件 : HuffmanTree.cpp 5/ 对应主程序文件 : main.cpp 6 7 8 9#include 10#include 11#inc

12、lude 12using namespace std; 13struct HuffmanNode /定义哈夫曼树各结点14 15 int weight; /存放结点的权值，假设只考虑处理权值为整数的情况16 int parent; /记录结点父亲位置， -1 表示为根结点，否则表示为非根结点17 int lchild,rchild; /分别存放该结点的左、右孩子的所在单元的编号18; 19class HuffmanTree /建立哈夫曼树类20 21private: 22 HuffmanNode *Node; /哈夫曼树中结点的存储结构23 char *Info; /用来保存各字符信息24 i

13、nt LeafNum; /树中的叶子结点总数25public: 26 HuffmanTree(); /构造函数27 HuffmanTree(); /析构函数28 void Initialization(int WeightNum); /初始化函数：根据 WeightNum名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 25 页 - - - - - - - - - 个权值建立一棵哈夫曼树29 void Encoder(); /编码函数：利用构造好的哈夫曼树对字符进行编码30

14、 void Decoder(); /译码函数：对二进制串进行译码31 void Print(); /印文件函数：把已保存好的编码文件显示在屏幕32 void TreePrinting(); /印哈夫曼树函数：将已在内存中的哈夫曼树以直观的方式显示在终端上33; / 程序名： HuffmanTree.cpp / 程序功能：实现哈夫曼树类的源文件(并用其来实现编 / 译码) / 作者：蔡丽敏/ 日期： 2008.12.27 / 版本： 1.0 1#includeHuffmanTree.h 2#include 3 using namespace std; 4 5/*/ 6/ 构造函数 7/ 函数功能

15、：将结点指针初始化为NULL 8/ 函数参数：无 9/ 参数返回值：无 10HuffmanTree:HuffmanTree() 11 12 Node=NULL; /将树结点初始化为空 13 Info=NULL; /将字符数组初始化为空 14 LeafNum=0; /将叶子数初始化为0 15 16/*/ 17/ 析构函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 25 页 - - - - - - - - - 18/ 函数功能：将所有结点的空间释放 19/ 函数参数：无

16、20/ 参数返回值：无 21HuffmanTree:HuffmanTree() 22 23 delete Node; /释放结点空间 24 delete Info; /释放字符存储空间 25 26/*/ 27/ 初始化函数 28/ 函数功能：从终端读入字符集大小n，以及 n 个字符和 n 个权值 , 29/ 建立哈夫曼树 , 并将它存放在文件hfmTree 中. 30/ 函数参数： int WeightNum 表示代码个数 31/ 参数返回值：无 32void HuffmanTree:Initialization(int WeightNum) /初始化 33 34 int i,j,pos1,p

17、os2,max1,max2; / 35 36 Node=new HuffmanNode2*WeightNum-1; /WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1 个 37 /Info=new char2*WeightNum-1; 38 Info=new charWeightNum; 39 for(i=0;iWeightNum;i+) 40 41 cout请输入第 i+1Infoi; 45 getchar(); 46 coutNodei.weight; /输入权值 48 Nodei.parent=-1; /为根结点名师资料总结 - - -精品资料欢迎下载 - -

18、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 25 页 - - - - - - - - - 49 Nodei.lchild=-1; /无左孩子 50 Nodei.rchild=-1; /无右孩子 51 52 53 for(i=WeightNum;i2*WeightNum-1;i+) /表示需做 WeightNum-1次合并 54 55 pos1=-1; 56 pos2=-1; /分别用来存放当前最小值和次小值的所在单元编号 57 max1=32767; /32767为整型数的最大值 58 max2=32767; /分

19、别用来存放当前找到的最小值和次小值 59 60 for(j=0;ji;j+) /在跟节点中选出权值最小的两个 61 if(Nodej.parent=-1) /是否为根结点 62 if(Nodej.weightmax1) /是否比最小值要小 63 64 max2=max1; /原最小值变为次小值 65 max1=Nodej.weight; /存放最小值 66 pos2=pos1; /修改次小值所在单元编号 67 pos1=j; /修改最小值所在单元编号 68 69 else 70 if(Nodej.weightmax2) /比原最小值大但比原次小值要小 71 72 max2=Nodej.weig

20、ht; /存放次小值 73 pos2=j; /修改次小值所在的单元编号 74 75 /for 76 Nodepos1.parent=i; /修改父亲位置 77 Nodepos2.parent=i; 78 Nodei.lchild=pos1; /修改儿子位置 79 Nodei.rchild=pos2; 80 Nodei.parent=-1; /表示新结点应该是根结点 81 Nodei.weight=Nodepos1.weight+Nodepos2.weight; 82 /for 83 LeafNum=WeightNum; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

21、- - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 25 页 - - - - - - - - - 84 85 86 char ch; 87 coutch; 89 if(ch=y|ch=Y) 90 91 ofstream fop; /以二进制方式打开hfmTree.dat文件，并当重新运行时覆盖原文件 92 fop.open(hfmTree.dat,ios:out|ios:binary|ios:trunc); 93 if(fop.fail() /文件打开失败 94 cout文件打开失败！ n; 95 fop.write(char*)&WeightNu

22、m,sizeof(WeightNum); /写入 WeightNum 96 for(i=0;iWeightNum;i+) /把各字符信息写入文件 97 98 fop.write(char*)&Infoi,sizeof(Infoi); 99 flush(cout); 100 101 for(i=0;i2*WeightNum-1;i+) /把个节点内容写入文件102 103 fop.write(char*)&Nodei,sizeof(Nodei); 104 flush(cout); 105 106 fop.close(); /关闭文件107 108 cout 哈夫曼树已构造完成。 n; 109/I

23、nitialization 110 111/*/ 112/ 编码函数113/ 函数功能：利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入） ，114/ 对文件 ToBeTran中的正文进行编码 , 然后将结果代码存 ( 传输)到文件 CodeFile 中. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 25 页 - - - - - - - - - 115/ 函数参数：无116/ 参数返回值：无117void HuffmanTree:Encoder()

24、118 119 if(Node=NULL) /哈夫曼树不在内存，从文件hfmTree 中读入120 121 ifstream fip; /以二进制方式打开 hfmTree.dat文件122 fip.open(hfmTree.dat,ios:binary|ios:in); 123 if(fip.fail() /文件打开失败124 125 cout文件打开失败！ n; 126 return; /结束本函数127 128 fip.read(char*)&LeafNum,sizeof(LeafNum); /读取叶子数129 Info=new charLeafNum; 130 Node=new Huff

25、manNode2*LeafNum-1; 131 for(int i=0;iLeafNum;i+) /读取字符信息132 fip.read(char*)&Infoi,sizeof(Infoi); 133 for(i=0;i2*LeafNum-1;i+) /读取结点信息134 fip.read(char*)&Nodei,sizeof(Nodei); 135 136 137 char *Tree; /用于存储需编码内容138 int i=0,num; 139 char Choose; /让用户选择读取文件或重新输入需编码内容140 coutChoose; 142 if(Choose=1) /读取文件

26、 ToBeTran.txt 143 144 ifstream fip1(ToBeTran.txt); 145 if(fip1.fail() /文件不存在146 147 cout文件打开失败 !n; 148 return; /结束本函数149 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 25 页 - - - - - - - - - 150 char ch; 151 int k=0; 152 while(fip1.get(ch) 153 154 k+; /计算 Code

27、File 中代码长度155 156 fip1.close(); 157 158 Tree=new chark+1; 159 ifstream fip2(ToBeTran.txt); 160 161 k=0; 162 while(fip2.get(ch) 163 164 Treek=ch; /读取文件内容，并存到Tree 中165 k+; 166 167 fip2.close(); 168 Treek=0; /结束标志169 cout需编码内容为 :; 170 coutTreeendl; 171 /if(Choose=1) 172 173 else /Choose!=1,重新输入174 175

28、string tree; /用于输入需编码内容，由于string类对象可以输入任意长度，176 /所以先利用这个对象输入，再转存在Tree 中177 178 cin.ignore(); 179 cout请输入需要编码的内容 ( 可输入任意长，结束时请按2 下回车):n; 180 getline(cin,tree,n); /输入任意长字符串，181 /getline以回车 (n)作为结束符， 第一次按回车表示字符串结束，第二次按回车才开始输出。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

29、 第 12 页，共 25 页 - - - - - - - - - 182 while(treei!=0) 183 i+; 184 num=i; /计算 tree 长度185 i=0; 186 Tree=new charnum+1; 187 while(treei!=0) /将 tree 中的字符转存到 Tree 中188 189 Treei=treei; 190 i+; 191 192 Treei=0; /结束标志符193 194 195 ofstream fop(CodeFile.dat,ios:trunc); /存储编码后的代码 ,并覆盖原文件196 i=0; 197 int k=0; 1

30、98 char *code; 199 code=new charLeafNum; /为所产生编码分配容量为LeafNum的存储空间200 /因为不等长编码中最长的编码一定不会超过要求编码的字符个数201 while(Treek!=0) /对每一个字符编码202 203 int j,start=0; 204 for(i=0;iLeafNum;i+) 205 if(Infoi=Treek) /求出该文字所在单元的编号206 break; 207 j=i; 208 while(Nodej.parent!=-1) /结点 j 非树根209 210 j=Nodej.parent; /非结点 j 的双亲结

31、点211 if(Nodej.lchild=i) /是左子树，则生成代码0 212 codestart+=0; 213 else /是右子树，则生成代码1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 25 页 - - - - - - - - - 214 codestart+=1; 215 i=j; 216 217 codestart=0; /置串结束符218 219 220 for(i=0;istart/2;i+) /对二进制序列进行逆置221 222 j=codei

32、; 223 codei=codestart-i-1; 224 codestart-i-1=j; 225 226 i=0; 227 while(codei!=0) /存储代码228 229 fopcodei; 230 i+; 231 232 k+; 233 234 fop.close(); 235 cout 已编码！且存到文件CodeFile.dat中！nn; 236 /Encode 237 238/*/ 239/ 译码函数240/ 函数功能：利用已建好的哈夫曼树, 对传输到达的 CodeFile 中的数据代码进行译码 , 241/ 将译码结果存入文件TextFile中. 242/ 函数参数：无

33、243/ 参数返回值：无244void HuffmanTree:Decoder() 245 246 int i=0,k=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 25 页 - - - - - - - - - 247 int j=LeafNum*2-1-1; /表示从根结点开始往下搜索248 char* BitStr; 249 250 ifstream fip1(CodeFile.dat); /利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码25

34、1 if(fip1.fail() /文件打开失败，还未编码252 253 cout 请先编码！ n; 254 return; 255 256 cout 经译码, 原内容为 :; 257 char ch; 258 while(fip1.get(ch) 259 260 k+; /计算 CodeFile 中代码长度261 262 fip1.close(); 263 264 BitStr=new chark+1; 265 ifstream fip2(CodeFile.dat); 266 k=0; 267 while(fip2.get(ch) 268 269 BitStrk=ch; /读取文件内容270

35、 k+; 271 272 fip2.close(); 273 BitStrk=0; /结束标志符274 if(Node=NULL) /还未建哈夫曼树275 276 cout请先编码 !n; 277 return; 278 279 ofstream fop(TextFile.dat); /将字符形式的编码文件写入文件 CodePrin 中名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 25 页 - - - - - - - - - 280 while(BitStri!=0)

36、 281 282 if(BitStri=0) 283 j=Nodej.lchild; /往左走284 else 285 j=Nodej.rchild; /往右走286 if(Nodej.rchild=-1) /到达叶子结点287 288 coutInfoj; /输出叶子结点对应的字符289 j=LeafNum*2-1-1; /表示重新从根结点开始往下搜索290 fopInfoj; /存入文件291 /if、292 i+; 293 /while 294 fop.close(); 295 296 coutn译码成功且已存到文件TextFile.dat中！nn; 297/Decoder 298/*/

37、 299/ 印文件代码函数300/ 函数功能：将文件CodeFile 以紧凑格式显示在终端上，301/ 每行 50 个代码。同时将此字符形式的编码文件写入文件CodePrin 中。302/ 函数参数：无303/ 参数返回值：无304void HuffmanTree:Print() 305 306 char ch; 307 int i=1; 308 ifstream fip(CodeFile.dat); /读取文件309 ofstream fop(CodePrin.dat); /存储文件310 if(fip.fail() 311 312 cout没有文件，请先编码！ n; 名师资料总结 - -

38、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 25 页 - - - - - - - - - 313 314 return; 315 316 while(fip.get(ch) 317 318 coutch; /读取文件内容319 fopch; /存到文件中320 if(i=50) /每行输出 50 个字符321 322 coutendl; 323 i=0; 324 325 i+; 326 327 coutendl; 328 fip.close(); /关闭 CodeFile.dat文件32

39、9 fop.close(); /关闭 CodePrin.dat文件330 331/*/ 332/ 印哈夫曼树函数333/ 函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式 )显示在终端上，334/ 同时将此字符形式的哈夫曼树写入文件TreePrint中。335/ 函数参数：无336/ 参数返回值：无337void HuffmanTree:TreePrinting() 338 339 if(Node=NULL) /未建立哈夫曼树340 341 cout请先建立哈夫曼树！ n; 342 return; 343 344 int i; 345 int j=0,k=LeafNum-1; 名

40、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 25 页 - - - - - - - - - 346 string *HC; 347 HC=new stringLeafNum; /定义存储 Huffman 编码字符串数组348 for (i=0;iLeafNum;i+) 349 350 char *temp=new char100; /实验目的，本处没有求二叉树的深度，而采用固定长度的数组存储Huffman 中间编码351 int k=100; 352 int m=i;

41、353L1:if (Nodem.parent!=-1) /自定义跳转标签354 355 if (NodeNodem.parent.lchild=m) 356 357 temp-k=1; 358 359 else 360 361 temp-k=0; 362 363 m=Nodem.parent; 364 goto L1; /跳转到指定的标签L1 365 366 else 367 368 int n; 369 for (n=k;n100;n+) 370 371 HCi=HCi+tempn; 372 373 374 couti+1号字符的编码为： HCin; /输出 Huffman编码375 376

42、 377 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 25 页 - - - - - - - - - / 程序名： main.cpp / 程序功能：主函数源文件/ 作者：蔡丽敏/ 日期： 2008.12.27 / 版本： 1.0 / 主函数/ 参数返回值：无1/ 程序名： main.cpp 2/ 程序功能：主函数源文件 3 4#includeHuffmanTree.h 5#include 6#include 7 8/*/ 9/ 主函数10/ 参数返回值：无11 12i

43、nt main() 13 14 15 cout(I) 初始化;n; 16 cout(E) 编码;n; 17 cout(D) 译码;n; 18 cout(P) 印代码文件 ;n; 19 cout(T) 印哈夫曼树 n; 20 cout(Q) 退出nn; 21 HuffmanTree huftree; /定义哈夫曼树对象22 int weight; 23 char Choose; 24 while(1) 25 26 coutChoose; 28 switch(Choose) 29 30 case I: 31 case i: 32 coutweight; 34 huftree.Initializat

44、ion(weight); /初始化哈夫曼树35 break; 36 case E: 37 case e: 38 huftree.Encoder(); 39 break; 40 case D: 41 case d: 42 huftree.Decoder(); 43 break; 44 case P: 45 case p: 46 huftree.Print(); 47 break; 48 case T: 49 case t: 50 huftree.TreePrinting(); 51 break; 52 case Q: 53 case q: 54 coutn *感谢使用本系统 !*nn; 55 s

45、ystem(pause); /暂停运行56 return 0; 57 58 cout(I) 初始化;n; 59 cout(E) 编码;n; 60 cout(D) 译码;n; 61 cout(P) 印代码文件 ;n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 25 页 - - - - - - - - - 62 cout(T) 印哈夫曼树 n; 63 cout(Q) 退出nn; 64 65 66 ( 四) 、调试分析1、由于二维指针和string类，还有文件操作的推敲

46、不足， 使程序调试时费时不少。还有对单个空格字符的输入，也花了一些时间， 不过最终能实现单个空格的输入，还是值得的。2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性，特别是文件操作方面，如果可能的话，可以把文件读入、读出分别写成一个函数（就是把文件名作为参数） ，然后就可以直接调用了。3、本程序模块划分比较合理，且利用指针和string类对象实现字符串的操作，操作方便。4、算法的时空分析在此程序中，存储字符串都用了指针，先动态申请空间，然后再存，这样就有效的利用了空间，不过为了实现任意长字符串的输入，引入了string类，先定义string对象，再输入。最后转存到字符

47、指针里，这样就浪费了一些空间。而对于哈夫曼树算法本身，由于这里只是一个静态的，所以当进行网络传输时，可能会显得效率比较低。5、本实验采用数据抽象的程序设计方法，将程序分为3 个模块，使得设计时思路清晰，实现时调试可以顺利完成， 各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。( 五) 、用户手册1、本程序的运行环境为DOS 操作系统2、进入演示程序后即显示文本方式的用户界面3、进入界面后，就会提示输入字符串的输入形式，结束符为“回车符”。( 六) 、测试结果(1) I. 初始化(Initialization)。从终端读入字符集大小n，以及 n 个字符和 n个权值 , 建立哈夫曼树

48、, 并将它存放在文件hfmTree 中. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 25 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 25 页 - - - - - - - - - (2) E. 编码(Encoding) 。利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree 中读入） ， 对

49、文件 ToBeTran中的正文进行编码 , 然后将结果代码存 (传输)到文件 CodeFile 中. (3) D. 译码(Decoding) 。利用已建好的哈夫曼树, 对传输到达的 CodeFile 中的数据代码进行译码 , 将译码结果存入文件TextFile中. (4) P. 印文件代码 (Print)。将文件 CodeFile 以紧凑格式显示在终端上，每行50 个代码。同时将此字符形式的编码文件写入文件CodePrin 中。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页

50、，共 25 页 - - - - - - - - - (5) T. 印哈夫曼树 (TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式 )显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。（6）Q 退出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 25 页 - - - - - - - - - ( 七) 、附录源程序文件名清单：HuffmanTree.h /元素结点定义单元HuffmanTree.cpp /链表实现单元mai