数据结构课程设计—地铁建设问题.docx
- 文档编号:14764067
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:23
- 大小:50.88KB
数据结构课程设计—地铁建设问题.docx
《数据结构课程设计—地铁建设问题.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计—地铁建设问题.docx(23页珍藏版)》请在冰点文库上搜索。
软件学院
课程设计报告书
课程名称 数据结构课程设计 设计题目 地铁建设问题 专业班级 学号 姓名
指导教师
2015年1月
目录
1设计时间 4.
2设计目的 .4.
3设计任务 4
4设计内容 4.
4.1需求分析 5
4.2总体设计 5
4.3详细设计 7
4.4测试与分析 .7.
4.4.1测试 1.2
4.4.2分析 1.3
4.5附录 14
5总结与展望 20
参考文献 22
成绩评定 23
1设计时间
2015年1月19日一2012年1月23日
2设计目的
通过课程设计,加深对数据结构》这一课程所学内容的进一步理解与巩固,加深对结构化设计思想的理解,能对系统功能进行分析,并设计合理的模块化结构。
提高程序开发功能,能运用合理的控制流程编写清晰高效的程序。
训练C程序调试能力,能将一个中小型各级组织系统联调通过。
开发一个中小型系统,掌握系统研发全过程。
培养分析问题、解决实际问题的能力。
3设计任务
某城市要在各个辖区之间修建地铁,由于地铁建设费用昂贵,因此需要合理安排地铁建设线路,使市民可以沿地铁到达各个辖区,并使总费用最小。
4设计内容
设计思路:
(1)输入各个辖区名称和各辖区间直接距离(地铁铺设费用与距离成正比)。
如:
北京到大连的直接距离是100公里•
(2)根据辖区距离信息,计算出应该在哪些辖区建立地铁线路。
(3)输出应该建设的地铁线路及所需建设总里程。
本程序中用到的所有抽象数据类型的定义;
typedefcharInfoType
typedefcharVertexType[MAX_NAME]
typedefstruct
{
VRTypeadj;
InfoType*info;、
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,
arcnum;
}MGraph;
typedefstruct
{
VertexTypeadjvex;
VRTypelowcost;
}minside[MAX_VERTEX_NUM];
4.1需求分析
输出应该建设的地铁线路及所需建设总里程 。
要求输出建设地铁的最短路线,再利
用其最短路线上的权值把总的里程计算出来 ,已达到最省的费用,实现该地铁的建设。
4.2总体设计
1•首先要了解本题中的要求,要用已经学的邻接矩阵,根据输入的辖区信息,建立图模型,使用的数据结构是无向图,采用邻接矩阵存储。
2.根据普利姆算法计算最小生成树。
假设WN=(V,{E})是一个含有n个顶点的连通网,TV是WN上最小生成树中顶点的集合,TE是最小生成树中边的集合。
显然,在算法执行结束时,TV=V,而TE是E的一个子集。
在算法开始执行时,TE为空集,TV中只有一个顶点,因此,按普里姆算法构造最小生成树的过程为:
在所有其一个顶点已经落在生成树上,而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边,逐条加在生成树上,直至生成树中含有n-1条边为止。
3.了解了这些就可以实现它的基本操作,然后构建一个邻接矩阵,输入各个辖区构成一个无向连通图,并把直接距离当作权值来标记,之后,进行普里姆的算法,使其生成最小生成树,并带有权值了,把这些辖区输出,并把最小路径和最少的费用输出,这样就完成了操作。
本题出现的调用函数是:
i=creatgraph(&g);
MiniSpanTree_PRIM(g,a);
k=locatevex(&g,a);
minimun(structtree*a,Graphg) ;
主程序流程图:
”
主函数
4.3详细设计
typedefstruct{
charV[M][10];
intR[M][M];
intvexnum;
}Graph;
intlocatevex(Graph*g,chara[10])
inti;
for(i=0;i
{
if(strcmp(a,g->V[i])==0)
returni;
}
if(i==g->vexnum)
return-1;
}
intcreatgraph(Graph*g)
{
inti=O,j,m,k,p;
chara[10],b[10];
printf("所有的辖区,以0为结束\n");
scanf("%s",g->V[i]);
while(strcmp("0",g->V[i])!
=0)
{
i++;
scanf("%s",g->V[i]);
}
g->vexnum=i;
for(i=0;i
for(j=0;j
g->R[i][j]=INFINITY;
printf("辖区之间的路程,以000为结束标志\n");
scanf("%s%s%d",a,b,&m);
while(strcmp("O",a)!
=O||strcmp("O",b)!
=O||m!
=0)
{
k=locatevex(g,a);p=locatevex(g,b);
if(k==-1)
{
printf("没有%s这个辖区\n",a);
return0;
}
if(p==-1)
{
printf("没有%s这个辖区\n",b);
return0;
}
g->R[k][p]=g->R[p][k]=m;
scanf("%s%s%d",a,b,&m);
}
return1;
}
structtree{
intweizhi;
intlowcost;
};
intminimun(structtree*a,Graphg)
{
inti,k,m=O;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 地铁 建设 问题