20##级数据结构实验报告

实验名称： 实验3——哈夫曼树

学生姓名： 陈家斌

班    级： 2009211121

班内序号： 16

学    号： 09210619

日    期： 20##年12月3日

1．实验要求

【实验目的】

通过选择下面两个题目之一进行实现，掌握如下内容：

Ø  掌握二叉树基本操作的实现方法

Ø  了解赫夫曼树的思想和相关概念

Ø  学习使用二叉树解决实际问题的能力

【题目】

利用二叉树结构实现赫夫曼编/解码器。

【基本要求】

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

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

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

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

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

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

【测试数据】

   I love data Structure, I love Computer。I will try my best to study data Structure.

提示：

    1、用户界面可以设计为“菜单”方式：能够进行交互。

    2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的

…… …… 余下全文

一、    需求分析

1、 本演示程序实现Haffman编/译码器的作用， 目的是为信息收发站提供一个编/译系统，从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：① 对需要传送的数据预先编码；② 对从接收端接收的数据进行译码；

2、 本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树；

3、 本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果；

4、 本演示程序将综合使用C++和C语言；

5、 测试数据：

(1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，可将其的权值看为5，29，7，8，14，23，3，11

(2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.

一、   概要设计

1、 设定哈夫曼树的抽象数据类型定义

ADT Huffmantree{

数据对象：D={a_i| a_i ∈Charset,i=1,2,3,……n,n≥0}

数据关系：R1＝{< a_i-1, a_i >| a_i-1, a_i ∈D, i=2,3,……n}
　　基本操作：
　　 Initialization(&HT，&HC,w，n,ch)

…… …… 余下全文

20##级数据结构实验报告

实验名称： 实验三——树

学生姓名： 王璇

班    级： 2009211118

班内序号： 29

学    号： 09210543

日    期： 20##年12月20日

1．实验要求

利用二叉树结构实现哈夫曼编/解码器

基本要求如下:

初始化:能够对输入的任意长度的字符串s进行统计,统计每个字符的频率,并建立哈夫曼树.

建立编码表:利用已经建好的哈夫曼树进行编码,并将每个字符的编码输出.

编码: 根据编码表对输入的字符串进行编码,并将编码后的字符串输出.

编码:利用已经建好的哈夫曼树对编码后的字符串进行译码,并输出译码结果.

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

2. 程序分析

哈夫曼树类里的成员函数声明如下：

class Huffman

{

private:

       HNode *HTree;//哈夫曼树

       HCode *HCodeTable;//哈夫曼编码表

       int num;

       char aftercode[1000];

       int countcode;

public:

       void CreateHTree(int a[],int n);//创建哈夫曼树

…… …… 余下全文

哈夫曼编码器实验报告

学院：计算机学院

班级：计科0801班

姓名：***

学号：***

一．实验目的

练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码

二．实验环境

Microsoft visual c++

三、问题描述

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

四、需求分析

（1）初始化;从终端输入字符集的大小n，以及n个字符和n个权值建立哈夫曼树。

（2）输出哈夫曼树，及各字符对应的编码。

（3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。

（4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。

五、概要设计

#include ＜iostream.h＞

#include ＜iomanip.h＞

#include ＜string.h＞

#include ＜malloc.h＞

#include ＜stdio.h＞

//typedef int TElemType;

const int UINT_MAX=1000;

char str[50];

typedef struct

{

int weight,K;

int parent,lchild,rchild;

}HTNode,* HuffmanTree;

typedef char **HuffmanCode;

//-----------全局变量-----------------------

…… …… 余下全文

数据结构实验报告

                 实验名称：实验三哈夫曼树

                 学生姓名：

                 班    级：

                 班内序号：

                 学    号：

                 日    期：

程序分析：

2.1 存储结构：二叉树

2.2 程序流程：

template <class T>

class BiTree

{

public:

          BiTree();             //构造函数，其前序序列由键盘输入

…… …… 余下全文

数据结构课内实验报告

哈夫曼树

专业：计算机信息工程学院

班级：物联网

姓名： 25678899

学号： 23458900

指导老师：张红

“哈夫曼树”实验报告

一、实验目的：

（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

二、实验内容：

a.随机生成数据并统计

b.创建哈夫曼树;

c.哈夫曼编码

d.哈夫曼译码；

三、概要设计

1、创建哈夫曼树的描述：

数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放；

算法思想：1.先把三叉链表中1-N个元素进行初始化，存放叶子节

点，他们都没有孩子和双亲。2.再初始化后n-1个非叶子节点元素。3.

从当前森林中（在森林中树的根节点的双亲为0）选择两棵根的权值最

小的树；删除合并是将选到的两棵树的根权和存入数组当前最前面的空

闲元素中，并置入相应的双亲与孩子的位置。4.重复上述步骤直到森林

中只含有一棵二叉树为止；

2、哈夫曼树编码的描述：

数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放； 算法思想：1.申请存储哈夫曼编码串的头指针数组，申请一个字符型指针，用来存放临时的编码串；2.从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中；3.重复上述步骤，直到所有的叶子节点都被编码完；

哈夫曼树译码的描述：

数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放； 算法思想：1.从根结点开始向下递推，若其编码当前的数值为0，则到该节点的左孩子，否则转到其右孩子；重复上述步骤直到该编码中全部访问完，则树中对应的叶子节点则为所求2.依据上述步骤，对编码数组

…… …… 余下全文

哈夫曼树及其应用实验报告

   实验 四    哈夫曼树及其的应用

 一、实验目的

1．在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。

2.掌握构造哈夫曼树以及哈夫曼编码的方法。

3、熟练掌握哈夫曼树（最优二叉树）特征及其应用

二、实验内容

题目一、哈夫曼树和哈夫曼编码：

从终端输入若干个字符，统计（或指定）字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。 

设计要求：

⑴ 哈夫曼殊和哈夫曼编码的存储表示参考教材事例

⑵ 在程序中构造四个子程序为

① int freqchar(char *text, HTree *t)   /*统计字符出现的频率*/

② int createhtree(HTree *t) /*根据字符出现的频率建立哈夫曼树*/

③ void coding(HTree *t,int head_i,char *code)

/*对哈夫曼树进行编码*/

④ void printhtree(HTree *t,int head_i,int deep,int* path)

/*中序打印树*

三、实验步骤

㈠、数据结构与核心算法的设计描述

struct frequence//统计频率

{

    char a;

    int n;

}

typedef struct

{

    unsigned int weight;// 用来存放各个结点的权值

    unsigned int parent,lchild,rchild;//指向双亲、 孩子结点的指针

…… …… 余下全文