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