下载文档原格式
一、实验目的1. 理解霍夫曼编码的基本原理和算法流程。
2. 掌握霍夫曼编码的构建过程和编码方法。
3. 通过实验验证霍夫曼编码在数据压缩方面的效果。
4. 提高编程能力和数据结构应用能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理霍夫曼编码是一种基于字符出现频率进行编码的数据压缩方法。
其基本原理如下：1. 对字符进行统计，得到每个字符出现的频率。
2. 根据频率对字符进行排序，频率高的字符排在前面。
3. 构建霍夫曼树，将频率高的字符放在树的左侧，频率低的字符放在树的右侧。
4. 从树根到叶子节点，为每个字符分配一个二进制编码，频率高的字符用较短的编码表示，频率低的字符用较长的编码表示。
四、实验步骤1. 定义一个结构体HuffmanNode，用于存储字符及其频率。
2. 实现一个函数用于统计字符频率。
3. 实现一个函数用于构建霍夫曼树。
4. 实现一个函数用于生成霍夫曼编码。
5. 实现一个函数用于解码霍夫曼编码。
6. 编写主函数，进行实验验证。
五、实验过程1. 定义结构体HuffmanNode，用于存储字符及其频率。
```cppstruct HuffmanNode {char ch;int weight;HuffmanNode lchild, rchild;};```2. 实现一个函数用于统计字符频率。
```cppvoid StatFrequency(char str, int freq) {int length = strlen(str);for (int i = 0; i < 256; ++i) {freq[i] = 0;}for (int i = 0; i < length; ++i) {freq[(int)str[i]]++;}}```3. 实现一个函数用于构建霍夫曼树。
```cppHuffmanNode CreateHuffmanTree(int freq, int length) {HuffmanNode nodes = new HuffmanNode[length + 1];for (int i = 0; i < length; ++i) {nodes[i].ch = 'a' + i;nodes[i].weight = freq[i];nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = length; i < length + 1; ++i) {nodes[i].ch = '\0';nodes[i].weight = 0;nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = 0; i < length - 1; ++i) {HuffmanNode minNode1 = &nodes[0];HuffmanNode minNode2 = &nodes[1];for (int j = 0; j < length + 1; ++j) {if (nodes[j].weight < minNode1->weight) {minNode2 = minNode1;minNode1 = &nodes[j];} else if (nodes[j].weight < minNode2->weight && nodes[j].weight > minNode1->weight) {minNode2 = &nodes[j];}}nodes[i].weight = minNode1->weight + minNode2->weight;nodes[i].lchild = minNode1;nodes[i].rchild = minNode2;minNode1->parent = &nodes[i];minNode2->parent = &nodes[i];}return &nodes[length - 1];}```4. 实现一个函数用于生成霍夫曼编码。
数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告1. 实验目的本实验旨在通过实践理解哈夫曼编码的原理和实现方法，加深对数据结构中树的理解，并掌握使用Python编写哈夫曼编码的能力。
2. 实验原理哈夫曼编码是一种用于无损数据压缩的算法，通过根据字符出现的频率构建一棵哈夫曼树，并根据哈夫曼树对应的编码。
根据哈夫曼树的特性，频率较低的字符具有较长的编码，而频率较高的字符具有较短的编码，从而实现了对数据的有效压缩。
实现哈夫曼编码的主要步骤如下：1. 统计输入文本中每个字符的频率。
2. 根据字符频率构建哈夫曼树，其中树的叶子节点代表字符，内部节点代表字符频率的累加。
3. 遍历哈夫曼树，根据左右子树的关系对应的哈夫曼编码。
4. 使用的哈夫曼编码对输入文本进行编码。
5. 将编码后的二进制数据保存到文件，同时保存用于解码的哈夫曼树结构。
6. 对编码后的文件进行解码，还原原始文本。
3. 实验过程3.1 统计字符频率首先，我们需要统计输入文本中每个字符出现的频率。
可以使用Python中的字典数据结构来记录字符频率。
遍历输入文本的每个字符，将字符添加到字典中，并递增相应字符频率的计数。
```pythondef count_frequency(text):frequency = {}for char in text:if char in frequency:frequency[char] += 1else:frequency[char] = 1return frequency```3.2 构建哈夫曼树根据字符频率构建哈夫曼树是哈夫曼编码的核心步骤。
我们可以使用最小堆（优先队列）来高效地构建哈夫曼树。
首先，将每个字符频率作为节点存储到最小堆中。
然后，从最小堆中取出频率最小的两个节点，将它们作为子树构建成一个新的节点，新节点的频率等于两个子节点频率的和。
将新节点重新插入最小堆，并重复该过程，直到最小堆中只剩下一个节点，即哈夫曼树的根节点。
数据结构课程设计设计题目：哈夫曼树编码译码课题名称院系学号姓名哈夫曼树编码译码年级专业成绩1、课题设计目的：在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，时常应用于数据压缩。
哈弗曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。
这张编码表的特殊之处在于，它是根据每一个源字符浮现的估算概率而建立起来的。
课题设计目的与设计意义2、课题设计意义：哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。
树中从根到每一个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或者“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。
哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。
指导教师：年月日第一章需求分析 (1)第二章设计要求 (1)第三章概要设计 (2)(1)其主要流程图如图 1-1 所示。
(3)(2)设计包含的几个方面 (4)第四章详细设计 (4)(1)①哈夫曼树的存储结构描述为： (4)(2)哈弗曼编码 (5)(3)哈弗曼译码 (7)(4)主函数 (8)(5)显示部份源程序： (8)第五章调试结果 (10)第六章心得体味 (12)第七章参考文献 (12)附录： (12)在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，时常应用于数据压缩。
哈弗曼编码使用一张特殊的编码表将源字符 (例如某文件中的一个符号) 进行编码。
第1篇实验名称：基于仿真平台的编码算法性能评估实验日期：2023年4月10日实验地点：计算机实验室实验目的：1. 了解编码算法的基本原理和应用场景。
2. 通过仿真实验，评估不同编码算法的性能。
3. 分析编码算法在实际应用中的优缺点。
实验环境：1. 操作系统：Windows 102. 编译器：Visual Studio 20193. 仿真平台：MATLAB 2020a4. 编码算法：Huffman编码、算术编码、游程编码实验内容：1. 编写Huffman编码算法，实现字符序列的编码和解码。
2. 编写算术编码算法，实现字符序列的编码和解码。
3. 编写游程编码算法，实现字符序列的编码和解码。
4. 在仿真平台上，分别对三种编码算法进行性能评估。
实验步骤：1. 设计Huffman编码算法，包括构建哈夫曼树、编码和解码过程。
2. 设计算术编码算法，包括编码和解码过程。
3. 设计游程编码算法，包括编码和解码过程。
4. 编写仿真实验代码，对三种编码算法进行性能评估。
5. 分析实验结果，总结不同编码算法的优缺点。
实验结果及分析：一、Huffman编码算法1. 编码过程：- 对字符序列进行统计，计算每个字符出现的频率。
- 根据频率构建哈夫曼树，叶子节点代表字符，分支代表编码。
- 根据哈夫曼树生成编码，频率越高的字符编码越短。
2. 解码过程：- 根据编码，从哈夫曼树的根节点开始，沿着编码序列遍历树。
- 当遍历到叶子节点时，输出对应的字符。
3. 性能评估：- 编码长度：Huffman编码的平均编码长度最短，编码效率较高。
- 编码时间：Huffman编码算法的编码时间较长，尤其是在构建哈夫曼树的过程中。
二、算术编码算法1. 编码过程：- 对字符序列进行统计，计算每个字符出现的频率。
- 根据频率，将字符序列映射到0到1之间的实数。
- 根据映射结果，将实数序列编码为二进制序列。
2. 解码过程：- 对编码的二进制序列进行解码，得到实数序列。
哈夫曼树编码实验报告哈夫曼树编码实验报告引言：哈夫曼树编码是一种常用的数据压缩算法，通过对数据进行编码和解码，可以有效地减小数据的存储空间。
本次实验旨在探究哈夫曼树编码的原理和应用，并通过实际案例验证其有效性。
一、哈夫曼树编码原理哈夫曼树编码是一种变长编码方式，根据字符出现的频率来确定不同字符的编码长度。
频率较高的字符编码较短，频率较低的字符编码较长，以达到最佳的数据压缩效果。
1.1 字符频率统计首先，需要对待编码的数据进行字符频率统计。
通过扫描数据，记录每个字符出现的次数，得到字符频率。
1.2 构建哈夫曼树根据字符频率构建哈夫曼树，频率较低的字符作为叶子节点，频率较高的字符作为父节点。
构建哈夫曼树的过程中，需要使用最小堆来维护节点的顺序。
1.3 生成编码表通过遍历哈夫曼树，从根节点到每个叶子节点的路径上的左右分支分别赋予0和1，生成对应的编码表。
1.4 数据编码根据生成的编码表，将待编码的数据进行替换，将每个字符替换为对应的编码。
编码后的数据长度通常会减小，实现了数据的压缩。
1.5 数据解码利用生成的编码表，将编码后的数据进行解码，恢复原始数据。
二、实验过程与结果为了验证哈夫曼树编码的有效性，我们选择了一段文本作为实验数据，并进行了以下步骤：2.1 字符频率统计通过扫描文本，统计每个字符出现的频率。
我们得到了一个字符频率表，其中包含了文本中出现的字符及其对应的频率。
2.2 构建哈夫曼树根据字符频率表，我们使用最小堆构建了哈夫曼树。
频率较低的字符作为叶子节点，频率较高的字符作为父节点。
最终得到了一棵哈夫曼树。
2.3 生成编码表通过遍历哈夫曼树，我们生成了对应的编码表。
编码表中包含了每个字符的编码，用0和1表示。
2.4 数据编码将待编码的文本数据进行替换，将每个字符替换为对应的编码。
编码后的数据长度明显减小，实现了数据的压缩。
2.5 数据解码利用生成的编码表，将编码后的数据进行解码，恢复原始文本数据。
一、实训目的本次实训旨在通过实际操作，让学生掌握哈夫曼树的基本概念、构建方法以及编码解码过程，加深对数据结构中树型结构在实际应用中的理解。
通过本次实训，学生能够：1. 理解哈夫曼树的基本概念和构建原理；2. 掌握哈夫曼树的编码和解码方法；3. 熟悉Java编程语言在哈夫曼树编码中的应用；4. 提高数据压缩和传输效率的认识。
二、实训内容1. 哈夫曼树的构建（1）创建叶子节点：根据给定的字符及其权值，创建叶子节点，并设置节点信息。
（2）构建哈夫曼树：通过合并权值最小的两个节点，不断构建新的节点，直到所有节点合并为一棵树。
2. 哈夫曼编码（1）遍历哈夫曼树：从根节点开始，按照左子树为0、右子树为1的规则，记录每个叶子节点的路径。
（2）生成编码：将遍历过程中记录的路径转换为二进制编码，即为哈夫曼编码。
3. 哈夫曼解码（1）读取编码：将编码字符串按照二进制位读取。
（2）遍历哈夫曼树：从根节点开始，根据读取的二进制位，在哈夫曼树中寻找对应的节点。
（3）输出解码结果：当找到叶子节点时，输出对应的字符，并继续读取编码字符串。
三、实训过程1. 准备工作（1）创建一个Java项目，命名为“HuffmanCoding”。
（2）在项目中创建以下三个类：- HuffmanNode：用于存储哈夫曼树的节点信息；- HuffmanTree：用于构建哈夫曼树、生成编码和解码；- Main：用于实现主函数，接收用户输入并调用HuffmanTree类进行编码和解码。
2. 编写代码（1）HuffmanNode类：```javapublic class HuffmanNode {private char data;private int weight;private HuffmanNode left;private HuffmanNode right;public HuffmanNode(char data, int weight) {this.data = data;this.weight = weight;}}```（2）HuffmanTree类：```javaimport java.util.PriorityQueue;public class HuffmanTree {private HuffmanNode root;public HuffmanNode buildHuffmanTree(char[] data, int[] weight) {// 创建优先队列，用于存储叶子节点PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();for (int i = 0; i < data.length; i++) {HuffmanNode node = new HuffmanNode(data[i], weight[i]);queue.offer(node);}// 构建哈夫曼树while (queue.size() > 1) {HuffmanNode left = queue.poll();HuffmanNode right = queue.poll();HuffmanNode parent = new HuffmanNode('\0', left.weight + right.weight);parent.left = left;parent.right = right;queue.offer(parent);}root = queue.poll();return root;}public String generateCode(HuffmanNode node, String code) {if (node == null) {return "";}if (node.left == null && node.right == null) {return code;}generateCode(node.left, code + "0");generateCode(node.right, code + "1");return code;}public String decode(String code) {StringBuilder result = new StringBuilder();HuffmanNode node = root;for (int i = 0; i < code.length(); i++) {if (code.charAt(i) == '0') {node = node.left;} else {node = node.right;}if (node.left == null && node.right == null) { result.append(node.data);node = root;}}return result.toString();}}```（3）Main类：```javaimport java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("请输入字符串：");String input = scanner.nextLine();System.out.println("请输入字符及其权值（例如：a 2 b 3 c 5）："); String[] dataWeight = scanner.nextLine().split(" ");char[] data = new char[dataWeight.length / 2];int[] weight = new int[dataWeight.length / 2];for (int i = 0; i < dataWeight.length; i += 2) {data[i / 2] = dataWeight[i].charAt(0);weight[i / 2] = Integer.parseInt(dataWeight[i + 1]);}HuffmanTree huffmanTree = new HuffmanTree();HuffmanNode root = huffmanTree.buildHuffmanTree(data, weight); String code = huffmanTree.generateCode(root, "");System.out.println("编码结果：" + code);String decoded = huffmanTree.decode(code);System.out.println("解码结果：" + decoded);scanner.close();}}```3. 运行程序（1）编译并运行Main类，输入字符串和字符及其权值。
实验二Huffman编码一实验目的1 通过本实验实现信源编码——Huffman编码2 编写M文件实现，掌握Huffman编码方法二实验要求1 了解matlab中M文件的编辑、调试过程2 编写程序实现Huffman编码算法三实验步骤1 输入Huffman编码程序2 运行程序，按照提示输入相应信息，并记录输入信息，及运行结果。
注：观察结果方法：data(1).Code显示a1的编码，同理显示data(2).Code，a2的编码结果。
3 思考：该程序编出的Huffman码是否是最小码方差的码？为什么？四报告要求五附Huffman编码程序clearN=input('请输入信源符号的个数：') ;for i=1:N%data(1).name=input('请输入各信源符号的名称：');data(i).p=input('请输入各信源符号发生的概率：');endfor i=1:Npp(i)=data(i).p;data(i).imap=i; %各符号在编码过程中的指针data(i).Code=''; %各符号的编码结果endfor j = 1:N % N——信源符号的个数for i = 1:N - jif (pp(i) > pp(i + 1))fT = pp(i);pp(i) = pp(i + 1);pp(i + 1) = fT;for k = 1:Nif data(k).imap == idata(k).imap = i + 1;elseif data(k).imap == i + 1data(k).imap = i;endendendendendp=pp;%%%%%%%%%%%%%%%%%%%%% %// 计算哈夫曼编码表%// 开始编码for i=1:N-1for k = 1:Nif data(k).imap== idata(k).Code = strcat('1',data(k).Code);elseif (data(k).imap== i + 1)data(k).Code = strcat('0',data(k).Code);endendp(i + 1) = p(i + 1)+p(i);for k = 1:Nif (data(k).imap == i)data(k).imap = i + 1;endendfor j = i + 1:N-1if p(j) >p(j + 1)fT =p(j);p(j) = p(j + 1);p(j + 1) = fT;for k = 1:Nif (data(k).imap == j)data(k).imap = j + 1;elseif (data(k).imap == j + 1)data(k).imap = j;endendendendend。
一、问题描述1. 实验题目：huffman编解码2. 基本要求：初始化（I nitialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。
编码（E ncoding）。
利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree 中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
解码（D ecoding）。
利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。
打印代码文件（Print）。
将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。
同时将此字符形式的编码文件写入文件CodePrint中。
打印Huffman树（T ree Printing）。
将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。
3. 测试数据：用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编字符集大小 n，n个字符和 n个权值均从终端读入，初始化后的huffman树存储在hfmTree文件中，待编码文件为ToBeTran,编码结果以文本的方式存储在文件CodeFile中，解码文件存在TextFile中,打印的编码和赫夫曼树分别存储在CodePrint和TreePrint文件中。
用户界面可以设计为“菜单”方式：显示上述功能符号，再加上一个退出功能“Q”，表示退出（quit）。
用户键入一个选择功能符，此功能执行完毕后再显示此菜单，直至某次用户选择了Q为止。
二、需求分析1. 本程序可以根据输入字符集和频度建立huffman树并且对给定文本进行编解码，还可以直接读入建立好的huffman树再对给定文本编解码，打印编码、解码结果、表格形式及树形的huffman树。
第1篇一、实验目的1. 理解霍夫曼编码的基本原理和实现方法。
2. 掌握霍夫曼编码在数据压缩中的应用。
3. 通过实验，加深对数据压缩技术的理解。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 20194. 数据源：文本文件三、实验原理霍夫曼编码是一种常用的数据压缩算法，适用于无损数据压缩。
它通过使用变长编码表对数据进行编码，频率高的数据项使用短编码，频率低的数据项使用长编码。
霍夫曼编码的核心是构建一棵霍夫曼树，该树是一种最优二叉树，用于表示编码规则。
霍夫曼编码的步骤如下：1. 统计数据源中每个字符的出现频率。
2. 根据字符频率构建一棵最优二叉树，频率高的字符位于树的上层，频率低的字符位于树下层。
3. 根据最优二叉树生成编码规则，频率高的字符分配较短的编码，频率低的字符分配较长的编码。
4. 使用编码规则对数据进行编码，生成压缩后的数据。
5. 在解码过程中，根据编码规则恢复原始数据。
四、实验步骤1. 读取文本文件，统计每个字符的出现频率。
2. 根据字符频率构建最优二叉树。
3. 根据最优二叉树生成编码规则。
4. 使用编码规则对数据进行编码，生成压缩后的数据。
5. 将压缩后的数据写入文件。
6. 读取压缩后的数据，根据编码规则进行解码，恢复原始数据。
7. 比较原始数据和恢复后的数据，验证压缩和解码的正确性。
五、实验结果与分析1. 实验数据实验中，我们使用了一个包含10000个字符的文本文件作为数据源。
在统计字符频率时，我们发现字符“e”的出现频率最高，为2621次，而字符“z”的出现频率最低，为4次。
2. 实验结果根据实验数据，我们构建了最优二叉树，并生成了编码规则。
使用编码规则对数据源进行编码，压缩后的数据长度为7800个字符。
将压缩后的数据写入文件，文件大小为78KB。
接下来，我们读取压缩后的数据，根据编码规则进行解码，恢复原始数据。
比较原始数据和恢复后的数据，发现两者完全一致，验证了压缩和解码的正确性。
哈夫曼编码实验报告心得简介哈夫曼编码是一种用于数据压缩的算法，在信息论和编码理论中扮演着重要的角色。
它基于将出现频率较高的字符用较短的二进制编码表示，而将较少出现的字符用较长的二进制编码表示，从而达到压缩数据的目的。
在这次实验中，我对哈夫曼编码进行了深入的学习和实践，并对其进行了评估和测试。
通过实验，我对哈夫曼编码有了更深入的了解，并收获了一些宝贵的心得体会。
实验过程步骤一：构建哈夫曼树首先，我需要根据给定的数据集构建哈夫曼树。
在构建哈夫曼树的过程中，我采用了优先队列来保存节点，每次选择权重最小的节点进行合并，直到最终合并成一棵完整的哈夫曼树。
步骤二：生成编码表构建好哈夫曼树之后，我需要根据这棵树生成每个字符对应的二进制编码。
这一步需要按照哈夫曼树的路径从根节点到叶子节点进行遍历，每经过一条左子树的路径，就加上一个0，每经过一条右子树的路径，就加上一个1，直到达到叶子节点为止。
步骤三：进行编码压缩生成编码表之后，我根据编码表对原始数据进行了编码压缩。
将每个字符通过其对应的二进制编码进行替换，得到了压缩后的数据。
步骤四：进行解码还原最后，我对压缩后的数据进行解码还原。
通过对编码表的反向查找，将二进制编码转换为原始字符，得到了还原后的数据。
心得体会通过这次实验，我对哈夫曼编码有了更深入的了解。
一开始我遇到了一些困难，例如如何构建哈夫曼树和生成编码表，但通过查阅相关资料和和老师的指导，我逐渐掌握了相关的知识和技巧。
实验中，我发现哈夫曼编码在压缩数据方面有着很好的效果。
根据实验结果，使用哈夫曼编码可以将原始数据压缩到原来的约50%左右，这对于节省存储空间和加快数据传输速度都有着重要的意义。
另外，在实验过程中，我也意识到了哈夫曼编码的一些局限性。
由于是根据字符出现的频率进行编码，在处理一些重复的字符时，哈夫曼编码的压缩效果并不理想。
此外，哈夫曼编码的编解码速度受到哈夫曼树的构建和编码表的生成等步骤的影响，对于大规模数据的处理并不高效。
《数据结构》课程设计上机实习报告课设题目Huffman编码和解码班级学生姓名学号指导教师时间2015.12-2015.1一、设计目的1.进一步熟悉C语言开发环境，熟悉用C语言完成一个应用程序的设计过程，掌握有关编辑、调试和整合程序的方法和技巧。
2.通过此设计，了解《数据结构》课程中霍夫曼编码的的有关内容，明确其操作，熟悉其设计，同时学习到有关位向量的内容，对文件掌握加深二、设计内容Huffman编码与解码 (必做)（Huffman编码、二叉树）[问题描述]对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。
[基本要求]（1）输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。
（2）在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即0 1的信息用比特位表示，不能用字符’0’和’1’表示。
（3）提供读编码文件生成原文件的功能。
三、数据结构说明在该程序中我仅仅使用了两个结构体来完成编码，用位域来实现bite流存储：const int MAXSIZE=300;//定义一次分配的Huffman储存单词最大量为500 const int OVERFLOW = 0;const int ERROR = 0;const int LineCountNum=500;typedef struct WordCount{char Word;//存放字符int freq;int parent , lchild , rchild;//存放亲子节点位置int place;//用来保存第一次堆排序后，建立霍夫曼表前的相对位置char *HuffmanCode;//存放霍夫曼编码}WordCount , *WC;//存放单词结点的结构体typedef struct HuffmanTree{WC w;int Number;//存储有多少数据存入}HuffmanTree , *HTree;typedef struct{unsigned int a:1;}bite;//设置位段，存储一个bite//**************操作函数声明***********void InitHuffmanTree(HTree &H);//初始化霍夫曼树void HeapSort(WC &W , int Number , int choice);//堆排序核心函数void HeapAdjust(WC &W , int down , int up , int choice);//堆排序调整函数,实现两种排序void HuffmanCoding(HTree &H , WC &HT); //求霍夫曼树和霍夫曼编码表void ShowHuffmanTree(HTree H);//输出霍夫曼树void Select(WC &W , int i , int &s1 , int &s2);//选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回void GetTheDeCode(HTree H);//将编码结果写入函数void PutTheDeCode(FILE *fp1 , FILE *fp2);//将编码结果解码得到文章void CountTheWord(HTree &H , FILE *fp);//记录单词权值void ShowTheEassy(FILE *wp);//展示文章四、详细设计1.首先我给出了编码和解码的菜单供其选择2.在编码功能中，我先通过CountTheWord（）函数进行单词权值记录，然后进入编码功能，值得一提的是，编码时我给堆排序设计了两种排序形式——对权值的排序和对位置的排序，以达到选择两个最小的权值结点的最优时间复杂度的目的，此功能通过switch实现，但要给编码结构体中放置一个place 空间，这也从侧面反映了时间和空间矛盾的地方(值得一提的是，有些编码并不可见且有特殊含义，如换行符，所以将字符放入文件中时，并不对其进行处理，读出是进行顺序读出)3.编码结束后将编码结果，对应字符分别存放在文件中，然后对整篇文章进行编码4.解码时依据霍夫曼编码的唯一性进行比较求解，遇到同样的字符即返回对应的字母并写入解码文件中五、调试与测试(测试数据：献给艾米莉的玫瑰)1.首先打开文件进行字符权值统计并输出结果（有些符号不可见,所以无法显示）2.然后对其进行堆排序3.输出编码表，及其对应亲子关系(#号代表为父结点)4.输出编码结果（可以轻易看出编码具备唯一性）5.将编码写入文件，一下显示文件部分内容位域存储的bite编码文档编码对应的字符顺序存储（可以看到因为换行符的存在，自动换行了）6.解码（将文章在命令行显示，也写入了翻译文档(以doc格式保存)）六、课程设计总结本次程序设计过程中遇到过许多大大小小的问题，也在设计思路上遇到过难题，但都在各方面的努力下得到了解决。
一些问题如下：1.Bite形式保存由于以前没学到过位向量的内容，有一段时间无法实现这个功能，后来在网络上偶然接触到位域的内容，认识到其可行性，于是解决了此问题2.选择最小的两个权值一开始我认识的这个可能很复杂，又联想到堆排序可以对其有序输出，但我又不想改变其位置，所以增设一个place记录一开始的编码表位置，进行编码时改变后可以轻易还原总结：霍夫曼编码在通信领域内是十分重要的内容，对其的掌握既能帮助我们理解二叉树的重要性，也能为我们未来工作提供一个更广阔的舞台七、附录/**题目：Huffman编码的编码和解码*作者：杨欢*学号：161420325*完成时间：2015-12-30算法思想：以书上的霍夫曼算法为核心进行文章（所有内容，包括标点，换行符，所以命令行可能无法显示部分字符）编码和解码。
对于比特位的存储，我选择用位域进行简单方便的操作。
文件的读写都以最基本的方式进行。
测试文章上，我选择艾米莉的玫瑰这一小说测试，数据量大，可以验证程序的正确性*/#include<stdio.h>#include<stdlib.h>#include<string.h>const int MAXSIZE=300;//定义一次分配的Huffman储存单词最大量为500 const int OVERFLOW = 0;const int ERROR = 0;const int LineCountNum=500;typedef struct WordCount{char Word;//存放字符int freq;int parent , lchild , rchild;//存放亲子节点位置int place;//用来保存第一次堆排序后，建立霍夫曼表前的相对位置char *HuffmanCode;//存放霍夫曼编码}WordCount , *WC;//存放单词结点的结构体typedef struct HuffmanTree{WC w;int Number;//存储有多少数据存入}HuffmanTree , *HTree;typedef struct{unsigned int a:1;}bite;//设置位段，存储一个bite//**************操作函数声明***********void InitHuffmanTree(HTree &H);//初始化霍夫曼树void HeapSort(WC &W , int Number , int choice);//堆排序核心函数void HeapAdjust(WC &W , int down , int up , int choice);//堆排序调整函数,实现两种排序void HuffmanCoding(HTree &H , WC &HT); //求霍夫曼树和霍夫曼编码表void ShowHuffmanTree(HTree H);//输出霍夫曼树void Select(WC &W , int i , int &s1 , int &s2);//选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回void GetTheDeCode(HTree H);//将编码结果写入函数void PutTheDeCode(FILE *fp1 , FILE *fp2);//将编码结果解码得到文章void CountTheWord(HTree &H , FILE *fp);//记录单词权值void ShowTheEassy(FILE *wp);//展示文章//************主函数***************int main(){FILE *fp , *wp;HTree H;WC HT;//存放编码表printf("*************菜单**************************\n") ;printf("*********1.编码文档********\n");printf("*********2.解码文档********\n");printf("*********0.退出****************************\n");printf("请输入您的选择:");int choice;scanf("%d" ,&choice);getchar();while(choice != 0){switch(choice){case 1:InitHuffmanTree(H);if(!(fp = fopen("献给艾米莉的玫瑰.txt" , "r"))){//以文本文件形式打开文件printf("此文件不存在\n");exit(ERROR);}printf("文件打开成功\n");CountTheWord(H , fp);printf("按任意键统计该文章各字符出现的频率为\n");getchar();ShowHuffmanTree(H);printf("按任意键开始堆排序\n");getchar();HeapSort(H->w , H->Number , 1);//对频率排序printf("按任意键输出堆排序后的情况\n");getchar();ShowHuffmanTree(H);printf("现在开始进行霍夫曼树的构建和霍夫曼编码的构建\n");HuffmanCoding(H , HT);printf("输入任意键输出霍夫曼编码表：");getchar();printf("字符位置权值左孩子右孩子父亲\n");for(int i=1 ; i<=2*H->Number ; ++i){printf("%c %d %d %d %d %d\n" , HT[i].Word , i ,HT[i].freq ,HT[i].lchild , HT[i].rchild , HT[i].parent);}printf("按任意键输出构建的霍夫曼编码结果:");getchar();for(int i=1 ; i<=H->Number ; ++i){printf("%c 对应的编码为%s\n" , H->w[i].Word ,H->w[i].HuffmanCode);}printf("按任意键将结果写入文件\n");getchar();GetTheDeCode(H);free(H);//释放空间，避免影响break;case 2:PutTheDeCode(fp , wp);printf("该英文文章为\n");ShowTheEassy(wp);printf("\n");fclose(fp);break;case 0:break;}printf("请输入您的选择:");scanf("%d" ,&choice);getchar();}return 0;}//*********操作函数实现**********void InitHuffmanTree(HTree &H){if(!(H = (HuffmanTree *)malloc(sizeof(HuffmanTree))))exit(OVERFLOW);if(!(H->w = (WC)malloc(sizeof(WordCount)*MAXSIZE))) exit(OVERFLOW);//创建结点H->Number = 0;}//****************将结果写入文件******************** void GetTheDeCode(HTree H){FILE *fp , *wp;//********将编码表写出********if(!(fp = fopen("编码表文档.txt" , "w"))){//以二进制方式写出文章编码printf("此文件不存在\n");clearerr(fp);exit(ERROR);}for(int i=1 ; i<=H->Number ; ++i)fprintf(fp , "%s\n" , H->w[i].HuffmanCode);fclose(fp);if(!(fp = fopen("编码表对应单词文档.txt" , "w"))){//以二进制方式写出文章编码printf("此文件不存在\n");clearerr(fp);exit(ERROR);}for(int i=1 ; i<=H->Number ; ++i)fprintf(fp , "%c" , H->w[i].Word); //因为存在换行符，需要进行读取换行符，所以不进行分行存储fclose(fp);//********将编码文档写出***********if(!(fp = fopen("献给艾米莉的玫瑰.txt" , "r"))){//打开文章进行对比写出编码结果printf("此文件不存在\n");clearerr(fp);exit(ERROR);}if(!(wp = fopen("编码文档.txt" , "wb"))){//以二进制形式写出编码文档printf("此文档不存在\n");clearerr(wp);exit(ERROR);}bite Save;while(!feof(fp)){char Count;fscanf(fp , "%c" , &Count);for(int i=1 ; i<=H->Number ; ++i){if(Count == H->w[i].Word){//寻找到匹配的，得到其字符编码，现在将其以Bite位写出到文件for(int j=0 ; j<strlen(H->w[i].HuffmanCode) ; ++j){if(H->w[i].HuffmanCode[j] == '1')Save.a = 1;elseSave.a = 0;fwrite(&Save , sizeof(bite) , 1 , wp);//用位段写进文件}break;}}}fclose(fp);fclose(wp);printf("写出成功\n");}//***********将编码文件翻译成英文************void PutTheDeCode(FILE *fp , FILE *wp){HTree H;InitHuffmanTree(H);//*************读取编码文件********if(!(fp = fopen("编码表文档.txt" , "r"))){printf("此文件不存在\n");clearerr(fp);exit(ERROR);}int Num = 1;char Count[MAXSIZE];//存放出来的0 1字符串memset(Count , 0 , MAXSIZE*sizeof(char));while(!feof(fp)){fscanf(fp , "%s" , Count);if(strlen(Count) != 0){if(!(H->w[Num].HuffmanCode = (char*)malloc((strlen(Count)+1)*sizeof(char))))exit(OVERFLOW);strcpy(H->w[Num].HuffmanCode , Count);memset(Count , 0 , strlen(Count)*sizeof(char));//清零++Num;}}//将编码导出fclose(fp);if(!(fp = fopen("编码表对应单词文档.txt" , "r"))){printf("此文件不存在\n");clearerr(fp);exit(ERROR);}Num = 1;while(!feof(fp)){H->w[Num].Word = fgetc(fp);++Num;}fclose(fp);//**************翻译**********if(!(fp = fopen("编码文档.txt" , "rb"))){//以二进制读取编码文档printf("此文件不存在\n");clearerr(fp);exit(ERROR);}if(!(wp = fopen("翻译文档.doc" , "w"))){//写出文章编码printf("此文件不存在\n");clearerr(wp);exit(ERROR);}bite Put;//位段，用来将字符读出Num = Num-2;//存储了多余的换行符并且多加了一次，还原真实数目int NumberCount = strlen(H->w[Num].HuffmanCode);//存放最小的霍夫曼编码数，减小后面的比较次数int CT , i=0 ,j=1;while(!feof(fp)){if(i < NumberCount){//从最小字符串开始可以减少循环fread(&Put , sizeof(bite) , 1 , fp);if(Put.a == 1)Count[i] = '1';elseCount[i] = '0';++i;}else{while(j<=Num){if(strcmp(Count , H->w[j].HuffmanCode) == 0){//依据霍夫曼编码的唯一性,遇到编码相同即可进行单词写入fprintf(wp , "%c" , H->w[j].Word);//编码匹配，清空计数和数组,状态重置memset(Count , 0 , sizeof(char)*(i+1));i = 0;j = 1;break;}++j;if(j > Num){//代表当前编码不是霍夫曼编码，继续读入编码fread(&Put , sizeof(bite) , 1 , fp);if(Put.a == 1)Count[i] = '1';elseCount[i] = '0';j = 1;++i;}}}}fclose(fp);fclose(wp);}//**************解码文章输出**********void ShowTheEassy(FILE *wp){if(!(wp = fopen("翻译文档.doc" , "r"))){//写出文章编码printf("此文件不存在\n");clearerr(wp);exit(ERROR);}char Line[LineCountNum];while(!feof(wp)){fgets(Line , LineCountNum , wp);printf("%s" , Line);memset(Line , 0 , sizeof(char)*strlen(Line));//清零}}//***********存储单词***************void CountTheWord(HTree &H , FILE *fp){int WordNumCount = 1;//单词结点记载int jcount;//单词重复比较操作时的临时变量char LineCount[LineCountNum];//读入文章时规定一行最大单词量char Acount;H->Number = 0;while(!feof(fp)){//当文件未读到文件尾时进行循环memset(LineCount , 0 , LineCountNum);//清零fgets(LineCount , LineCountNum , fp);//行输出for(int i=0; i<strlen(LineCount) ; ++i){Acount = LineCount[i];if(WordNumCount == 1){H->w[WordNumCount].Word = Acount;H->w[WordNumCount].freq = 1;++H->Number;++WordNumCount;}else{jcount = WordNumCount-1;while(jcount >=1)//进行重复单词的比较{if(H->w[jcount].Word == Acount){++H->w[jcount].freq;break;}--jcount;if(jcount < 1){//代表无重复单词，进行加操作H->w[WordNumCount].Word = Acount;H->w[WordNumCount].freq = 1;++H->Number;++WordNumCount;}}}}}fclose(fp);//关闭文件}//**************堆排序函数****************8void HeapAdjust(WC &W , int down , int up , int choice){//已知除W[down].freq外均满足堆定义,case 1对频率排序，case 2对原本位置排序WordCount rc = W[down];switch(choice){case 1:for(int j=2*down ; j<=up ; j*=2){if(j<up && (W[j].freq < W[j+1].freq))++j;//j为频率较大的记录下标if(!(rc.freq < W[j].freq))break;//rc应插入在位置down上W[down] = W[j];down = j;}case 2:for(int j=2*down ; j<=up ; j*=2){if(j<up && (W[j].place < W[j+1].place))++j;//为位置较大的记录下标if(!(rc.place < W[j].place))break;//rc应插入在位置down上W[down] = W[j];down = j;}}W[down] = rc;}void HeapSort(WC &W , int Number , int choice){WordCount t;for(int i=Number/2 ; i>0 ; --i)HeapAdjust(W , i , Number , choice);//建成大顶堆for(int i=Number ; i>1 ; --i){//将堆顶记录和当前未经排序的子序列1..i中最后一个记录交换t = W[1];W[1] = W[i];W[i] = t;//1....i-1重新调整为大顶堆HeapAdjust(W , 1 , i-1 , choice);}}//**************霍夫曼编码核心函数***********void HuffmanCoding(HTree &H , WC &HT){//****************霍夫曼编码表构建**************if(H->Number <= 1)return;int m = 2*H->Number , i , s1 , s2;//0号单元未用WC p;//存放霍夫曼列表if(!(HT = (WordCount *)malloc(sizeof(WordCount)*(m+1))))//0号未用exit(OVERFLOW);for(p=HT , i=1; i<=H->Number ; ++i){p[i].Word = H->w[i].Word;p[i].freq = H->w[i].freq;p[i].parent = p[i].lchild = p[i].rchild = 0;p[i].place = i;//位置保存}i=H->Number+1;while(i<=m){p[i].Word = '#';//代表为空p[i].freq = 0;p[i].parent = p[i].lchild = p[i].rchild = 0;p[i].place = i;//位置保存++i;}for(i=H->Number+1 ; i<=m ; ++i){Select(HT , i-1 , s1 , s2);//选择最小的两个数HT[s1].parent = i;HT[s2].parent = i;HT[i].lchild = HT[s1].place;HT[i].rchild = HT[s2].place;//********存放堆排序前的位置HT[i].freq = HT[s1].freq + HT[s2].freq;HeapSort(HT , i , 1);//对i个数进行堆排序,始终保持频率升序}//**************从叶子到根求霍夫曼编码*************char *cd;if(!(cd = (char *)malloc((H->Number)*sizeof(char))))//分配n个字符编码的头指针向量exit(0);HeapSort(HT , m , 2);//对i个数进行堆排序,还原成本来的位置cd[H->Number-1] = '\0';for(i=1 ; i<=H->Number ; ++i){int start = H->Number-1;//编码结束符位置int c=i;//原位置取回int f=HT[i].parent;//原位置的父结点取回while(f!=0){if(HT[f].lchild == c)cd[--start] = '0';elsecd[--start] = '1';c=f;f=HT[f].parent;}if(!(H->w[i].HuffmanCode = (char*)malloc((H->Number-start)*sizeof(char))))exit(OVERFLOW);strcpy(H->w[i].HuffmanCode , &cd[start]);}}//*****************从编码文件生成源文件*****************void PutsHuffmanCodingToPC(FILE *fp , HTree &H){fwrite(&H , sizeof(HuffmanTree) , 1 , fp);}//***********输出霍夫曼树*****************void ShowHuffmanTree(HTree H){for(int i=1 ; i<=H->Number ; ++i){printf("%c %d " , H->w[i].Word , H->w[i].freq);if(i%2 == 0)printf("\n");}printf("\n");}//选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回，已经进行了堆排序void Select(WC &W , int i , int &s1 , int &s2){for(int j=1 ; j<=i ; ++j){if(W[j].parent == 0){s1 = j;++j;while(j<=i){if(W[j].parent == 0){s2 = j;break;}++j;}break;}}报告成绩：年月日。
