数据结构课程设计实验报告(赫夫曼编码)

数据结构哈夫曼编码器课程设计报告数据结构哈夫曼编码器课程设计报告1.引言1.1 编写目的本文档旨在详细介绍数据结构课程设计中的哈夫曼编码器的设计过程和实现方法。

1.2 背景哈夫曼编码是一种常用的数据压缩技术，通过构建变长编码表，将频率较高的字符用较短的编码表示，从而减小数据的存储和传输开销。

1.3 参考资料[1] 斯科特·梅耶, 数据结构与算法分析[C], 机械工业出版社, 2014.[2] Thomas H.Cormen, Charles E.Leiserson, RonaldL.Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press, 2009.2.需求分析2.1 功能需求①输入文件用户可以输入需要进行哈夫曼编码的文件路径。

②编码操作系统根据输入的文件，相应的哈夫曼编码，并显示编码结果。

③解码操作用户可以输入已经编码过的文件，系统将根据编码表进行解码，并显示解码结果。

2.2 非功能需求①性能要求系统在处理大规模文件时需要具备较高的性能，保证编码和解码的效率。

②用户友好性系统需要提供简洁明了的界面，方便用户操作。

③可扩展性系统需要具备良好的扩展性，满足未来需求变化的需要。

3.概要设计3.1 总体设计系统采用面向对象的设计方法，主要包含以下几个类：① HuffmanEncoder该类负责对输入文件进行哈夫曼编码的操作。

② HuffmanDecoder该类负责对已编码文件进行解码的操作。

③ HuffmanTree该类是哈夫曼树的实现，用于构建编码和解码所需的编码表。

3.2 类的详细设计① HuffmanEncoder3.①属性●inputFile: 输入文件路径●codeTable: 编码表3.②方法●setInput: string): 设置输入文件路径●generateCodeTable(): 编码表●encodeFile(): 对输入文件进行编码② HuffmanDecoder3.①属性●encodedFile: 已编码文件路径●codeTable: 编码表3.②方法●setEncoded: string): 设置已编码文件路径●setCodeTable(table: object): 设置编码表●decodeFile(): 对已编码文件进行解码③ HuffmanTree3.①属性●root: 哈夫曼树的根节点3.②方法●buildTree(frequencies: object): 根据字符频率构建哈夫曼树●buildCodeTable(): 构建字符与编码的对应关系表4.详细设计4.1 HuffmanEncoder类①属性●inputFile: string，输入文件路径●codeTable: object，编码表②方法4.① setInput: string)●作用：设置输入文件路径●输入：，string类型，输入文件路径●输出：无4.② generateCodeTable()●作用：编码表●输入：无●输出：无4.③ encodeFile()●作用：对输入文件进行编码●输入：无●输出：无5.实现6.测试与验证7.项目总结8.附件8.1 源代码文件8.2 测试文件9.法律名词及注释9.1 哈夫曼编码哈夫曼编码是一种变长编码方法，通过构建树形结构，将频率较高的字符用较短的编码表示。

一、实验目的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. 实现一个函数用于生成霍夫曼编码。

实验报告课程名称：数据结构实验名称：赫夫曼编码及应用院（系）：计算机与通信工程学院专业班级：计算机科学与技术姓名：学号：指导教师：2020 年 5 月12 日一、实验目的掌握赫夫曼树和赫夫曼编码的基本思想和算法的程序实现。

二、实验内容及要求1、任务描述a.提取原始文件中的数据（包括中文、英文或其他字符），根据数据出现的频率为权重，b.构建Huffman编码表；c.根据Huffman编码表对原始文件进行加密，得到加密文件并保存到硬盘上；d.将加密文件进行解密，得到解码文件并保存点硬盘上；e.比对原始文件和解码文件的一致性，得出是否一致的结论。

2、主要数据类型与变量a.对Huffman树采用双亲孩子表示法，便于在加密与解密时的操作。

typedef struct Huffman* HuffmanTree;struct Huffman{unsigned int weight; //权值unsigned int p, l, r;//双亲，左右孩子};b．对文本中出现的所有字符用链表进行存储。

typedef struct statistics* List;struct statistics {char str; //存储此字符int Frequency; //出现的频率（次数）string FinalNum; //Huffman编码struct statistics* Next;};3、算法或程序模块对读取到的文本进行逐字符遍历，统计每个字符出现的次数，并记录在创建的链表中。

借助Huffman树结构，生成结构数组，先存储在文本中出现的所有字符以及它们出现的频率（即权值），当作树的叶子节点。

再根据叶子节点生成它们的双亲节点，同样存入Huffman树中。

在完成对Huffman树的创建与存储之后，根据树节点的双亲节点域以及孩子节点域，生成每个字符的Huffman编码，并存入该字符所在链表节点的FinalNum域。

实验五哈夫曼树和哈夫曼树编码学院专业班学号姓名一．实习目的1.掌握哈夫曼树的顺序存储方式；2.掌握建立哈夫曼树的方法；3.掌握由哈夫曼树构造哈夫曼编码的方法。

二．实习内容1.建立哈夫曼树的顺序存储结构；2.编程实现构建一棵哈夫曼树。

3.编程实现由哈夫曼树构造出哈夫曼编码三．实习步骤1. 程序代码#include<malloc.h> // malloc()等#include<limits.h> // INT_MAX等#include<stdio.h> //#include<stdlib.h> //#include<string.h>typedef struct{unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表int min(HuffmanTree t,int i){ // 返回i个结点中权值最小的树的根结点序号，函数select()调用int j,flag;unsigned int k=UINT_MAX; // 取k为不小于可能的值(无符号整型最大值) for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0) // t[j]是树的根结点k=t[j].weight,flag=j;t[flag].parent=1; // 给选中的根结点的双亲赋1，避免第2次查找该结点return flag;}void select(HuffmanTree t,int i,int &s1,int &s2){ // 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个int j;s1=min(t,i);s2=min(t,i);if(s1>s2){j=s1;s1=s2;s2=j;}}void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 算法6.12{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start;unsigned c,f;HuffmanTree p;char *cd;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用for(p=HT+1,i=1;i<=n;++i,++p,++w){(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i<=m;++i,++p)(*p).parent=0;for(i=n+1;i<=m;++i) // 建赫夫曼树{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}// 从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));// 分配n个字符编码的头指针向量([0]不用)cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间cd[n-1]='\0'; // 编码结束符for(i=1;i<=n;i++){ // 逐个字符求赫夫曼编码start=n-1; // 编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)// 从叶子到根逆向求编码if( HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));// 为第i个字符编码分配空间strcpy( HC[i], &cd [start] ); // 从cd复制编码(串)到HC}free(cd); // 释放工作空间}void main(){HuffmanTree HT;HuffmanCode HC;int *w,n,i;printf("请输入权值的个数(>1): ");scanf("%d",&n);w=(int*)malloc(n*sizeof(int));printf("请依次输入%d个权值(整型):\n",n);for(i=0;i<=n-1;i++)scanf("%d",w+i);HuffmanCoding(HT,HC,w,n);printf("huffman树存储结构：\n");for( i=1;i<2*n;i++)printf("%4d%4d%4d%4d\n", HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);// 输出哈夫曼树的每个结点的权值、父亲结点序号、左孩子和右孩子序号。

(此文档为word格式，下载后您可任意编辑修改！) +数据结构课程设计题目：赫夫曼编码院、系：计算机科学与工程学院学科专业：计算机科学与技术学生：高经典学号：指导教师：梁晨2010年12月22日目录1课程设计的题目-----02课程设计的目的（设计要解决的问题）3概要设计（函数划分、总体设计）----14详细设计（算法、流程图、程序）-----25调试结果--6课程设计总结---- -337心得体会二课程设计的目的<1>巩固构造赫夫曼树的算法。

<2>设计实验用程序实现赫夫曼树的构造。

<3>熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编码。

三概要设计（函数划分、总体设计）<一>总体设计（1）输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。

（2）定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点，然后按照一定的规则构造赫夫曼树。

（3）开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把‚0‛接进链表是右孩子的把‚1‛接进链表，直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。

（4）从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到顺序的赫夫曼编码，直到把所有的叶子结点都访问到。

（5）用一个字符型的指针指向字符串的第一个字符，从存储叶子结点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头开始访问顺序表中的各元素，直到找到叶子结点的元素和当前字符相等就结束访输出赫夫曼编码，回到表头，指针后移，直到输出字符串的最后一个字符的赫夫曼编码，这样就得到输入字符串的赫夫曼编码。

数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告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·哈夫曼树：由哈夫曼编码算法构建的一种特殊的二叉树，用于表示字符编码的结构。

数据结构试验报告霍夫曼编码（DOC X页）数据结构实验报告(三)学院自动化学院学号姓名日期 2014-12-09实验目的1、掌握哈夫曼编码原理;2、熟练掌握哈夫曼树的生成方法;3、理解数据编码压缩和译码输出编码的实现;4、掌握二叉树的基本3操作。

实验内容利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

实验要求1) 初始化(Initialzation)。

利用下表给出的字符集和频度的=;实际统计数据建立哈夫曼树，并将它存于文件hfmTree中;字符空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 1547 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 12) 编码(EnCoding)。

利用已建好的哈夫曼树(若不在内存中，则从文件hfmTree中读入)，对以下报文进行编码，结果存入文件CodeFile中;报文内容:THIS PROGRAM IS MY FAVORITE3) 译码(Decoding)。

利用已建好的哈夫曼树，对文件CodeFile中编码后的报文进行解码，结果存入文件Textfile中;4) 输出(Output)。

输出字符集中每个字符的哈夫曼编码;输出原始报文，及其编码文件CodeFile和解码文件Textfile的内容。

扩展要求:将2)的编码结果以二进制形式存入CodeFile中，输出原始报文长度和编码后的报文长度。

1 需求分析(1) 将实验要求中的表格写在文件“HfmTree.txt”中，程序初始化时从该文件中读取字符及其频度，并据此建立Hfm树，生成编码表，打印出编码表; (2) 编码:用上一步生成的编码表，对报文进行编码，考虑到数据压缩性，这一步将编码结果以二进制文件进行存储，文件名为CodeFile; (3) 解码:从文件CodeFile中读入编码后的报文，利用建立好的Hfm树对其进行一一解码，输出解码结果，同时将结果存入Textfile.txt中; 2 概要设计因本次实验涉及许多字符串的操作，文件读写，并且除了霍夫曼树外，还用到了许多其他数据结构，而本次实验重点在霍夫曼树上，为了省去编写其他数据结构的时间，本次实验选用了C#语言和 .NetFrameWork 4.0来实现。

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

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

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

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

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

数据结构设计性实验Huffman编码与译码学号姓名班级设计性实验—Huffman 编码与译码一．实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman 树的建立方法，Huffman 编码的方法，进而设计出Huffman 译码算法，并编程实现。

二．实验要求：在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。

写出技术工作报告并附源程序。

三．实验内容及任务：1．设字符集为26个英文字母，其出现频度如下表所示。

2．建Huffman 树； 3．利用所建Huffman 树对任一字符串文件进行编码——即设计一个Huffman 编码器；4．对任一字符串文件的编码进行译码——即设计一个Huffman 译码器。

实现步骤：1．数据存储结构设计； 2．操作模块设计； 3．建树算法设计； 4．编码器设计；5． 译码器设计；51 48 1 15 63 57 20 32 5 1频度z y x w v u t 字符11611882380频度p 21 f q15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符四．分析以及算法描述1.分析问题1)首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。

2)认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法①又给定的n个权值{w1，w2，w3，……，w n}构造根节点的二叉树，从而得到一个二叉树森林F={T1，T2，T3，……T n}。

②在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。

③在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，将新的二叉树加入到二叉树森林F中。

④重复②和③，当二叉树森林F只剩下一棵二叉树时，这棵二叉树是所构造的霍夫曼树。

3)练习通过普通树来构造霍夫曼树。

数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告一、实验背景1：引言在日常生活中，信息传输已经成为了一个非常重要的环节。

通过对信息进行编码，可以有效地减少信息传输的开销和存储空间。

哈夫曼编码是一种常见的无损数据压缩方法，广泛应用于图像、音频和视频等领域。

本实验旨在通过实现哈夫曼编码算法，深入理解其工作原理，并对其性能进行评估。

2：实验目的本实验旨在：a：了解哈夫曼编码算法的基本原理；b：实现哈夫曼编码算法，并将其应用于对文本进行压缩；c：评估哈夫曼编码算法在不同文本数据上的性能。

二、实验内容1：哈夫曼编码原理介绍2：哈夫曼编码的实现思路a：构建哈夫曼树b：哈夫曼编码表c：对文本进行编码和解码3：实验环境介绍a：硬件环境b：软件环境4：实验步骤详解a：构建哈夫曼树的实现方法b：哈夫曼编码表的实现方法c：文本编码和解码的实现方法5：实验数据与结果分析a：不同文本数据的压缩结果对比 b：压缩性能的评估指标6：实验心得与建议a：实验过程中遇到的问题b：改进与优化方向三、实验结果与分析1：实验数据a：不同文本数据的大小与内容b：压缩率等性能指标数据2：实验结果分析a：不同文本数据对压缩效果的影响b：压缩率与文本数据的关系c：哈夫曼编码的运行时间分析四、结论根据实验结果和分析，可以得出以下结论：1：哈夫曼编码算法能够有效地减少文本数据的存储空间。

2：不同文本数据的压缩率存在差异，与文本的特性有关。

3：哈夫曼编码算法的运行时间与文本数据的长度成正比关系。

附件：1：实验源代码2：实验数据和结果法律名词及注释：1：无损数据压缩：指通过编码和解码过程，在不导致数据信息损失的情况下减少数据量。

2：哈夫曼编码：一种变长编码方式，通过更少的编码长度来表示频率较高的字符，从而达到减少编码长度的目的。