1、数据结构与算法设计数据结构与算法设计 课程设计任务书课程设计任务书 题 目 哈弗曼编码 学生姓名 学号 专业班级 设 计 内 容 与 要 求 【问题描述】 哈弗曼编码在数据压缩方面应用十分广泛.本课程设计主要是用哈弗曼树(最优 二叉树)实现字符串编码及哈弗曼树的 GUI 输出,并验证哈弗曼编码能否与实际应用 相吻合,进而总结哈弗曼树的实际应用价值. 【软件功能】 1) 实现哈弗曼树的构建； 2）利用哈弗曼树生成叶结点字符的哈弗曼编码； 3) 实现各字符哈弗曼编码及哈弗曼树的 GUI 界面输出. 【算法思想】 （一）哈弗曼编码利用的抽象数据存储结构是链表、数组和基于链表的二叉树。 在实现过程中先
2、将各字符根据权值从小到大存储于在逻辑上连续叶节点的链表中， 然后根据链表比较选取最小和次小两权值建立子二叉树，且子二叉树根节点保存其 子节点权值之和，通过子二叉树根节点权值与链表上其他节点权值再比较，进而合 并，重组，循环最终构建成基于链表的最优二叉树即哈弗曼树。最后，使左分支为 0，右分支为 1，从叶节点向上直到根节点循环遍历哈弗曼树，获得各字符哈弗曼编 码，并保存于相应字符的哈弗曼树叶节点的顺序存储结构数组中。 （二）功能实现模块： 1) 调用统计频数函数和排序函数，根据权值从小到大生成 List 类型的链表； 2) 调用建树函数，根据链表比较选取最小和次小两权值建立二叉树，记录节 点的左
3、右孩子及双亲的位置关系，最终构建成哈弗曼树，且记录的左孩子权值小于 右孩子； 3) 调用编码函数，根据已建立的哈夫曼树，从叶结点向上直到根结点建立哈 夫曼编码，并保存于相应字符的哈弗曼树叶结点的顺序存储结构中。 4) 调用遍历函数和打印函数，遍历各字符的哈弗曼编码并打印在 GUI 界面上； 起止时间 2012 年 6 月 18 日 至 2012 年 7 月 1 日 指导教师签名 2012 年 6 月 18 日 系（教研室）主任签名 2012 年 6 月 18 日 学生签名 年 月 日 以 Java 编程语言，要求软件带有简单的 GUI（利用 AWT 或者 Swing实现） ； 附：报告格式 数
4、据结构与算法设计课程设计 【设计题目】 哈弗曼编码 【问题描述】 哈弗曼编码在数据压缩方面应用十分广泛.本课程设计主要是用哈 弗曼树(最优二叉树)实现字符串编码及哈弗曼树的 GUI 输出,并验证哈 弗曼编码能否与实际应用相吻合,进而总结哈弗曼树的实际应用价值. 【软件功能】 1) 实现哈弗曼树的构建； 2）利用哈弗曼树生成叶结点字符的哈弗曼编码； 3) 实现各字符哈弗曼编码及哈弗曼树的 GUI 界面输出. 【算法思想】 （一）哈弗曼编码利用的抽象数据存储结构是链表、数组和基于链 表的二叉树。在实现过程中先将各字符根据权值从小到大存储于在逻辑 上连续叶节点的链表中，然后根据链表比较选取最小和次小
5、两权值建立 子二叉树，且子二叉树根节点保存其子节点权值之和，通过子二叉树根 节点权值与链表上其他节点权值再比较，进而合并，重组，循环最终构 建成基于链表的最优二叉树即哈弗曼树。最后，使左分支为 0，右分支 为 1，从叶节点向上直到根节点循环遍历哈弗曼树，获得各字符哈弗曼 编码，并保存于相应字符的哈弗曼树叶节点的顺序存储结构数组中。 （二）功能实现模块： 1) 调用统计频数函数和排序函数，根据权值从小到大生成 List类型的链表； 2) 调用建树函数，根据链表比较选取最小和次小两权值建立二叉 树，记录节点的左右孩子及双亲的位置关系，最终构建成哈弗曼树，且 记录的左孩子权值小于右孩子； 3) 调用
6、编码函数，根据已建立的哈夫曼树，从叶结点向上直到根结 点建立哈夫曼编码，并保存于相应字符的哈弗曼树叶结点的顺序存储结 构中。 4) 调用遍历函数和打印函数， 遍历各字符的哈弗曼编码并打印在GUI 界面上； 【逻辑结构设计】 本课程设计应用的逻辑结构设计包括：线性非连续的的链式存储结构、 线性连续的数组存储结构和基于链表的二叉树。 【存储结构设计】 （1）哈弗曼树结点存储结构设计类： class TreeNode private int weight; /统计该节点的字符属性在文件中出现得频率 private char ch; /节点的字符属性 private TreeNode right;/右节点 private TreeNode left; /左节点 private TreeNode parent; /父节点 private String hfmcode=“; /保存编码的属性 private st
