数据结构哈夫曼编码课程设计报告
《数据结构》 课程设计报告
题目:哈夫曼编码的实现
专业:软件工程
班级:软件0901
学号:091203111
姓名:管 向 华
任课教师:殷 新 春
2010 年 12 月 26 日
目 录
一.问题描述
二.需求分析
三.概要设计
四.详细设计
五.测试数据和测试结果
六.设计与调试分析
七.课程设计小结
八.用户手册
九.附录
一.问题描述 哈夫曼编码译码的实现,首要的是根据给定的n个权值构造哈夫曼树。通过遍历此二叉树完成哈夫曼编码。
哈夫曼树从根到每个叶子都有一条路径,对路径上的各分支约定指向左子树根的分支编码为“0”,指向右子树根的分支编码为“1”,从根到每个叶子相应路径上的“0”和“ 1”组成的序列就是这个叶子(字符)的编码。
二.需求分析
1.利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。是为这样的信息收发站写一个哈夫曼的编/译码系统。
2.大量的图像信息数据会给存储器的存储容量,通信干线信道的带宽,以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量,提高信道带宽以及计算机的处理速度等硬件方法来解决这个问题是不现实的,这时就要考虑软件压缩方法。压缩的关键字在于编码,如果在对数据进行编码时,对于常见的数据,编码器输出较短的码字,而对于少见的数据则用较长的码字表示,就能够实现数据压缩。
3.测试数据(附后)。
三.概要设计
1.抽象数据类型树定义如下:
ADT Tree {
数据对象 D:D是具有相同特性的数据元素的集合。
数据关系 R:若D为空集,则称为空树;
若D仅含一个数据元素,则R为空集,否则R={H},H是如下二元关系:
(1) 在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;
(2) 若D-{root}≠Φ,则存在D-{root}的一个划分D1,D2,„,Dm(m>0),对任意
j≠k(1≤j, k≤m)有Dj∩Dk=Φ,且对任意的i(1≤i≤m),惟一存在数据元素 xi∈Di,有∈H;
(3) 对应于D-{root}的划分,H-{,„,}有唯一的一个划分H1,H2,„,Hm(m>0),对任意j≠k(1≤j, k≤m)有Hj∩Hk=Φ,且对任意i(1≤i
≤m),Hi是Di上的二元关系,(Di,{Hi})是一棵符合本定义的树,称为根root
的子数。
基本操作P:
InitTree(&T);
操作结果:构造空树T。
DestroyTree(&T);
初始条件:树T存在。
操作结果:销毁树T。
CreateTree(&T,definition);
初始条件:definition给出树T的定义。
操作结果:按definition构造数。
ClearTree(&T);
初始条件:树T存在。
操作结果:将树T清为空树。
TreeEmpty(T);
初始条件:树T存在。
操作结果:若T为空树,则返回TRUE,否则FALSE。
TreeDepth(T);
初始条件:树T存在。
操作结果:返回T的深度。
Root(T);
初始条件:树T存在。
操作结果:返回T的根。
Value(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:返回cur_e的值。
Assign(T,cur_e,value);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:结点为cur_e赋值为value。
Parent(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e是T的非根结点,则返回它的双亲,否则函数值为“空” LeftChild(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e是T的非子叶结点,则返回它的最左孩子,否则返回
“空”。
RightSibling(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e有右兄弟,则返回它的右兄弟,否则函数值为“空”。
InsertChild(&T,&p,i,c);
初始条件:树T存在,p是指向T中某个结点,1≤i≤p所指结点的度+1,
非空树c与T不相交。
操作结果:插入c为T中p指结点的第i棵子树。
DeleteChild(&T,&p,i);
初始条件:树T存在,p是指向T中某个结点,1≤i≤p指结点的度。 操作结果:删除T中p所指向的第i棵子树。
TraverseTree(T,Visit());
初始条件:树T存在,Visit是对结点操作的应用函数。
操作结果:按某种次序对T的每个结点调用函数visit()一次且至多一次。一
旦visit()失败,则操作失败。
}ADT Tree
2.主程序
void main()
{
进入界面;
选择需要的操作;
输入叶节点个数;
输入结点与对应的权值;
输出叶节点对应的编码;
}
3.本程序有四个模块,调用关系如图:
主程序模块
初始化模块 输出哈夫曼编码模块 构造哈夫曼树模块
四.详细设计
哈夫曼树结点的存储结构:
typedef struct
{
int data; //结点值
int Weight; //权值
int Flag; //标识是否待构节点,是的话用0表示,否则1表示
int Parent; //父节点
int LChild; //左节点
int RChild; //右节点
}hnodetype;
/****-----------------------------------------------------------------------------*****/
//函数名:InitHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
//参数: (传入)hnodetype HuffNode[] 哈夫曼树结点
// (传入)hcodetype HuffCode[] 哈夫曼树编码树结点
// (传入)Int n 结点数量
//功能: 哈夫曼结点初始化
/****-----------------------------------------------------------------------------*****/
void InitHaffman(hnodetype HuffNode[],int n)
{
int i;
//把生成的节点初始化,把指向父亲的指针,左孩子、右孩子的指针都先置空
for(i=0;i
{
HuffNode[i].Weight=0;
HuffNode[i].Parent=0;
HuffNode[i].Flag=0;
HuffNode[i].LChild=-1;
HuffNode[i].RChild=-1;
}
for(i=0;i
{
getchar();
printf("输入第%d个叶结点值:",i+1);
scanf("%c",&HuffNode[i].data);
printf("输入对应结点权值:");
scanf("%d",&HuffNode[i].Weight);
}
}
/****-------------------------------------------------------------------------------*****/
//函数名:OutputHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
//参数: (传入)hnodetype HuffNode[] 哈夫曼树结点
// (传入)hcodetype HuffCode[] 哈夫曼树编码树结点
// (传入)Int n 结点数量
//功能: 输出哈夫曼编码
/****------------------------------------------------------------------------------*****/
void OutputHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
{
int i,j;
printf("%d个叶结点对应编码为:\n",n);
for(i=0;i
{
printf("%c----",HuffNode[i].data);
for(j=HuffCode[i].Start+1;j
printf("%d",HuffCode[i].Bit[j]);
printf("\n");
}
}
/****-------------------------------------------------------------------------------*****/
//函数名:Haffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
//参数: (传入)hnodetype HuffNode[] 哈夫曼树结点
// (传入)hcodetype HuffCode[] 哈夫曼树编码树结点
// (传入)Int n 结点数量
//功能: 构造哈夫曼树,根据树生成哈夫曼编码
/****------------------------------------------------------------------------------*****/
void Haffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
{
int i,j,m1,m2,x1,x2,c,p;
hcodetype cd;
for(i=0;i
{
//根据哈夫曼树的构造过程,始终选择最小权值的两个节点构成一棵二叉树
m1=m2=MAXVALUE;
//x1和x2为最小权重的两个结点位置
x1=x2=0;
//循环从fla为0的节点中找到一个,供下面取最小值
for(j=0;j
{
if(HuffNode[j].Weight
{
m2=m1;
x2=x1;
m1=HuffNode[j].Weight;
x1=j; //记下x1的地址
}
else if(HuffNode[j].Weight
{ m2=HuffNode[j].Weight;
x2=j; //记下x2的地址
}
}
五.测试数据和测试结果
测试数据:
哈夫曼树的6个结点为a、b、c、d、g、,其权值分别为3,9,12,3,2,71。 测试结果:
输入叶结点个数n:
6
输入第1个叶结点值:a
输入对应结点权值:3
输入第2个叶结点值:b
输入对应结点权值:9
输入第3个叶结点值:c
输入对应结点权值:12
输入第4个叶结点值:d
输入对应结点权值:3
输入第5个叶结点值:e
输入对应结点权值:2
输入第6个叶结点值:f
输入对应结点权值:71
6个叶结点对应编码为:
a-----01011
b-----011
c-----00
d-----0100
e-----01010
f-----1
六.设计与调试分析
设计与分析:
(1)将给定的n个权值{W1,W2,„„,Wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,„„,Tn},其中每棵二叉树只有一个根结点;
(2)在森林中选取两棵根结点权值最小的二叉树作为左右子树,构造一棵新二叉树,新二叉树的根结点权值为这两棵树根的权值之和;
(3)在森林中,将上面选择的这两棵根权值最小的二叉树从森林中删除,并将刚刚新构造的二叉树加入到森林中;
(4)重复上面(2)和(3)的操作,直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。
七.课程设计小结
本次程序设计使我不仅深化理解了教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且在总体分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到了综合训练。
本次实验我选择Huffman编译码器的课题。帮助我深入研究树的各种存储结构的特性及其应用。由于课程设计着眼于原理与应用的结合,使我学会把书本上和课堂上学到的知识用于解决实际问题,从而培养了一部分计算机软件工作所需要的动手能力。
我通过对Huffman编译码原理的学习,再通过分析、设计、编码、调试等各环节,实现了Huffman编译码器的数据实现和界面实现。在Huffman编译码器数据结构的算法设计中我同时用到了多种技术和方法,如算法设计的构思方法,算法的编码,递归技术,与二叉树和树相关的技术等。从而帮助我深入学习研究了树的各种存储结构的特性及其应用。。
此次课程设计并没有划定具体题目,包括算法需求都由我们度量,思路开阔。我始终和同学探讨并独立研究新的功能的实现。通过尝试来学习,通过实践去理解。
要对自己有信心,出错是必然的。“屡战屡败,屡败屡战”,不怕受挫的心理承受能力和从零开始的决心是走向成功的必要条件。
学会与别人学习讨论,但不依赖别人,可以通过借鉴思路从而创新,但决不照搬别人的东西。
八.用户手册
1.本程序在win_tc环境下运行。进入win-tc系统,点击菜单栏的超级工具集的中文DOS
环境运行。
2.进入程序后,会看到如下界面:
******欢迎进入哈夫曼编译码器******
******1.进行编译 ******
******2.退出系统 ******
**********************************
请选择操作:
此时,你可以选择操作1,即进行哈夫曼编译,输入数据,得出结果。
九.附录
源程序文件名清单:
#include
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE 59
#define MAXBIT 10
typedef struct
{
int data; //结点值
int Weight; //权值
int Flag; //标识是否待构节点,是的话用0表示,否则1表示
int Parent; //父节点
int LChild; //左节点
int RChild; //右节点
}hnodetype;
/****-----------------------------------------------------------------------------*****/
//函数名:InitHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
//参数: (传入)hnodetype HuffNode[] 哈夫曼树结点
// (传入)hcodetype HuffCode[] 哈夫曼树编码树结点
// (传入)Int n 结点数量
//功能: 哈夫曼结点初始化
/****-----------------------------------------------------------------------------*****/
void InitHaffman(hnodetype HuffNode[],int n)
{
int i;
//把生成的节点初始化,把指向父亲的指针,左孩子、右孩子的指针都先置空 for(i=0;i
{
HuffNode[i].Weight=0;
HuffNode[i].Parent=0;
HuffNode[i].Flag=0;
HuffNode[i].LChild=-1;
HuffNode[i].RChild=-1;
}
for(i=0;i
{
getchar();
printf("输入第%d个叶结点值:",i+1);
scanf("%c",&HuffNode[i].data);
printf("输入对应结点权值:");
scanf("%d",&HuffNode[i].Weight);
}
}
/****-------------------------------------------------------------------------------*****/
//函数名:OutputHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
//参数: (传入)hnodetype HuffNode[] 哈夫曼树结点
// (传入)hcodetype HuffCode[] 哈夫曼树编码树结点
// (传入)Int n 结点数量
//功能: 输出哈夫曼编码
/****------------------------------------------------------------------------------*****/
void OutputHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
{
int i,j;
printf("%d个叶结点对应编码为:\n",n);
for(i=0;i
{
printf("%c----",HuffNode[i].data);
for(j=HuffCode[i].Start+1;j
printf("%d",HuffCode[i].Bit[j]);
printf("\n");
}
}
/****-------------------------------------------------------------------------------*****/
//函数名:Haffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
//参数: (传入)hnodetype HuffNode[] 哈夫曼树结点
// (传入)hcodetype HuffCode[] 哈夫曼树编码树结点
// (传入)Int n 结点数量
//功能: 构造哈夫曼树,根据树生成哈夫曼编码
/****------------------------------------------------------------------------------*****/
void Haffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
{
int i,j,m1,m2,x1,x2,c,p;
hcodetype cd;
for(i=0;i
{
//根据哈夫曼树的构造过程,始终选择最小权值的两个节点构成一棵二叉树 m1=m2=MAXVALUE;
//x1和x2为最小权重的两个结点位置
x1=x2=0;
//循环从fla为0的节点中找到一个,供下面取最小值
for(j=0;j
{
if(HuffNode[j].Weight
{
m2=m1;
x2=x1;
m1=HuffNode[j].Weight;
x1=j; //记下x1的地址
}
else if(HuffNode[j].Weight
{ m2=HuffNode[j].Weight;
x2=j; //记下x2的地址
}
}
//把找到的两个节点按照哈夫曼树的规则构建一个二叉树,x1为左孩子,x2为右孩子 HuffNode[x1].Parent=n+i;
HuffNode[x2].Parent=n+i;
HuffNode[x1].Flag=1; //将x1的下标置1
HuffNode[x2].Flag=1; //将x2的下标置1
HuffNode[n+i].Weight=HuffNode[x1].Weight+HuffNode[x2].Weight;
HuffNode[n+i].LChild=x1;
HuffNode[n+i].RChild=x2;
}
for(i=0;i
{
cd.Start=n-1;
c=i;
p=HuffNode[c].Parent;
while(p!=0) //当父节点不为根节点的时候,逆序往上找 {
//如果当前是左孩子,则编码为0
if(HuffNode[p].LChild==c)cd.Bit[cd.Start]=0;
//当前是右孩子的话编码为1
else cd.Bit[cd.Start]=1;
cd.Start--;
c=p;
p=HuffNode[c].Parent;
}
for(j=cd.Start+1;j
{
HuffCode[i].Bit[j]=cd.Bit[j];
HuffCode[i].Start=cd.Start;
}
}
}
void main()
{
hnodetype HuffNode[MAXNODE];
hcodetype HuffCode[MAXLEAF];
int n;
int c;
printf("**********************************\n");
printf(" \n");
printf(" \n");
printf(" \n");
printf("******欢迎进入哈夫曼编译码器******\n");
printf(" \n");
printf("******1.进行编译 ******\n");
printf(" \n");
printf("******2.退出系统 ******\n");
printf("**********************************\n");
printf("请选择操作:");
scanf("%d",&c);
if(c2)
c=0;
switch(c)
{case 0: printf("输入错误!\n");break;
case 1:
printf("输入叶结点个数n:\n");
scanf("%d",&n);
InitHaffman(HuffNode,n);
Haffman(HuffNode,HuffCode,n);
OutputHaffman(HuffNode,HuffCode,n); break; case 2:exit (0); break;
}
getch();
}
参考文献:
数据结构(C语言版)
数据结构题集(C语言版)
数据结构实验教程
严蔚敏 吴伟民 编著 严蔚敏 吴伟民 米 宁高晓兵 张凤琴 高晓军 万 能 编著
编著