哈夫曼树实验报告_3.docVIP

2011-2012学年第一学期 数据结构课内实验报告 学院：计算机学院 专业：计算机科学与技术 姓名： 李变 学号：09） 指导老师： 王春梅 实验题目 实验目的： a. 创建哈夫曼树; b. 哈夫曼编码 c. 哈夫曼译码； 实验内容： 创建哈夫曼树； 哈夫曼编码； 哈夫曼译码； 数据结构及算法思想： 创建哈夫曼树的描述： 数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放； 算法思想：1.先把三叉链表中1-N个元素进行初始化，存放叶子节点，他们都没有孩子和双亲。2.再初始化后n-1个非叶子节点元素。3.从当前森林中（在森林中树的根节点的双亲为0）选择两棵根的权值最小的树；删除合并是将选到的两棵树的根权和存入数组当前最前面的空闲元素中，并置入相应的双亲与孩子的位置。4.重复上述步骤直到森林中只含有一棵二叉树为止； 哈夫曼树编码的描述： 数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放； 算法思想：1.申请存储哈夫曼编码串的头指针数组，申请一个字符型指针，用来存放临时的编码串；2.从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中；3.重复上述步骤，直到所有的叶子节点都被编码完； 哈夫曼树译码的描述： 数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放； 算法思想：1.从根结点开始向下递推，若其编码当前的数值为0，则到该节点的左孩子，否则转到其右孩子；重复上述步骤直到该编码中全部访问完，则树中对应的叶子节点则为所求2.依据上述步骤，对编码数组中所有编码全部进行译码； 模块划分： 1.选择两个权值最小的结点； 2.创建哈夫曼树； 3.打印哈夫曼树 4.哈夫曼编码 5.哈夫曼译码 详细设计及运行结果： 1. 创建哈夫曼树： 2.哈夫曼编码： 3.哈夫曼译码： 调试情况，设计技巧及体会 这次实验最大遗憾是没有把二叉树很好的打印出来，对于本程序的主要部分，Huffman树的生成和Huffman码的编译，没有任何的创新，无论是算法还是基本框架都是套用课本上的经典算法，时间复杂度都为o(n).另外在创建哈夫曼树时选择两个权值的结点的效率不是太高。每次都要先找到最大的权值，然后再进行比较，经过两次循环找到两个最小的权值，这一个函数的时间复杂度比创建，编码，译码的时间复杂度都要高。哈夫曼编码时通过动态的指针数组存放个叶子节点的编码，节省了好多空间，效率比较好。 通过这次试验，自我感觉收获很深，无论是对于编程本身还是对集成开发环境的使用上，还有对知识掌握的熟练程度上，都有了很大的提高。 本次实验中出现的最大问题仍然是函数间参数的传递问题，上一个二叉树实验也遇到了同样的问题，函数间传递参数掌握的很不好。为了解决这个问题我花了大量的时间。刚开始时，程序老提示函数参数类型不匹配，可我感觉是正确的，后来通过请教同学才明白，原来我函数形参类型是指针型，而我穿过去的实参全是变量值；后来程序编译可以通过但是运行就是得不到自己想要的结果，这个问题困惑了好长时间，后来通过调试终于发现问题的所在，依然是没有搞清楚值和地址的区别。 源程序清单（电子版）