c++数据结构试验哈夫曼树

c++c++数据结构实验哈夫曼树数据结构实验哈夫曼树 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 数据结构实验报告数据结构实验报告 1 1．实验要求．实验要求 i.i. 实验目的实验目的: : （（1 1）） 掌握二叉树基本操作的实现方法掌握二叉树基本操作的实现方法 （（2 2）） 掌握二叉树基本操作的实现方法掌握二叉树基本操作的实现方法 （（3 3）） 了解哈夫曼树的思想和相关概念了解哈夫曼树的思想和相关概念 （（4 4）） 学习使用二叉树解决实际问题的能力学习使用二叉树解决实际问题的能力 （（5 5）） 熟悉熟悉 C++C++语言的基本编程方法，语言的基本编程方法， 掌握集掌握集 成编译环境的调试方法，成编译环境的调试方法， 熟练改错方熟练改错方法。法。 （（6 6）） 熟悉设计算法的过程熟悉设计算法的过程 （（7 7）） 进一步掌握指针、异常处理的使用进一步掌握指针、异常处理的使用 ii.ii. 实验内容：实验内容： 利用二叉树结构实现赫夫曼编利用二叉树结构实现赫夫曼编/ /解码器。解码器。 基本要求：基本要求： 1 1、、初始化初始化(Init)(Init)：： 能够对输入的任意长度能够对输入的任意长度 的字符串的字符串 s s 进行统计，统计每个字符的频进行统计，统计每个字符的频 度，并建立赫夫曼树度，并建立赫夫曼树 2 2、、建立编码表建立编码表(CreateTable)(CreateTable)：利用已经：利用已经 建好的赫夫曼树进行编码，并将每个字符建好的赫夫曼树进行编码，并将每个字符 第第2 2页页 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 的编码输出。的编码输出。 3 3、、编码编码(Encoding)(Encoding)：根据编码表对输入：根据编码表对输入 的字符串进行编码，并将编码后的字符串的字符串进行编码，并将编码后的字符串 输出。输出。 4 4、、译码译码(Decoding)(Decoding)：利用已经建好的赫：利用已经建好的赫 夫曼树对编码后的字符串进行译码，并输夫曼树对编码后的字符串进行译码，并输 出译码结果。出译码结果。 5 5、、打印打印(Print)(Print)：以直观的方式打印赫夫：以直观的方式打印赫夫 曼树（选作）曼树（选作） 6 6、、计算输入的字符串编码前和编码后的计算输入的字符串编码前和编码后的 长度，并进行分析，讨论赫夫曼编码的压长度，并进行分析，讨论赫夫曼编码的压 缩效果。缩效果。 测试数据：测试数据： I IlovelovedatadataStructure,Structure,I Ilovelove Computer.I will try my best to study dataComputer.I will try my best to study data structure.structure. 提示：提示： 1 1、用户界面可以设计为“菜单”方式：、用户界面可以设计为“菜单”方式： 能够进行交互。能够进行交互。 2 2、根据输入的字符串中每个字符出现、根据输入的字符串中每个字符出现 的次数统计频度，对没有出现的的次数统计频度，对没有出现的 第第3 3页页 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 字符一律不用编码。字符一律不用编码。 iii.iii. 代码要求：代码要求： 1 1、必须要有异常处理，比如删除空链表时、必须要有异常处理，比如删除空链表时 需要抛出异常；需要抛出异常； 2 2、保持良好的编程的风格：、保持良好的编程的风格： 代码段与段之间要有空行和缩近代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函函数名之前应该添加注释说明该函 数的功能数的功能 关键代码应说明其功能关键代码应说明其功能 3 3、递归程序注意调用的过程，防止栈溢出、递归程序注意调用的过程，防止栈溢出 2. 2. 程序分析程序分析 树形结构是一种非线性结构可以用结点之间树形结构是一种非线性结构可以用结点之间 的分支来表示层次关系，的分支来表示层次关系， 二叉树是每个结点最多二叉树是每个结点最多 两个子树的有序树，十分适合计算机处理问题，两个子树的有序树，十分适合计算机处理问题， 而哈夫曼树是一种特殊的二叉树，而哈夫曼树是一种特殊的二叉树， 它将权值大的它将权值大的 数据放在了离根较近的结点处，数据放在了离根较近的结点处， 这样使得带权路这样使得带权路 径长度最短，是非常好的存储方式。径长度最短，是非常好的存储方式。 2.12.1 存储结构存储结构 1. 1.结点结构的存储方式：结点结构的存储方式： 根（下面结点的父结点）结点：根（下面结点的父结点）结点： 第第4 4页页 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 左孩子左孩子 右孩子右孩子 ………… structstruct hnodehnode// //哈夫曼树结点的结构哈夫曼树结点的结构 体体 { { intint weight; weight; intint parent; parent; intint lchild; lchild; intint rchild; rchild; charchar data; data; }; }; 结点存储示意图：结点存储示意图： intint weightweight intint parentparent intint lchildlchild 第第5 5页页 intint rchildrchild charchar datadata 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 2. 2.编码表的实现中使用了以下结构体编码表的实现中使用了以下结构体：： StructStructhcodehcode// //编码表结构编码表结构 体体 { { char data;char data;// //字符字符 char code[100];char code[100];// //编码内容编码内容 }; }; 示意图为：示意图为： char datachar datacharchar code[100]code[100] 3. 3.在在 selectselect 函数中使用的结构体：函数中使用的结构体： structstruct nodenode { { intint num; num; charchar data; data; }; }; int numint num 2.22.2关键算法分析：关键算法分析： charchar datadata A)InitA)Init 初始化：初始化： 统计需要编码的字符串中每个统计需要编码的字符串中每个 第第6 6页页 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 字符的频度并建立哈夫曼树字符的频度并建立哈夫曼树 实现：在函数中设置了一个数组实现：在函数中设置了一个数组 typetype 用来用来 统计字符串中字符的类型，统计字符串中字符的类型，nono 数组则用于数组则用于 统计每种字符串的个数，统计每种字符串的个数，coun