课程设计报告：Huffman编码

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

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

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

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

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

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

四、 实验数据源1．12345[]:0.40.20.20.10.1s s s s s X P ⎧⋅⎨⎩:{0,1}X2．123456[]:0.240.200.180.160.140.08s s s s s s X P ⎧⋅⎨⎩:{0,1}X 五、实验组织运行要求以学生自主训练为主的开放模式组织教学六、实验条件（1）微机（2）MATLAB 编程工具七、实验原理七、实验代码clear% S=[0.4,0.2,0.2,0.1,0.1]; S=[0.24,0.20,0.18,0.16,0.14,0.08];% S=[0.20,0.19,0.18,0.17,0.15,0.10,0.01];S0=sort(S); %将序列进行升序排列S1=fliplr(S0); %将升序排列的概率进行左右翻转得到降序排列t=length(S1); %得到信源符号的个数coding_table=[S1']; %创建编码过程表,第一列for i=1:length(S1)-1s=coding_table(t,i)+coding_table(t-1,i); %最小两个值相加S1(t-1)=s;S1(t)=0;t=t-1;S1=fliplr(sort(S1)); %进行重新降序排列coding_table=[coding_table,S1']; %排序结果加入到编码过程表for j=1:length(S1)if s==S1(j)b(i)=j; %记录两个最小概率相加得到的值在新排序中的位置。

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

数据结构设计性实验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篇一、实验背景霍夫曼树编码是一种基于字符频率进行数据压缩的算法，由David A. Huffman在1952年提出。

该算法通过构建霍夫曼树，为不同频率的字符分配不同长度的编码，从而实现数据压缩。

本实验旨在通过C语言实现霍夫曼树编码，并验证其压缩和解压缩效果。

二、实验目的1. 理解霍夫曼树编码的基本原理和步骤。

2. 掌握C语言实现霍夫曼树编码的方法。

3. 评估霍夫曼树编码的压缩效果和解压缩准确性。

三、实验原理霍夫曼树编码的核心思想是构建一棵霍夫曼树，该树由字符和它们的频率构成。

霍夫曼树的构建过程如下：1. 统计输入数据中每个字符的频率。

2. 将字符和频率作为节点，构建最小堆（优先队列）。

3. 重复以下步骤，直到堆中只剩下一个节点：a. 从堆中取出两个频率最小的节点，作为左右子节点。

b. 将这两个节点合并为一个新节点，其频率为两个节点频率之和。

c. 将新节点插入堆中。

4. 最小堆中的最后一个节点即为霍夫曼树的根节点。

霍夫曼树的叶子节点代表字符，非叶子节点代表子节点的频率之和。

根据霍夫曼树的构建，可以生成每个字符的编码，频率高的字符分配较短的编码，频率低的字符分配较长的编码。

四、实验步骤1. 数据准备：选择一段文本数据作为实验对象。

2. 字符频率统计：统计文本数据中每个字符的出现次数。

3. 构建霍夫曼树：根据字符频率构建霍夫曼树。

4. 生成编码表：根据霍夫曼树生成字符编码表。

5. 编码数据：使用编码表对文本数据进行编码。

6. 解压缩数据：根据编码表对编码后的数据进行解压缩。

7. 结果分析：比较原始数据和压缩数据的差异，评估压缩效果和解压缩准确性。

五、实验结果1. 字符频率统计：统计结果显示，字符“e”、“t”、“a”等在文本中出现的频率较高。

2. 构建霍夫曼树：成功构建了霍夫曼树，树中包含了所有字符及其频率。

3. 生成编码表：根据霍夫曼树生成了字符编码表，频率高的字符分配了较短的编码。

4. 编码数据：使用编码表对文本数据进行编码，成功生成了压缩数据。

霍夫曼编码的课程设计一、教学目标本课程的教学目标是使学生掌握霍夫曼编码的基本原理和方法，能够运用霍夫曼编码对字符串进行编码和解码。

具体来说，知识目标包括了解霍夫曼编码的背景和原理，理解霍夫曼编码的构造过程，掌握霍夫曼编码的编码和解码方法。

技能目标包括能够运用霍夫曼编码对给定的字符串进行编码和解码，能够分析和解决编码过程中遇到的问题。

情感态度价值观目标包括培养学生的逻辑思维能力，提高学生的问题解决能力，激发学生对计算机科学和信息论的兴趣。

二、教学内容本课程的教学内容主要包括霍夫曼编码的基本原理、构造过程和编码解码方法。

首先，介绍霍夫曼编码的背景和原理，使学生了解霍夫曼编码的起源和作用。

然后，讲解霍夫曼编码的构造过程，包括统计字符出现的频率、构造霍夫曼树和生成霍夫曼码表。

接着，教授霍夫曼编码的编码和解码方法，使学生能够运用霍夫曼编码对字符串进行编码和解码。

最后，通过实例分析和练习题，让学生巩固所学内容，提高实际操作能力。

三、教学方法为了实现本课程的教学目标，将采用多种教学方法相结合的方式进行教学。

首先，采用讲授法，向学生讲解霍夫曼编码的基本原理和构造过程。

其次，采用讨论法，引导学生分组讨论霍夫曼编码的编码和解码方法，促进学生之间的交流和合作。

此外，还将运用案例分析法，通过分析具体的实例，使学生更好地理解和掌握霍夫曼编码的应用。

最后，安排实验课，让学生亲自动手进行编码和解码操作，提高学生的实际操作能力。

四、教学资源为了支持本课程的教学内容和教学方法，将选择和准备适当的教五、教学评估本课程的教学评估将采用多种方式，以全面、客观、公正地评估学生的学习成果。

评估方式包括平时表现、作业和考试。

平时表现将根据学生在课堂上的参与度、提问和回答问题的积极性以及小组讨论的表现进行评估。

作业将包括编程练习和理论题目，以检验学生对霍夫曼编码的理解和应用能力。

考试将包括笔试和实践操作两部分，以全面评估学生的知识掌握和实际操作能力。

数据结构课程设计报告--Huffman编码与文件压缩课程设计报告题目：题目三哈夫曼编码与文件压缩课程名称：数据结构专业班级：计算机科学与技术1003班学号：姓名：鲁辰指导教师：报告日期：2012.09.26计算机科学与技术学院目录1任务书 (4)2 绪言 (5)2.1 课题背景 (5)2.2 课题研究的目的和意义 (5)2.3 国内外概况 (5)2.4 课题的主要研究工作 (5)3 系统设计方案的研究 (6)3.1 系统的控制特点与性能要求 (6)3.2 系统实现的原理 (6)3.2.1 Huffman算法 (6)3.2.2 Huffman编码 (6)3.2.3 压缩过程 (6)3.2.4 解压过程 (7)3.3 系统实现方案分析 (7)3.3.1 实现Huffman编码及压缩所需的变量 (7)3.3.2文件名处理 (9)3.3.3 实现Huffman编码及压缩过程所需要的函数 (10)3.3.4 实现解压缩过程所需要的函数 (13)3.3.5 输入输出 (13)4 基于Huffman编码的文件压缩程序的设计 (14)4.1 主模块功能介绍 (14)5 系统的实现 (15)5.1 目标程序运行截图 (15)5.2 测试及测试数据分析 (15)5.2.1 测试数据 (15)5.2.2 测试数据分析 (16)6 总结与展望 (18)参考文献 (19)附录英文缩写词 (20)1任务书题目三哈夫曼编码与文件压缩☐设计目的：掌握二叉树、哈夫曼树的概念，性质与存储结构，能够利用哈夫曼算法实现哈夫曼编码，并应用于文件压缩，从而提高学生综合运用知识的技能与实践能力。

☐设计内容：分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。

有兴趣的同学可以查阅资料实现Lempel-Ziv sliding window压缩方法，并与之比较。

第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。

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

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

《数据结构》课程设计上机实习报告课设题目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储存单词最大量为500const 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. 理解霍夫曼编码的基本原理，掌握霍夫曼编码算法的步骤。

2. 学会运用霍夫曼编码对给定数据进行压缩，并能够解释编码过程中的数据变化。

3. 了解霍夫曼编码在数据通信和存储中的应用，理解其在提高数据传输效率方面的优势。

技能目标：1. 能够运用所学知识，独立完成霍夫曼编码的算法实现，提高编程能力。

2. 学会分析霍夫曼编码在不同场景下的适用性，培养问题解决和决策能力。

3. 培养团队协作能力，通过小组讨论和合作，共同解决编码过程中遇到的问题。

情感态度价值观目标：1. 培养学生对算法学习的兴趣，激发主动探索和研究的热情。

2. 培养学生的创新意识，鼓励他们尝试优化霍夫曼编码算法，提高效率。

3. 培养学生面对问题时的耐心和毅力，使他们认识到解决问题的重要性。

课程性质：本课程为信息技术课程，旨在让学生通过学习霍夫曼编码，掌握数据压缩的基本原理和方法。

学生特点：学生具备一定的编程基础，对算法有一定的了解，但对霍夫曼编码的了解较少。

教学要求：结合学生特点和课程性质，采用任务驱动法、讨论法等教学策略，以实际案例为引导，引导学生主动探索，提高实践能力。

在教学过程中，注重培养学生的团队合作能力和创新思维。

通过本课程的学习，使学生能够将所学知识应用于实际问题中，提高数据传输和存储的效率。

二、教学内容1. 引入数据压缩的概念，介绍霍夫曼编码的背景和基本原理。

- 章节：数据压缩基础- 内容：数据压缩的必要性、霍夫曼编码的发展历程、编码原理。

2. 详细讲解霍夫曼编码的算法步骤和实现方法。

- 章节：霍夫曼编码算法- 内容：算法流程、编码过程、解码过程、编程实现。

3. 分析霍夫曼编码在数据通信和存储中的应用案例。

- 章节：霍夫曼编码应用- 内容：数据传输、图像压缩、音频压缩、实际案例分析。

4. 探讨霍夫曼编码的优化方法及其在现实场景中的适用性。

- 章节：霍夫曼编码优化- 内容：算法优化方法、适用场景分析、效率提升。

数据结构课程设计信息科学与工程学院：学院计算机科学与技术专业：1601 计卓级：班号：学：学生姓名指导教师：23/ 1年月日题目名称一、实验内容哈夫曼编码译码系统【问题描述】用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

【基本要求】1）初始化。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。

2）编码。

利用已建好的哈夫曼树对输入英文进行编码，编码结果存储在数组中。

3）译码。

利用已建好的哈夫曼树将数组中的代码进行译码，结果存入一个字符数组。

4）输出编码。

将编码结果显示在终端上，每行50个代码。

5）输出哈夫曼树。

将哈夫曼树以直观的方式（树或凹入表形式）显示出来。

【实现提示】用户界面可以设计为“菜单”方式，再加上一个“退出”功能。

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

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

参考教材P240-246【选做内容】将哈夫曼树保存到文件中，编码和译码的结果也分别存放在两个文本文件中。

23/ 2二、数据结构设计储存结构struct HNodeType {//字符结构体类型int weight;//权int parent;//双亲位置int lchild;//左孩子int rchild;//右孩子char inf;// 字符};struct HcodeType {存储编码int bit[MaxBit];// int start;// 起始位置};三、算法设计1、在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1。