数据结构课程方案地铁建设问题.docx
《数据结构课程方案地铁建设问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程方案地铁建设问题.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构课程方案地铁建设问题
个人资料整理仅限学习使用
软件学院
课程设计报告书
课程名称数据结构课程设计
设计题目地铁建设问题
专业班级
学号
姓名
指导教师
2018年1月
个人资料整理仅限学习使用
11设计时间12设计目的3设计任务14设计内容14.1需求分析1
4.2总体设计2
4.3详细设计4
4.4测试与分析11
114.4.1测试134.4.2分析14附录4.5
20
总结与展望5
22参考文献22
成绩评定
个人资料整理仅限学习使用
设计时间1
日212018年1月月2018年116日至2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。
数据结构是实践性很强的课程。
课程设计是加强学生实践能力的一个语言的算法转换成强有力手段。
要求学生掌握数据结构的应用、算法的编写、类C程序并上机调试的基本方法。
课程设计要求学生在完成程序设计的同时能够写出C比较规范的设计报告。
严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。
设计任务3某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。
地铁铺设费用与距离成正比）；输入各个辖区名称和各辖区间直接距离<1.
2.根据辖区距离信息，计算出应该在哪些辖区建立地铁线路；3.输出应该建设的地铁线路及所需建设总里程。
4设计内容需求分析4.1、程序所能达到的功能：
1根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵（1>存储。
根据普利姆算法计算最小生成树。
（2>地铁铺设费用与距离成正<输入各个辖区代号，名称和各辖区间直接距离（3>比）。
个人资料整理仅限学习使用
根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。
（4>输出应该建设的地铁线路及所需建设总里程。
（5>2、输入的形式及内容：
4.4.1测试部分。
包括城市名称、城市间距离权值、起始地点，详见3、输出的形式及内容：
包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程，详见
4.4.1测试部分。
、测试数据：
4测试部分。
abcd及其之间的距离权值，详见4.4.1四个城市总体设计4.2
数据类型的定义4.2.1图的邻接矩阵存储数据类型定义：
1.typedefstruct{
charV[M][10]。
intR[M][M]。
。
）intvexnum。
Graph辅助数组数据类型定义：
2.typedefstruct{
intadjvex。
}。
intlowcostclosedge[MAX]。
基本操作：
4.2.2CreateCity（&G>
个人资料整理仅限学习使用
；G操作结果：
构造一个无向图LocateDistri（Graphg,intu>
操作结果：
找出目标城市的位置；Min（Graphg,closedgeclosedge>
操作结果：
求出点与点之间的最短路径；.distrinam[1]>
Prim（G,G操作结果：
用普里姆算法找到连接各辖区的最短路；主程序的流程4.2.3所示：
1主程序的流程如图
个人资料整理仅限学习使用
1
图调用）关系4.2.4各程序模块之间的层次<所示：
调用）关系如图2各程序模块之间的层次<
2
图详细设计4.34.3.1预处理#include
#include
#include
#include
#defineINFINITY10000
#defineM20
创建图的结构体typedefstruct{//。
//顶点数组，用来存储辖区的值即辖区的名称charV[M][10]。
intR[M][M]//邻接矩阵，邻接矩阵的元素值为辖区之间的距离
个人资料整理仅限学习使用
辖区的个数intvexnum。
//。
}Graphstructtree{
。
intweizhi。
intlowcost。
}创建辖区无向图的算法4.3.2n个结点，创建辖区邻接矩阵intcreatgraph（Graph*g>//创建辖区无向图，图中含有{
inti=0,j,m,k,p。
chara[10],b[10]。
*****\n>。
printf（*****欢迎使用本程序解决地铁建设问题。
printf（*******请按照提示依次输入相关信息*******\n>。
作为结束标志****\n>0printf（***请输入所有的辖区，以输入结点值。
//scanf（%s,g->V[i]>while（strcmp（
{
i++。
scanf（%s,g->V[i]>。
}
。
g->vexnum=ii++>ivexnum。
。
for（i=0j++>。
for（j=0jvexnum。
。
g->R[i][j]=INFINITY//初始化
个人资料整理仅限学习使用
。
000为结束标志*\n>printf（*请输入辖区之间的路程，以输入辖区结点及辖区之间的距离。
//scanf（%s%s%d,a,b,&m>while（strcmp（
{
在图中的位置查找a,bk=locatevex（g,a>。
p=locatevex（g,b>。
//if（k==-1>
{
*****\n,a>。
printf（*****对不起，输入错误，没有%s这个辖区
return0。
}
if（p==-1>
{
。
%s这个辖区*****\n,b>printf（*****对不起，输入错误，没有。
return0}
k之间的距离相同p和p到。
g->R[k][p]=g->R[p][k]=m//k到输入辖区结点及辖区之间的距离scanf（%s%s%d,a,b,&m>。
//
}
return1。
}
structtree{
。
intweizhiintlowcost。
}。
个人资料整理仅限学习使用
辖区之间的距离辖区与ki//求出第k辖区，此时minimun（structinttree*a,Graphg>
最短{
inti,k,m=0。
i++>ifor（i=0。
{
if（m==0&&a[i].lowcost!
=0>
{
。
m=1。
k=i}
if（m==1&&a[i].lowcost!
=0>
{
if（a[i].lowcost
。
k=i}
}
returnk。
}
定位函数4.3.3在辖区图中的位置intlocatevex（Graph*g,chara[10]>//查找辖区u{
inti。
iu=V[i]i++>//ivexnumfor（i=0。
。
循环执行条件是当时停止，求值
个人资料整理仅限学习使用
{
if（strcmp（a,g->V[i]>==0>
returni。
}
if（i==g->vexnum>
return-1。
}
求最小生成树的结点算法4.3.4辖区之间的距离ki辖区与g>//求出第k辖区，此时*a,Graphintminimun（structtree
最短{
inti,k,m=0。
i++>。
for（i=0。
iif（m==0&&a[i].lowcost!
=0>
{
m=1。
k=i。
}
if（m==1&&a[i].lowcost!
=0>
{
if（a[i].lowcost
。
k=i}
}
个人资料整理仅限学习使用
。
returnk}
算法及输出4.3.5PRIMvoidMiniSpanTree_PRIM（Graphg,chara[10]>
{
。
structtreeclosedge[M]inti,j,k,money=0。
k=locatevex（&g,a>。
i++>ifor（i=0。
{
if（i!
=k>
{
之间的距离k，iclosedge[i].lowcost=g.R[k][i]。
//两辖区k相邻的最近的辖区设为辖区与辖区iclosedge[i].weizhi=k。
//}
}
U={u}
//初始化，closedge[k].lowcost=0。
。
printf（********根据您的输入建立邻接表为:
********\n>i++>。
。
ij++>。
。
for（j=0j。
printf（|%d|,g.R[i][j]>}
个人资料整理仅限学习使用
。
printf（\
\n>}
。
得到应建设地铁的辖区及之间权值为:
****\n>printf（****i++>。
。
ik结点//求出最小生成树T的下一个结点，第。
k=minimun（closedge,g>money+=closedge[k].lowcost。
输//%s%d\n,i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost>。
printf（%d:
%s
出生成树的边集顶点并入U第closedge[k].lowcost=0。
//kj++>j。
for（j=0{
新顶点并入集后，选择新的边，将小的边放到辅if（g.R[k][j]//助数组中{
。
closedge[j].weizhi=k。
closedge[j].lowcost=g.R[k][j]}
}
}
。
printf（******据统计地铁的总建设路程为：
%d*******\n,money>}
主函数模块4,3,6voidmain（>
个人资料整理仅限学习使用
{
inti。
。
Graphg。
chara[10]。
i=creatgraph（&g>if（i>
{
。
请输入起始地点为：
************\n>printf（***********scanf（%s,a>。
MiniSpanTree_PRIM（g,a>。
}
。
printf（**********感谢使用本程序，谢谢！
*********\n>}
4.4测试与分析4.4.1测试测试数据：
为例31.以图
个人资料整理仅限学习使用
3
图4输入城市区域名称，如图所示：
2.
4
图
根据需要，依次输入各个区域代号和边的权值，如图3.5所示：
5
图根据提示，输入地铁站的起始地点如图4.6所示：
6
图5.7输出最终结果，如图所示：
个人资料整理仅限学习使用
7
图4.4.2分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在设计之初，我对于整个算法的思路的理解并不清晰。
最首要的任务就是选择合适的计算思路，并加以实现。
经过查阅，我发现解决此类问题的核心思想就是最小生成树的生成。
于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。
在实验过程中遇到的最大难题是普里姆算法的编写。
通过在书上和网上查阅资料，询问同学老师，结合之前上机实验的经验，我理清思路。
经过编写，调试，最终完成了程序的设计。
算法的时间复杂度和空间复杂度的分析2.表达是求值，主要是，空间复杂度为O（2n>本程序算法的时间复杂度为O（n^3>运用栈的相关知识解决的问题。
在此问题之中要运用到函数的多次调用等等。
3.针对可能出现的输入错误，作出相应的应对措施：
8如输入辖区之间的权值时，当输入错误的辖区时会有报错提示，如图所示：
个人资料整理仅限学习使用
8
图4.5附录源程序：
#include
#include
#include
#include
#defineINFINITY10000
#defineM20
创建图的结构体typedefstruct{//顶点数组，用来存储辖区的值即辖区的名称。
//charV[M][10]//。
邻接矩阵，邻接矩阵的元素值为辖区之间的距离intR[M][M]//辖区的个数intvexnum。
。
}Graph在辖区图中的位置intlocatevex（Graph*g,chara[10]>//查找辖区u{
inti。
iu=V[i]i++>//ivexnumfor（i=0。
。
循环执行条件是当时停止，求值
个人资料整理仅限学习使用
{
if（strcmp（a,g->V[i]>==0>
。
returni}
if（i==g->vexnum>
。
return-1}
n个结点，创建辖区邻接矩阵intcreatgraph（Graph*g>//创建辖区无向图，图中含有{
inti=0,j,m,k,p。
chara[10],b[10]。
*****\n>。
printf（*****欢迎使用本程序解决地铁建设问题。
printf（*******请按照提示依次输入相关信息*******\n>。
作为结束标志****\n>请输入所有的辖区，以printf（***0//。
输入结点值scanf（%s,g->V[i]>while（strcmp（
{
i++。
。
scanf（%s,g->V[i]>}
。
g->vexnum=ii++>ivexnum。
。
for（i=0j++>。
jvexnum。
for（j=0//g->R[i][j]=INFINITY。
初始化
个人资料整理仅限学习使用
。
为结束标志*\n>请输入辖区之间的路程，以printf（*000输入辖区结点及辖区之间的距离。
//scanf（%s%s%d,a,b,&m>while（strcmp（
{
a,b在图中的位置。
。
p=locatevex（g,b>//查找k=locatevex（g,a>if（k==-1>
{
*****\n,a>。
对不起，输入错误，没有%s这个辖区printf（*****return0。
}
if（p==-1>
{
。
%s这个辖区*****\n,b>printf（*****对不起，输入错误，没有。
return0}
之间的距离相同k和p到pg->R[k][p]=g->R[p][k]=m。
//k到输入辖区结点及辖区之间的距离scanf（%s%s%d,a,b,&m>。
//}
return1。
}
structtree{
。
intweizhiintlowcost。
}。
个人资料整理仅限学习使用
辖区之间的距离辖区与k求出第k辖区，此时iintminimun（structtree*a,Graphg>//最短{
。
inti,k,m=0i++>。
for（i=0。
iif（m==0&&a[i].lowcost!
=0>
{
。
m=1。
k=i}
if（m==1&&a[i].lowcost!
=0>
{
if（a[i].lowcost
k=i。
}
}
。
returnk}
voidMiniSpanTree_PRIM（Graphg,chara[10]>
{
structtreeclosedge[M]。
。
inti,j,k,money=0。
k=locatevex（&g,a>i++>
i。
个人资料整理仅限学习使用
{
if（i!
=k>
{
之间的距离，iclosedge[i].lowcost=g.R[k][i]。
//两辖区kk相邻的最近的辖区设为辖区与辖区iclosedge[i].weizhi=k。
//}
}
U={u}
//初始化，closedge[k].lowcost=0。
:
********\n>。
printf（********根据您的输入建立邻接表为i++>。
i{
j++>。
for（j=0。
j。
printf（|%d|,g.R[i][j]>}
。
printf（\
\n>}
:
****\n>。
printf（****得到应建设地铁的辖区及之间权值为i++>。
。
for（i=1ik结点求出最小生成树k=minimun（closedge,g>。
//T的下一个结点，第。
money+=closedge[k].lowcost输出//。
printf（%d:
%s%s%d\n,i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost>生成树的边
个人资料整理仅限学习使用
U集//第k顶点并入closedge[k].lowcost=0。
j++>jfor（j=0。
{
新顶点并入集后，选择新的边，将小的边放到辅助if（g.R[k][j]//数组中{
。
closedge[j].weizhi=k。
closedge[j].lowcost=g.R[k][j]}
}
}
%d*******\n,money>据统计地铁的总建设路程为：
。
printf（******}
voidmain（>
{
inti。
。
Graphg。
chara[10]。
i=creatgraph（&g>if（i>
{
。
printf（***********请输入起始地点为：
************\n>scanf（%s,a>。
MiniSpanTree_PRIM（g,a>。
个人资料整理仅限学习使用
}
。
printf（**********感谢使用本程序，谢谢！
*********\n\n>}
总结与展望5
对于本程序的总结与展望5.1虽然在规定的时间内基本上完成了课程设计所要求的学习任务，但是由于个人能力以及时间上的局限性，造成设计的程序还存在着很多需要改进的地方。
比如没有很完整多样的输入与输出的报错处理程序，不能很好的应对程序在使用过程中出现的各种错误和突发事件；还有在辖区之间权值的输入过程中必须输入每个辖区与”权值，否则会造成输出错误的邻接表等等问题。
我希望在今后的学习生自身的“0活中，在老师的教导下，更加刻苦努力地学习相关知识，进一步完善这个程序。
对于数据结构课程设计的总结5.2语言和这个学期学到的数据结构C此次课程设计让我更加深入了解大一学到的课程。
课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。
程序设计时，不能怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，这正是实践操作的意义所在。
在具体操作中巩固这学期所学的数据结构的理论知识，达到课程设计的基本目的，也发现自己的不足之出，如程序逻辑的理解力语言所具有的语句简洁，使用灵活，执行效C不够强等等。
与此同时，我也体会到率高等特点。
特别是对图这种数据结构有了深刻的理解。
个人资料整理仅限学习使用
参考文献2007北京：
清华大学出版社，严蔚敏，吴伟民编著[1].2004
北京：
清华大学出版社，第二版）.<[2]谭浩强编著.C程序设计1999.北京：
清华大学出版社，程序设计题解与上机指导谭浩强编著.C<第二版）[3]
期年第81981.[4]姚诗斌数据库系统基础.计算机工程与应用，1992北京：
高等教育出版社，语言程序设计教程[5]谭浩强，张基温，唐永炎编著.C.2003
..C[6]丁峻岭编著语言程序设计中国铁道出版社，
个人资料整理仅限学习使用
成绩评定
教师签字成绩
升级会员 