武汉理工大学数据结构与算法综合实验哈夫曼树

《数据结构与算法》实验报告一、需求分析1.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。

对于双工通道（及可以双向传输信息的通道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站写一个哈夫曼的编/译码系统。

2.基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

（2）E：编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：译码（Decoding）。

利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

（4）P：印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

（5）T：印哈夫曼树（Tree printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示出，同时将此字符形式的哈夫曼树写入文件TreePrint中。

3.测试数据（1）利用教科书例6-2中的数据调试程序。

（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。

4,实现提示（1）编码结果以文本方式存储在文件CodeFile中。

（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”表示退出运行Quit。

请用户键入一个选择功能符。

此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。

（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。

实验四数据结构与程序设计专题实验报告赫夫曼树学院:物理与电子学院班级:电信1105班姓名:刘岩学号:1404110729实验报告一、实验任务实验题目：数据结构与程序设计专题实验二、实验内容实验三：树的基本操作及基于霍夫曼树的编码/译码（一）实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。

（二）基本要求：熟练掌握树的操作。

（三）内容提要：给定一段字符，构建霍夫曼树；根据该树求每个字符的编码，并对该段字符串进行编码；将得到的编码进行译码；基于该霍夫曼树，通过遍历算法来输出该树中的叶子节点。

注：在实现时要求霍夫曼树的左右孩子的大小关系（左孩子节点值小于右孩子节点），在遍历的时候也可以为递归与非递归办法寻找叶子节点。

三、要点分析题目中涉及的主要知识点：1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）：（1）由给定的n个权值{w0, w1, w2, …, w n-1}，构造具有n棵二叉树的集合F = {T0, T1, T2, …, T n-1}，其中每一棵二叉树T i只有一个带有权值w i的根结点，其左、右子树均为空。

（2）重复以下步骤, 直到F中仅剩下一棵树为止：① 在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。

置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

② 在F中删去这两棵二叉树。

③ 把新的二叉树加入F。

2、用构造赫夫曼树以完成赫夫曼编码：把d1,d2,…, dn作为叶子结点，把w1,w2,…,wn作为叶子结点的权，构造赫夫曼树。

在赫夫曼树中结点的左分支赋0，右分支赋1，从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。

3、译码的过程是分解电文中的字符串，从根出发，按字符‘0’或‘1’确定找左孩子或右孩子，直至叶子节点，便求得该子串相应的字符。

四、程序的算法描述1、所用存储结构：typedef struct HfNode{int weight;int parent,lchild,rchild;}HfNode,*HuffmanTree; //动态分配数组存储霍夫曼树typedef char **HuffmanCode; //动态分配数组存储霍夫曼编码表2、程序中各函数的简要说明：(1)void Select(HuffmanTree &HT,int i,int &a,int &b)从前i个节点中选择权值最小的两个节点分别存入a,b中。

一、实验目的1. 理解哈夫曼树的概念及其在数据结构中的应用。

2. 掌握哈夫曼树的构建方法。

3. 学习哈夫曼编码的原理及其在数据压缩中的应用。

4. 提高编程能力，实现哈夫曼树和哈夫曼编码的相关功能。

二、实验原理哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，又称为最优二叉树。

其构建方法如下：1. 将所有待编码的字符按照其出现的频率排序，频率低的排在前面。

2. 选择两个频率最低的字符，构造一棵新的二叉树，这两个字符分别作为左右子节点。

3. 计算新二叉树的频率，将新二叉树插入到排序后的字符列表中。

4. 重复步骤2和3，直到只剩下一个节点，这个节点即为哈夫曼树的根节点。

哈夫曼编码是一种基于哈夫曼树的编码方法，其原理如下：1. 从哈夫曼树的根节点开始，向左子树走表示0，向右子树走表示1。

2. 每个叶子节点对应一个字符，记录从根节点到叶子节点的路径，即为该字符的哈夫曼编码。

三、实验内容1. 实现哈夫曼树的构建。

2. 实现哈夫曼编码和译码功能。

3. 测试实验结果。

四、实验步骤1. 创建一个字符数组，包含待编码的字符。

2. 创建一个数组，用于存储每个字符的频率。

3. 对字符和频率进行排序。

4. 构建哈夫曼树，根据排序后的字符和频率，按照哈夫曼树的构建方法，将字符和频率插入到哈夫曼树中。

5. 实现哈夫曼编码功能，遍历哈夫曼树，记录从根节点到叶子节点的路径，即为每个字符的哈夫曼编码。

6. 实现哈夫曼译码功能，根据哈夫曼编码，从根节点开始，按照0和1的路径，找到对应的叶子节点，即为解码后的字符。

7. 测试实验结果，验证哈夫曼编码和译码的正确性。

五、实验结果与分析1. 构建哈夫曼树根据实验数据，构建的哈夫曼树如下：```A/ \B C/ \ / \D E F G```其中，A、B、C、D、E、F、G分别代表待编码的字符。

2. 哈夫曼编码根据哈夫曼树，得到以下字符的哈夫曼编码：- A: 00- B: 01- C: 10- D: 11- E: 100- F: 101- G: 1103. 哈夫曼译码根据哈夫曼编码，对以下编码进行译码：- 00101110111译码结果为：BACGACG4. 实验结果分析通过实验，验证了哈夫曼树和哈夫曼编码的正确性。

赫夫曼树实验报告赫夫曼树实验报告引言：赫夫曼树是一种用于数据压缩的重要算法，它通过构建一棵二叉树来实现对数据的编码和解码。

本次实验旨在通过实际操作，深入了解赫夫曼树的原理和应用，并验证其在数据压缩中的有效性。

一、实验背景数据压缩在现代信息技术中起着至关重要的作用。

随着数据量的不断增加，如何有效地压缩数据成为了一个迫切的问题。

赫夫曼树作为一种经典的数据压缩算法，具有较高的压缩比和较快的解压速度，因此备受关注。

二、实验目的1. 了解赫夫曼树的原理和构建方法；2. 掌握赫夫曼编码的过程和步骤；3. 验证赫夫曼树在数据压缩中的有效性。

三、实验过程1. 构建赫夫曼树首先，我们需要统计待压缩数据中各个字符的出现频率。

然后，按照频率从小到大的顺序，将字符构建成一棵二叉树。

具体构建方法为：每次选取频率最低的两个字符，将它们作为左右子节点，生成一个新的节点，该节点的频率为左右子节点频率之和。

重复此过程，直到所有字符都被构建成树的节点。

2. 进行赫夫曼编码在赫夫曼树构建完成后，我们需要对每个字符进行编码。

编码的规则是：向左走为0，向右走为1。

从根节点开始，对每个字符进行路径搜索，直到找到对应的叶子节点，记录下路径上的0和1，即为该字符的编码。

3. 数据压缩与解压缩利用赫夫曼编码，我们可以对待压缩数据进行压缩。

将每个字符替换为对应的编码后，将所有编码拼接起来，即可得到压缩后的数据。

解压缩则是将编码根据赫夫曼树进行反向解码，得到原始数据。

四、实验结果通过实验，我们将不同类型的数据进行了压缩和解压缩，并与原始数据进行了对比。

结果表明，赫夫曼树在数据压缩中表现出色，能够显著减小数据的大小，同时保持数据的完整性。

五、实验总结赫夫曼树作为一种高效的数据压缩算法，具有广泛的应用前景。

通过本次实验，我们深入了解了赫夫曼树的原理和构建方法，并验证了其在数据压缩中的有效性。

赫夫曼树的应用不仅可以提高数据传输的效率，还可以节省存储空间，对于大数据时代的到来具有重要意义。

数据结构哈夫曼树实验报告一、实验内容本次实验的主要内容是哈夫曼树的创建和编码解码。

二、实验目的1. 理解并掌握哈夫曼树的创建过程；2. 理解并掌握哈夫曼编码的原理及其实现方法；3. 掌握哈夫曼树的基本操作，如求哈夫曼编码和哈夫曼解码等；4. 学习如何组织程序结构，运用C++语言实现哈夫曼编码和解码。

三、实验原理哈夫曼树的创建：哈夫曼树的创建过程就是一个不断合并权值最小的两个叶节点的过程。

具体步骤如下：1. 将所有节点加入一个无序的优先队列里；2. 不断地选出两个权值最小的节点，并将它们合并成为一个节点，其权值为这两个节点的权值之和；3. 将新的节点插入到队列中，并继续执行步骤2，直到队列中只剩下一棵树，这就是哈夫曼树。

哈夫曼编码：哈夫曼编码是一种无损压缩编码方式，它根据字符出现的频率来构建编码表，并通过编码表将字符转换成二进制位的字符串。

具体实现方法如下：1. 统计每个字符在文本中出现的频率，用一个数组记录下来；2. 根据字符出现的频率创建哈夫曼树；3. 从根节点开始遍历哈夫曼树，给左分支打上0的标记，给右分支打上1的标记。

遍历每个叶节点，将对应的字符及其对应的编码存储在一个映射表中；4. 遍历文本中的每个字符，查找其对应的编码表，并将编码字符串拼接起来，形成一个完整的编码字符串。

哈夫曼解码就是将编码字符串还原为原始文本的过程。

具体实现方法如下：1. 从根节点开始遍历哈夫曼树，按照编码字符串的位数依次访问左右分支。

如果遇到叶节点，就将对应的字符记录下来，并重新回到根节点继续遍历；2. 重复步骤1，直到编码字符串中的所有位数都被遍历完毕。

四、实验步骤1. 定义编码和解码的结构体以及相关变量；3. 遍历哈夫曼树，得到每个字符的哈夫曼编码，并将编码保存到映射表中；4. 将文本中的每个字符用其对应的哈夫曼编码替换掉，并将编码字符串写入到文件中；5. 使用哈夫曼编码重新构造文本，并将结果输出到文件中。

五、实验总结通过本次实验，我掌握了哈夫曼树的创建和哈夫曼编码的实现方法，也学会了如何用C++语言来组织程序结构，实现哈夫曼编码和解码。

哈夫曼树实验报告哈夫曼树实验报告引言：哈夫曼树是一种经典的数据结构，广泛应用于数据压缩、编码和解码等领域。

本次实验旨在通过构建哈夫曼树，探索其原理和应用。

一、哈夫曼树的定义和构建方法哈夫曼树是一种特殊的二叉树，其叶子节点对应于待编码的字符，而非叶子节点则是字符的编码。

构建哈夫曼树的方法是通过贪心算法，即每次选择权值最小的两个节点合并，直到构建出完整的哈夫曼树。

二、哈夫曼编码的原理和实现哈夫曼编码是一种可变长度编码，即不同字符的编码长度不同。

其原理是通过构建哈夫曼树来确定字符的编码，使得频率较高的字符编码较短，频率较低的字符编码较长。

这样可以有效地减少编码的长度，从而实现数据的压缩。

三、实验过程和结果在本次实验中，我们选择了一段文本作为输入数据，通过统计每个字符的频率，构建了对应的哈夫曼树。

然后，根据哈夫曼树生成了字符的编码表，并将原始数据进行了编码。

最后，我们通过对编码后的数据进行解码，验证了哈夫曼编码的正确性。

实验结果显示，通过哈夫曼编码后，原始数据的长度明显减少，达到了较好的压缩效果。

同时，解码后的数据与原始数据完全一致，证明了哈夫曼编码的可靠性和正确性。

四、哈夫曼树的应用哈夫曼树在实际应用中有着广泛的用途。

其中，最典型的应用之一是数据压缩。

通过使用哈夫曼编码，可以将大量的数据压缩为较小的存储空间，从而节省了存储资源。

此外，哈夫曼树还被广泛应用于网络传输、图像处理等领域，提高了数据传输的效率和图像的质量。

五、对哈夫曼树的思考哈夫曼树作为一种经典的数据结构，其优势在于有效地减少了数据的冗余和存储空间的占用。

然而，随着技术的不断发展，现代的数据压缩算法已经不再局限于哈夫曼编码，而是采用了更为复杂和高效的算法。

因此，我们需要在实际应用中综合考虑各种因素，选择合适的压缩算法。

六、总结通过本次实验，我们深入了解了哈夫曼树的原理和应用。

哈夫曼编码作为一种重要的数据压缩算法，具有广泛的应用前景。

在实际应用中，我们需要根据具体情况选择合适的压缩算法，以达到最佳的压缩效果和性能。

数据结构课程设计实验报告哈夫曼树的应用计算机学院信管专业数据结构课程设计题目：哈夫曼树的应用班级：姓名：学号：同组人姓名：起迄日期：课程设计地点:指导教师：完成日期：2012年12月目录一、需求分析 (3)二、概要设计 (4)三、详细设计 (6)四、调试分析和测试结果 (7)五、心得体会和总结 (10)六、参考文献 (10)七、附录 (11)一、需求分析（一）实验要求要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。

这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。

问题是将输入的信息保存入文件和从文件输出。

这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。

综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。

（二）实验任务一个完整的系统应具有以下功能：功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。

（三）实验步骤分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：完成功能1；3）进一步要求：完成功能2和3。

有兴趣的同学可以自己扩充系统功能。

一、实验目的1. 理解并掌握哈弗曼树的构建原理。

2. 学会使用哈弗曼树进行数据编码和解码。

3. 了解哈弗曼编码在数据压缩中的应用。

二、实验原理哈弗曼树（Huffman Tree）是一种带权路径长度最短的二叉树，用于数据压缩。

其基本原理是：将待编码的字符集合按照出现频率从高到低排序，构造一棵二叉树，使得叶子节点代表字符，内部节点代表编码，权值代表字符出现的频率。

通过这棵树，可以生成每个字符的编码，使得编码的平均长度最小。

三、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019四、实验步骤1. 构建哈弗曼树（1）创建一个结构体`HuffmanNode`，包含字符、权值、左子树和右子树指针。

```cppstruct HuffmanNode {char data;int weight;HuffmanNode left;HuffmanNode right;};（2）定义一个函数`HuffmanTree()`，用于创建哈弗曼树。

```cppHuffmanNode HuffmanTree(std::vector<char>& chars, std::vector<int>& weights) {// 创建初始二叉树std::vector<HuffmanNode> trees;for (int i = 0; i < chars.size(); ++i) {trees.push_back(new HuffmanNode{chars[i], weights[i], nullptr, nullptr});}// 构建哈弗曼树while (trees.size() > 1) {// 选择两个权值最小的节点auto it1 = std::min_element(trees.begin(), trees.end(),[](HuffmanNode a, HuffmanNode b) {return a->weight < b->weight;});auto it2 = std::next(it1);HuffmanNode parent = new HuffmanNode{0, it1->weight + it2->weight, it1, it2};// 删除两个子节点trees.erase(it1);trees.erase(it2);// 将父节点添加到二叉树集合中trees.push_back(parent);}// 返回哈弗曼树根节点return trees[0];}```2. 生成哈弗曼编码（1）定义一个函数`GenerateCodes()`，用于生成哈弗曼编码。

数据结构实验报告实验题目：Huffman编码与解码姓名：学号：院系：实验名称：Huffman编码与解码实验问题描述：本实验需要以菜单形式完成以下功能：1.输入电文串2.统计电文串中各个字符及其出现的次数3.构造哈弗曼树4.进行哈弗曼编码5.将电文翻译成比特流并打印出来6.将比特流还原成电文数据结构的描述：逻辑结构：本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。

在实验过程中我们也应用到了栈的概念。

存储结构：使用结构体来对数据进行存储：typedef struct{int weight;int parent,lc,rc;}HTNode,*HuffmanTree;typedef struct LNode{char *elem;int stacksize;int top;}SqStack;在main函数里面定义一个哈弗曼树并实现上述各种功能。

程序结构的描述：本次实验一共构造了10个函数：1.void HuffTree(HuffmanTree &HT,int n[],int mun);此函数根据给定的mun个权值构建哈弗曼树，n[]用于存放num个权值。

2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1,s2.3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n);此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。

4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S)；此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。

学生学号Xxxx 实验课成绩
学生实验报告书
实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名xxx
学生姓名xxx
学生专业班级xxxx
2015-- 2016学年第 2 学期
实验课程名称：数据结构与算法综合实验
2．综合分析和结论
由于上一次的哈夫曼树没有写成功所以我回去以后有好好学习了一下数据结构，本次实验也比第一次有了经验了，通过和视频的学习我本次把实验全都做出来了。

但在实现的过程中对算法的理解还不够透彻，有待提高。

第三部分：实验小结、收获与体会
通过本次试验，我进一步掌握了有关图的相关算法，也对数据结构在实际编程的应用中有了进一步的了解，也对深度优先搜索、迪杰斯特拉、普里姆算法有了进一步的了解。

同时，我也发现自己对于图的有关知识掌握的还远远不够，对于一些算法还不能熟练应用于编程中，所以，在以后的学习中，要多编程，以提高自己的动手编程能力。

201*级数据结构实验报告哈夫曼树的建立姓名：***学号：***********班级：指导老师：***日期：201*.12.25一、实验题目及要求：实验题目：哈夫曼编码器设计实验要求：哈夫曼(Huffman)树与哈夫曼码1．输入一个文本，统计各字符出现的频度，输出结果；2．使用二叉链表或三叉链表作存储结构，构造哈夫曼(Huffman)树； 3．确定和输出各字符的哈夫曼码；4．输入一个由0和1组成的代码序列，翻译并输出与之对应的文本；操作提示：一个完整的系统应具有以下功能：（1）初始化： 从终端读入一段英文字符，统计每个字符出现的频率，建立赫夫曼树，并将该树存入某文件；（2）编码： 利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中；（3）解码： 利用保存的赫夫曼编码，对任意输入的0，1序列能正确解码。

二、实验分析及内容1、 存储结构a. 哈夫曼树的存储结构该程序使用一个静态三叉链表来存储哈夫曼树：weight LChild RChild Parent 2 -1 -1 4 3 -1 -1 4 6 -1 -1 5 9 -1 -1 6 5 1 1 5 11 2 2 6 2055-1b. 哈夫曼编码表的存储结构把每个字符data 及对应的编码code 用一个结点存储，将所有的结点存储在数组中：data Code Z 100 C 101 B 11 Ac. 录入字符串以及存储字符的数组a[]、b[]的获取：先将录入的字符串存在一个字符数组S[]中，然后遍历数组S[]，先建立一个空的循环链表，然后再遍历数组S 的同时往链表里插入新的结点或者修改相应结点中的域值：0 1 2 3 4 5 60 1 2 3Data Weight Nextrrear2. 关键算法分析a.初始化哈夫曼树:用数组a[]初始化哈夫曼树：从0到n-1循环，分别对树中结点赋值：HTree[i].weight=a[i];HTree[i].lchild=-1;HTree[i].rchild=-1;HTree[i].parent=-1;b.创建哈夫曼树：（1）、从1——i中选择两个最小的结点：SelectMin（x,y,0,i）；（2）、将选中的两个结点插入到树中：HTree[x].parent=HTree[y].parent=ii;HTree[ii].weight=HTree[x].weight+HTree[y].weight;HTree[ii].lchild=x;HTree[ii].rchild=y;HTree[ii].parent=-1;d.创建编码表：（1）、自下而上从叶子节点找到根节点，左孩子标识为‘0’，右孩子标识为‘1’，将‘0’、‘1’储存在编码表的code[]中；（2）、将code[]中的‘0’、‘1’进行倒序；e.编码：根据编码表，进行编码：for(int i=0;i<n;i++){ if(*s==HCodeTable[i].data){cout<<HCodeTable[i].code;s++;}}f.译码：输入一串‘0’、‘1’代码，根据编码表进行译码：（1）、如果是‘0’，则转到当前结点的左孩子：if(*s=='0') parent=HTree[parent].lchild;（2）、如果是‘1’，则转到当前结点的右孩子：else parent=HTree[parent].rchild;5、源程序：#include "stdio.h"typedef struct{float weight;int parent,lchild,rchild;}huftree;typedef struct{int bit[100];int length;}hufcode;huftree tree[100];//哈夫曼树hufcode code[100];//编码int num,m;//个数，编码最大长度void HufBuild(){int i,j,p1,p2;float s1,s2;printf("How: ");scanf("%d",&num);m=2*num-1;printf("请输入各个编码频率: ");for(i=0;i<num;i++){scanf("%f",&tree[i].weight);tree[i+num].parent=tree[i].parent=0;tree[i+num].lchild=tree[i].lchild=0;tree[i+num].rchild=tree[i].rchild=0;}for(i=num;i<m;i++){s1=s2=1; p1=p2=0;for(j=0;j<i;j++)if(tree[j].parent==0)if(tree[j].weight<s1){s2=s1; s1=tree[j].weight;p2=p1; p1=j;}else if(tree[j].weight<s2){s2=tree[j].weight;p2=j;}tree[p1].parent=tree[p2].parent=i;tree[i].weight=tree[p1].weight+tree[p2].weight;tree[i].lchild=p1; tree[i].rchild=p2;}}void CodePrint(){int i,j,p,k;printf("各个编码如下: \n");for(i=0;i<num;i++){printf("%6.2f",tree[i].weight);p=tree[i].parent;j=i;code[i].length=num-1;while(p!=0){if(tree[p].lchild==j) code[i].bit[code[i].length]=1;else code[i].bit[code[i].length]=0;code[i].length--;j=p;p=tree[p].parent;}printf(" ");for(k=code[i].length+1;k<num;k++)printf("%d",code[i].bit[k]);printf("\n");}}void main(){printf("输入一个要进行哈夫曼编码的字符串:"); gets();printf("如下是编码表:");HufBuild();pringtf("请输入一串0和1的代码");CodePrint();}3、运行结果三、实验小结1、虽然最终顺利的编完了程序，但是总的来说哈夫曼树还是很不容易的。

《用哈夫曼编码实现文件压缩》实验报告课程名称《数据结构B》实验学期2014至2014 学年第 1 学期学生所在系部计算机系年级2010 专业班级网络B10-3学生姓名学号任课教师实验成绩用哈夫曼编码实现文件压缩1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

微型计算机、Windows 系列操作系统、Visual C++6.0软件根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

在文件存储时，一个整型的字符要占用一个字节的空间，对于某些不常用的字符这样会造成空间的浪费，但如果用位来存储数据，可以将字符重新编码，使那些常用的字符存储空间相对短的，不常用的字符相对长些，可以节约空间。

哈夫曼编码即是这样一个过程。

用哈夫曼编码进行文件压缩，首先应对所用的字符进行哈夫曼变编码，在这之前应先对所用字符进行权值统计。

在编码哈夫曼树的时候，选取两个权值最小的依次构造哈夫曼树，进行哈夫曼编码时，使哈夫曼树的左孩子上的分支编码为0，右孩子上的分支编码为1。

然后对文件进行压缩。

压缩过程用到了文件的读写。

头文件的构造：头文件首先应用宏定义，对文件要用到的数据进行定义，然后定义了结构体类型，将所要到字符的权值，数据，双亲编号与孩子编号放在结构体中，使程序间的关系变得紧密。

定义第二个结构体，其中包含结构体数组和树根的编号。

定义指针，使其指向第二个结构体。

接着类型定义，定义了结构体，其中包含字符原码值，哈夫曼编码值和哈夫曼编码值的长度，并将其取名为HaffCode。

将程序所用到的函数包含在头文件里。

哈夫曼树的构造：在程序开头先对程序所用到的变量进行定义，包括指向结构体的指针，整型变量，权值最小的结点的编号，第二小的结点的编号，权值最小的结点的权值，第二小的结点的权值。

数据结构实验报告：哈夫曼树及哈夫曼编码一、实验目的1. 理解哈夫曼树及哈夫曼编码的概念和原理；2. 掌握C语言中哈夫曼树及哈夫曼编码的实现方法；3. 分析和讨论哈夫曼编码在实际应用中的优势和不足。

二、实验内容和步骤1. 哈夫曼树的构建1.1 通过C语言实现哈夫曼树的构建算法；1.2 输入一组权值，按哈夫曼树构建规则生成哈夫曼树；1.3 输出生成的哈夫曼树结构，并进行可视化展示。

2. 哈夫曼编码的实现2.1 设计哈夫曼编码的实现算法；2.2 对指定字符集进行编码，生成哈夫曼编码表；2.3 对给定字符串进行哈夫曼编码，并输出编码结果。

三、实验过程及结果1. 哈夫曼树的构建在C语言中，通过定义结构体和递归算法实现了哈夫曼树的构建。

根据输入的权值，依次选择权值最小的两个节点构建新的父节点，直至构建完成整棵哈夫曼树。

通过调试和可视化展示，确认了程序正确实现了哈夫曼树的构建。

2. 哈夫曼编码的实现经过分析和设计，利用哈夫曼树的特点实现了哈夫曼编码的算法。

根据生成的哈夫曼树，递归地生成字符对应的哈夫曼编码，并输出编码结果。

对指定的字符串进行了编码测试，验证了哈夫曼编码的正确性和有效性。

四、实验结果分析1. 哈夫曼编码在数据传输和存储中具有较高的压缩效率和可靠性，能够有效减少数据传输量和存储空间；2. 哈夫曼树及哈夫曼编码在通信领域、数据压缩和加密等方面有着广泛的应用和重要意义；3. 在实际应用中，哈夫曼编码的构建和解码算法需要较大的时间和空间复杂度，对于大规模数据的处理存在一定的局限性。

五、实验总结通过本次实验，深入理解了哈夫曼树及哈夫曼编码的理论知识，并掌握了C语言中实现哈夫曼树及哈夫曼编码的方法。

对哈夫曼编码在实际应用中的优势和局限性有了更深入的认识，这对今后的学习和工作有着积极的意义。

六、参考文献1. 《数据结构（C语言版）》，严蔚敏赵现军著，清华大学出版社，2012年；2. 《算法导论》，Thomas H. Cormen 等著，机械工业出版社，2006年。

数据结构哈夫曼树实验报告一、实验目的本次实验的主要目的是深入理解和掌握哈夫曼树的数据结构及其相关算法，并通过实际编程实现来提高对数据结构的应用能力和编程技能。

二、实验环境本次实验使用的编程环境为具体编程语言名称，操作系统为具体操作系统名称。

三、实验原理哈夫曼树，又称最优二叉树，是一种带权路径长度最短的二叉树。

其基本原理是通过构建一棵二叉树，使得权值较大的节点距离根节点较近，权值较小的节点距离根节点较远，从而达到带权路径长度最小的目的。

在构建哈夫曼树的过程中，首先需要将所有的节点按照权值从小到大进行排序。

然后，选取权值最小的两个节点作为左右子树，构建一个新的父节点，该父节点的权值为左右子节点权值之和。

重复这个过程，直到所有的节点都被构建到哈夫曼树中。

哈夫曼编码是基于哈夫曼树的一种编码方式。

对于每个叶子节点，从根节点到该叶子节点的路径上，向左的分支编码为 0，向右的分支编码为 1，这样就可以得到每个叶子节点的哈夫曼编码。

四、实验步骤1、定义节点结构体｀｀｀ctypedef struct HuffmanNode ｛char data;int weight;struct HuffmanNode left;struct HuffmanNode right;｝ HuffmanNode;｀｀｀2、实现节点排序函数｀｀｀cvoid sortNodes(HuffmanNode nodes, int n) ｛for （int i ＝ 0; i ＜ n 1; i+＋）｛for （int j ＝ 0; j ＜ n i 1; j+＋）｛if （nodesj>weight ＞ nodesj ＋ 1>weight) ｛HuffmanNode temp ＝ nodesj;nodesj ＝ nodesj ＋ 1;nodesj ＋ 1 ＝ temp;｝｝｝｝｀｀｀3、构建哈夫曼树｀｀｀cHuffmanNode buildHuffmanTree(HuffmanNode nodes, int n) ｛while （n ＞ 1) ｛sortNodes(nodes, n)；HuffmanNode left ＝ nodes0;HuffmanNode right ＝ nodes1;HuffmanNode parent ＝（HuffmanNode ）malloc(sizeof(HuffmanNode)）；parent>data ＝＇＼0'；parent>weight ＝ left>weight ＋ right>weight;parent>left ＝ left;parent>right ＝ right;nodes0 ＝ parent;nodes1 ＝ nodesn 1;n;｝return nodes0;｝｀｀｀4、生成哈夫曼编码｀｀｀cvoid generateHuffmanCodes(HuffmanNode root, int codes, int index) ｛if （root>left) ｛codesindex ＝ 0;generateHuffmanCodes(root>left, codes, index ＋ 1)；｝if （root>right) ｛codesindex ＝ 1;generateHuffmanCodes(root>right, codes, index ＋ 1)；｝if （！root>left ＆＆！root>right) ｛printf(＂％c: ＂， root>data)；for （int i ＝ 0; i ＜ index; i+＋）｛printf(＂％d"， codesi)；｝printf(＂＼n"）；｝｝｀｀｀5、主函数｀｀｀cint main(）｛HuffmanNode nodes5 ＝｛（HuffmanNode ）malloc(sizeof(HuffmanNode)），（HuffmanNode ）malloc(sizeof(HuffmanNode)），（HuffmanNode ）malloc(sizeof(HuffmanNode)），（HuffmanNode ）malloc(sizeof(HuffmanNode)），（HuffmanNode ）malloc(sizeof(HuffmanNode)）｝；nodes0>data ＝＇A'；nodes0>weight ＝ 5;nodes1>data ＝＇B'；nodes1>weight ＝ 9;nodes2>data ＝＇C'；nodes2>weight ＝ 12;nodes3>data ＝＇D'；nodes3>weight ＝ 13;nodes4>data ＝＇E'；nodes4>weight ＝ 16;HuffmanNode root ＝ buildHuffmanTree(nodes, 5)；int codes100;generateHuffmanCodes(root, codes, 0)；return 0;｝｀｀｀五、实验结果与分析通过运行上述程序，得到了每个字符的哈夫曼编码：A: 00B: 01C: 10D: 110E: 111分析实验结果可以发现，权值较小的字符A 和B 对应的编码较短，而权值较大的字符D 和E 对应的编码较长。

数据结构与算法：哈夫曼树哈夫曼树给定N个权值作为N个叶⼦结点，构造⼀棵⼆叉树，若该树的带权路径长度达到最⼩，称这样的⼆叉树为最优⼆叉树，也称为哈夫曼树(Huffman Tree)。

哈夫曼树是带权路径长度最短的树，权值较⼤的结点离根较近。

重要概念路径：从⼀个节点到它往下可以达到的节点所经shu过的所有节点，称为两个节点之间的路径路径长度：即两个节点的层级差，如A节点在第⼀层，B节点在第四层，那它们之间的路径长度为4-1=3权重值：为树中的每个节点设置⼀个有某种含义的数值，称为权重值(Weight)，权重值在不同算法中可以起到不同的作⽤节点的带权路径长度：从根节点到该节点的路径长度与该节点权重值的乘积树的带权路径长度：所有叶⼦节点的带权路径长度之和，也简称为WPL哈夫曼树判断判断⼀棵树是不是哈夫曼树只要判断该树的结构是否构成最短带权路径。

在下图中3棵同样叶⼦节点的树中带权路径最短的是右侧的树，所以右侧的树就是哈夫曼树。

代码实现案例：将数组{13,7,8,3,29,6,1}转换成⼀棵哈夫曼树思路分析：从哈夫曼树的概念中可以看出，要组成哈夫曼树，权值越⼤的节点必须越靠近根节点，所以在组成哈夫曼树时，应该由最⼩权值的节点开始。

步骤：(1) 将数组转换成节点，并将这些节点由⼩到⼤进⾏排序存放在集合中(2) 从节点集合中取出权值最⼩的两个节点，以这两个节点为⼦节点创建⼀棵⼆叉树，它们的⽗节点权值就是它们的权值之和(3) 从节点集合中删除取出的两个节点，并将它们组成的⽗节点添加进节点集合中，跳到步骤(2)直到节点集合中只剩⼀个节点public class HuffmanTreeDemo {public static void main(String[] args) {int array[] = {13,7,8,3,29,6,1};HuffmanTree huffmanTree = new HuffmanTree();Node root = huffmanTree.create(array);huffmanTree.preOrder(root);}}//哈夫曼树class HuffmanTree{public void preOrder(Node root){if (root == null){System.out.println("哈夫曼树为空，⽆法遍历");return;}root.preOrder();}/*** 创建哈夫曼树* @param array 各节点的权值⼤⼩* @return*/public Node create(int array[]){//先将传⼊的各权值转成节点并添加到集合中List<Node> nodes = new ArrayList<>();for (int value : array){nodes.add(new Node(value));}/*当集合中的数组只有⼀个节点时,即集合内所有节点已经组合完成，剩下的唯⼀⼀个节点即是哈夫曼树的根节点*/while (nodes.size() > 1){//将节点集合从⼩到⼤进⾏排序//注意：如果在节点类没有实现Comparable接⼝，则⽆法使⽤Collections.sort(nodes);//在集合内取出权值最⼩的两个节点Node leftNode = nodes.get(0);Node rightNode = nodes.get(1);//以这两个节点创建⼀个新的⼆叉树，它们的⽗节点的权值即是它们的权值之和Node parent = new Node(leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;//再从集合中删除已经组合成⼆叉树的俩个节点，并把它们俩个的⽗节点加⼊到集合中nodes.remove(leftNode);nodes.remove(rightNode);nodes.add(parent);}//返回哈夫曼树的根节点return nodes.get(0);}}//因为要在节点的集合内，以节点的权值value，从⼩到⼤进⾏排序，所以要实现Comparable<>接⼝class Node implements Comparable<Node>{int weight;//节点的权值Node left;Node right;public Node(int weight) {this.weight = weight;}public void preOrder(){System.out.println(this);if (this.left != null){this.left.preOrder();}if (this.right != null){this.right.preOrder();}}@Overridepublic String toString() {return "Node{" +"weight=" + weight +'}';}@Overridepublic int compareTo(Node o) {return this.weight - o.weight;}}哈夫曼编码定长编码固定长度编码⼀种⼆进制信息的信道编码。

题目：哈夫曼编/译码器一、题目要求：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。

构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.二、概要设计：数据结构：typedef struct{int bit[MAXBIT];int start;} HCodeType; /* 编码结构体 */typedef struct{int weight;int parent;int lchild;int rchild;char value;} HNode; /* 结点结构体 */函数：void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n)作用：构造一个哈夫曼树，并循环构建int main ()作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译三、详细设计：哈夫曼树的建立：void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n){int i = 0, j, m1, m2, x1, x2;char x;/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */while (i<n){HuffNode[i].weight = 0;arent =-1;HuffNode[i].lchild =-1;HuffNode[i].rchild =-1;scanf("%c",&x);scanf("%c",&HuffNode[i].value); eight);}for (i=n; i<2*n-1; i++){HuffNode[i].weight = 0;arent =-1;HuffNode[i].lchild =-1;HuffNode[i].rchild =-1;HuffNode[i].value=i;}/* 循环构造 Huffman 树 */for (i=0; i<n-1; i++){m1=m2=MAXQZ; eight < m1 && HuffNode[j].parent==-1){m2=m1;eight;x1=j;}else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1) {m2=HuffNode[j].weight;x2=j;}} /* end for *//* 设置找到的两个子结点 x1、x2 的父结点信息 */HuffNode[x1].parent = n+i;HuffNode[x2].parent = n+i;HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight; HuffNode[n+i].lchild = x1;HuffNode[n+i].rchild = x2;}}叶子节点的哈夫曼编码的保存：for (j=+1; j<n; j++)HuffCode[i].bit[j] = [j];HuffCode[i].start = ;主函数展示：int main(){HNode HuffNode[MAXNODE];HCodeType HuffCode[MAXLEAF],cd;int i, j, c, p, n,k=0;char wen[100];char z;scanf ("%d", &n);HuffmanTree (HuffNode, n);for (i=0; i < n; i++){= n-1;c = i;p = HuffNode[c].parent;while (p != -1) /* 父结点存在 */{if (HuffNode[p].lchild == c)[] = 0;else[] = 1;; /* 求编码的低一位 */c=p;p=HuffNode[c].parent; /* 设置下一循环条件 */ } /* end while */for (j=+1; j<n; j++)HuffCode[i].bit[j] = [j];HuffCode[i].start = ;} /* end for */z=getchar();z=getchar();for(;z!='\n';z=getchar()){wen[k++]=z;for(i=0;i<n;i++){if(z==HuffNode[i].value){for (j=HuffCode[i].start+1; j < n; j++)printf ("%d", HuffCode[i].bit[j]);break;}else;}}printf("\n");for(i=0;i<k;i++){printf("%c",wen[i]);}printf("\n");return 0;}四、调试分析与心得体会：虽然哈夫曼树的建立有书上的参考，但是实际写整个代码的时候还是问题重重。