福 建 工 程 学 院

课程设计

课 程： 数据结构

题 目： 哈夫曼编码和译码

专 业： 信息管理信息系统

班 级： 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）对用户输入的字符进行编码

…… …… 余下全文

实验报告

一、实验目的

掌握哈夫曼树及其应用。

二、实验内容

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

三、实验步骤

（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{

…… …… 余下全文

《数据结构课程设计》实验报告

一、实验目的：

掌握赫夫曼编码的存储，理解赫夫曼树的算法。通过赫夫曼树的建立，完成赫夫曼编码的生成，并实现编码文件的译码。

二、内容与设计思想：（设计思想、主要数据结构、主要代码结构、主要代码段分析）

1、设计思想

输入一串电文字符：LINEARALGEBRAINTRODUCTIONOFCOMPUTERPASCALLANGUGEMTCROCOMPUTER,实现字符的赫夫曼编码，再对赫夫曼编码生成的字符串进行译码，输出电文字符串。

2、主要数据结构

1）赫夫曼树的存储结构定义：

#define n 100//叶子结点数

#define m 2*n-1//赫夫曼树中结点总数

typedef struct{

       int weight;//权值

       int lchild,rchild,parent;//左右孩子及双亲指针

}HTNode;//树中结点类型

typedef HTNode HuffmanTree[m+1];//零号单元不用

2）选择parent为0且权值最小的两个根结点的算法的定义：

void select(HuffmanTree T,int k,int &s1,int &s2)

{//在HT[1...k]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2，并靠引用参数带回主调函数

    int i,j;

    int minl=101;

    for(i=1;i<=k;i++) //找s1

        if(T[i].weight<minl && T[i].parent==0)

…… …… 余下全文

数据结构实验报告

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

学生姓名： 牛佳宁

班    级： 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;

…… …… 余下全文

数据结构作业报告

  ——哈夫曼编码实验报告

姓名：

班级：

学号：

摘要

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

内容

设计哈夫曼树的结构体（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.程序在运行中多次出现溢出，后发现是在生成哈夫曼树时没有将数组下标附初值。

…… …… 余下全文

实验报告与总结

一、实验目的

1、掌握哈夫曼编码原理；

2、熟练掌握哈夫曼树的生成方法；

    3、理解数据编码压缩和译码输出编码的实现。

二、实验要求

实现哈夫曼编码和译码的生成算法。

三、实验内容

先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。

五、实验原理

1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；

2、哈夫曼树的构造：

weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性，即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。

     通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。

六、实验流程

①　初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树；

②　根据符号概率的大小按由大到小顺序对符号进行排序；

③　把概率最小的两个符号组成一个节点；

④　重复步骤（2）（3），直到概率和为1；

…… …… 余下全文