- 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
- 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
最小生树课程设计
工学系课程设计报告
设 计 题 目:最小生成树
系 别:
专 业 (方 向):
年 级、 班:
学 生 姓 名:
学 生 学 号:
指 导 教 师:
年 月日
目录
一、系统开发的背景 1
二、系统分析与设计 1
(一) 系统功能要求 1
(二) 系统模块结构设计 1
三、系统的设计与实现 2
(一) 输入城市信息:create ( ) 2
(二) 判断是否能够生成最小生成树:judge( ) 2
(三) 求最小生成树:Kruskal( ) 3
四、系统测试 4
(一) 测试int menu ( )函数 4
(二) 测试void create ( )函数 4
(三) 测试void judge( )函数 5
(四) 测试void Kruskal( )函数 5
(五) 测试exit( )函数 5
五、总结 6
六、附件(代码、图表) 6
最小生成树
一、系统开发的背景
为了在保证连通即可的n个城市之间建设网络,求出最经济的架设方法,因此设计了这个程序PRIM算法和kruskal算法的基本思想求解出所有的最小生成树。存储结构可自行选择;
系统模块结构设计
通过对系统功能的分析,最小生成树功能如图1所示。
图1 最小生成树功能图
通过上图的功能分析,把整个系统划分为4个模块:
输入城市信息,该模块主要实现:输入城市的个数以及输入城市之间的邻接矩阵,借助函数create( )来实现;
判断是否生成模块,该模块主要实现判断是否能够生成最小生成树,借助函数judge ( )来实现;
3、 求最小生成树模块,该模块主要实现显示所输入城市之间各路段的权值,求出最小生成树,借助函数Kruskal( )来实现;
4、 退出模块,该模块主要实现终止正在执行的程序exit( )来实现;
三、系统的设计与实现
输入城市信息:create ( )
分析:首先输入城市的基本信息。
该模块的具体代码如下所示:
void create()
{
int i,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]);
}
}
(二) 判断是否能够生成最小生成树:judge( )
该模块的具体代码如下所示:
void judge()
{ int close[100],low[100],i,j,ans=0;
int use[100];
use[1]=1;
for(i=2;i=n;i++)
{
low[i]=arcs[1][i];
close[i]=1;
use[i]=0;
}
for(i=1;in;i++)
{ int min=100000000,k=0;
for(j=2;j=n;j++)
{
if(use[j]==0minlow[j])
{ min=low[j];
k=j;
}
}
for(j=2;j=n;j++)
{ if(use[j]==0low[j]arcs[k][j])
{
low[j]=arcs[k][j];
close[j]=k;
}
}ans+=arcs[close[k]][k];
}
if(ans=100000000)
printf(不能构成最小生成树\n);
else
printf(能构成最小生成树\n);
}
(三) 求最小生成树:Kruskal( )
该模块的具体代码如下所示:
void Kruskal()
{ int ans=0,i,j,k=0;
int index;
int count=0;
for(i=1;i=n;i++)
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+
您可能关注的文档
最近下载
- STEAM跨学科课程整合的理念、模式构建与实施挑战研究.docx VIP
- 产学合作协同育人创新创业教育改革项目申报书模板(包含内容).docx VIP
- 110千伏输电线路工程专业监理实施细则.doc VIP
- 智慧乡村、智慧农业产供销一体化、可追溯平台建设方案.pdf VIP
- 17J008 挡土墙(重力式、衡重式、悬臂式)(必威体育精装版).pdf VIP
- 产学合作协同育人教学内容和课程体系改革项目申报书模板—基于计算思维的大学计算机课程思政案例构建与实践(包含申报书内容、合作方案、合作协议).docx
- 智能建造系统架构与发展路径.docx VIP
- 智能建造系统架构与发展路径.docx VIP
- 制药公司生产安全事故应急预案.docx
- 产学合作协同育人教学内容和课程体系改革项目申报书模板—工科程序设计类课程的课程思政教学探索(包含申报书内容、合作方案、合作协议).docx
文档评论(0)