哈夫曼编码译码数据结构课程设计样本.doc

数据构造课程设计

题目：哈夫曼编码译码
姓名：
专业：通信工程
学号：
指引教师：吴泽晖

目　录
目录…………………………………………………………1
一、需求分析………………………………………………2
二、设计规定………………………………………………2
三、概要设计………………………………………………2
1、流程图……………………………………………2
2、设计包括几种某些……………………………4
四、详细设计………………………………………………2
五、显示成果………………………………………………9.
六、心得体会………………………………………………10
七、参照文献………………………………………………11

哈夫曼编码译码
一、 需求分析
在当今信息爆炸时代，如何采用有效数据压缩技术节约数据文献存储空间和计算机网络传送时间已越来越引起人们注重，赫夫曼编码正是一种应用广泛且非常有效数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权途径长度最小二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊编码表将源字符（例如某文献中一种符号）进行编码。这张编码表特殊之处在于，它是依照每一种源字符浮现估算概率而建立起来（浮现概率高字符使用较短编码，反之浮现概率低则使用较长编码，这便使编码之后字符串平均盼望长度减少，从而达到无损压缩数据目）。赫夫曼编码应用很广泛，运用赫夫曼树求得用于通信二进制编码称为赫夫曼编码。树中从根到每个叶子均有一条途径，对途径上各分支商定：指向左子树分支表达“0”码，指向右子树分支表达“1”码，取每条途径上“0”或“1”序列作为和各个叶子相应字符编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。
二、设计规定
对输入一串电文字符实现赫夫曼编码，再对赫夫曼编码生成代码串进行译码，输出电文字符串。普通咱们把数据压缩过程称为编码，解压缩过程称为解码。电报通信是传递文字二进制码形式字符串。但在信息传递时，总但愿总长度能尽量短，即采用最短码。假设每种字符在电文中浮现次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此相应到二叉树上，Wi为叶结点权，Li为根结点到叶结点途径长度。那么，∑WiLi正好为二叉树上带权途径长度。因而 ，设计电文总长最短二进制前缀编码，就是以n种字符浮现频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现功能： (1) 赫夫曼树建立； (2) 赫夫曼编码生成； (3) 编码文献译码。
三、 概要设计
哈夫曼编\译码器重要功能是先建立哈夫曼树，然后运用建好哈夫曼树生成哈夫曼编码后进行译码 。
在数据通信中，经常需要将传送文字转换成由二进制字符0、1构成二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中左分之代表0，右分支代表1，则从根节点到每个叶子节点所通过途径分支构成0和1序列便为该节点相应字符编码，称之为哈夫曼编码。
最简朴二进制编码方式是等长编码。若采用不等长编码，让浮现频率高字符具备较短编码，让浮现频率低字符具备较长编码，这样也许缩短传送电文总长度。哈夫曼树课用于构造使电文编码总长最短编码方案。
（1）其重要流程图如图1-1所示。

开始
结点数与否不不大于1
将data和权值赋给ht
输出根结点和权值
调用SELECT函数
计算根结点函数
父结点为两子结点之和
输出两子结点和已构造结点
与否为根结点？
左子与否为空？
此时编码为0
I<2*N?
I++
编码为1
结束
否
否
否
右子与否为空
是
是
否
否
是
是
是

（2）设计包括几种方面：① 赫夫曼树建立
赫夫曼树建立由赫夫曼算法定义可知，初始森林中共有n棵只具有根结点二叉树。算法第二步是：将当前森林中两棵根结点权值最小二叉树，合并成一棵新二叉树；每合并一次，森林中就减少一棵树，产生一种新结点。显然要进行n－1次合并，因此共产生n－1个新结点，它们都是具备两个孩子分支结点。由此可知，最后求得赫夫曼树中一共有2n－1个结点，其中n个结点是初始森林n个孤立结点。并且赫夫曼树中没有度数为1分支结点。咱们可以运用一种大小为2n--1一维数组来存储赫夫曼树中结点。
② 赫夫曼编码
规定电文赫夫曼编码，必要先定义赫夫曼编码类型，依照设计规定和实际需要定义类型如下：
typedet struct {
char ch；// 存储编码字符
char bits[N＋1]；// 存储编码位串
int len；// 编码长度
}CodeNode；// 编码构造体类型
③ 代码文献译码
译码基本思想是：读文献中编码，并与原先生成赫夫曼编码表比较，遇到相等时，即取出其相应字符存入一种新串中。
四、 详细设计
（1）①赫夫曼树存储构造描述为：
#define N 50 // 叶子结点数
#define M 2*N-1 // 赫夫曼树中结点总数
typedef struct {
int weight；// 叶子结点权值
int lchild，rchild，parent；// 左右孩子及双亲指针
}HTNode；// 树中结点类型
typedef HTNode HuffmanTree[M+1]；
②哈弗曼树算法
void CreateHT(HTNode ht[],int n) //调用输入数组ht[],和节点数n
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=-1； //所有结点有关域置初值-1
for (i=n;i<2*n-1;i++) //构造哈夫曼树
{
min1=min2=32767； //int范畴是-32768—32767
lnode=rnode=-1； //lnode和rnode记录最小权值两个结点位置
for (k=0;k<=i-1;k++)
{
if (ht[k].parent==-1) //只在尚未构造二叉树结点中查找
{
if (ht[k].weight<min1) //若权值不大于最小左节点权值
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
}
ht[lnode].parent=i;ht[rnode].parent=i； //两个最小节点父节点是i
ht[i].weight=ht[lnode].weight+ht[rnode].weight； //两个最小节点父节点权值为两个最小节点权值之和
ht[i].lchild=lnode;ht[i].rchild=rnode； //父节点左节点和右节点
}
}
（2）哈弗曼编码
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++) //依照哈夫曼树求哈夫曼编码
{
hc.start=n;c=i;
f=ht[i].parent;
while (f!=-1) //循序直到树根结点结束循环
{
if (ht[f].lchild==c) //解决左孩子结点
hc.cd[hc.start--]='0';
else //解决右孩子结点
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++； //start指向哈夫曼编码hc.cd[]中最开始字符
hcd[i]=hc;
}
}

void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码列表
{
int i,k;
printf(" 输出哈夫曼编码:\n")；
for (i=0;i<n;i++) //输出data中所有数据，即A-Z
{
printf(" %c:\t",ht[i].data)；
for (k=hcd[i].start;k<=n;k++) //输出所有data中数据编码
{
printf("%c",hcd[i].cd[k])；
}
printf("\n");
}
}

void editHCode(HTNode ht[],HCode hcd[],int n) //编码函数
{
char string[MAXSIZE]；
int i,j,k;
scanf("%s",string)； //把要进行编码字符串存入string数组中
printf("\n输出编码成果:\n");
for (i=0;string[i]!='#';i++) //#为终结标志
{
for (j=0;j<n;j++)
{
if(string[i]==ht[j].data) //循环查找与输入字符相似编号，相似就输出这个字符编码
{
for (k=hcd[j].start;k<=n;k++)
{
printf("%c",hcd[j].cd[k]);
}
break； //输出完毕后跳出当前for循环
}
}
}
}
（3）哈弗曼译码
void deHCode(HTNode ht[],HCode hcd[],int n) //译码函数
{
char code[MAXSIZE];
int i,j,l,k,m,x;
scanf("%s",code)； //把要进行译码字符串存入code数组中
while(code[0]!='#')
for (i=0;i<n;i++)
{
m=0； //m为想同编码个数计数器
for (k=hcd[i].start,j=0;k<=n;k++,j++) //j为记录所存储这个字符编码个数
{
if(code[j]==hcd[i].cd[k]) //当有相似编码时m值加1
m++;
}
if(m==j) //当输入字符串与所存储编码字符串个数相等时则输出这个data数据
{
printf("%c",ht[i].data);
for(x=0;code[x-1]!='#';x++) //把已经使用过code数组里字符串删除
{
code[x]=code[x+j];
}
}
}
}
（4）主函数
void main()
{
int n=26,i;
char orz,back,flag=1;
char str[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}； //初始化
int fnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16}； //初始化
HTNode ht[M]； //建立构造体
HCode hcd[N]； //建立构造体
for (i=0;i<n;i++) //把初始化数据存入ht构造体中
{
ht[i].data=str[i];
ht[i].weight=fnum[i];
}
while (flag) //菜单函数，当flag为0时跳出循环
（5）显示某些源程序：
{
printf("\n");
printf(" ********************************");
printf("\n ** 1---------------显示编码 **");
printf("\n ** 2---------------进行编码 **");
printf("\n ** 3---------------进行译码 **");
printf("\n ** 4---------------退出 **\n");
printf(" * **********************************");
printf("\n");
printf(" 请输入选取编号:");
scanf("%c",&orz);
switch(orz)
{
case 'a':
case 'A':
system("cls")； //清屏函数
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'b':
case 'B':
system("cls");
printf("请输入要进行编码字符串(以#结束):\n");
editHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'c':
case 'C':
system("cls");
DispHCode(ht,hcd,n);
printf("请输入编码(以#结束):\n");
deHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'd':
case 'D':
flag=0;
break;
default:
system("cls");
}}}
五、调试成果
进入主菜单

选A时显示成果

选取B时显示成果

选C时显示成果

六、心得体会
通过这次课程设计，让我对一种程序数据构造有更全面更进一步结识，依照不同需求，采用不同数据存储方式，不一定要用栈，二叉树等高档类型，有时用基本一维数组，只要运用得当，也能达到相似效果，甚至更佳，就如这次课程设计，通过用for多重循环，舍弃多余循环，提高了程序运营效率。在编写这个程序过程中，我复习了之前学基本语法，哈弗曼树最小途径求取，哈弗曼编码及译码应用范畴，程序构造算法等一系列问题它使我对数据构造变化了看法。在这次设计过程中，体现出自己单独设计模具能力以及综合运用知识能力，体会了学以致用、突出自己劳动成果喜悦心情，也从中发现自己平时学习局限性和薄弱环节，从而加以弥补。
七、参照文献
[1] 徐孝凯编著，《数据构造课程实验》，清华大学出版 第一版
[2] 张乃笑编著，《数据构造与算法》，电子工业出版社 10月
[3] 严蔚敏 《数据构造》（C语言版） 清华大学出版社
附录：
源程序如下：
#include <stdio.h>
#include <stdlib.h> //要用system函数要调用头文献
#include<conio.h> //用getch()要调用头文献
#include <string.h>
#define N 50 //义用N表达50叶节点数
#define M 2*N-1 //用M表达节点总数 当叶节点数位n时总节点数为2n-1
#define MAXSIZE 100

typedef struct
{
char data； //结点值
int weight； //权值
int parent； //双亲结点
int lchild； //左孩子结点
int rchild； //右孩子结点
}HTNode；

typedef struct
{
char cd[N]； //存储哈夫曼码
int start； //从start开始读cd中哈夫曼码
}HCode;

void CreateHT(HTNode ht[],int n) //调用输入数组ht[],和节点数n
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=-1； //所有结点有关域置初值-1
for (i=n;i<2*n-1;i++) //构造哈夫曼树
{
min1=min2=32767； //int范畴是-32768—32767
lnode=rnode=-1； //lnode和rnode记录最小权值两个结点位置
for (k=0;k<=i-1;k++)
{
if (ht[k].parent==-1) //只在尚未构造二叉树结点中查找
{
if (ht[k].weight<min1) //若权值不大于最小左节点权值
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
}
ht[lnode].parent=i;ht[rnode].parent=i； //两个最小节点父节点是i
ht[i].weight=ht[lnode].weight+ht[rnode].weight； //两个最小节点父节点权值为两个最小节点权值之和
ht[i].lchild=lnode;ht[i].rchild=rnode； //父节点左节点和右节点
}
}

void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++) //依照哈夫曼树求哈夫曼编码
{
hc.start=n;c=i;
f=ht[i].parent;
while (f!=-1) //循序直到树根结点结束循环
{
if (ht[f].lchild==c) //解决左孩子结点
hc.cd[hc.start--]='0';
else //解决右孩子结点
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++； //start指向哈夫曼编码hc.cd[]中最开始字符
hcd[i]=hc;
}
}

void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码列表
{
int i,k;
printf(" 输出哈夫曼编码:\n")；
for (i=0;i<n;i++) //输出data中所有数据，即A-Z
{
printf(" %c:\t",ht[i].data)；
for (k=hcd[i].start;k<=n;k++) //输出所有data中数据编码
{
printf("%c",hcd[i].cd[k])；
}
printf("\n");
}
}

void editHCode(HTNode ht[],HCode hcd[],int n) //编码函数
{
char string[MAXSIZE]；
int i,j,k;
scanf("%s",string)； //把要进行编码字符串存入string数组中
printf("\n输出编码成果:\n");
for (i=0;string[i]!='#';i++) //#为终结标志
{
for (j=0;j<n;j++)
{
if(string[i]==ht[j].data) //循环查找与输入字符相似编号，相似就输出这个字符编码
{
for (k=hcd[j].start;k<=n;k++)
{
printf("%c",hcd[j].cd[k]);
}
break； //输出完毕后跳出当前for循环
}
}
}
}

void deHCode(HTNode ht[],HCode hcd[],int n) //译码函数
{
char code[MAXSIZE];
int i,j,l,k,m,x;
scanf("%s",code)； //把要进行译码字符串存入code数组中
while(code[0]!='#')
for (i=0;i<n;i++)
{
m=0； //m为想同编码个数计数器
for (k=hcd[i].start,j=0;k<=n;k++,j++) //j为记录所存储这个字符编码个数
{
if(code[j]==hcd[i].cd[k]) //当有相似编码时m值加1
m++;
}
if(m==j) //当输入字符串与所存储编码字符串个数相等时则输出这个data数据
{
printf("%c",ht[i].data);
for(x=0;code[x-1]!='#';x++) //把已经使用过code数组里字符串删除
{
code[x]=code[x+j];
}
}
}
}

void main()
{
int n=26,i;
char orz,back,flag=1;
char str[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}； //初始化
int fnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16}； //初始化
HTNode ht[M]； //建立构造体
HCode hcd[N]； //建立构造体
for (i=0;i<n;i++) //把初始化数据存入ht构造体中
{
ht[i].data=str[i];
ht[i].weight=fnum[i];
}
while (flag) //菜单函数，当flag为0时跳出循环
{
printf("\n");
printf(" **************************************");
printf("\n ** A---------------显示编码 **");
printf("\n ** B---------------进行编码 **");
printf("\n ** C---------------进行译码 **");
printf("\n ** D---------------退出 **\n");
printf(" ****************************************");
printf("\n");
printf(" 请输入选取编号:");
scanf("%c",&orz);
switch(orz)
{
case 'a':
case 'A':
system("cls")； //清屏函数
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'b':
case 'B':
system("cls");
printf("请输入要进行编码字符串(以#结束):\n");
editHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'c':
case 'C':
system("cls");
DispHCode(ht,hcd,n);
printf("请输入编码(以#结束):\n");
deHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case 'd':
case 'D':
flag=0;
break;
default:
system("cls");
}
}
}