西安工业大学数据结构课程设计实验报告赫夫曼编码样本.doc

数据构造课程设计
赫夫曼编码

院 系： 计算机科学与工程学院
专 业： 计算机科学与技术
姓 名： 林煌东
学 号：
指引教师： 潘煜

01月03日
目录
一、实验目 3
二、题目——赫夫曼编码 3
1.问题描述 4
2.基本规定 4
3.测试规定 4
三、概要设计 4
1.分析赫夫曼树定义 4
2.所实现功能函数 4
3.系统构造图（功能模块图） 5
四、赫夫曼编码源代码 5
五、调试分析 10
1.输入 10
2.建立赫夫曼树 10
3.编码 10
六、实验心得与体会 11

一、实验目
数据构造作为一门学科重要研究数据各种逻辑构造和存储构造，以及对数据各种操作。因而，重要有三个方面内容：数据逻辑构造；数据物理存储构造；对数据操作（或算法）。普通，算法设计取决于数据逻辑构造，算法实现取决于数据物理存储构造。数据构造是信息一种组织方式，其目是为了提高算法效率，它普通与一组算法集合相相应，通过这组算法集合可以对数据构造中数据进行某种操作。
在当今信息时代，信息技术己成为当代知识经济核心技术。咱们时刻都在和数据打交道。例如人们在外出工作时找最短途径，在银行查询存款、通过互联网查新闻、以及远程教诲报名等，所有这些都在与数据发生关系。事实上，现实世界中实体通过抽象后来，就可以成为计算机上所解决数据。
数据构造课程重要是研究非数值计算程序设计问题中所浮现计算机操作对象以及它们之间关系和操作学科。数据构造是介于数学、计算机软件和计算机硬件之间一门计算机专业核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等重要基本，广泛应用于信息学、系统工程等各种领域。
学习数据构造是为了将实际问题中所涉及对象在计算机中表达出来并对它们进行解决。通过课程设计可以提高学生思维能力，增进学生综合应用能力和专业素质提高。通过本次课程设计重要达到如下目：
1.理解并掌握数据构造与算法设计办法，具备初步独立分析和设计能力；
2.初步掌握软件开发过程问题分析、系统设计、程序编码、测试等基本办法和技能；
3.提高综合运用所学理论知识和办法独立分析和解决问题能力；
4.训练用系统观点和软件开发普通规范进行软件开发，培养软件工作者所应具备科学工作办法和作风。
二、题目——赫夫曼编码
1.问题描述
运用赫夫曼编码进行通信可以大大提高信道运用率，缩短信息传播时间，减少传播成本。这规定在发送端通过一种编码系统对待传播数据预先编码，因而需要一种完整赫夫曼编码系统。试为发送端编写一种赫夫曼码编码系统。
2.基本规定
一种完整系统应具备如下功能：
（1）初始化（Initialization）：从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，输出成果。
（2）编码（Encoding）：运用已建好赫夫曼树，对赫夫曼树进行编码，输出成果。
3.测试规定
已知某系统在通信联系中只也许浮现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。
三、概要设计
1.分析赫夫曼树定义
（1）赫夫曼树节点数据类型定义为：
typedef struct
{
int weight； //节点权值
int parent,lchild,rchild； //左右孩子节点
}htnode,*huffmantree;
typedef char * *huffmancode；
2.所实现功能函数
（1）void huffmancoding(huffmantree ht,huffmancode hc,int *w,int n)
//初始化赫夫曼树，解决函数得到数据按照赫夫曼规则建立2叉树。此函数块调用了Select()函数。
（2）void select(huffmantree ht,int n,int *s1,int *s2)
//Select()函数，选出赫夫曼树到n为止，权值最小且parent为02个节点。
（3）int main()主函数
//让顾客运用已建好赫夫曼树对输入数据进行编码，输出成果。使用数组存储，然后分别调用排序函数，建立赫夫曼函数，编码函数等来实现功能。
3.系统构造图（功能模块图）
赫夫曼编码
初始化赫夫曼树
打印编码
编码
打印赫夫曼树

四、赫夫曼编码源代码
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
typedef struct
{
int weight； //节点权值
int parent,lchild,rchild； //双亲、左右孩子节点
}htnode,*huffmantree;
typedef char * *huffmancode；
void select (huffmantree ht,int n,int *s1,int *s2) //挑选权值较小两个节点
{
int i,j,temp;
for(i=1;i<=n;i++)
if(ht[i].parent==0)
{
*s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(ht[j].parent==0)
{
*s2=j;
break;
}
for(i=1;i<=n;i++) //挑选权值较小左节点
{
if(ht[i].parent==0)
if(ht[*s1].weight>ht[i].weight)
if(*s2!=i)
*s1=i;
}
for(j=1;j<=n;j++) //挑选权值较小右节点
{
if(ht[j].parent==0)
if(ht[*s2].weight>ht[j].weight)
if(*s1!=j)
*s2=j;
}
if(*s1>*s2)
{
temp=*s1;
*s1=*s2;
*s2=temp;
}
}
void huffmancoding(huffmantree ht,huffmancode hc,int *w,int n)
{ //求赫夫曼树算法
int i,m;
int start,c,f;
int s1,s2;
char *cd;
if(n<=1) //n不大于2无需构造赫夫曼树
return ;
m=2*n-1； //一共有m=2n-1个节点
ht=(huffmantree) malloc((m+1)*sizeof(htnode))； //0号单元没用；
for(i=1;i<=n;i++) //数组初始化
{
ht[i].weight=w[i-1];
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
for(;i<=m;++i)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
printf("************构造过程***************\n");
for(i=n+1;i<=m;i++)
{
select(ht,i-1,&s1,&s2)； //自己编写代码
ht[s1].parent=i;ht[s2].parent=i;
ht[i].lchild=s1;ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
for(i=1;i<=m;i++)
{
printf("┌──┬──┬──┬──┬───┐\n");
printf(" %d %d %d %d %d\n",i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
}
printf("└──┴──┴──┴──┴───┘\n");
//从叶子到根节点逆向求每个字符赫夫曼编码
//分派n个字符编码头指针向量；
cd=(char*)malloc(n*sizeof(char))； //分派球编码工作空间
cd[n-1]='\0'； //编码结束符
for(i=1;i<=n;i++)
{ //逐个字符求赫夫曼编码
start=n-1； //编码结束符位置
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
{ //从叶子到根你想编码分派空间
if(ht[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
}
hc[i]=(char*)malloc((n-start)*sizeof(char));
//为第i个字符编码分派空间
strcpy(hc[i],&cd[start])； //从cd复制编码（字符串）到hc
}
}//huffancoding
int main()
{
int i,n;
int *w;
huffmantree ht;
huffmancode hc;
printf("请输入构建赫夫曼树节点数与权值");
scanf("%d\n",&n);
hc=(huffmancode)malloc(n*sizeof(huffmancode));
w=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
scanf("%d\n",&w[i]);
}
huffmancoding(ht,hc,w,n);
printf("输出编码为：\n");
for(i=1;i<=n;i++)
{
printf("┌──────┬───────┐\n");
printf(" 权重为:%d 编码为:%s\n",w[i-1],hc[i]);
}
printf("└──────┴───────┘\n");
fflush(stdin);
getchar();
return 0;
}
五、调试分析
1.输入：

2.建立赫夫曼树：

3.编码：

六、实验心得与体会
在这次课程设计中，自己在编写好源代码后调试中浮现了不少错误，遇到了诸多麻烦及困难，在我调试修改程序中错误时，通过度析，我学到了：
1.在定义头文献时可多不可少，即咱们可多写些头文献，必定不会出错，但是若没有定义所引用有关头文献，必然调试不通过；
2.编写和调试程序时应当有足够耐心和细心等。
通过本次数据构造课程设计，我学习了诸多在上课没懂知识，并对求赫夫曼树及赫夫曼编码算法有了更加深刻理解，更巩固了课堂中学习关于于赫夫曼编码知识，真正学会一种算法了。当求解一种算法时,不是拿到问题就不加思考地做，而是一方面要先对它有个大概理解，接着再详细地分析每一步怎么做，无论自己此前与否有解决过相似问题，只要按照以上环节，必然会顺利地做出来。
这次课程设计，我在编辑中犯了某些不应有错误，在不断分析后明确并改正了错误和疏漏，使程序有了更高质量,也使我懂得了一种成功项目必要在写代码前，先对课题有充分思考和规划，否则虽然完毕了项目也会挥霍诸多时间和精力，科学合理编程办法也是我这次课程设计最大收获。