数据结构与算法实验报告 3霍夫曼树.doc

数据结构与程序设计专题实验报告 实验报告 一、实验任务 实验题目：数据结构与程序设计专题实验 二、实验内容 实验三：树的基本操作及基于霍夫曼树的编码/译码 （一）实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。 （二）基本要求：熟练掌握树的操作。 （三）内容提要：给定一段字符，构建霍夫曼树；根据该树求每个字符的编码，并对该段字符串进行编码；将得到的编码进行译码；基于该霍夫曼树，通过遍历算法来输出该树中的叶子节点。 注：在实现时要求霍夫曼树的左右孩子的大小关系（左孩子节点值小于右孩子节点），在遍历的时候也可以为递归与非递归办法寻找叶子节点。 三、要点分析 题目中涉及的主要知识点： 1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）： （1）由给定的n个权值{w0, w1, w2, …, wn-1}，构造具有n棵二叉树的集合F = {T0, T1, T2, …, Tn-1}，其中每一棵二叉树Ti只有一个带有权值wi的根结 点，其左、右子树均为空。 （2）重复以下步骤, 直到F中仅剩下一棵树为止： ① 在F, 做为左、右子树构造一棵 新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的 权值之和。 ② 在F ③ 把新的二叉树加入F 把d1,d2,…, dn 作为叶子结点，把w1,w2,…,wn作为叶子结点 的权，构造赫夫曼树。在赫夫曼树中结点的左分支赋0，右 分支赋1，从根结点到叶子结点的路径上的数字拼接起来就 是这个叶子结点字符的编码。 3、译码的过程是分解电文中的字符串，从根出发，按字符‘0’或‘1’确定找 左孩子或右孩子，直至叶子节点，便求得该子串相应的字符。 四、解题步骤 编程平台：Microsoft Visual C++ 6.0 编程平台应用： 第一步：打开Microsoft Visual C++ 6.0运行软件； 第二步：在主菜单中选文件→新建。 第三步：在出现的如下界面中选取“工程”项，选择“Win32 Console Application”，填写工程名称，选择存储路径，点击“确定”。 第四步：勾选“一个简单的程序”复选框。 第五步：在出现的编译环境中编写程序。 五、程序的算法描述 1、所用存储结构： typedef struct HfNode { int weight; int parent,lchild,rchild; }HfNode,*HuffmanTree; //动态分配数组存储霍夫曼树 typedef char **HuffmanCode; //动态分配数组存储霍夫曼编码表 程序中各函数的简要说明： (1)void Select(HuffmanTree HT,int i,int a,int b) 从前i个节点中选择权值最小的两个节点分别存入a,b中。设置a，b两个变量用“打擂台”的方 法求出两个最小值。 (2)void CreatHuffmanTree(HuffmanTree HT,int n,int Weight[]) 根据Weight[53]及Letter[52]中的信息建立具有2n-1个节点的Huffman树。 首先创建有2*n-1 个节点的存储空间，将前n个节点的权值付为对应的Weight[i]，双亲结点和左右孩子结点均置 为零。剩余结点的权值、双亲结点和左右孩子结点置为零。之后，i从n+1到2*n-1每次加1， 在HT[1..i-1]中选取parent为零且weight最小的两个节点，将他们的双亲结点置为HT[i]。 (3)void HuffmanCoding(HuffmanTree HT,HuffmanCode HC, int n) 获得n个字符的Huffman码。从叶子节点到根逆向求编码。先求叶子结点的双亲结点，如果该结 点为左孩子，则在Huffman码中从后往前字符置为‘0’；若为右孩子则置为‘1’，直至根节点结 束。 (4)char *HuffmanEncoding(HuffmanCode hc, int n,char Text[],char Letter[]) 对输入文本进行Huffman编码。将要编码的字符串传入函数，截取一个字符，与编码表中的字符 比较，找到对应的huffman码