数据结构课程教学设计报告.doc

!- 数据结构课程设计报告 题目： 哈夫曼树和编码应用 学生姓名：学 号： 班 级：指导教师： 2011年 6 月 3日目录l 课程设计目的-3l 课程设计题目-3l 需求分析-4l 设计原理-4l 系统功能框架图-5l 流程图-6l 设计思路-71. 主函数2. 创建哈夫曼树3. 输出哈夫曼树4. 对哈夫曼树进行编码5. 译码l 程序源代码-8l 运行结果-13l 实验心得-21一、课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。二、课程设计题目-哈夫曼树和编码应用（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树的存储结构；（2）利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对给定的n个字符正文进行编码，并输出每个字符的编码。（3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符序列，并输出结果。三、需求分析 1、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。本实验要求：2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。4、在本系统中，用户可以对任意字符串进行编码/译码。5、程序执行的命令包括：1) 创建哈弗曼树2) 输出哈夫曼树3) 对哈夫曼树进行编码 4) 输出哈弗曼编码5) 译码6) 退出(Q)6、测试数据：（）利用教科书例6-31中的数据调试程序。（）权值：1、3、5、7四、设计原理将建立哈夫曼树、实现哈弗曼编码、哈弗曼译码都定义成类成员函数，然后在主函数中调用它们。建立哈夫曼树时，将哈夫曼树的结构定义为一个类的一维数组，类成员为权值、双亲、左孩子、右孩子、字符、编码、编码开始的位置，还有各项功能函数。用一个数组类hftree 存储。要实现哈夫曼编码，只要在所创建的哈夫曼树上进行二进制编码：往左走，编码为0，往右走编码为1，然后将从根结点到树叶的所有0、1排列起来，则得到该树叶的哈弗曼编码。用一个数组类code 存储哈夫曼译码，就是将输入的编码还原成对应的字符。五、系统功能框架图主函数主菜单Switch选择Case1创建哈夫曼树Case2输出哈夫曼树Case3对哈夫曼树进行编码Case4输出哈夫曼树编码Case5译码Case6退出程序程序流程图：Y输入所需要执行的功能chch=1ch=2ch=3ch=4ch=5ch=6NNNNN内存Y输入所创建的哈夫曼树读入数据Y内存输出哈夫曼树数据Y内存对哈夫曼树进行编码读入数据内存输出哈弗曼编码数据YY内存结束开始对哈夫曼树进行译码输入需要进行译码的数据b=3YN六、设计思路： 根据题目的要求，在这个程序的设计中，我们要创建哈夫曼树，还要对哈夫曼树进行编码和译码，所以我运用了类，类的成员函数有结点的双亲结点，左、右孩子结点，权值，数据，编码和各种功能函数。然后运用所学的数据结构中的有关哈夫曼树的知识完成该程序的设计。 l 主函数用while函数实现窗口选择界面的循环。再构建一个switch的选择，根据用户对功能的需要，进入具有不同功能的函数，每一个case选择后都以break跳出。最后当输入字符为6时结束，while的界面循环。结束程序。l 创建哈夫曼树 输入权值、字符之后，因为分左右孩子，所以定义整型变量p1,p2分别指向两个权值最小位置，定义整型变量s1,s2分别代表两个最小权值。利用for循环选择没有双亲结点的权值与最小权值s1进行比较，如果小于s1，则将其权值赋予s1，位置为p1；如果大于s1,小于s2，则将其权值赋予s2，位置为p2；如果大于s2，则重新选择。当所有的位置确定之后，将左右孩子依次进行合并。哈夫曼树创建成功。l 输出哈夫曼树利用一个for循环，将所创建的哈夫曼树的所有权值、双亲、左孩子、右孩子全部输出就输出了一个哈夫曼树。 l 对哈夫曼树进行编码在所创建的哈夫曼树上进行二进制编码：是其双亲的左孩子，编码为0；是其双亲的右孩子，编码为1；然后将从根结点到树叶的所有0、1排列起来，则得到该树叶的哈弗曼编码。l 输出哈弗曼编码利用一个for循环，将所创建的哈夫曼树的字符、权值所对应的哈弗曼二进制编码输出。l 译码用while循环输入二进制编码，以3结束。找到二进制编码所对应的结点在哈夫曼树中对应的位置，输出该位置的字符。这就是二进制编码的译码。七、程序源代码#include#include#include#include#include#includeclass treepublic:float weight; /权值int parent,lchild,rchild; /双亲结点，左、右孩子结点 int bit99; /编码的存放位置int start; /编码开始的位置char data; /字符内容void creathuffmantree(tree hftree,int m,int n);void printhuffmantree(tree hftree,int m);void huffmancode(tree hftree,tree code,int n);void printhuffmancode(tree hftree,tree code,int n);void trancode(tree hftere,tree code,int m);void tree:creathuffmantree(tree hftree,int m,int n)/创建哈夫曼树 int i,j,p1,p2;float s1,s2;for(i=1;i=m;i+)/初始化hftreei.parent=0;hftreei.lchild=0;hftreei.rchild=0;hftreei.weight=0;cout请输入n个权值endl;for(i=1;ihftreei.weight; cout请输入n个字符endl; for(i=1;ihftreei.data ;for(i=n+1;i=m;i+)p1=p2=0; /p1、p2分别指向两个权值最小的位置s1=s2=32767; /代表两个最小权值for(j=1;j=i-1;j+)if(hftreej.parent=0)if(hftreej.weights1) /比较s2=s1;s1=hftreej.weight;p2=p1;p1=j;elseif(hftreej.weights2)s2=hftreej.weight;p2=j;hftreep1.parent=i; /合并hftreep2.parent=i;hftreei.lchild=p1;hftreei.rchild=p2;hftreei.weight=hftreep1.weight+hftreep2.weight;cout返回!endl; void tree:printhuffmantree(tree hftree,int m) cout输出哈夫曼树endl;for(int i=1;i=m;i+)couti hftreei.weight hftreei.parent hftreei.lchild hftreei.rchildendl;cout返回!endl;void tree:huffmancode(tree hftree,tree code,int n) /编码int c,p;tree cd;for (int i=1;i=n;i+)cd.start=n+1;c=i;p=hftreei.parent;while(p!=0) cd.start-;cd.data=hftreei.data;if(hftreep.lchild=c)cd.bitcd.start=0;else cd.bitcd.start=1;c=p;p=hftreep.parent;codei=cd;cout返回!endl;void tree:printhuffmancode(tree hftree,tree code,int n)for(int i=1;i=n;i+)cout字符 hftreei.data的权值为:hftreei.weightsetw(5)编码为:;for(int j=codei.start;j=n;j+)coutcodei.bitj ;coutendl;cout返回!endl;void tree:trancode(tree hftree,tree code,int m)/译码int i=m;char b;cout请输入需要翻译的编码(以3结束译码):b;while(b!=3) if(b=0)i=hftreei.lchild;else i=hftreei.rchild;if(hftreei.lchild=0)cout译码为：endl;couthftreei.datab; cout返回!endl;void main() int k,n,m; ifstream input_file; /文件输入输出流 ofstream output_file; tree t; tree hftree99; tree code99; char cn; while(cn!=6) cout *哈夫曼编码*endl; coutendl; coutendl; coutendl; cout 1 建立哈夫曼树endl; cout 2 输出哈夫曼树endl; cout 3 哈夫曼树编码endl; cout 4 输出哈夫曼编码endl; cout 5 译码 endl; cout 6 退出endlendl; coutcn; coutendl; switch (cn) case 1: coutk; n=k; m=2*n-1; t.creathuffmantree(hftree, m, n); break; /生成huffman树 case 2:t.printhuffmantree(hftree,m);break; case 3:t.huffmancode(hftree,code,n);break; case 4:t.printhuffmancode(hftree,code,n);break; case 5:t.trancode(hftree,code,m);break; coutendl; coutendl; cout 欢迎使用！endl;八、运行结果九、实验心得哈夫曼编码是一种无损压缩编码方式，以哈夫曼树-即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法，用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。当然本程序的目的不在于如何去压缩一个文件信息，而是通过创建哈夫曼树，由哈夫曼树编码得二进制编码，再对其进行译码，来了解哈夫曼树编码实现过程。从而学习了解哈夫曼树及其编码，也是为了帮助数据结构和计算机语言初学者学习之用。此程序不完美，还有很多有待完善的地方。而我也应该加强对数据结构和C+语言的学习和应用。这样才能为自己的以后打下扎实的基础。