课程设计构造哈夫曼树.docx
《课程设计构造哈夫曼树.docx》由会员分享，可在线阅读，更多相关《课程设计构造哈夫曼树.docx（12页珍藏版）》请在冰点文库上搜索。
课程设计构造哈夫曼树
中国矿业大学徐海学院计算机系
《软件认知实践》报告
姓名：
学号：
专业：
设计题目：
指导教师：
2013年12月
第1章题目概述
设计程序以实现构造哈夫曼树的哈夫曼算法
第1.1节题目要求
（1）可以使用实验工具的有关功能。
（2）要能演示构造过程。
（3）求解出所构造的哈夫曼树的带权路径长度。
第1.2节主要难点
（1）构造哈夫曼树：
根据给定的权值构成二叉树集合，其中每棵二叉树中只有一个带权的根节点，其左右子树均为空；在二叉树集合中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左、右子树上根节点的权值之和；在二叉树集合中删除这两棵树，并将得到的二叉树加入集合中；重复上述步骤，直至二叉树集合中只含一棵树为止。
（2）求带权路径长度：
先求每个叶子结点到树根之间的路径长度与该叶子结
点所带权值之积，在将所得之积求和。
第2章系统流程图
第3章数据结构和算法
使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定时间复杂度内寻找到最佳（最短）路径，节约比较次数。
1.Inithuffmantree（&T）
操作结果：
构造一个已知结点和权值的huffmantree.
2.Destoryhuffmantree（&T）
条件：
huffmantree已经存在
结果：
销毁huffmantree.
3.huffmancoding（&T）
条件：
huffmantree已经存在
结果：
输出huffmancode.
4.Visithuffmantree（&T）
条件：
huffmantree已经存在
结果：
显示huffmantree.
代码运行结果
第4章核心代码分析
（1）定义
ints1=0,s2=0;//定义两个全局变量
typedefstruct//定义/结构体
{
intc;//字符域
intw;//权值域
intp,l,r;/双亲域/左孩子域右孩子域，
}HT,*HuffmanTree;//动态分配数组存储赫夫曼树
typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码
HT*HTree;
（2）找出两个最小权值s1，s2
voidSelect（HT*HTree,intb）
{
inti,j,t;
for（i=1;i<=b;i++）
if（!
HTree[i].p）
{
s1=i;
break;
}
for（j=i+1;j<=b;j++）
if（!
HTree[j].p）
{
s2=j;
break;
}
for（i=1;i<=b;i++）
if（（HTree[s1].w>HTree[i].w）&&（!
HTree[i].p）&&（s2!
=i））
s1=i;
for（j=1;j<=b;j++）
if（（HTree[s2].w>HTree[j].w）&&（!
HTree[j].p）&&（s1!
=j））
s2=j;
if（s1>s2）//令s1小于s2
{
t=s1;
s1=s2;
s2=t;
}
}
HuffmanCodeHCode
（3）输出状态图
voidpr（HT*HTree,intm）
{
inti;
HT*h;
printf（"\n输出状态图\n字符\t权值\t双亲\t左孩子\t右孩子"）;
h=HTree+1;
for（i=1;i<=m;i++,h++）
{
printf（"\n%c\t%d\t%d\t%d\t%d",h->c,h->w,h->p,h->l,h->r）;
}
（4）逐个字符求赫夫曼编码
voidStrcpy（char*p1,char*p2,inti,intj）
{
intk;
for（k=0;i<=j;k++,i++）
*（p1+k）=*（p2+i）;
}
（5）逐个字符求赫夫曼编码
voidbm（HT*HTree,intn,char*code）
{
inti,start,t,P;
for（i=1;i<=n;i++）
{
start=n-1;//编码结束符位置
for（t=i,P=HTree[i].p;P!
=0;t=P,P=HTree[P].p）//从叶子到根逆向求编码
{
if（HTree[P].l==t）
code[--start]='0';//左孩子编码为0
else
code[--start]='1';//有孩子编码为1
}
HCode[i]=（char*）malloc（（n-start）*sizeof（char））;//为第i个字符编码分配空间
Strcpy（HCode[i],code,start,n-1）;//把code占到hcode上
}
}
（6）输出赫夫曼编码函数
voidPrint（HuffmanTreeHTree,HuffmanCodeHCode,intn）
{
inti;
for（i=1;i<=n;i++）
{
printf（"%c--",HTree[i].c）;
printf（"%d--",HTree[i].w）;
printf（"%s",HCode[i]）;
printf（"\n"）;
}
}
（7）带权路径长度
dq（HT*HTree,intn）
{
inti,l,P,WPL;
intwpl[100];
for（i=1;i<=n;i++）
{
for（l=0,P=HTree[i].p;P!
=0;P=HTree[P].p）
l+=1;//l是路径个数
wpl[i]=HTree[i].w*l;
}
for（i=1,WPL=0;i<=n;i++）
WPL+=wpl[i];
returnWPL;
}
（8）主函数
voidmain（）
{
intn,m,i,C,W,WPL;
HT*h;
printf（"赫夫曼树应用！
"）;
printf（"\n输入叶子节点个数:
"）;
scanf（"%d",&n）;
m=2*n-1;
HTree=（HT*）malloc（（m+1）*sizeof（HT））;//0号单元未用,初始化赫夫曼树
h=HTree+1;
printf（"\n输入%d个字符的Asc码（97-133）和权值:
",n）;
//叶子结点初始化
for（i=1;i<=n;i++,h++）
{
scanf（"%d",&C）;
scanf（"%d",&W）;
h->c=C;
h->w=W;
h->p=0;
h->l=0;
h->r=0;
}
//中间结点初始化
for（i=n+1;i<=m;i++,h++）
{
h->c='';
h->w=0;
h->p=0;
h->l=0;
h->r=0;
}
printf（"\n初始\n"）;
pr（HTree,m）;//输出初始状态图
//建赫夫曼树
for（i=n+1;i<=m;i++）
{
Select（HTree,i-1）;
HTree[s1].p=i;
HTree[s2].p=i;
HTree[i].l=s1;
HTree[i].r=s2;
HTree[i].w=HTree[s1].w+HTree[s2].w;
}
//输出终结状态图
printf（"\n终结\n"）;
pr（HTree,m）;
//从叶子到根逆向求赫夫曼树编码
char*code;
HCode=（HuffmanCode）malloc（（n+1）*sizeof（char））;//0号单元未用,分配n个字符编码的头指针向量
code=（char*）malloc（n*sizeof（char））;//分配求编码的公用工作空间
code[n-1]='\0';//编码结束符
bm（HTree,n,code）;
printf（"\n赫夫曼编码为:
\n"）;
Print（HTree,HCode,n）;
//带权路径长度
WPL=dq（HTree,n）;
printf（"\n带权路径长度:
%d\n",WPL）;
}
第5章实验小结
通过这一段时间的课程设计，我通过查找资料，仔细思考，运行修改，编出赫夫曼树应用这个程序。
在编程序的过程中，也遇到了很多困难：
检查没有错误却无法得出想要的结果，语句也和书上的一样却无法连接结点，又或是想达到的效果编不出来等等。
这说明我们掌握的知识不够完整，不够扎实，需要加深巩固。
我们一点点地摸索、求证、询问、查找，虽然还有不完美的地方，终于将程序完成，也对树的知识有了更深的理解。
这一周的课程设计让我收获颇丰，也感谢老师平时上课的教导。
参考文献
严蔚敏吴伟民编.《数据结构（c语言版）》.清华大学出版社
谭浩强编.《C程序设计》.清华大学出版社
升级会员 