数据结构课程设计哈夫曼树及其应用

计算机学院信管专业

数据结构课程设计

题 目： 哈夫曼树的应用 班 级：

姓 名： 学 号： 同组人姓名：

起迄日期： 课程设计地点: 指导教师：

评阅意见： 成绩评定： 评阅人： 日期： 完成日期：2012年12月

目 录

一、 需求分析…………………………………………3 二、 概要设计…………………………………………4 三、 详细设计…………………………………………6 四、 调试分析和测试结果……………………………7 五、 心得体会和总结……………………………… 10 六、 参考文献……………………………………… 10 七、 附录…………………………………………… 11

2

一、 需求分析

（一）实验要求

要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只

计算机学院信管专业

数据结构课程设计

题 目： 哈夫曼树的应用 班 级：

姓 名： 学 号： 同组人姓名：

起迄日期： 课程设计地点: 指导教师：

评阅意见： 成绩评定： 评阅人： 日期： 完成日期：2012年12月

目 录

一、 需求分析…………………………………………3 二、 概要设计…………………………………………4 三、 详细设计…………………………………………6 四、 调试分析和测试结果……………………………7 五、 心得体会和总结……………………………… 10 六、 参考文献……………………………………… 10 七、 附录…………………………………………… 11

2

一、 需求分析

（一）实验要求

要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只

实验四 哈夫曼树编码

一、实验目的

1、掌握哈夫曼树的一般算法；

2、掌握用哈夫曼树对字符串进行编码；

3、掌握通过哈夫曼树对字符编码进行译码得过程。 二、实验基本要求 1、设计数据结构； 2、设计编码算法；

3、分析时间复杂度和空间复杂度 三、程序实现

此程序中包含六个函数：Select（）、HuffmanTree（）、BianMa（）、BianMa2（）、YiMa（）、 Sum（），其功能及实现过程如下： #include

struct element//哈夫曼树结点类型 { int weight; int lchild,rchild,parent; };

struct Char//字符编码表信息 { char node; int weight; char code[20]; };

void Select(element hT[],int &i1,int &i2,int k)//在hT[]中查找最小值及次小值 { int min1=9999,min2=9999; i1=i2=0; for(int i=0;i

void HuffmanTree(element huffTree[],Char zifuma[],int n) //

实验四 哈夫曼树编码

一、实验目的

1、掌握哈夫曼树的一般算法；

2、掌握用哈夫曼树对字符串进行编码；

3、掌握通过哈夫曼树对字符编码进行译码得过程。 二、实验基本要求 1、设计数据结构； 2、设计编码算法；

3、分析时间复杂度和空间复杂度 三、程序实现

此程序中包含六个函数：Select（）、HuffmanTree（）、BianMa（）、BianMa2（）、YiMa（）、 Sum（），其功能及实现过程如下： #include

struct element//哈夫曼树结点类型 { int weight; int lchild,rchild,parent; };

struct Char//字符编码表信息 { char node; int weight; char code[20]; };

void Select(element hT[],int &i1,int &i2,int k)//在hT[]中查找最小值及次小值 { int min1=9999,min2=9999; i1=i2=0; for(int i=0;i

void HuffmanTree(element huffTree[],Char zifuma[],int n) //

数据结构课程设计报告

题目：哈夫曼树及其应用

学生姓名： 刘昶志 学 号： 1021111609 班 级： 10211116 指导教师： 张军

2012年 6 月 3 日

东华理工大学 软件学院 软件工程系

1

目录

1、 需求分析说明~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3 2、 总体设计~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~4 3、 详细设计~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~5 4、 实现部分~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~7 5、 程序测试~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~9 6、 总结~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~10

东华理工大学 软件学院 软件工程系

2

一．需求分析说明

设计目的：

熟悉树的各种存储结构及其特点

北京邮电大学电信工程学院

2008级数据结构实验报告

实验名称： 实验三 树 学生姓名： 班 级： 班内序号： 学 号：

日 期： 20013年11月26日

1．实验要求

实验目的

通过选择下面两个题目之一进行实现，掌握如下内容： 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力 实验内容

利用二叉树结构实现赫夫曼编/解码器。 基本要求：

1. 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建

立赫夫曼树

2. 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输

出。

3. 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4. 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结

果。

5. 打印(Print)：以直观的方式打印赫夫曼树（选作）

6. 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

2. 程序分析

哈夫曼树结点的储存结构除了二叉树所有的双亲域parents，左子树域lchild，右子树域

四、综合设计（课程设计）摘要： 在这次课程设计中，所进行的实验是：哈夫曼编码和编译器。对哈夫曼树进行建立，由节点的权值建立最小二叉树，哈夫曼树haftree，并由所建立的哈夫曼树进行编码，求出各个节点的编码。在由所求的哈夫曼树，输入一段二进制电文，能够输出那所建立的哈夫曼树中的节点。建立的haftree用图形化表示出来。在整个代码实现中，窗体的实现，功能的完善，哈夫曼树的建立，哈夫曼树的编码，遇到了许多难题，haftree对象数组的分配空间，节点的属性等都比较困难。在整个过程中，用的是C#语言，包的应用，字符串数组的空间分配，在计算每个字符的权值时，用的是sizeOf()检索整个字符串，计算字符的权值，建立字符出现频度的表格，根据表格中每个字符频度建立起哈夫曼树。从根节点出发检索每个节点的左右孩子，如果是左孩子遍历左边，路径为0，然后左孩子为根节点；如果是右孩子，遍历右孩子，路径为1，然后右孩子为根节点。在重新上述方法，直到所有的节点都遍历完，每个节点的编码就确定后输出来。 在译码过程中，由所输入的二进制电文，根据所建立的哈夫曼树，如果是0走左边，如果是1，走右边，直到节点的左右孩子为空时，输出给节点的信息，在回到根节点重新遍历后面的二进制电

课程设计说明书 No 1

赫夫曼树的建立 1课程设计目的 (1)掌握算法的编写方法。 (2)掌握C语言的算法转换成C程序并上机调试的基本方法。 (3)根据建立好的函数输入二叉树，对其输入的字符出现的频率作为权值输出其相对应的赫夫曼树。 2设计方案论证 2.1 问题描述 2.1.1赫夫曼树的基本概念 相关概念：路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。路径长度：路径上面的分支个数。树的路径长度：从树根到每一个结点的路径长度之和。结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。 最优二叉树（哈夫曼树）：给定n个权值{w1,w2,…,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。按照结构体来存放树的结点的权值，双亲、左孩子、右孩子。通过建立赫夫曼树函数输入二叉树，并

数据结构课设

哈夫曼编译码器

学 号： 姓 名： 提交日期： 成 绩：

东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术

一、 实验名称

哈夫曼编/译码器的实现

二、 实验要求

【问题描述】

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。

【基本要求】

一个完整的系统应具有以下功能：

(1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

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

(4)P：打印代码文件(

实验报告

实验课名称：数据结构实验 实验名称：文件压缩问题 班级：20132012 学号： 姓名： 时间：2015-6-9 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 二、数据结构设计 首先定义一个结构体： struct head { unsigned char b; //记录字符 long count; //权重 int parent,lch,rch; //定义双亲，左孩子，右孩子 char bits[256]; //存放哈夫曼编码的数组 } header[512],tmp; //头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511 三、算法设计 输入要压缩的文件读文件并计算字符频率根据字符的频率，利用Huffman编码思想创建Huffman树由创建的Huffman树来决定字符对应的编