中衡算法分析与【设计明细】-实验二-哈夫曼编码

哈夫曼编码的实验报告哈夫曼编码的实验报告一、引言信息的传输和存储是现代社会中不可或缺的一部分。

然而，随着信息量的不断增加，如何高效地表示和压缩信息成为了一个重要的问题。

在这个实验报告中，我们将探讨哈夫曼编码这一种高效的信息压缩算法。

二、哈夫曼编码的原理哈夫曼编码是一种变长编码方式，通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而实现信息的压缩。

它的核心思想是利用统计特性，将出现频率较高的字符用较短的编码表示，从而减少整体编码长度。

三、实验过程1. 统计字符频率在实验中，我们首先需要统计待压缩的文本中各个字符的出现频率。

通过遍历文本，我们可以得到每个字符出现的次数。

2. 构建哈夫曼树根据字符频率，我们可以构建哈夫曼树。

哈夫曼树是一种特殊的二叉树，其中每个叶子节点代表一个字符，并且叶子节点的权值与字符的频率相关。

构建哈夫曼树的过程中，我们需要使用最小堆来选择权值最小的两个节点，并将它们合并为一个新的节点，直到最终构建出一棵完整的哈夫曼树。

3. 生成编码表通过遍历哈夫曼树，我们可以得到每个字符对应的编码。

在遍历过程中，我们记录下每个字符的路径，左边走为0，右边走为1，从而生成编码表。

4. 进行编码和解码在得到编码表后，我们可以将原始文本进行编码，将每个字符替换为对应的编码。

编码后的文本长度将会大大减少。

为了验证编码的正确性，我们还需要进行解码，将编码后的文本还原为原始文本。

四、实验结果我们选取了一段英文文本作为实验数据，并进行了哈夫曼编码。

经过编码后，原始文本长度从1000个字符减少到了500个字符。

解码后的文本与原始文本完全一致，验证了哈夫曼编码的正确性。

五、讨论与总结哈夫曼编码作为一种高效的信息压缩算法，具有广泛的应用前景。

通过将出现频率较高的字符用较短的编码表示，哈夫曼编码可以在一定程度上减小信息的存储和传输成本。

然而，哈夫曼编码也存在一些局限性，例如对于出现频率相近的字符，编码长度可能会相差较大。

YU
实验二：Huffman编码的实现
实验学时：3
实验类型：（演示、验证、综合、√设计、研究）
实验要求：（√必修、选修）
一、实验目的
理解和掌握huffman编码的基本原理和方法，实现对信源符号的huffman编码。

二、实验内容
1. 理解和掌握huffman编码的基本原理和方法
2. 通过MATLAB编程实现对单信源符号的huffma编码
3. 计算信源的信息熵、平均码长以及编码效率
三、实验原理
1．Huffman编码按信源符号出现的概率而编码，其平均码长最短，所以是最优码。

2．无失真信源编码定理：
对于熵为H(X)的离散无记忆的平稳信源，必存在一种无失真编码，使每符号的平均码长满足不等式：H(S)H(S)?L??1 logrlogr
3．二元Huffman编码：若将编码设计为长度不等的二进制编码，即让待传字符串中出现概率大的字符采用尽可能短的码字，而把长的码字分配给概率小的信源符号。

构造方法如下：
（a）将信源概率分布按大小以递减次序排列；合并两概率最小者，得
到新信源；并分配0/1符号。

（b）新信源若包含两个以上符号返回（a），否则到（c）。

（c）从最后一级向前按顺序写出每信源符号所对应的码字。

四、实验数据源
1．[X?P]:??s1s2s3s4s5X:{0,1} ?0.40.20.20.10.1。

数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告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.引言1.1 概述概述部分将对哈夫曼编解码算法进行简要介绍，包括该算法的产生背景、主要特点以及应用领域等方面的内容。

哈夫曼编解码算法是一种基于权重分布的压缩算法，它通过对输入的数据流进行编码和解码来实现数据的压缩和恢复。

该算法由大卫·哈夫曼（David A. Huffman）于1952年提出，是一种被广泛应用于信息论和数据压缩领域的有效算法。

该算法的主要特点是根据输入数据的权重分布构建一棵哈夫曼树，通过不等长的编码方式来表示输入数据中出现频率较高的字符或数据块。

编码时，出现频率较高的字符使用较短的二进制编码，而出现频率较低的字符则使用较长的二进制编码，以此来实现数据的压缩效果。

哈夫曼编码算法在数据压缩领域有着广泛的应用。

由于压缩后的数据长度较短，可以大大节省存储空间和传输带宽，因此被广泛应用于各种数据传输和存储场景中，如文件压缩、图像压缩、语音压缩等。

此外，哈夫曼编码算法的设计思想也对后续的数据压缩算法提供了重要的借鉴和参考价值。

本文将详细介绍哈夫曼编码算法的原理、设计与实现，并通过实例和实验验证算法的性能和效果。

通过对哈夫曼编码算法的研究与分析，可以更好地理解该算法的优势和不足，并为后续的算法改进和优化提供参考。

最后，本文将总结哈夫曼编码算法的主要特点和应用场景，并对未来的研究方向提出展望。

1.2 文章结构文章结构部分主要介绍本文的各个部分以及每个部分的内容安排。

在本文中，共包含引言、正文和结论三个部分。

引言部分主要介绍了整篇文章的背景和目的。

在概述部分，简要说明了哈夫曼编解码算法的概念和作用，以及该算法在通信领域的重要性。

然后，文章结构部分具体说明了本文的组织结构，以便读者能够清晰地了解文章的整体脉络。

正文部分是本文的主体，分为两个部分：哈夫曼编码算法原理和哈夫曼编码算法设计与实现。

在哈夫曼编码算法原理部分，将详细介绍哈夫曼编码算法的基本原理，包括频率统计、构建哈夫曼树和生成哈夫曼编码等步骤。

数据结构实验报告----约瑟夫环一、需求分析：约瑟夫环是程序的一道经典例题，可以使用数据结构的单链表进行编写。

二、概要设计：大体上可以使用单链表通过节点的创建和删除来达到人数出列的效果，可以大大缩短程序量。

三、详细设计：1、首先定义一个单链表，然后分别做创建链表、以及对应的输入数据，删除节点对应的删除数据，以及输出功能。

最后用主函数实现上述功能。

下为程序源代码：#include<stdio.h>#include<malloc.h>typedef struct Lnode //创建一个单链表{int num;int key;struct Lnode *next;}Joseph;struct Lnode *head,*p,*p1;int creatlinklist(int n) //为节点分配内存，创建节点{int i=0;head = (struct Lnode*)malloc(sizeof(struct Lnode));if(!head){return 0;}p=head;for(i = 0;i<n-1;i++){p1=(struct Lnode*)malloc(sizeof(struct Lnode));if(!p1){return 0;}p->next=p1;p=p1;}p->next=head;p1=head;return 0;}int input(int n) //在分配的节点上输入数据{int i=0;int j=0;printf("please input the keys:\n");for(i =1;i<n+1;i++){scanf("%d",&j);p1->num=i;p1->key=j;p1=p1->next;}p1=p;return j;}int output(int m,int n) \\在约瑟夫环的规定上输出数据删除节点{int i=0;int a=0;for(i =0;i <n;i++){for(a=0;a<m-1;a++){p1=p1->next;}p=p1->next;m=p->key;printf("%d\n",p->num);p1->next=p->next;free(p);}return 0;}void main(){int m=0;int n=0;printf("请输入上限值和人数值：\n");scanf("%d%d",&m,&n);creatlinklist(n);input(n);printf("出对的人：\n");output(m,n);}四、调试分析：程序仅能使用一次，并且输入格式没有提示，容易犯错。

哈夫曼树编码实验报告哈夫曼树编码实验报告引言：哈夫曼树编码是一种常用的数据压缩算法，通过对数据进行编码和解码，可以有效地减小数据的存储空间。

本次实验旨在探究哈夫曼树编码的原理和应用，并通过实际案例验证其有效性。

一、哈夫曼树编码原理哈夫曼树编码是一种变长编码方式，根据字符出现的频率来确定不同字符的编码长度。

频率较高的字符编码较短，频率较低的字符编码较长，以达到最佳的数据压缩效果。

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篇一、实验目的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。

接下来，我们读取压缩后的数据，根据编码规则进行解码，恢复原始数据。

比较原始数据和恢复后的数据，发现两者完全一致，验证了压缩和解码的正确性。

实验1哈夫曼编码实验的目的是掌握哈夫曼编码的原理，掌握哈夫曼树的生成方法。

了解数据压缩。

实验要求实现Huffman编解码器生成算法。

三。

实验内容首先统计待压缩文件中出现的字符和字母的数量，根据字符字母和空格的概率对其进行编码，然后读取要编码的文件并将其存储在另一个文件中；然后调用已编码的文件，对输出进行解码，最后存储到另一个文件中。

5实验原理1。

假设树的权值是用huffn树的定义来构造的。

每个加权叶为wi，权值路径最小的二叉树成为Huffman树或最优二叉树。

Huffman树的结构：权重是一个输入频率的数组，这些值根据节点对象中的数据属性按顺序分配给HTs，即每个HT节点对应一个输入频率。

然后，根据数据属性，从最小值到最大值取两个最小值和这个小HT节点，将它们的数据相加，构造一个新的htnode作为它们的父节点。

指针parentleftchild和rightchild被分配了相应的值。

将这个新节点插入最小堆。

按照这个程序，我们能建一棵树吗？通过构造的树，从下至上搜索父节点，直到父节点成为树的顶点。

这样，每次向上搜索后，根据原始节点是父节点的左子节点还是右子节点记录1或0。

每一个01都有一个完整的编码，每一个都有一个完整的编码。

初始化，以文本文件中的字符数为权值，生成Huffman树，按符号概率由大到小对符号进行排序，概率最小的两个符号形成一个节点。

重复步骤（）（），直到概率和为1，从根节点到每个符号对应的“叶”，概率高的符号标为“0”，概率低的符号从根节点开始，对符号7进行编码。

实验程序ා include<iostream>ා include<iomanip>ා include<iomanip>使用命名空间STD；typedef struct//节点结构{char data；//记录字符值long int weight；//记录字符权重unsigned int parent，lchild，rchild；}Htnode，*HuffmanTree；typedef char**huffmancode；//dynamicly allocate array to store Huffman code table void select（HuffmanTree&amp;HT，int i，int&amp;S1，int&amp;S2）//选择HT[1中权重最小且父节点不为0的两个节点。

数据结构哈夫曼编码实验报告实验目的：本实验旨在了解和实现哈夫曼编码算法，通过将字符转换为对应的哈夫曼编码来实现数据的压缩和解压缩。

一、引言1.1 背景介绍哈夫曼编码是一种基于字符出现频率的编码方法，通过使用不等长编码来表示不同字符，从而实现数据的高效压缩。

该编码方法在通信、存储等领域有着广泛的应用。

1.2 目标本实验的目标是实现哈夫曼编码算法，通过对给定文本进行编码和解码，验证哈夫曼编码的有效性和可靠性。

二、实验过程2.1 数据结构设计在实现哈夫曼编码算法时，我们需要设计合适的数据结构来存储字符和对应的编码。

常用的数据结构包括树和哈希表。

我们将使用二叉树作为数据结构来表示字符的编码。

2.2 构建哈夫曼树哈夫曼树是由给定字符集合构建而成的最优二叉树。

构建哈夫曼树的过程分为两步：首先根据字符出现频率构建叶子节点，然后通过合并叶子节点和父节点构造哈夫曼树。

2.3 哈夫曼编码表根据构建好的哈夫曼树，我们可以对应的哈夫曼编码表。

哈夫曼编码表由字符和对应的编码组成，可以用于字符的编码和解码。

2.4 文本压缩利用的哈夫曼编码表，我们可以对给定的文本进行压缩。

将文本中的字符逐个替换为对应的哈夫曼编码，从而实现数据的压缩。

2.5 文本解压缩对压缩后的数据进行解压缩时，我们需要利用的哈夫曼编码表，将哈夫曼编码逐个替换为对应的字符，从而还原出原始的文本数据。

三、实验结果我们使用不同长度、不同频率的文本进行了实验。

实验结果表明，哈夫曼编码在数据压缩方面有着显著的效果，可以大大减小数据存储和传输的开销。

四、实验总结通过本实验，我们深入理解了哈夫曼编码算法的原理和实现过程，掌握了数据的压缩和解压缩技术。

哈夫曼编码作为一种经典的数据压缩算法，具有重要的理论意义和实际应用价值。

附件：本文档附带哈夫曼编码实验的源代码和实验数据。

法律名词及注释：在本文档中，涉及的法律名词和注释如下：1.哈夫曼编码：一种数据压缩算法，用于将字符转换为可变长度的编码。

哈夫曼编码实验报告哈夫曼编码实验报告一、引言哈夫曼编码是一种用于数据压缩的算法，由大卫·哈夫曼于1952年提出。

它通过将出现频率高的字符用较短的编码表示，从而实现对数据的高效压缩。

本实验旨在通过实际操作和数据分析，深入了解哈夫曼编码的原理和应用。

二、实验目的1. 掌握哈夫曼编码的基本原理和算法；2. 实现哈夫曼编码的压缩和解压缩功能；3. 分析不同数据集上的压缩效果，并对结果进行评估。

三、实验过程1. 数据集准备本实验选取了三个不同的数据集，分别是一篇英文文章、一段中文文本和一段二进制数据。

这三个数据集具有不同的特点，可以用来评估哈夫曼编码在不同类型数据上的压缩效果。

2. 哈夫曼编码实现在实验中，我们使用了Python编程语言来实现哈夫曼编码的压缩和解压缩功能。

首先，我们需要统计数据集中各个字符的出现频率，并构建哈夫曼树。

然后，根据哈夫曼树生成每个字符的编码表，将原始数据转换为对应的编码。

最后，将编码后的数据存储为二进制文件，并记录编码表和原始数据的长度。

3. 压缩效果评估对于每个数据集，我们比较了原始数据和压缩后数据的大小差异，并计算了压缩比和压缩率。

压缩比是指压缩后数据的大小与原始数据大小的比值，压缩率是指压缩比乘以100%。

通过对比不同数据集上的压缩效果，我们可以评估哈夫曼编码在不同类型数据上的性能。

四、实验结果与分析1. 英文文章数据集对于一篇英文文章，经过哈夫曼编码压缩后，我们发现压缩比为0.6，即压缩后的数据只有原始数据的60%大小。

这说明哈夫曼编码在英文文本上具有较好的压缩效果。

原因在于英文文章中存在大量的重复字符，而哈夫曼编码能够利用字符的出现频率进行编码，从而减少数据的存储空间。

2. 中文文本数据集对于一段中文文本，我们发现哈夫曼编码的压缩效果不如在英文文章上的效果明显。

压缩比为0.8，即压缩后的数据只有原始数据的80%大小。

这是因为中文文本中的字符种类较多，并且出现频率相对均匀，导致哈夫曼编码的优势减弱。

一、设计思想(一) 哈夫曼树的设计思想对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。

首先给定n个权值制造n个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。

（二）哈夫曼编码与解码的设计思想在数据通讯中，经常要将传送的文字转换为二进制字符0和1组成的二进制串，称这个过程为编码。

与子相对的是解码或是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。

在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。

首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。

以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。

二、算法流程图（一）哈夫曼树的流程图图1哈夫曼树的流程图（二）编码与解码的流程图图2编码与解码的流程图图片说明：（左边）编码流程图，（右边）解码流程图。

三、源代码下面给出的是用中缀转后缀算法实现的程序的源代码：#include "stdio.h"#include "string.h"#define MAX 100 /*定义常量*/struct HaffNode{int weight; /*权值*/int parent; /*双亲结点下标*/char ch;int rchild;}*myHaffTree; /*构造哈夫曼树*/struct Coding{char bit[MAX]; /*定义数组*/char ch;int weight; /*字符的权值*/}*myHaffCode; /*定义结构体*/void Haffman(int n) /*定义哈夫曼函数*/{int i,j,x1,x2,s1,s2;for (i=n+1;i<=2*n-1;i++) /*树的初始化*/{s1=s2=10000;x1=x2=0;for (j=1;j<=i-1;j++) /*构造哈夫曼树的非叶子结点*/{if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s1) /*分配左右结点*/ {s2=s1;x2=x1;s1=myHaffTree[j].weight;x1=j;}else if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s2){s2=myHaffTree[j].weight;x2=j;}}myHaffTree[x1].parent=i;myHaffTree[x2].parent=i;myHaffTree[i].weight=s1+s2; /*左右子组合为新树*/myHaffTree[i].lchild=x1;myHaffTree[i].rchild=x2;}}void HaffmanCode(int n) /*构造n个结点哈夫曼编码*/{int start,c,f,i,j,k;char *cd;cd=(char *)malloc(n*sizeof(char));myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));cd[n-1]='\0';for(i=1;i<=n;++i) /*n个叶子结点的哈夫曼编码*/{for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent)if(myHaffTree[f].lchild==c) cd[--start]='0';else cd[--start]='1';for(j=start,k=0;j<n;j++){myHaffCode[i].bit[k]=cd[j];k++;}myHaffCode[i].ch=myHaffTree[i].ch; /*取编码对应的权值*/ myHaffCode[i].weight=myHaffTree[i].weight;}free(cd);}Init() /*定义有返回值的函数*/ {int i,n,m;printf("please input the number of words:");scanf("%d",&n);m=2*n-1;myHaffTree=(struct HaffNode *)malloc(sizeof(struct HaffNode)*(m+1));for(i=1;i<=n;i++){printf("please input the word and the equal:");scanf("%s%d",&myHaffTree[i].ch,&myHaffTree[i].weight);myHaffTree[i].parent=0;myHaffTree[i].lchild=0;myHaffTree[i].rchild=0;}for(i=n+1;i<=m;i++){myHaffTree[i].ch ='#';myHaffTree[i].lchild=0;myHaffTree[i].parent=0;myHaffTree[i].rchild=0;myHaffTree[i].weight=0;}Haffman(n);HaffmanCode(n);for(i=1;i<=n;i++){printf("%c %d",myHaffCode[i].ch,myHaffCode[i].weight);printf("\n");}printf("init success!\n");return n;}void Caozuo_C(int m) /* 编码函数*/{int n,i,j;char string[50],*p;printf("please input the words：");scanf("%s",string);n=strlen(string); /*计算字符串长度*/ for(i=1,p=string;i<=n;i++,p++) /*进行编码*/{for(j=1;j<=m;j++)if(myHaffCode[j].ch==*p)printf("%s\n",myHaffCode[j].bit);}}void Caozuo_D(int n) /*解码函数*/{int i,c;char code[1000],*p;printf("please input the coding："); /*输入二进制编码*/ scanf("%s",code);for(p=code,c=2*n-1;*p!='\0';p++) /*进行解码*/{if(*p=='0') /*结束条件*/{c=myHaffTree[c].lchild; /*赋值*/if(myHaffTree[c].lchild==0) /* 扫描*/{printf("%c",myHaffTree[c].ch);c=2*n-1;continue; /*结束*/}}else if(*p=='1'){c=myHaffTree[c].rchild;if(myHaffTree[c].lchild==0){printf("%c",myHaffTree[c].ch);c=2*n-1; /*赋值*/continue;}}}printf("\n");}void main() /*主函数*/{int n;char char1; /*定义字符*/n=Init(); /*函数的调用*/printf("A.coding B.codeprinting C.exit\nplease input the process:\n");while(1){scanf("%c",&char1);if(char1=='c') /*判断字符*/break;switch(char1){case'A':Caozuo_C(n);break; /*执行编码操作*/case'B':Caozuo_D(n);break; /*执行解码操作*/case'C':;break;}}}四、运行结果（一）中缀转后缀算法的运行结果：五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：●问题1:刚开始不知道如何建一个好树，因为我开始试着建了几个二叉树，不知道什么原因运行的时候那编码总是不对，跟在草稿纸上自己画的那个二叉树总是不相符，就找原因。

算法实验2-哈夫曼编码实验报告
哈夫曼编码又称为霍夫曼编码，是1952年由克劳德·哈夫曼（Claude Elwood Shannon）提出的一种数据压缩和编码方法。

它可以从一个字符串中挑选出重复出现频率较高的字母等字符，将这些字母用比它们出现次数少的符号代替，从而达到减少数据存储空间的目的。

哈夫曼编码在文件压缩和网络传输中有着巨大的应用。

哈夫曼编码的原理基于信息论，利用熵的概念来实现数据压缩和编码。

熵是信息源发送信息的期望的信息量的度量，也就是说，发送的信息越多，熵越大。

所以，哈夫曼编码就是根据被发送信息的可能性来构造字符编码的，这样就能够优化发送的信息长度，从而实现数据压缩。

哈夫曼编码的基本步骤是：首先，根据待编码的字符统计其出现的频率，形成一棵二叉树；接着，给每个最底层的叶子节点分配编码，这里使用的是0和1来代替；最后，把最底层节点上的编码和字母相关联形成一个字符集。

哈夫曼编码得到的编码串中每个字符的编码长度都不一样，每个字符的编码长度取决于它出现的频率。

出现次数越多的字符编码得越短，这就使得哈夫曼编码能够获得比其他编码更短的编码长度，从而更好地完成数据压缩任务。

哈夫曼编码是实现数据压缩和编码的一种有效方法，它可以将数据压缩到最小可能的体积，同时使用起来非常简单。

它非常适用于实施网络传输的压缩处理，可以有效减少传输所需的时间，提高数据传输的效率。

实验报告-2Huffman编码《信息与编码》课内实验报告学⽣姓名:及学号：学院:理学院班级:课程名称：信息与编码实验题⽬:Huffman编码指导教师副教授姓名及职称：讲师实验师2014年3⽉14⽇⽬录⼀、实验⽬的 (1)⼆、实验内容 (1)三、实验要点及说明 (1)四、实现⽅法 (1)五、实验结果 (2)六、源程序清单 (2)七、思考及总结 (5)⼀、实验⽬的1．掌握变长编码及即时码的特点； 2．理解Huffman 编码的特性及编码⽅法；⼆、实验内容对给定信源，统计信源分布，在信源概率分布确定情况下，进⾏Huffman 编码，并给出编码结果，并计算平均码长。

三、实验要点及说明通过matlab 编程，计算相应结果并绘制图形，理解相关性质。

四、实现⽅法以matlab 软件为基础，通过编程，对给出或计算出的概率分布计算相应Huffman 编码，并计算平均码长。

通过matlab 编程计算，步骤如下：1. ⽣成表⽰信源的概率分布p 和表⽰信号字母表的元包数组u ；2. 根据公式??=+-+-==.,,3,2,)1(,1,k j j k r j k j a t j 计算霍夫曼压缩表的列数k 和各列的⾏数j t ，为后⾯的计算做准备；3. 根据霍夫曼压缩表的构建⽅法，循环计算各概率列的数值，同时对各概率列排序并获取插⼊元素的位置（⿊框标记位置）；4. 根据霍夫曼编码表的构建⽅法，从后往前计算出各列的霍夫曼编码；5. 将霍夫曼编码表中的第⼀列霍夫曼编码重新排序，得到最终霍夫曼编码。

五、实验结果霍夫曼编码表六、源程序清单运⾏命令：>> p=1./(8:16);>> p(10)=1-sum(p);>> for i=0:3u(i+1)={num2str(i)};end;>> [huff,summ,huffbiao] = huffman(p,u);源程序：function [huff,summ,huffbiao] = huffman(p,u) a=size(p,2); %获取第⼀列长度r=size(u,2); %获取信号字母个数huff=cell(1,a); %存储霍夫曼编码k=round((a-1)/(r-1)+0.5); %求列数huffbiao=cell(a,2*k); %存储霍夫曼压缩表t=zeros(1,k); %存储各列长度list=zeros(1,k-1); %存储标记位置pp=1:a; %标记排序后的位置t(1)=a;summ=0;for j=2:kt(j)=(k-j+1)*r-k+j; %求各列长度end;for j=a-1:-1:1 %⾸次排序for h=1:jp(h)=p(h+1);p(h+1)=temp;temp=pp(h);pp(h)=pp(h+1);pp(h+1)=temp;end;end;end;for i=1:ahuffbiao(i,1)={p(i)};end;for i=1:k-1temp=sum(p(t(i+1):t(i)));%求和num=0;for j=1:t(i+1) %插⼊，重排序if temp>=p(j)if temp>p(j) || j==t(i+1)num=num+1;end;temp1=p(j);p(j)=temp;temp=temp1;if num==1list(i)=j; %获取标记位置end;end;end;p(t(i+1)+1:t(i))=0; %将⽆⽤的部分置为0for h=1:t(i+1)huffbiao(h,2*i+1)={p(h)}; %⽣成霍夫曼压缩表end;end;for i=k:-1:1huff(j)=u(j); %给霍夫曼压缩表最后概率列赋值end;elsetemp=huff(list(i)); %缓存编码for h=list(i)+1:t(i+1)huff(h-1)=huff(h); %给该列的前段赋值，即将后⼀列的标记位后⾯的编码提前⼀位end;for j=t(i+1):t(i)huff(j)=strcat(temp,u(j-t(i+1)+1)); %给该列的后段赋值，即将后⼀列的标记位编码与信号字母表对应编码连接后赋值end;end;for h=1:t(i)huffbiao(h,2*i)=huff(h); %⽣成霍夫曼压缩表end;end;for j=a-1:-1:1 %霍夫曼编码排序for h=1:jif pp(h)>pp(h+1)temp=pp(h);pp(h)=pp(h+1);pp(h+1)=temp;temp=huff{h};huff{h}=huff{h+1};huff{h+1}=temp;end;end;end;for i=1:asumm=summ+huffbiao{i,1}*length(huffbiao{i,2}); %求平均码长end;huff=huff';end七、思考及总结本次课内实验我理解了信源的最优变长编码的基本思想，明⽩了霍夫曼编码是⼀种⽤于⽆损数据压缩的熵编码（权编码）算法，通过编程演算熟练地掌握了Huffman信源编码⽅法，同时了解了变长编码及即时码的特点。

×××学院实验报告纸计算机科学与工程学院（院、系）网络工程专业071班组计算机算法设计与分析课学号2007102××姓名121 实验日期2010.教师评定哈夫曼编码问题1、实验目的：根据最优二叉树构造哈夫曼编码利用哈夫曼树很容易求出给定字符集及其概率分布的最优前缀码。

哈夫曼编码正是一种应用广泛且非常，本次试验通过设计一个算法，体会和掌握哈夫曼编码要点。

2、算法分析：给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子T[i]为出发点，向上回溯至根为止。

上溯时走左分支则生成代码0，走右分支则生成代码1。

3、程序代码：问题描述：已知每一个字符出现的频率，构造哈夫曼树，并设计哈夫曼编码。

功能描述：键入权值和相应字符按照“树状结构”打印构造好的哈夫曼树，并打印出每一个字符对应的哈夫曼编码。

选作内容：已知一个字符串，将其进行编码；已知一串编码，可以将其译码成字符串。

cprintf("请输入哈夫曼编码测试数据，在此建议为'thisprogramme is my favorite'");printf("\n");cprintf("注意小写,空格由大写字母T代替，并且字符数小于27.\n");scanf("%s",sstring);if(strlen(sstring)>=MAXNODE){printf("you input the data number >=MAXNODE.");exit(1);}for(i=0;i<strlen(sstring);i++){for(j=0;j<MAXBIT;j++)if(sstring[i]==haffcode[j].data){k=j;break;}if(k<0||k>MAXNODE-1){printf("在系统中找不到与第个%d字符相匹配的编码\n",i+1);continue;}newhaffcode[i].start=haffcode[k].start;newhaffcode[i].weight=haffcode[k].weight;newhaffcode[i].data=haffcode[k].data;for(s=haffcode[k].start+1;s<MAXBIT;s++)newhaffcode[i].bit[s]=haffcode[k].bit[s];}pprintf(newhaffcode,strlen(sstring));}void end()4、时间复杂度分析：算法的时间复杂度分析：程序部分用双循环嵌套结构，时间复杂度为O（n2）. 算法的空间复杂度分析：算法的空间复杂度为O（n）5、总结：通过一个简单的例子，掌握了哈夫曼编码的算法思想和要点。

实验二哈夫曼树及哈夫曼编码译码的实现实验二:哈夫曼树及哈夫曼编码译码的实现(验证性、4学时) 一、实验目的和要求构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。

(1)掌握树的有关操作算法2)熟悉树的基本存储方法 ((3)学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构;输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。

三、实验环境硬件:(1)学生用微机(2)多媒体教室或远程教学(3)局域网环境软件:(1)Windows XP中文操作系统 (2)Turbo C 3.0 四、算法描述及实验步骤1( 算法描述(1) 建立叶子结点——由于每个叶子结点都有一个权重值，构造哈夫曼树的过程中每个分枝节点的权重值等于两个孩子结点权重值的和，所以应该有一个权重域和指向左右孩子的两个指针域;(2) 另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。

(3) 构建哈夫曼编码——在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点，每回退一步走过哈夫曼树的一个分枝得到一个哈夫曼编码值;由于每个叶子结点的哈夫曼编码是从根就诶点到相应叶子结点的路径上各分枝代码所组成的0、1序列，所以先得到的分枝代码为说求编码的低位码而后得到的为高位码。

2( 算法流程图构建哈夫曼树算法流程哈夫曼编码算法流程3( 代码#include<stdio.h>#define maxvalue 10000//定义最大权值常量#define maxnodenumber 100//定义结点最大数目常量 typedef struct{int weight;int parent,lchild,rchild; }htnode;typedef htnode *huffmantree;//定义哈夫曼树类型 htnodeht[maxnodenumber]; //定义静态三叉链表存储区数组#define maxbit 10//定义哈夫曼编码的最大长度 typedef struct//定义保存一个叶子结点哈夫曼编码的结构 {int bit[maxbit];//哈夫曼编码域为一维数组int start;//开始位置域为整型}hcodetype;//定义哈夫曼编码类型hcodetype cd[maxnodenumber];//定义存放哈夫曼编码的数组cd void crthuffmantree(int n);//建立哈夫曼树void gethuffmancode(int n);//哈夫曼编码void main (){int nodenum;printf("inputnodenum:"); scanf("%d",&nodenum);crthuffmantree(nodenum); gethuffmancode(nodenum); }void crthuffmantree(int n)//该算法对n个叶子结点建立哈夫曼树，权重值由键盘逐个输入{int i,j,m1,m2,k1,k2;//定义局部变量for(i=0;i<2*n-1;i++)//数组ht初始化{ht[i].weight=0;//权重初始化为0ht[i].parent=-1;//3个指针域初始化为-1，即NULL ht[i].lchild=-1;ht[i].rchild=-1;}for (i=0;i<n;i++)//读入n个叶子结点的权重值scanf("%d",&ht[i].weight); for(i=0;i<n-1;i++)//控制n-1趟生成新结点构造哈夫曼树 {m1=maxvalue;//预置最小权值变量为最大权值 m2=maxvalue;//预置次小权值变量为最大权值 k1=0;k2=0;//预置最小和次小权值结点位置为下标0处for (j=0;j<n+i;j++)//控制一趟中找处最小权值的结点if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;//若第j个结点权小于当前最小的m1改为次小的m1=ht[j].weight;k1=j;//并记下新的当前最小权值及位置}elseif(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}//否则若小于当前次小的m2则更新m2及其位置ht[k1].parent=n+i;//修改最小权值结点的双亲为刚生成的新结点ht[k2].parent=n+i;//修改次小权值结点的双亲刚好生成的新结点ht[n+i].weight=ht[k1].weight+ht[k2].weight;//填新生成结点的权重值ht[n+i].lchild=k1;//新生成结点的左孩子指针指向k1ht[n+i].rchild=k2;//新生成结点的右孩子指针指向k2}}void gethuffmancode(int n) /*对具有n个叶子结点的哈夫曼树ht,求所有叶子结点的哈夫曼编码并输出*/{int i,j,c,p; /*定义局部变量*/for(i=0;i<n;i++) /*定义存放哈夫曼编码的数组cd*/ {c=i;j=maxbit; /*为求一个结点的哈夫曼编码初始化c和j*/ do{j--; /*j指向bit中存放编码位的正确位置*/ p=ht[c].parent; /*p指向c 的双亲结点*/if(ht[p].lchild==c) /*如果c是p的左孩子*/cd[i].bit[j]=0; /*编码位上赋0*/elsecd[i].bit[j]=1; /*否则c是p的右孩子，编码位上赋1*/ c=p; /*更新c为p,为求下一个编码位做准备*/ }while(ht[p].parent!=-1); /*当未到达根结点继续做do循环*/ cd[i].start=j; /*求完一个叶子结点的哈夫曼编码时，记下编码开始位置*/}for(i=0;i<n;i++) /*输出n个叶子结点的哈夫曼编码*/{for(j=cd[i].start;j<maxbit;j++) /*逐位输出一个编码*/printf("%d",cd[i].bit[j]);printf("\n"); /*输出完一个哈夫曼编码后换行*/ }}五、调试过程一次编译二次编译三次编译六、实验结果七、总结(1) 深刻体会构建哈夫曼树的整个过程，对整体有个总的理解; (2) 复习以前所学C语言的一些语法，例如:for循环，if循环，while循环 (3) 理解哈夫曼的编码过程，编码思想(4) 此程序的不足之处在于在进行哈夫曼编码时未能对字符进行编制，有待改进。