构造最小生成树实验.docx
- 文档编号:1069280
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:18
- 大小:113.50KB
构造最小生成树实验.docx
《构造最小生成树实验.docx》由会员分享,可在线阅读,更多相关《构造最小生成树实验.docx(18页珍藏版)》请在冰点文库上搜索。
构造最小生成树实验
C语言与数据结构实习报告
题目:
构造可以使n个城市连接的最小生
成树
学号
姓名
专业班级
指导教师
实践日期
目录
一、综合训练目的与要求3
二、综合训练任务3
三、总体设计4
四、详细设计说明4
五、调试与测试6
六、实习日志8
七、实习总结9
八、附录:
核心代码清单9
一、综合训练目的与要求
按照数据结构、C程序设计教学计划的安排,7月19日到30日,开展为期两周的数据结构与C程序设计课程设计。
该课程设计是数据结构、C语言程序设计课程的重要实践教学环节,是一次全面的系统分析与设计能力的培养,是实现该专业学生总体培养目标的重要教学环节。
使学生通过了解学科领域的发展动向,培养数据结构与程序设计的基本思想,独立分析和解决实践问题的能力,提高和锻炼学生动手能力。
实习的基本要求
(1)结合实践,学生选题与教师指定题目相结合,老师对题目的合理性、学生分组进行确认;
(2)对所选题目,运用面向过程的分析与设计方法,给出系统分析与设计的结果,要求必须要运用数据结构课程中相关的基本知识;
(3)选择熟悉的开发工具,用C语言完成系统实现和测试,掌握系统实现和测试的方法,必须要有详尽的程序注释;
(4)撰写开发文档,培养编写系统分析与设计文档的水平。
二、综合训练任务
主要任务:
给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。
设计该程序的基本要求:
1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。
要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。
2、表示城市间距离网的邻接矩阵(要求至少6个城市,10条边)
3、最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。
三、总体设计
《1》该程序的主要功能:
能实现根据输入城市的信息可以判断该城市间的距离网是否构成最小生成树,遍历城市生成最小生成树,通过计算得到最小生成树的代价。
《2》该城市间的距离网用邻接矩阵表示
《3》用克鲁斯卡尔(Kruskal)算法建立最小生成树
四、详细设计说明
《1》该程序的主要功能:
能实现根据输入城市的信息可以判断出该城市间的距离网是否构成最小生成树,遍历城市生成最小生成树,通过计算得到最小生成树的代价。
该程序的模块结构功能图及主要函数如下:
a)intmain()//主程序
b)intmenu()//菜单函数
c)voidcreate()//输入城市信息函数
d)voidjudge()//判断是否能够生成最小生成树函数
e)voiddisplay()//打印输出
f)voidset()//初始化pre[],rank[]函数
g)voidfind()//判断是否构成回路函数
h)voidUnion()//将能构成最小生成树的边添加到一个集合
l)voidKrushal()//克鲁斯算法求最小生成树
《2》该城市间的距离网使用邻接矩阵表示,邻接矩阵存储方法(数组存储方法),利用两个数组来存储一个图。
用a[i][j]数组,利用邻接矩阵方式来储存城市与城市间信息。
《3》算法设计
(1)克鲁斯卡尔算法思想基本描述:
假设连通图N=(V,{E}),则令最小生成树的初始状态为只有n顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。
在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。
以此类推,直至T中所有顶点都在同一个连通分量上为止。
(2)克鲁斯卡尔算法设计
a.设置计数器E,初值为0,记录已选中的边数。
将所有边从小到大排序,存于p[]中。
b.从p[]中选择一条权值最小的边,检查其加入到最小生成树中是否会构成回路,若是,则此边不加入生成树;否则,加入到生成树中,计数器E累加1。
c.从E中删除此最小边,转b继续执行,直到k=n-1,算法结束
d.判断是否构成回路的方法:
设置集合S,其中存放已加入到生成树中的边所连接的顶点集合,当一条新的边要加入到生成树中时,检查此边所连接的两个顶点是否都已经在S中,若是,则表示构成回路,否则,若有一个顶点不在S中或者两个顶点都不在S中,则不够成回路。
克鲁斯卡尔算法生成最小生成树的过程
(3)防止不能构成最小生成树的图
为避免输入的图构成的不是连通图,设计了judge()函数来判断输入数据构成的是否为连通图,此函数的主要算法是源于普里姆(PRIM)算法,经过改编,形成了新的函数。
五、调试与测试
以一个6个城市、10条边的网络图为例进行测试
16
20115
196
22149
18
网络图
GE=
邻接矩阵
1、开始画面
2、输入信息
设置两顶点之间无边时∞权值为10000
3、数据处理
(1)、判断能否构成最小生成树
(2)、遍历所有城市生成最小生成数
16
115
6
18
生成的最小生成树
(3)、退出
六、实习日志
7月19日
在查阅有关资料和老师的指导下,我对要做的题目有了初步的了解,并能掌握了在网上查阅资料的技能。
今天的主要任务是写(C语言与数据结构)的实施计划书,通过写实施计划书,我掌握了一些发送电子邮件的技巧。
7月20日
昨天已经对所搞的题目有一定的了解,今天主要是进行编程,调试程序。
通过自己动手才知道,自己的编程能力还是有待提高的。
7月21日
今天在调试的过程抱着好玩的心态写了一句代码;system(“color4A”);使原本黑黑的界面变成了多种好看的颜色。
嘿嘿……现在才知道写代码好好玩。
7月22日
对克鲁斯卡尔进一步的研究也探索,对具体的步骤进行分析了一下,总的来说对这克鲁斯算法设计还是有较高的兴趣。
7月23日
今天尝试用克鲁斯卡尔算法求最小生成树,刚开始的时候错误一大堆,看者这些错误,心情老郁闷了。
但我还是不能放弃,像蜗牛一样,一个错误一个错误改。
7月24日—7月25日休息日。
7月26日
经过两天的修改程序,用克鲁斯卡尔算法求最小生成树的程序修改得差不多了。
看着自己辛苦开发出来程序,还挺高兴的,虽然程序还存在问题,但毕竟是自己开发出来的。
嘿嘿。
7月27日
今天主要是开发一个输入城市信息的函数,在网上查了很多相关的资料,最终还是确定用Create()函数。
因为这个函数相对比较好用,容易掌握。
7月28日
经过几天的努力,对构造可以n个城市连接的最小生成树的系统程序大体上完成了,还有几个小错误,但程序基本的结构与算法已经设计好了。
虽然我对这个系统程序的功能不是很满意,但也没办法,技术水平就这样子。
自己以后会越加努力,设计出更好的系统程序。
7月29日
今天上午的时间用来制作演讲PPT,下午的时间用来答辩,由于表达能力不好,在演讲时,完蛋了。
哎……以后要多加练习了。
7月30号
今天是实习的最好一天了,实习的日子里有很多感慨,在编写程序上有了一定的进步。
废话也就不多说了。
以后的日子里,一定要像一只蜗牛,慢慢的成长,步步高升。
嘎嘎……
七、实习总结
通过两周的《数据结构与C语言》课程实训,我不仅对图的概念有了一个新的认识,而且对算法和C语言有了更深的理解,在学习了《数据结构》这门课后,我慢慢地体会到了其中的奥妙,图能够在计算机中存在,首先要捕捉它有哪些具体化、数字化的信息,比如说权值、顶点个数等,这也是说明了想要把生活中的信息转化成到计算机中必须用数字来完整的构成一个信息库,而图的存在,又涉及到了顶点与顶点之间的联系,图分为有向图和无向图,而无向图又是有向图在权值双向相等下的一种特例。
在这次求可使构成n个城市的最小生成树的程序设计中,我采用了a[i][j]数组利用邻接矩阵方式来储存城市与城市间信息,再利用经典的克鲁斯克尔算法求得了最小生成树。
在这次课程设计中,我明白了编写一段代码,我们不仅要考虑它的可行性,更应该考虑它的算法复杂度,运行效率。
做同一件事,一万个人有一万种做法,换而言之,一万个人写一段代码实现同一个功能可以得到一万段代码。
由此,我们可以看出做一件事要精益求精,多加斟酌。
八、附录:
核心代码清单
#include
#include
#include
#definemax20
#defineMAX_LNT10
typedefstructnode/*构造一个结构体,两个城市可以看成起点和终点,之间的道路可以看成一个边*/
{
intstr;/*起点*/
intend;/*终点*/
intdis;/*距离*/
}node;
nodep[max],temp;/*p记录城市信息*/
intpre[100],rank[100];/*用于判断是否构成回路*/
intn=0,arcs[MAX_LNT][MAX_LNT];/*n表示城市个数,arcs[][]记录城市间权值*/
intmenu()/*菜单函数*/
{
intm;
printf("..........................2010年7月29日......................\n\n");
printf("求最小生成树\n");
printf("________________________________\n\n");
printf("1输入城市之间的信息\n");
printf("2判断是否能构成一个最小生成树\n");
printf("3遍历所有城市生成最小生成树\n");
printf("4退出\n");
printf("________________________________\n\n");
printf("请输入所选功能1-4\n");
system("colorE");/*改变界面颜色的,对程序没什么影响*/
scanf("%d",&m);
returnm;
}
/*下面三个函数作用是检验当一条边添加进去,是否会产生回路*/
voidset(intx)/*初始化*/
{
pre[x]=x;
rank[x]=0;
}
intfind(intx)/*找到这个点的祖先*/
{
if(x!
=pre[x])
pre[x]=find(pre[x]);
returnpre[x];
}
voidUnion(intx,inty)/*将这两个添加到一个集合里去*/
{
x=find(x);
y=find(y);
if(rank[x]>=rank[y])
{
pre[y]=x;
rank[x]++;
}
elsepre[y]=x;
}
voidKruskal()
{
intans=0,i,j,k=0;/*ans用来记录生成最小树的权总值*/
intindex;
intcount=0;/*记录打印边的条数*/
for(i=1;i<=n;i++)/*初始化数组pre[x],rank[x]*/
set(i);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
p[++k].str=i;
p[k].end=j;
p[k].dis=arcs[i][j];/*先把所有城市之间的路段看成一个边*/
}
}
for(i=1;i<=k;i++)/*把所有的边按从小到大进行排序*/
{
index=i;
for(j=i+1;j<=k;j++)if(p[j].dis
temp=p[index];
p[index]=p[i];
p[i]=temp;
}
for(i=1;i<=k;i++)
{
if(find(p[i].str)!
=find(p[i].end))/*如果这两点连接在一起不构成一个回路,则执行下面操作*/
{
printf("\t第%d条路段为:
%d--%d,权值为%d\n",++count,p[i].str,p[i].end,p[i].dis);/*将这条边的起点、终点打印出来*/
ans+=p[i].dis;/*说明这条路段要用*/
Union(p[i].str,p[i].end);
}
}
printf("\t遍历所有城市得到最小生成树的代价为:
%d\n\n",ans);
}
voidcreate()/*输入城市信息*/
{
inti,j;
printf("请输入城市的个数:
\n");
scanf("%d",&n);
printf("输入%d个城市的邻接矩阵:
\n",n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&arcs[i][j]);
}
}
voiddisplay()/*显示生成的最小生成树*/
{
if(n==0)
{
printf("这里没有城市之间的信息\n");
return;
}
printf("遍历所有城市得到最小生成树为:
\n\n\n");
Kruskal();
}
voidjudge()/*判断是否能够生成最小生成树*/
{
intclose[100],low[100],i,j,ans=0;/*close[j]表示离j最近的顶点,low[j]表示离j最短的距离*/
intuse[100];
use[1]=1;
for(i=2;i<=n;i++)
{
low[i]=arcs[1][i];/*初始化*/
close[i]=1;
use[i]=0;
}
for(i=1;i { intmin=100000000,k=0; for(j=2;j<=n;j++) { if(use[j]==0&&min>low[j])/*找到最小的low[]值,并记录*/ { min=low[j]; k=j; } } for(j=2;j<=n;j++) { if(use[j]==0&&low[j]>arcs[k][j]) { low[j]=arcs[k][j];/*修改low[]值和close[]值*/ close[j]=k; } } ans+=arcs[close[k]][k]; } if(ans>=100000000)printf("不能构成最小生成树\n"); elseprintf("能构成最小生成树\n"); } intmain()/*主函数*/ { while (1) { switch(menu()) { case1: create();break;/*输入城市信息*/ case2: judge();break;/*判断是否能够生成最小生成树*/ case3: display();break;/*显示生成的最小生成树*/ case4: exit(0); } } return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 构造 最小 生成 实验