北邮数据结构实验报告实验三哈夫曼

数据结构实验报告实验名称：实验3——哈夫曼编码学生姓名：班级：班内序号：学号：日期：2013年11月24日1．实验要求利用二叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

2. 程序分析2.1存储结构：struct HNode{char c;//存字符内容int weight;int lchild, rchild, parent;};struct HCode{char data;char code[100];}; //字符及其编码结构class Huffman{private:HNode* huffTree; //Huffman树HCode* HCodeTable; //Huffman编码表public:Huffman(void);void CreateHTree(int a[], int n); //创建huffman树void CreateCodeTable(char b[], int n); //创建编码表void Encode(char *s, string *d); //编码void Decode(char *s, char *d); //解码void differ(char *,int n);char str2[100];//数组中不同的字符组成的串int dif;//str2[]的大小~Huffman(void);};结点结构为如下所示：三叉树的节点结构：struct HNode//哈夫曼树结点的结构体{ int weight;//结点权值int parent;//双亲指针int lchild;//左孩子指针int rchild;//右孩子指针char data;//字符};示意图为：int weight int parent int lchild int rchild Char c 编码表节点结构：struct HCode//编码表结构体{char data;//字符char code[100];//编码内容};示意图为：基本结构体记录字符和出现次数:struct node{int num;char data;};示意图为:2.关键算法分析(1).初始化:伪代码：1.输入需要编译的文本内容2.将输入的内容保存到数组str1中3.统计出现的字符数目,并且保存到变量count中4.统计出现的不同的字符，存到str2中，将str2的大小存到dif中时间复杂度O(n！)（2）.创建哈夫曼树算法伪代码：1.创建一个长度为2*n-1的三叉链表2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3.从三叉链表的第n个结点开始，3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。

数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告1·实验目的1·1 理解哈夫曼编码的基本原理1·2 掌握哈夫曼编码的算法实现方式1·3 熟悉哈夫曼编码在数据压缩中的应用2·实验背景2·1 哈夫曼编码的概念和作用2·2 哈夫曼编码的原理和算法2·3 哈夫曼编码在数据压缩中的应用3·实验环境3·1 硬件环境：计算机、CPU、内存等3·2 软件环境：编程语言、编译器等4·实验过程4·1 构建哈夫曼树4·1·1 哈夫曼树的构建原理4·1·2 哈夫曼树的构建算法4·2 哈夫曼编码4·2·1 哈夫曼编码的原理4·2·2 哈夫曼编码的算法4·3 实现数据压缩4·3·1 数据压缩的概念和作用4·3·2 哈夫曼编码在数据压缩中的应用方法5·实验结果5·1 构建的哈夫曼树示例图5·2 哈夫曼编码表5·3 数据压缩前后的文件大小对比5·4 数据解压缩的正确性验证6·实验分析6·1 哈夫曼编码的优点和应用场景分析6·2 数据压缩效果的评估和对比分析6·3 实验中遇到的问题和解决方法7·实验总结7·1 实验所获得的成果和收获7·2 实验中存在的不足和改进方向7·3 实验对于数据结构学习的启示和意义附件列表：1·实验所用的源代码文件2·实验中用到的测试数据文件注释：1·哈夫曼编码：一种用于数据压缩的编码方法，根据字符出现频率构建树形结构，实现高频字符用较短编码表示，低频字符用较长编码表示。

2·哈夫曼树：由哈夫曼编码算法构建的一种特殊的二叉树，用于表示字符编码的结构。

数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告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 构建哈夫曼树根据字符频率构建哈夫曼树是哈夫曼编码的核心步骤。

我们可以使用最小堆（优先队列）来高效地构建哈夫曼树。

首先，将每个字符频率作为节点存储到最小堆中。

然后，从最小堆中取出频率最小的两个节点，将它们作为子树构建成一个新的节点，新节点的频率等于两个子节点频率的和。

将新节点重新插入最小堆，并重复该过程，直到最小堆中只剩下一个节点，即哈夫曼树的根节点。

数据结构实验报告实验名称：哈夫曼树学生姓名：袁普班级：2013211125班班内序号：14号学号：2013210681日期：2014年12月实验目的和内容利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串 s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印哈夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

7、可采用二进制编码方式（选作）测试数据：I love data Structure, I love Computer。

I will try my best to studydata Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码2. 程序分析2.1 存储结构用struct结构类型来实现存储树的结点类型struct HNode{int weight; //权值int parent; //父节点int lchild; //左孩子int rchild; //右孩子};struct HCode //实现编码的结构类型{char data; //被编码的字符char code[100]; //字符对应的哈夫曼编码};2.2 程序流程2.3 关键算法分析算法1：void Huffman::Count()[1] 算法功能：对出现字符的和出现字符的统计，构建权值结点，初始化编码表[2] 算法基本思想：对输入字符一个一个的统计，并统计出现次数，构建权值数组，[3] 算法空间、时间复杂度分析：空间复杂度O（1），要遍历一遍字符串，时间复杂度O（n）[4] 代码逻辑：leaf=0; //初始化叶子节点个数int i,j=0;int s[128]={0}; 用于存储出现的字符for(i=0;str[i]!='\0';i++) 遍历输入的字符串s[(int)str[i]]++; 统计每个字符出现次数for(i=0;i<128;i++)if(s[i]!=0){data[j]=(char)i; 给编码表的字符赋值weight[j]=s[i]; 构建权值数组j++;}leaf=j; //叶子节点个数即字符个数for(i=0;i<leaf;i++)cout<<data[i]<<"的权值为："<<weight[i]<<endl;算法2：void Init();[1] 算法功能：构建哈弗曼树[2] 算法基本思想：根据哈夫曼树构建要求，选取权值最小的两个结点结合，新结点加入数组，再继续选取最小的两个结点继续构建。

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

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

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

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

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

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

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

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

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

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

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

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

数据结构哈夫曼编码实验报告【正文】1.实验目的本实验旨在研究哈夫曼编码的原理和实现方法，通过实验验证哈夫曼编码在数据压缩中的有效性，并分析其应用场景和优缺点。

2.实验原理2.1 哈夫曼编码哈夫曼编码是一种无损数据压缩算法，通过根据字符出现的频率构建一颗哈夫曼树，将频率较高的字符用较短的编码表示，频率较低的字符用较长的编码表示。

哈夫曼编码的编码表是唯一的，且能够实现前缀编码，即一个编码不是另一个编码的前缀。

2.2 构建哈夫曼树构建哈夫曼树的过程如下：1) 将每个字符及其频率作为一个节点，构建一个节点集合。

2) 每次从节点集合中选择出现频率最低的两个节点，构建一个新节点，并将这两个节点从集合中删除。

3) 将新节点加入节点集合。

4) 重复以上步骤，直到节点集合中只有一个节点，这个节点就是哈夫曼树的根节点。

2.3 编码过程根据哈夫曼树，对每个字符进行编码：1) 从根节点开始，根据左子树为0，右子树为1的规则，将编码依次加入编码表。

2) 对于每个字符，根据编码表获取其编码。

3) 将编码存储起来，得到最终的编码序列。

3.实验步骤3.1 数据读取与统计从输入文件中读取字符序列，并统计各个字符的频率。

3.2 构建哈夫曼树根据字符频率构建哈夫曼树。

3.3 构建编码表根据哈夫曼树，构建每个字符的编码表。

3.4 进行编码根据编码表，对输入的字符序列进行编码。

3.5 进行解码根据哈夫曼树，对编码后的序列进行解码。

4.实验结果与分析4.1 压缩率分析计算原始数据和压缩后数据的比值，分析压缩率。

4.2 编码效率分析测试编码过程所需时间，分析编码效率。

4.3 解码效率分析测试解码过程所需时间，分析解码效率。

4.4 应用场景分析分析哈夫曼编码在实际应用中的优势和适用场景。

5.结论通过本次实验，我们深入了解了哈夫曼编码的原理和实现方法，实践了哈夫曼编码的过程，并对其在数据压缩中的有效性进行了验证。

实验结果表明，哈夫曼编码能够实现较高的压缩率和较高的编解码效率。

数据结构实验报告实验名称:实验三树——哈夫曼编／解码器学生姓名:班级:班内序号：学号:日期:２014年12月11日1.实验要求利用二叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Iｎiｔ):能够对输入得任意长度得字符串s进行统计,统计每个字符得频度,并建立赫夫曼树2、建立编码表(CreaｔeTabｌｅ)：利用已经建好得赫夫曼树进行编码,并将每个字符得编码输出。

3、编码(Encｏｄing）:根据编码表对输入得字符串进行编码,并将编码后得字符串输出。

4、译码(Ｄecｏding）：利用已经建好得赫夫曼树对编码后得字符串进行译码，并输出译码结果。

5、打印(Ｐrint)：以直观得方式打印赫夫曼树(选作）6、计算输入得字符串编码前与编码后得长度,并进行分析,讨论赫夫曼编码得压缩效果。

测试数据:I lｏvｅdata Sｔｒｕcture, I lovｅputｅr。

I wiｌｌtrｙmy best ｔｏsｔudy ｄata Structure、提示：１、用户界面可以设计为“菜单”方式:能够进行交互。

2、根据输入得字符串中每个字符出现得次数统计频度,对没有出现得ﻩ字符一律不用编码。

2、程序分析2、1存储结构Ｈuffmａn树给定一组具有确定权值得叶子结点,可以构造出不同得二叉树,其中带权路径长度最小得二叉树称为Hｕffｍan树,也叫做最优二叉树。

wｅighｔlchilｄｒcｈｉld paｒｅnt２－1－1-15－1-1-16-1－1-17-１－1-1９-１-1-1wｅigｈt lchild rchilｄparent 2-1-155-1－156-１－167-１－１69-１-177017１3２38165482967-12、2 关键算法分析(1)计算出现字符得权值利用AＳCII码统计出现字符得次数,再将未出现得字符进行筛选,将出现得字符及頻数存储在数组ａ[]中。

void Huffmａn::Iｎｉt(){ﻩｉｎｔｎNｕm［256]＝ {0}；／/记录每一个字符出现得次数ｉnｔ ch = cin、get();ｉnt i=0;ﻩwｈｉle(（ｃｈ!='\r') ＆& （ch!='\n'）)ﻩ｛ﻩﻩｎＮｕm[cｈ]＋＋; ／/统计字符出现得次数ﻩstr[i＋+] ＝ cｈ; //记录原始字符串ﻩcｈ = cin、geｔ（）; //读取下一个字符ﻩ}str[ｉ]='\0';n = 0;for ( ｉ=０;ｉ＜256;i＋+)ﻩ｛ﻩﻩｉｆ(nNｕm[i]>０) /／若nＮum[i］==0,字符未出现ﻩ{l[ｎ] = (cｈａｒ)i;ﻩa［ｎ] = nNum[ｉ]；n++;ﻩ}}}时间复杂度为O(１);（2）创建哈夫曼树:算法过程:Huffman树采用顺序存储---数组;数组得前ｎ个结点存储叶子结点,然后就是分支结点,最后就是根结点；首先初始化叶子结点元素—循环实现；以循环结构，实现分支结点得合成，合成规则按照hｕfｆmaｎ树构成规则进行。