实验四--哈夫曼树与哈夫曼编码.doc

实验四哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容[问题描述]已知n个字符在原文中出现的频率求它们的哈夫曼编码。[基本要求]1.初始化：从键盘读入n个字符以及它们的权值建立Huffman树。（具体算法可参见教材P147的算法6.12）2.编码：根据建立的Huffman树求每个字符的Huffman编码。对给定的待编码字符序列进行编码。[选作内容]１.译码：利用已经建立好的Huffman树对上面的编码结果译码。译码的过程是分解电文中的字符串从根结点出发按字符’0’和’1’确定找左孩子或右孩子直至叶结点便求得该子串相应的字符。4.打印Huffman树。［测试数据］利用教材P.148例6－2中的数据调试程序。可设8种符号分别为ABCDEFGH。编/译码序列为“CFBABBFHGH”(也可自己设定数据进行测试)。算法设计1、主要思想：******************赫夫曼树的构造**********************(1)由给定的n个权值{w1w2…wn}构造具有n棵二叉树的森林F={T1T2…Tn}其中每棵二叉树Ti只有一个带权为wi的根结点其左、右子树均为空。(2)在F中选取两棵根结点的权值最小的二叉树作为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。(3)在F中删去这两棵二叉树把新的二叉树加入F。(4)重复(2)和(3)直到F中仅剩下一棵树为止。****************************霍夫曼编码*****************************主要用途是实现数据压缩。由于赫夫曼树中没有度为1的节点则一棵有n个叶子结点的赫夫曼树共有2n-1个结点可以存储在一个大小为2n-1的一维数组中。由于在构成赫夫曼树之后为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言既须知双亲的信息又需知孩子结点的信息。本程序包含三个模块1）主函数Intmain(){先输入结点总数；分别输入各个结点；调用建立哈夫曼树函数；调用编码函数读入建立的哈夫曼树进行编码}元素类型、结点类型和指针类型typedefstruct//定义新数据类型即结点结构{intweight;//权重域intparentlchildrchild;//指针域}htnode;//结点类型标识符//typedefhtnode*huffmanstree;//定义哈弗曼数类型htnodeht[maxnodenumber];//定义三叉链表存储数组typedefstruct//定义保存一个叶子节点哈弗曼编码的结构{intbit[maxbit];//定义一维数组为编码域intstart;//定义位置域}hcnodetype;//定义编码类型主函数和其他函数清单1）Intmain(){先输入结点总数；分别输入各个结点；调用建立哈夫曼树函数；调用编码函数读入建立的哈夫曼树进行编码}2）htnode*creatstree(intn)——建立哈夫曼树算法实现函数3）voidgetstree(htnode*htintn)——哈夫曼编码算法及打印函数的实现四、调试分析输入结点总数分别输入各个结点赫夫曼的编码总结本次实验电子报告中我原来打算加上各函数的简单流程图但是由于我处理图形方面还比较不熟练画了三四个小时也不太满意所以索性将几个小时的努力通过del键结束了所以这次报告不太令人满意我将在以后的报告中加上示意图多学习同学优秀的地方．也会在以后的学习过程中要尽量考虑周全使程序更有实用价值提高编程能力。我更加认识到自己动手的重要性因为问题看起来很简单但是等到亲自去实践时你会发现出现很多问题。正是通过不断的发现问题、解决问题我们才更加深刻的领悟到为核心进而更好的掌握所学的知识；其次我认识到了自己不明白的地方一定要向老师请教老师的点拨让人豁然开朗有助于我们更好的理解和掌握。最后我理解栈的顺序结构实现了一些基本操作掌握了栈的先进后出的特点并且能运用这一点解决实际问题。六、源代码#include<stdio.h>#include<iostream.h>#include<malloc.h>#definemaxvalue10000//定义最大权值常量#definemaxn