数据结构设计报告2.docVIP

数据结构 课程设计报告 专 业 计算机科学与技术 班 级 0902班 学 号 2009115010207 姓 名 夏丽霞 指 导 教 师 夏端峰老师 时 间 湖 北 师 范 学 院 计 算 机 科 学 与 技 术 学 院 第二章 赫夫曼编码的应用 随着赫夫曼编码应用的广泛普及，深入了解和准确掌握赫夫曼编码已经成为每一个计算机专业学子最基本的要求。那么究竟什么是赫夫曼编码呢？ 利用赫夫曼树求得的用于通信的二进制编码即称为赫夫曼编码。树中从根结点到每个叶子都有一条路径，对路径上的分支进行约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子对应的字符的编码极为赫夫曼编码。 假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n中字符，则电文总长度为∑WiLi。若将此对应到二叉树上，Wi为叶子节点的权，Li为根结点到叶子结点的路径长度。那么，∑WiLi恰好为二叉树上带权路径长度。 2.1 设计要求 本章实验的设计要求是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。要求实现： （1）赫夫曼树的建立； （2）赫夫曼编码的生成； （3）编码文件的译码。 2.2 设计分析 该程序是要将电文（实际上就是一串字符串）中不同字符分别作为叶子结点元素，将其在该字符串中出现的次数作为结点的权值，构造一棵赫夫曼树，并得到各个叶子结点的赫夫曼编码直至整个输入的字符串的赫夫曼编码。以实现电文的编码。而后再进行逆过程实现电文的译码。 根据设计要求分析，为实现上述功能，应将变量定义函数、三个功能函数及主控函数分别放在不同的源程序文档中，然后将所有函数放在一个文件夹里，当前面几个源程序分别调试完成后即可进行整个电文编码/译码系统程序的运行测试了。 2.3 算法实现 赫夫曼树的建立 赫夫曼算法的定义：初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n-1次合并，所以共产生n-1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的赫夫曼树中一共有2n-1个结点，其中n个叶结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。 赫夫曼树的存储结构描述为： #define n 100 #define m 2*n-1 typedef struct { int weight; int lchild,rchild,parent; }HTNode; typedef HTNode HuffmanTree[m+1]; 要实现赫夫曼树算法，首先要实现在HT[1…k]中选择parent为0且权值最小的两个根结点的选择算法；另外，还要有一个实现统计输入电文字符串中的各种字符出现的频率以及字符的种类的算法。假设电文中仅含有大写字符。 赫夫曼树建立的三步骤： （1）选择parent为0且权值最小的两个根结点的算法； （2）统计字符串中字符的种类以及各类字符的个数； 假设电文字符串全是大写字母，那么该算法的实现思想是：先定义一个含有26个元素的临时整型数据，用来存储各种字母出现的次数。因为大写字母的ASCII码与整数1-26之间相差64，因此在算法中使用字母减去64作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；另外，要求出电文字符串中有多少种字符，并保存这些字符以供编码时使用。统计和保存都比较容易实现，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组的元素中。 （3）构造赫夫曼树。 赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedef struct { char ch; char bits[9]; int len; }CodeNode; typedef CodeNode HuffmanCode[n+1]; 其大致步骤如下： （1）赫夫曼编码算法 （2）建立正文的编码文件 建