福 建 工 程 学 院

课程设计

课 程： 数据结构

题 目： 哈夫曼编码和译码

专 业： 信息管理信息系统

班 级： 1002班

座 号： 15号

* ** ***

20XX年 6月 27日

实验题目：哈夫曼编码和译码

一、要解决的问题

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

二、算法基本思想描述：

根据给定的字符和其中每个字符的频度,构造哈夫馒树,并输出字符集中每个字符的哈夫曼编码.将给定的字符串根据其哈夫曼编码进行编码,并进行相应的译码.

三、设计

1. 数据结构的设计

（1）哈夫曼树的表示

设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（htnode）定义个哈夫曼数组（hfmt[]）。

迷宫定义如下：

typedef struct

{

int weight;

int lchild;

int rchild;

int parent;

char key;

}htnode;

typedef htnode hfmt[MAXLEN];

（2）对原始字符进行编码

初始化哈夫曼树（inithfmt）。

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

并显示出每个字符的编码。

1.void inithfmt(hfmt t)//对结构体进行初始化

2.void inputweight(hfmt t)//输入函数

3.void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数

4.void creathfmt(hfmt t)//创建哈夫曼树的函数

5.void phfmnode(hfmt t)//对字符进行初始编码

（3）对用户输入的字符进行编码

…… …… 余下全文

数据结构作业报告

  ——哈夫曼编码实验报告

姓名：

班级：

学号：

摘要

本程序能执行让一段字符以哈夫曼编码的形式被转存，或将一段哈夫曼编码翻译成字符，通过字符的频率统计，哈夫曼树的建立，递归求字符的哈夫曼编码完成，这个程序让我熟悉哈夫曼编码的全过程。

内容

设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（htnode）定义一个哈夫曼数组（hfmt[]）。使用循环过程，每次选择两个权值最小、且没有父母的节点，将其权值相加建立新的节点放置在哈夫曼数组的最末尾。循环直至数组中仅有一个节点没有父母时结束，至此哈夫曼树建立。

从哈夫曼编码中存储某一字符的单元开始，不断寻找它的父母节点，并判断上一节点是其父母节点的左孩子还是右孩子。左孩子记录为“0”，右孩子记录为“1”，直至找到哈夫曼树的根节点为止。从根节点开始，读取哈夫曼编码的每一位，“0”则寻找节点的左孩子，“1”则寻找节点的右孩子。直至节点没有孩子为止，此时读取该节点所存储的字符即可。

变量说明：

void inithfmt(hfmt t)对结构体进行初始化

void inputweight(hfmt t)输入函数

void selectmin(hfmt t,int i,int *p1,int *p2)选中两个权值最小的函数

void creathfmt(hfmt t)创建哈夫曼树的函数

void phfmnode(hfmt t)对字符进行初始编码

void huffpath 递归求哈夫曼编码

程序执行结果

第一次运行结果：

第二次运行结果：

第三次运行结果：

结论

本程序思路基本正确，运行结果合法的，可以满足哈夫曼编码的转存和翻译。

编程中遇到的问题以及解决方法

1.程序在运行中多次出现溢出，后发现是在生成哈夫曼树时没有将数组下标附初值。

…… …… 余下全文

          

                      姓    名：   刘阳

             班    级： 信息0703

             学    号：0903070312

             实验时间： 08.11.14

             指导老师：   赵颖

目  录

一、实验内容……………………………………………………………2

二、实验说明……………………………………………………………2

三、结构体定义和程序结构的说明……………………………………3

1.结构体定义的说明………………………………………………3

2.程序结构的说明…………………………………………………3

四、程序设计的基本思想、部分源代码及注释………………………3

…… …… 余下全文

数据结构实验报告

实验名称： 实验三——哈夫曼编码

学生姓名： 牛佳宁

班    级： 2010211107

班内序号： 27

学    号： 10210213

日    期： 20##年12月10日

1．实验要求

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

1、读入一串字符，统计字符个数及权值。

2、建立哈夫曼树。

3、根据哈夫曼树建立哈夫曼表。

4、将字符串进行编码。

5、输入一串01数，进行解码。　 

2. 程序分析

2.1 存储结构

哈夫曼树为正则二叉树，有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的数组来储存哈夫曼树的各个结点，如图

对应的编码表可用如图所示结构

2.2 关键算法分析

一、创建哈夫曼树

1、根据权值初始化哈夫曼树

     for(int i=0;i<n;i++)

              {

               HTree[i].weight=a[i];

               HTree[i].LChild=-1;

               HTree[i].RChild=-1;

…… …… 余下全文

实验报告

一、实验目的

掌握哈夫曼树及其应用。

二、实验内容

利用哈夫曼算法，构造最优二叉树，然后对构造好的二叉树的叶子结点进行前缀编码。

三、实验步骤

（1）审清题意，分析并理出解决问题的基本思路。（2） 根据基本思路，设计好程序的算法。 （3）根据算法编写源程序。（4） 在计算机上编译程序，检验程序的可运行性

数据结构设计：

// 赫夫曼树和赫夫曼编码的存储结构

 typedef struct // 结点的结构，在教科书第147页

 { unsigned int weight; // 结点的权值

   unsigned int parent,lchild,rchild;

 }HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树

 typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) // 算法6.12

 { // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC

   int start;

   unsigned f;

 // 以下是从叶子到根逆向求每个字符的赫夫曼编码

 int m,i,s1,s2;

   unsigned c;

   HuffmanTree p;

   char *cd;

   if(n<=1) // 叶子结点数不大于n

     return;

…… …… 余下全文

数

据

结

构

实

验

       

班级:软件C092

姓名:孙琼芳

学号:098586

一．实验目的

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

源程序

#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;

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

HuffmanTree HT;

HuffmanCode HC;

int w[50],i,j,n;

char z[50];

int flag=0;

 int numb=0

// -----------------求哈夫曼编码-----------------------

  struct  cou{

…… …… 余下全文

数据结构实验报告

实验名称： 实验3——树（哈夫曼编/解码器）

学生姓名：

班    级：

班内序号：

学    号：

日    期： 20##年12月5日

1．          实验要求

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

基本要求：

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

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

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

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

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

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

并用I love data Structure, I love Computer。I will try my best to study data Structure.进行测试。

2. 程序分析

哈夫曼树结点的存储结构包括双亲域parent，左子树lchild，右子树rchild，还有字符word，权重weight，编码code

对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。统计每个字符出现的次数作为叶子的权重，统计次数可以根据每个字符不同的ASCII码，根据叶子结点的权重建立一个哈夫曼树。

…… …… 余下全文