《哈夫曼树的应用》课程设计.doc

哈夫曼树的应用课程设计学生姓名： 学 号： 专业班级： 计算机科学与技术051班 指导教师： 二00八年十二月二十七日目 录1.课程设计目的 12.课程设计题目设计和要求 13. 课程设计报告内容 14. 结论 255.参考书目 251. 课程设计目的 树型结构是一种应用极为广泛的非线性数据结构,也是本课程设计的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次课程设计突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的. 2. 课程设计题目描述和要求 【问题描述】 利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统. 【基本要求】：一个完整的系统应以下功能: (1) I. 初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中. (2) E. 编码(Encoding)。利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中. (3) D. 译码(Decoding)。利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile中. (4) P. 印文件代码(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 测试数据： (1) 利用下述中的数据调试程序。 (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 3.课程设计报告内容哈夫曼编码/译码 (一)、 需求分析 1、 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时 间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。 本课程设计要求： 2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码 3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。 4、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。 5、在本系统中，用户可以对任意长的字符串可进行编码/译码。 6、程序执行的命令包括： 1) 初始化(I)2) 编码(E)3) 译码(D) 4) 印代码文件(P)5) 印哈夫曼树(T)6) 退出(Q) 7、测试数据： (1) 利用下述中的数据调试程序。 (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 (二)、概要设计 为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。 1. 抽象数据类型定义为： ADT HuffmanTree 数据对象：D=ai| aiCharSet,i=1,2,n, n0 数据关系：R= ai-1, aiD, ai-1基本操作P： HuffmanTree(); 构造函数 HuffmanTree(); 析构函数 Initialization(int WeightNum); 操作结果：构造哈夫曼树。 Encoder() 初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。 操作结果：对字符串进行编码 Decoder(); 初始条件：哈夫曼树已存在且已编码。 操作结果：对二进制串进行译码 Print() 初始条件：编码文件已存在。 操作结果：把已保存好的编码文件显示在屏幕 TreePrinting() 初始条件：哈夫曼树已存在。 操作结果：将已在内存中的哈夫曼树以直观的方式显示在终端上 2.本程序包含三个模块： 1)主程序模块： void main() 初始化； do 接受命令； 处理命令； while(“命令”=”退出”) 2)、建树模块实现定义的抽象数据类型 3)、编/译码模块实现字符串的编/译码 各模块之间的调用关系如下： 主程序模块 建树模块 编/译码模块程序代码如下 / 程序名：HuffmanTree.h / 程序功能：哈夫曼树类的头文件(并用其来实现编/译码) / 作者：蔡丽敏 / 日期：2008.12.27 / 版本：1.0 /对应类实现文件: HuffmanTree.cpp /对应主程序文件: main.cpp 1/ 程序名：HuffmanTree.h 2/ 程序功能：哈夫曼树类的头文件(并用其来实现编/译码) 3 4/对应类实现文件: HuffmanTree.cpp 5/对应主程序文件: main.cpp 6 7 8 9#include10#include11#include12using namespace std;13struct HuffmanNode /定义哈夫曼树各结点1415 int weight; /存放结点的权值，假设只考虑处理权值为整数的情况16 int parent; /记录结点父亲位置，-1表示为根结点，否则表示为非根结点17 int lchild,rchild; /分别存放该结点的左、右孩子的所在单元的编号18;19class HuffmanTree /建立哈夫曼树类2021private:22 HuffmanNode *Node; /哈夫曼树中结点的存储结构23 char *Info; /用来保存各字符信息24 int LeafNum; /树中的叶子结点总数25public:26 HuffmanTree(); /构造函数27 HuffmanTree(); /析构函数28 void Initialization(int WeightNum); /初始化函数：根据WeightNum个权值建立一棵哈夫曼树29 void Encoder(); /编码函数：利用构造好的哈夫曼树对字符进行编码30 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/ 函数功能：将结点指针初始化为NULL 8/ 函数参数：无 9/ 参数返回值：无 10HuffmanTree:HuffmanTree() 11 12 Node=NULL; /将树结点初始化为空 13 Info=NULL; /将字符数组初始化为空 14 LeafNum=0; /将叶子数初始化为0 15 16/*/ 17/ 析构函数 18/ 函数功能：将所有结点的空间释放 19/ 函数参数：无 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,pos2,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; /为根结点 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; /分别用来存放当前找到的最小值和次小值 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.weight; /存放次小值 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; 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*)&WeightNum,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/Initialization110111/*/112/ 编码函数113/ 函数功能：利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），114/ 对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.115/ 函数参数：无116/ 参数返回值：无117void HuffmanTree:Encoder()118119 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 HuffmanNode2*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) /读取文件ToBeTran.txt143 144 ifstream fip1(ToBeTran.txt);145 if(fip1.fail() /文件不存在146 147 cout文件打开失败!n;148 return; /结束本函数149 150 char ch;151 int k=0;152 while(fip1.get(ch) 153 154 k+; /计算CodeFile中代码长度155 156 fip1.close(); 157 158 Tree=new chark+1;159 ifstream fip2(ToBeTran.txt);160161 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)172173 else /Choose!=1,重新输入174 175 string tree; /用于输入需编码内容，由于string类对象可以输入任意长度，176 /所以先利用这个对象输入，再转存在Tree中177 178 cin.ignore();179 cout请输入需要编码的内容(可输入任意长，结束时请按2下回车):n;180 getline(cin,tree,n); /输入任意长字符串，181 /getline以回车(n)作为结束符，第一次按回车表示字符串结束，第二次按回车才开始输出。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;198 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的双亲结点211 if(Nodej.lchild=i) /是左子树，则生成代码0212 codestart+=0;213 else /是右子树，则生成代码1214 codestart+=1;215 i=j;216 217 codestart=0; /置串结束符218219 220 for(i=0;istart/2;i+) /对二进制序列进行逆置221 222 j=codei;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 /Encode237238/*/239/ 译码函数240/ 函数功能：利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,241/ 将译码结果存入文件TextFile中.242/ 函数参数：无243/ 参数返回值：无244void HuffmanTree:Decoder()245246 int i=0,k=0;247 int j=LeafNum*2-1-1; /表示从根结点开始往下搜索248 char* BitStr;249 250 ifstream fip1(CodeFile.dat); /利用已建好的哈夫曼树将文件CodeFile中的代码进行译码251 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 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中280 while(BitStri!=0)281 282 if(BitStri=0)283 j=Nodej.lchild; /往左走284 else285 j=Nodej.rchild; /往右走286 if(Nodej.rchild=-1) /到达叶子结点287 288 coutInfoj; /输出叶子结点对应的字符289 j=LeafNum*2-1-1; /表示重新从根结点开始往下搜索290 fopInfoj; /存入文件291 /if、292 i+;293 /while294 fop.close();295 296 coutn译码成功且已存到文件TextFile.dat中！nn;297/Decoder298/*/299/ 印文件代码函数300/ 函数功能：将文件CodeFile以紧凑格式显示在终端上，301/ 每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。302/ 函数参数：无303/ 参数返回值：无304void HuffmanTree:Print()305306 char ch;307 int i=1;308 ifstream fip(CodeFile.dat); /读取文件309 ofstream fop(CodePrin.dat); /存储文件310 if(fip.fail()311 312 cout没有文件，请先编码！n;313314 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文件329 fop.close(); /关闭CodePrin.dat文件330331/*/332/ 印哈夫曼树函数333/ 函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，334/ 同时将此字符形式的哈夫曼树写入文件TreePrint中。335/ 函数参数：无336/ 参数返回值：无337void HuffmanTree:TreePrinting()338339 if(Node=NULL) /未建立哈夫曼树340 341 cout请先建立哈夫曼树！n;342 return;343 344 int i;345 int j=0,k=LeafNum-1;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;353L1:if (Nodem.parent!=-1) /自定义跳转标签354 355 if (NodeNodem.parent.lchild=m)356 357 temp-k=1;358 359 else360 361 temp-k=0;362 363 m=Nodem.parent;364 goto L1; /跳转到指定的标签L1365 366 else367 368 int n;369 for (n=k;n100;n+)370 371 HCi=HCi+tempn;372 373 374 couti+1号字符的编码为：HCin; /输出Huffman编码375 376377/ 程序名：main.cpp / 程序功能：主函数源文件 / 作者：蔡丽敏 / 日期：2008.12.27 / 版本：1.0 / 主函数 /参数返回值：无 1/ 程序名：main.cpp 2/ 程序功能：主函数源文件 3 4#includeHuffmanTree.h 5#include 6#include 7 8/*/ 9/ 主函数10/参数返回值：无1112int main()131415 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.Initialization(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 system(pause); /暂停运行56 return 0;57 58 cout(I) 初始化;n;59 cout(E) 编码;n;60 cout(D) 译码;n;61 cout(P) 印代码文件;n;62 cout(T) 印哈夫曼树n;63 cout(Q) 退出nn;64 6566(四)、调试分析 1、由于二维指针和string类，还有文件操作的推敲不足，使程序调试时费时不少。还有对单个空格字符的输入，也花了一些时间，不过最终能实现单个空格的输入，还是值得的。 2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序