算法125031郝耀峰实验6.docx
《算法125031郝耀峰实验6.docx》由会员分享，可在线阅读，更多相关《算法125031郝耀峰实验6.docx（8页珍藏版）》请在冰点文库上搜索。
算法125031郝耀峰实验6
院（系）计算机学院
专业软件工程
班级12计科3班
姓名郝耀峰
学号1250312025
同组人无
实验室S4310
组号
日期2014.12.10
课程算法设计与分析
指导教师宋婉娟
成绩
实验项目编号06
实验项目名哈夫曼编码算法
1、实验目的
掌握贪心法的设计思想，，掌握贪心法的执行过程，掌握贪心法的求解过程，熟练掌握求解过程的步骤，掌握贪心选择的性质，通过实际的用贪心法解决的问题，更加深刻，透彻的了解贪心法的解题方法。
二、实验环境（仪器设备、软件等）
1、机房电脑windowXP
2、MicrosoftVisualC++6.0
3、实验原理（或要求）
1、用贪心法实现哈夫曼编码的算法
四、实验步骤
程序代码如下：
#include
#include
#include
typedefchar*HuffmanCode;
typedefstruct
{
unsignedintweight;//用来存放各个结点的权值
unsignedintparent,LChild,RChild;
}HTNode,*HuffmanTree;//动态分配数组，存储哈夫曼树
//选择两个parent为0，且weight最小的结点s1和s2
voidSelect（HuffmanTree*ht,intn,int*s1,int*s2）
{
inti,min;
for（i=1;i<=n;i++）
{
if（（*ht）[i].parent==0）
{
min=i;
break;
}
}
for（i=1;i<=n;i++）
{
if（（*ht）[i].parent==0）
{
if（（*ht）[i].weight<（*ht）[min].weight）
min=i;
}
}
*s1=min;
for（i=1;i<=n;i++）
{
if（（*ht）[i].parent==0&&i!
=（*s1））
{
min=i;
break;
}
}
for（i=1;i<=n;i++）
{
if（（*ht）[i].parent==0&&i!
=（*s1））
{
if（（*ht）[i].weight<（*ht）[min].weight）
min=i;
}
}
*s2=min;
}
//构造哈夫曼树ht。
w存放已知的n个权值
voidCrtHuffmanTree（HuffmanTree*ht,int*w,intn）
{
intm,i,s1,s2;
m=2*n-1;
*ht=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
for（i=1;i<=n;i++）//1--n号存放叶子结点，初始化
{
（*ht）[i].weight=w[i];
（*ht）[i].LChild=0;
（*ht）[i].parent=0;
（*ht）[i].RChild=0;
}
for（i=n+1;i<=m;i++）
{
（*ht）[i].weight=0;
（*ht）[i].LChild=0;
（*ht）[i].parent=0;
（*ht）[i].RChild=0;
}//非叶子结点初始化
printf（"\nHuffmanTree:
\n"）;
for（i=n+1;i<=m;i++）//创建非叶子结点，建哈夫曼树
{
//在（*ht）[1]~（*ht）[i-1]的范围内选择两个parent为0
//且weight最小的结点，其序号分别赋值给s1、s2
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;
printf（"%d（%d,%d）\n",（*ht）[i].weight,（*ht）[s1].weight,（*ht）[s2].weight）;
}
printf（"\n"）;
}//哈夫曼树建立完毕
//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
voidCrtHuffmanCode（HuffmanTree*ht,HuffmanCode*hc,intn）
{
char*cd;
inti,start,p;
unsignedintc;
hc=（HuffmanCode*）malloc（（n+1）*sizeof（char*））;//分配n个编码的头指针
cd=（char*）malloc（n*sizeof（char））;//分配求当前编码的工作空间
cd[n-1]='\0';//从右向左逐位存放编码，首先存放编码结束符
for（i=1;i<=n;i++）//求n个叶子结点对应的哈夫曼编码
{
start=n-1;//初始化编码起始指针
for（c=i,p=（*ht）[i].parent;p!
=0;c=p,p=（*ht）[p].parent）//从叶子到根结点求编码
if（（*ht）[p].LChild==c）
cd[--start]='0';//左分支标0
else
cd[--start]='1';//右分支标1
hc[i]=（char*）malloc（（n-start）*sizeof（char））;//为第i个编码分配空间
strcpy（hc[i],&cd[start]）;
}
free（cd）;
for（i=1;i<=n;i++）
printf（"HuffmanCodeof%3dis%s\n",（*ht）[i].weight,hc[i]）;
printf（"\n"）;
}
voidmain（）{
HuffmanTreeHT;
HuffmanCodeHC;
int*w,i,n,wei;
printf（"\nn="）;
scanf（"%d",&n）;
w=（int*）malloc（（n+1）*sizeof（int））;
printf（"\ninputthe%delement'sweight:
\n",n）;
for（i=1;i<=n;i++）
{
printf（"%d:
",i）;
fflush（stdin）;
scanf（"%d",&wei）;
w[i]=wei;
}
CrtHuffmanTree（&HT,w,n）;
CrtHuffmanCode（&HT,&HC,n）;
}
4、记录与处理（实验数据、误差分析、结果分析）
实验运行结果如下：
6、思考题
1、冠军淘汰赛问题的算法。
程序代码如下：
#include
usingnamespacestd;
intComp（inta,intb）;
charGame（charr[],intn）;
charGame（charr[],intn）
{
inti=n;
while（i>1）
{
i=i/2;
for（intj=0;jif（Comp（r[j+i],r[j]））
r[j]=r[j+i];
}
returnr[0];
}
intComp（inta,intb）
{
if（areturn0;
if（a>b）
return1;
}
intmain（）
{
charr[8]={'a','c','r','w','h','t','j','o'};
cout<<"thewinneris"<return0;
}
7、实验小结
通过本次实验掌握了贪心法的设计思想，，掌握了贪心法的执行过程，掌握了贪心法的求解过程，熟练掌握了求解过程的步骤，掌握了贪心选择的性质，通过实际的用贪心法解决的问题，更加深刻，透彻的了解贪心法的解题方法。
升级会员 