数据结构课程设计-赫夫曼编码(C语言)

中南大学数据结构课程设计报告题目哈夫曼编译器学生姓名孙毅指导教师杨希学院信息科学与工程学院专业班级信息安全1401班二○一六年十一月1 / 23目录一、课程设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础，实践性强，课程设计是加强学生实践能力的一个重要手段。

课程设计要求学生在完成程序设计的同时能够写出规范的设计报告，培养学生分析问题、解决问题，提高学生软件设计能力。

二、课程设计的内容哈夫曼编译器2.1、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

对于双向传输信息的信道，每端都需要一个完整的编译码系统。

为这样的信息收发站编写哈夫曼编译系统。

2.2、基本要求(1)从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。

(2)利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。

(3)利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。

(4)输出代码文件，以紧凑格式显示。

(5)以直观的方式输出哈夫曼树，同时将此字符形式的哈夫曼树写入文件中。

三、问题描述，解决的方法3.1从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。

a.首先设计一个结构体，成员有权值、左右儿子、以及字符本身，再设计一个输入函数，函数中要求输入字符集大小n，以及这n个字符和他们各自对应的权值。

b.再根据以上的各种输入结合建立哈夫曼树的思想原理建立起哈夫曼树，设计的函数包括有两个，一个是选中最小权值的两棵树，另一个是创建哈夫曼树。

3.2利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。

a.第一步是要求用户输入待编码文件的路径，再根据路径读取待编码文件里的内容，再利用哈夫曼树将内容编码。

b.将编码的结果存入文件中，文件起名为编码结果.txt，这个工作已经在编码路径的同时并完成了。

《数据结构》课程设计报告%设计题目?学院名称信息工程学院专业班级12 计本 2姓名张翠翠学号17 ______$题目：哈夫曼(Huffman)编/译码器一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

二、设计目标帮助学生熟练掌握树的应用和基本操作，重点掌握二叉树的存储，这里以哈夫曼树为设计目标进一步提高学生的设计能力及对树的理解。

三、任务要求；一个完整的系统应具有以下功能：1) I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree 中。

2) E：编码（Encoding）。

利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

3) D：译码（Decoding）。

利用已建好的哈夫曼树将文件CodeFile 中的代码进行译码，结果存入文件TextFile中。

4) P：印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

5) T：印哈夫曼树（Tree Printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

四、需求分析~利用哈夫曼树(Huffman)编/译码（一）、初始化哈夫曼树（二）、建立哈夫曼树（三）、对哈夫曼树进行编码（四）、输出对应字符的编码（五）、译码过程五、概要设计哈夫曼树的存储结构描述~typedef struct{unsigned int weight;unsigned int parent, lchild, rchild;}HTNode, *HuffmanTree;哈弗曼树的算法void CreateHT(HTNode ht[],int n)arent=ht[i].lchild=ht[i].rchild=-1; arent==-1) eight<min1) eight;lnode=k;}}else if (ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i;eight=ht[lnode].weight+ht[rnode].weight;child=lnode;ht[i].rchild=rnode; arent;while (f!=-1) child==c) arent;、}++; ata);for (k=hcd[i].start;k<=n;k++) d[k]); }printf("\n");}}#void editHCode(HTNode ht[],HCode hcd[],int n) ata)tart;k<=n;k++){printf("%c",hcd[j].cd[k]);}break; tart,j=0;k<=n;k++,j++)d[k]) ata);for(x=0;code[x-1]!='#';x++) ata=str[i];ht[i].weight=fnum[i];}（while (flag) .");getch();system("cls");break;case 'b':case 'B':system("cls");printf("请输入要进行编码的字符串(以#结束):\n"); &editHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'c':case 'C':system("cls");！DispHCode(ht,hcd,n);printf("请输入编码(以#结束):\n");deHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'd':<case 'D':flag=0;break;default:system("cls");}}}字符（空格A B C D E F G&HI J K L M频度186【64132232103211547—57153220由上表画出哈夫曼树：…由哈夫曼树得出各字符的编码：字符编码字符编码空格10|0001DA010E111111001 B011111%FC0000G01110关系调用：；该程序的流程图：`【开始结点数是否大于1将data 和权值赋给ht输出根结点和权值调用selectmin 函数 计算根结点函数父结点为两子结点之和"是否为根结点左子是否为空此时编码为0i<=2*ni++编码为1结束、否否右子是否为空是是否否|是是七、测试分析白盒：查看代码完整性￥白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作。

c 哈夫曼编码课程设计一、课程目标知识目标：1. 学生能理解哈夫曼编码的基本原理，掌握其构建过程和应用场景。

2. 学生能运用哈夫曼编码进行数据压缩，并了解压缩比的概念。

3. 学生能理解哈夫曼编码在通信、图像处理等领域的重要性。

技能目标：1. 学生能够运用所学知识，独立构建哈夫曼树并进行编码。

2. 学生能够分析给定数据，选择合适的编码方法进行数据压缩。

3. 学生能够运用编程工具实现哈夫曼编码和解码过程。

情感态度价值观目标：1. 学生通过学习哈夫曼编码，培养对数据压缩技术的兴趣，提高信息素养。

2. 学生在合作学习过程中，培养团队协作能力和沟通能力。

3. 学生了解我国在数据压缩领域的研究成果，增强民族自豪感。

课程性质：本课程为信息技术课程，旨在帮助学生掌握数据压缩的基本方法，提高数据处理能力。

学生特点：学生处于高年级阶段，具备一定的编程基础和逻辑思维能力。

教学要求：结合学生特点和课程性质，注重理论与实践相结合，培养学生的实际操作能力和创新能力。

通过分解课程目标为具体学习成果，使学生在学习过程中能够明确自身的学习进度和目标。

二、教学内容1. 哈夫曼编码基本原理：介绍哈夫曼编码的概念、原理和优势，结合教材相关章节，使学生理解哈夫曼编码在数据压缩中的应用。

- 哈夫曼树的构建方法- 哈夫曼编码的生成过程- 压缩比的概念及其计算方法2. 哈夫曼编码的实际操作：通过实际操作，让学生掌握哈夫曼编码的构建和编码过程。

- 利用编程工具实现哈夫曼树的构建- 编程实现哈夫曼编码的生成- 数据压缩与解压缩的实际操作3. 哈夫曼编码的应用案例分析：结合教材案例，分析哈夫曼编码在通信、图像处理等领域的作用。

- 通信领域的数据压缩- 图像处理中的哈夫曼编码应用- 其他领域中的应用案例4. 编程实践：布置相关编程任务，巩固学生对哈夫曼编码的理解和应用。

- 实现哈夫曼编码的压缩和解压缩程序- 分析不同数据集的压缩效果，优化哈夫曼编码方法教学内容安排和进度：第1课时：哈夫曼编码基本原理及构建方法第2课时：哈夫曼编码的实际操作（构建哈夫曼树、生成编码）第3课时：哈夫曼编码的应用案例分析第4课时：编程实践（实现压缩与解压缩程序，优化编码方法）三、教学方法本课程将采用以下教学方法，以促进学生的主动参与和深入理解：1. 讲授法：对于哈夫曼编码的基本原理和概念，通过教师清晰的讲解，结合教材内容，使学生快速掌握理论基础。

赫夫曼编\译码器摘要本次课程设计过程中我主要根据课本中的实现思想及算法编写程序，体现以课本知识的应用为主，在学习了线性表、栈、队列、二叉树、树和图等结构的基础上，以能够更加熟练的应用所学知识，并能结合一些著名算法来实现对一些实际问题的应用，例如，赫夫曼树等，从而更为深刻理解数据结构的内涵，熟悉它们各自的应用场合及方法。

有些在平时课程中并没有掌握的内容在这次课程设计中都是先通过看课本学懂了，然后再在课程设计中加深印象，实现算法的应用和扩展。

这次课程设计的设计内容主要是通过实际的例子和程序来实现课本中所学习的算法的应用。

程序设计设计语言采用C++,程序运行平台为Windows XP。

赫夫曼编\译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成哈夫曼编码后进行译码。

赫夫曼编译系统分为五个功能模块：原始数据载入，打印编码规则、编码、译码。

以二叉树的应用为基础，包括统计信息，并通过构建赫夫曼树、对信息进行赫夫曼编码，将编码信息等存入文档。

关键字数据结构栈和队列赫夫曼树赫夫曼编码目录1引言 (1)1.1课程设计目的 (1)1.2课程设计背景 (1)1.3课程设计主要内容 (1)2需求分析 (3)3 概要设计 (4)3.1 设计思想 (4)3.2 函数间的关系 (4)3.3数据结构与算法设计 (4)4详细设计 (6)4.1 赫夫曼的主要结构 (6)5 调试分析 (8)6 测试并列出测试结果 (9)6.1 测试方式 (9)6.2 测试结果 (9)7 总结 (13)致谢 (14)参考文献 (14)附录 (15)1 引言当今社会，计算机技术和通信技术已不断发展，处理和传输的数据量越来越庞大。

如何采用有效的数据压缩技术引起了人们的极大重视。

从而产生了哈夫曼编码，它是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，通常我们将压缩技术称为编码，解压缩过程称为解码。

树状结构简称为树，是一种以分支关系进行定义的层次结构，是十分重要的非线性数据结构，在计算机软件设计方面，有着广泛的应用。

目录一、概述 (1)二、系统分析 (1)三、概要设计 (2)四、详细设计 (4)4.1 赫夫曼树的建立 (4)4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法 (5)4.1.2 统计字符串中字符的种类以及各类字符的个数 (7)4.1.3构造赫夫曼树 (8)4.2赫夫曼编码 (10)4.2.1赫夫曼编码算法 (10)4.2.2建立正文的编码文件 (11)4.3代码文件的译码 (12)五、运行与测试 (14)六、总结与心得 (14)参考文献 (15)附录 (15)一、概述本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出电文字符串。

在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

二、系统分析赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。

假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为∑W i L i 。

若将此对应到二叉树上，W i 为叶节点的权，L i 为根节点到叶节点的路径长度。

那么，∑W i L i 恰好为二叉树上带权路径长度。

因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树，此构造过程成为赫夫曼编码。

根据设计要求和分析，要实现设计，必须实现以下方面的功能：（1）赫夫曼树的建立；（2）赫夫曼编码的生成；（3）编码文件的译码；三、概要设计程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

目录目录 (1)1 课程设计的目的和意义 (3)2 需求分析 (5)3 系统设计 (6)（1)设计思路及方案 (6)（2)模块的设计及介绍 (6)(3)主要模块程序流程图 (9)4 系统实现 (14)（1）主调函数 (14)(2)建立HuffmanTree (14)(3）生成Huffman编码并写入文件 (18)（4)电文译码 (19)5 系统调试 (22)小结 (25)参考文献 (26)附录源程序 (27)1 课程设计的目的和意义在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。

哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0"码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1"的序列作为和各个对应的字符的编码，这就是哈夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串。

但在信息传递时,总希望总长度尽可能最短，即采用最短码。

作为软件工程专业的学生，我们应该很好的掌握这门技术。

在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。

在课程设计过程中,我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。

这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。

在课程设计过程中,我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。

更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见.同时,师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。

哈夫曼编码译码器数据结构C语言哈夫曼编码译码器数据结构C语言⒈简介本文档旨在介绍一个使用C语言实现的哈夫曼编码译码器的数据结构。

哈夫曼编码是一种用于数据压缩的算法，它通过将频率较高的字符用较短的编码表示，从而实现数据的压缩和解压缩。

⒉哈夫曼编码（Huffman Coding）基本概念⑴字符频率统计在进行哈夫曼编码之前，我们首先需要统计每个字符在待编码的数据中出现的频率。

通过遍历数据，记录每个字符的出现次数，我们可以得到一个字符频率的统计表。

⑵构建哈夫曼树通过字符频率的统计表，我们可以构建一个哈夫曼树。

哈夫曼树是一种二叉树，其中每个叶节点表示一个字符，而每个内部节点表示一个权重，即两个子节点的频率之和。

⑶哈夫曼编码在哈夫曼树构建完成后，我们可以根据树的结构每个字符的编码。

哈夫曼编码的特点是没有任何一个字符的编码是另一个字符编码的前缀，这种编码方式称为前缀编码。

⑷哈夫曼译码根据字符的哈夫曼编码，我们可以将编码后的数据进行解码，还原为原始的数据。

通过遍历哈夫曼树，从根节点开始，根据每个二进制位的取值进行向左或向右的移动，直至叶节点，然后获取该叶节点对应的字符。

⒊数据结构设计⑴结点结构定义一个哈夫曼树的结点结构，包含以下字段：●`char data`：字符●`int frequency`：字符的频率●`int is_leaf`：是否为叶节点●`struct Node left_child`：左子节点●`struct Node right_child`：右子节点⑵频率统计表使用一个数组或链表来记录每个字符的频率统计信息，包含以下字段：●`char data`：字符●`int frequency`：字符的频率⑶编码表使用一个数组或链表来记录每个字符的哈夫曼编码，包含以下字段：●`char data`：字符●`char code`：编码⒋算法流程⑴字符频率统计算法步骤：⒈初始化频率统计表为空。

⒉读取待编码的数据。

数据结构课程设计一、目的《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。

本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、要求通过这次设计，要求在数据结构析逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

三、内容2.哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

【基本要求】(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)设字符集及频度如下表：字符空格A B C D E F G H I J K L M频度186 64 13 22 32 103 21 15 47 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 1【选做内容】(1)译码功能；(2)显示哈夫曼树；(3)界面设计的优化。

哈夫曼编写编译码一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，这要求在发送端通过一个编码系统对待传输预先编码，在接收端将传来的数据进行译码。

对于双工通道，每端都需要一个完整的编/译码系统。

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

二、概要设计1．哈夫曼树的定义：在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。

2．哈夫曼树的构造：假设有N个权值，则构造出的哈夫曼树有N个叶子结点。

N个权值分别设为W1,W2,……….Wn,则哈夫曼树的构造规则为：（1）将W1，W2，……….Wn看成有N棵树的森林；（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左，右子树，且新树的根结点为其左，右子树结点权值之和；（3）从森林中删除选取取的两面三刀棵树，并将新树加入森林；（4）重复（2）（3）步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。

用c语言实现哈夫曼编码哈夫曼编码是一种用于无损数据压缩的熵编码算法。

以下是一个简单的使用C语言实现哈夫曼编码的例子。

这个例子只实现了编码过程，没有实现解码过程。

c复制代码#include<stdio.h>#include<stdlib.h>#include<string.h>// 节点结构体typedef struct Node {char data;int freq;struct Node *left, *right;} Node;// 创建新节点Node* newNode(char data, int freq) {Node* node = (Node*) malloc(sizeof(Node));node->data = data;node->freq = freq;node->left = node->right = NULL;return node;}// 计算前缀和int getSum(Node* root) {if (!root) return0;return root->freq + getSum(root->left) + getSum(root->right);}// 创建哈夫曼树Node* createHuffmanTree(char data[], int freq[], int size) { if (size == 0) return NULL;Node *left = newNode(data[size-1], freq[size-1]);Node *right = createHuffmanTree(data, freq, size-1);Node *top = newNode(0, getSum(right));top->left = left;top->right = right;return top;}// 打印哈夫曼编码void printHuffmanCode(Node* root, int n, char code[]) {if (!root) return;if (root->data != 0) printf("%c: ", root->data);code[n] = root->data;printHuffmanCode(root->left, n+1, code);printHuffmanCode(root->right, n+1, code);}int main() {char data[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};int freq[] = {5, 9, 12, 13, 16, 45};int size = sizeof(data)/sizeof(data[0]);Node* root = createHuffmanTree(data, freq, size);char code[256] = {0}; // 存放哈夫曼编码，初始为空字符串，表示没有编码，对应字符的编码为空字符串。

以下是C语言实现哈夫曼树编码的示例代码：```c#include <stdio.h>#include <stdlib.h>// 定义结构体表示节点struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};// 创建新节点struct TreeNode* newNode(int val) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;}// 计算权值和int calculateWeightSum(struct TreeNode* root) {if (root == NULL) {return 0;}return root->val + calculateWeightSum(root->left) + calculateWeightSum(root->right);}// 构建哈夫曼树struct TreeNode* buildHuffmanTree(int** freq, int size) {// 创建频率数组int arr[size];for (int i = 0; i < size; i++) {arr[i] = freq[i][0];}// 构建哈夫曼树struct TreeNode* root = NULL;int index = 0;while (index < size) {int min1 = INT_MAX, min2 = INT_MAX;int min1Index = -1, min2Index = -1;for (int i = 0; i < size; i++) {if (arr[i] < min1 && arr[i] != 0) {min1 = arr[i];min1Index = i;}if (arr[i] < min2 && arr[i] != 0) {min2 = arr[i];min2Index = i;}}// 创建新节点作为左右子树，并加入频率数组中arr[min1Index] = 0;arr[min2Index] = 0;struct TreeNode* left = newNode(min1);struct TreeNode* right = newNode(min2);left->left = right;right->right = left;// 将左右子树作为新的根节点，并更新频率数组和根节点指针if (root == NULL) {root = left;} else {struct TreeNode* parent = root;while (parent->left != NULL) {parent = parent->left;}parent->left = left;left->parent = parent;while (parent->right != NULL) {parent = parent->right;}parent->right = right;right->parent = parent;}index += 2; // 跳过左右子树，继续寻找下一对最小的节点构建子树，直到遍历完所有节点为止。