算法分析实验单元三.docx
- 文档编号:9376347
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:17
- 大小:67.63KB
算法分析实验单元三.docx
《算法分析实验单元三.docx》由会员分享,可在线阅读,更多相关《算法分析实验单元三.docx(17页珍藏版)》请在冰点文库上搜索。
算法分析实验单元三
《算法分析与设计》实验报告
专业:
计科班级:
F1402班日期:
2017.4.11成绩
学生姓名:
苏朋辉学号:
201416010211指导老师:
李磊
实验单元三贪心算法
一、实验题目
实验一哈夫曼树
二、实验目的
了解前缀编码的概念,掌握最优子结构性质的证明方法;掌握贪心算法的设计思想并能熟练运用。
三、实验内容
设需要编码的字符集为{d1,d2,•••,dn},它们出现的频率为{w1,w2,•••,wn},应用哈弗曼树构造最短的编码。
哈弗曼编码的基本思想是:
在集合中选择两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树,且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和;随后删除这两颗树,同时将新得到的二叉树加入F中。
不断重复,最后直到剩下一棵树,这棵树便是哈弗曼树。
四、实验结果(代码及运行结果)
代码如下:
#include
#include
#include
typedefstruct
{
unsignedintweight;//用来存放各个结点的权值
unsignedintparent,LChild,RChild;//指向双亲、孩子结点的指针
}HTNode,*HuffmanTree;//动态分配数组,存储哈夫曼树
typedefchar*HuffmanCode;//动态分配数组,存储哈夫曼编码
//选择两个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("\n哈夫曼树为:
\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;//定义的存放编码的空间
inta[100];
inti,start,p,w=0;
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个叶子结点对应的哈夫曼编码
{
a[i]=0;
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]='1';//左分支标1
a[i]++;
}
else
{
cd[--start]='0';//右分支标0
a[i]++;
}
}
hc[i]=(char*)malloc((n-start)*sizeof(char));//为第i个编码分配空间
strcpy(hc[i],&cd[start]);//将cd复制编码到hc
}
free(cd);
for(i=1;i<=n;i++)
printf("权值为%d的哈夫曼编码为:
%s\n",(*ht)[i].weight,hc[i]);
for(i=1;i<=n;i++)
w+=(*ht)[i].weight*a[i];
printf("带权路径为:
%d\n",w);
}
intmain()
{
HuffmanTreeHT;
HuffmanCodeHC;
int*w,i,n,wei;
printf("**哈夫曼编码**\n");
printf("请输入结点个数:
");
scanf("%d",&n);
w=(int*)malloc((n+1)*sizeof(int));
printf("\n输入这%d个元素的权值:
\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);
}
运行结果为:
五、实验体会
实验开始时对数据变量的修改有一部分没有太注意,没有传引用,导致实验结果过出现很多错误甚至是不能运行,设置断点调试后才找出问题所在。
通过这次试验,虽然感觉收获了很多。
无论是对于编程本身还是对集成开发环境的使用上,还有对前缀编码、数据压缩的基本方法以及最优子结构性质等知识的理解上,都有了很大的提高。
对于哈夫曼树算法和贪心算法有了更深的印象。
但在参考网上材料的同时,看到大牛使用二叉堆实现哈弗曼树的博客,顿时感觉自己算法功底真的很差。
实验虽然结束了,但自己还是留下很多问题啊,只能课后自己继续专研啦!
每天进步一点点!
《算法分析与设计》实验报告
专业:
计科班级:
F1402班日期:
2017.4.18成绩
学生姓名:
苏朋辉学号:
201416010211指导老师:
李磊
实验单元二贪心算法
五、实验题目
实验二最小生成树
六、实验目的
熟悉贪心算法的基本原理与使用范围;熟悉和掌握贪心算法求最小生成树问题。
七、实验内容
给定一个带权图G=(V,E),求G的最小生成树。
Kruskal算法的基本思想是:
对所有的边进行排序,然后依次加入顶点,如果不构成回路,就加入,否则舍弃这条边,得到的最终图变成一棵树,即为最小生成树。
八、实验结果(代码及运行结果)
(1)所用数据结构,图的存储结构模块(nodetype.h)
#definemaxSize20
typedefstruct{
intno;
}VertexType;//结点类型定义
typedefstruct{
intn;//图的顶点数
inte;//图的所有边数
VertexTypevex[maxSize];//顶点信息
intedges[maxSize][maxSize];//各边的权值
}MGraph;//图的存储结构
typedefstruct{
inta;//边的起点
intb;//边的终点
intw;//边的权值
}Road;//权值非0的边的存储结构
(2)主模块(main_Kruskal.cpp)
#include
#include
#include"nodetype.h"
#include"initlize.h"
#include"roadinfor.h"
#include"heapSort.h"
#include"kruskal.h"
intmain(){
intsum=0;//存储最小生成树的总代价
Initlize(g);//图信息的初始化,录入初始信息
Roadinfor(road,g.n);//录入边的信息
printf("最小生成树边的编号起点终点权值\n");
Kruska(g,road,v,sum);//调用Kruskal算法,输出最小生成树
printf("\n最小代价生成树为:
%d\n",sum);
return0;
}
(3)读取数据模块,图的初始化(initlize.h)
//初始化图结构,录入图的信息
voidInitlize(MGraph&g){
inti,j;
printf("请输入图的顶点数目:
\n");
scanf("%d",&g.n);//读取顶点数目
printf("请输入各边的权值:
(不相临接的两顶点权值为0)\n\n");
for(i=1;i<=g.n;i++){
g.vex[i].no=i;
for(j=1;j<=g.n;j++){
printf("边[%d][%d]的权值为:
",i,j);
scanf("%d",&g.edges[i][j]);
printf("\n");
}
}
}
MGraphg;//图
Roadroad[maxSize];//边的信息
intv[maxSize];//顶点集
(4)读取各条候选边(待排序边)信息模块(roadinfor.h)
//读取各边的信息,并将之存入road[]中
voidRoadinfor(Roadroad[],inte){
inti,j;
intk=1;
for(i=1;i<=e;i++){
for(j=i;j<=e;j++){
if(g.edges[i][j]!
=0){
road[k].a=i;
road[k].b=j;
road[k].w=g.edges[i][j];
k++;
}
}
}
}
(5)将待检测边进行堆排序模块(heapSort.h)
intSizearray(Roadroad[]);//求边的数目,即road[]数组元素的个数//R[low]到R[high]范围内对位置low到high结点进行调整
voidSift(Roadroad[],intlow,inthigh);
//将边对象road2的信息赋值给边对象road1
voidSwitch(Road&road1,Roadroad2);
voidverse(Roadroad[]);//将road数组倒置
voidHeapSort(Roadroad[],inte){//对边的权值进行堆排序,从小到大
inti;
Roadtemp;
for(i=(Sizearray(road))/2;i>=1;){
Sift(road,i,Sizearray(road));//建立初始小顶堆
i--;
}
for(i=(Sizearray(road));i>=2;i--){//取得堆顶元素之后,不断对堆进行调准
Switch(temp,road[1]);
Switch(road[1],road[i]);
Switch(road[i],temp);
//只需要从新的堆顶开始调准,只有堆顶可能不满足小顶堆条件
Sift(road,1,i-1);
}
}
voidSift(Roadroad[],intlow,inthigh){
inti,j;
i=low;
j=2*i;
Roadtemp;
Switch(temp,road[i]);//先将堆顶存入temp
while(j<=high){
if(jroad[j+1].w)//找到其最小的儿子
j++;
if(temp.w>road[j].w){//若不满足小顶堆条件,则需进行调准
Switch(road[i],road[j]);
i=j;
j=2*i;
}
else{
break;
}
}
Switch(road[i],temp);//最后确定road[i]的位置
}
intSizearray(Roadroad[]){
inti,n=0;
for(i=1;road[i].w!
=0;i++){
n++;
}
returnn;
}
voidSwitch(Road&road1,Roadroad2){
road1.a=road2.a;//road1起点赋值
road1.b=road2.b;//road1终点赋值
road1.w=road2.w;//road1权值赋值
}
voidverse(Roadroad[]){
inti,n;
Roadtemp;
n=Sizearray(road);
for(i=1;i<=n/2;){
Switch(temp,road[i]);
Switch(road[i],road[n-i+1]);
Switch(road[n-i+1],temp);
i++;
}
}
(6)运用贪心策略——Kruskal算法构造最小生成树(kruskal.h)
intGetRoot(inta);//取得顶点的根节点,从而得到连通分支
//Kruskal算法,实现求最小生成树
voidKruska(MGraph&g,Roadroad[],intv[],int&sum){
inti,x,y;
inta,b;
//顶点ver[i]初始时表示各在不同的连通分支v[i]中,父结点依次为v[i]
for(i=1;i<=g.n;i++){
v[i]=i;
}
//堆排序,将边按照从小到大的顺序排序
HeapSort(road,g.e);
verse(road);
for(i=1;i<=Sizearray(road);i++){
//得到起点所在的连通分支号
x=GetRoot(road[i].a);
//得到终点所在的连通分支号
y=GetRoot(road[i].b);
//添加road[i]不会成环,将边road[i]添加其中
if(x!
=y){
printf("%d%d%d%d\n",
i,road[i].a,road[i].b,road[i].w);
if(x!
=road[i].a){
//road[i]的起点已经被修改过,这时需要修改边road[i]的终点的连通分支号
v[road[i].b]=road[i].a;
sum+=road[i].w;
}else{
//road[i]的起点未被修改过,这时修改边road[i]的起点的连通分支号
v[road[i].a]=road[i].b;
sum+=road[i].w;
}
}
}
}
//顶点a所在的连通分支号
intGetRoot(inta){
while(a!
=v[a]){
a=v[a];
}
returna;
}
算法分析
从Kruskal算法中可以看到,执行该算法时间主要花费在堆排序和单层循环上,而循环是线性级的,则可以认为时间复杂性主要花费在堆排序上,由堆排序算法可知,Kruskal算法的时间复杂度为O(eloge),其中e为图的边数。
运行结果为:
五、实验体会
通过实现求最小生成树的两种算法,Prim算法和Kruskal算法,一个从顶点集考虑,一个从边集考虑,分别实现了构造最小生成树,当然Prim从单个顶点出发,利用贪心策略,开始顶点不同,可能构造的最小生成树可能不同,但最终的总耗费却是唯一的。
同时思考问题的角度不同,带来执行算法效率的不同,Prim的时间复杂度为O(n2)(n为图的顶点数),与图的顶点数有关,边数无关,故适合顶点数目稀少的图,即密集图,而Kruskal的时间复杂度为O(eloge)(e为图中边的数目),与图的边数有关,故适合边数较少的稀疏图
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 实验 单元