毕业设计地铁建设问题数据结构课程设计.docx
《毕业设计地铁建设问题数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《毕业设计地铁建设问题数据结构课程设计.docx（19页珍藏版）》请在冰点文库上搜索。
毕业设计地铁建设问题数据结构课程设计
软件学院
课程设计报告书
课程名称数据结构课程设计
设计题目地铁建设问题
专业班级
学号
姓名
指导教师
2013年1月
1设计时间
2013年1月16日至2013年1月21日
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;
intlowcost;}
closedge[MAX];
4.2.2基本操作：
CreateCity（&G）
操作结果：
构造一个无向图G；
LocateDistri（Graphg,intu）
操作结果：
找出目标城市的位置；
Min（Graphg,closedgeclosedge）
操作结果：
求出点与点之间的最短路径；
Prim（G,G.distrinam[1]）
操作结果：
用普里姆算法找到连接各辖区的最短路；
4.2.3主程序的流程
主程序的流程如图1所示：
图1
4.2.4各程序模块之间的层次（调用）关系
各程序模块之间的层次（调用）关系如图2所示：
图2
4.3详细设计
4.3.1预处理
#include
#include
#include
#include
#defineINFINITY10000
#defineM20
typedefstruct{//创建图的结构体
charV[M][10];//顶点数组，用来存储辖区的值即辖区的名称
intR[M][M];//邻接矩阵，邻接矩阵的元素值为辖区之间的距离
intvexnum;//辖区的个数
}Graph;
structtree{
intweizhi;
intlowcost;
};
4.3.2创建辖区无向图的算法
intcreatgraph（Graph*g）//创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵
{
inti=0,j,m,k,p;
chara[10],b[10];
printf（"*****欢迎使用本程序解决地铁建设问题*****\n"）;
printf（"*******请按照提示依次输入相关信息*******\n"）;
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;ivexnum;i++）
for（j=0;jvexnum;j++）
g->R[i][j]=INFINITY;//初始化
printf（"*请输入辖区之间的路程，以000为结束标志*\n"）;
scanf（"%s%s%d",a,b,&m）;//输入辖区结点及辖区之间的距离
while（strcmp（"0",a）!
=0||strcmp（"0",b）!
=0||m!
=0）
{
k=locatevex（g,a）;p=locatevex（g,b）;//查找a,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;//k到p和p到k之间的距离相同
scanf（"%s%s%d",a,b,&m）;//输入辖区结点及辖区之间的距离
}
return1;
}
structtree{
intweizhi;
intlowcost;
};
intminimun（structtree*a,Graphg）//求出第k辖区，此时i辖区与k辖区之间的距离最短
{
inti,k,m=0;
for（i=0;i{
if（m==0&&a[i].lowcost!
=0）
{
m=1;
k=i;
}
if（m==1&&a[i].lowcost!
=0）
{
if（a[i].lowcostk=i;
}
}
returnk;
}
4.3.3定位函数
intlocatevex（Graph*g,chara[10]）//查找辖区u在辖区图中的位置
{
inti;
for（i=0;ivexnum;i++）//循环执行条件是当u=V[i]时停止，求i值
{
if（strcmp（a,g->V[i]）==0）
returni;
}
if（i==g->vexnum）
return-1;
}
4.3.4求最小生成树的结点算法
intminimun（structtree*a,Graphg）//求出第k辖区，此时i辖区与k辖区之间的距离最短
{
inti,k,m=0;
for（i=0;i{
if（m==0&&a[i].lowcost!
=0）
{
m=1;
k=i;
}
if（m==1&&a[i].lowcost!
=0）
{
if（a[i].lowcostk=i;
}
}
returnk;
}
4.3.5PRIM算法及输出
voidMiniSpanTree_PRIM（Graphg,chara[10]）
{
structtreeclosedge[M];
inti,j,k,money=0;
k=locatevex（&g,a）;
for（i=0;i{
if（i!
=k）
{
closedge[i].lowcost=g.R[k][i];//两辖区k，i之间的距离
closedge[i].weizhi=k;//与辖区i相邻的最近的辖区设为辖区k
}
}
closedge[k].lowcost=0;//初始化，U={u}
printf（"********根据您的输入建立邻接表为:
********\n"）;
for（i=0;i{
for（j=0;j{
printf（"|%d|",g.R[i][j]）;
}
printf（"\n\n"）;
}
printf（"****得到应建设地铁的辖区及之间权值为:
****\n"）;
for（i=1;i{
k=minimun（closedge,g）;//求出最小生成树T的下一个结点，第k结点
money+=closedge[k].lowcost;
printf（"%d:
%s%s%d\n",i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost）;//输出生成树的边
closedge[k].lowcost=0;//第k顶点并入U集
for（j=0;j{
if（g.R[k][j]{
closedge[j].weizhi=k;
closedge[j].lowcost=g.R[k][j];
}
}
}
printf（"******据统计地铁的总建设路程为：
%d*******\n",money）;
}
4,3,6主函数模块
voidmain（）
{
inti;
Graphg;
chara[10];
i=creatgraph（&g）;
if（i）
{
printf（"***********请输入起始地点为：
************\n"）;
scanf（"%s",a）;
MiniSpanTree_PRIM（g,a）;
}
printf（"**********感谢使用本程序，谢谢！
*********\n"）;
}
4.4测试与分析
4.4.1测试
测试数据：
1.以图3为例
图3
2.输入城市区域名称，如图4所示：
图4
3.根据需要，依次输入各个区域代号和边的权值，如图5所示：
图5
4.根据提示，输入地铁站的起始地点如图6所示：
图6
5.输出最终结果，如图7所示：
图7
4.4.2分析
1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析
在设计之初，我对于整个算法的思路的理解并不清晰。
最首要的任务就是选择合适的计算思路，并加以实现。
经过查阅，我发现解决此类问题的核心思想就是最小生成树的生成。
于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。
在实验过程中遇到的最大难题是普里姆算法的编写。
通过在书上和网上查阅资料，询问同学老师，结合之前上机实验的经验，我理清思路。
经过编写，调试，最终完成了程序的设计。
2.算法的时间复杂度和空间复杂度的分析
本程序算法的时间复杂度为O（n^3），空间复杂度为O（2n）表达是求值，主要是运用栈的相关知识解决的问题。
在此问题之中要运用到函数的多次调用等等。
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;
for（i=0;ivexnum;i++）//循环执行条件是当u=V[i]时停止，求i值
{
if（strcmp（a,g->V[i]）==0）
returni;
}
if（i==g->vexnum）
return-1;
}
intcreatgraph（Graph*g）//创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵
{
inti=0,j,m,k,p;
chara[10],b[10];
printf（"*****欢迎使用本程序解决地铁建设问题*****\n"）;
printf（"*******请按照提示依次输入相关信息*******\n"）;
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;ivexnum;i++）
for（j=0;jvexnum;j++）
g->R[i][j]=INFINITY;//初始化
printf（"*请输入辖区之间的路程，以000为结束标志*\n"）;
scanf（"%s%s%d",a,b,&m）;//输入辖区结点及辖区之间的距离
while（strcmp（"0",a）!
=0||strcmp（"0",b）!
=0||m!
=0）
{
k=locatevex（g,a）;p=locatevex（g,b）;//查找a,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;//k到p和p到k之间的距离相同
scanf（"%s%s%d",a,b,&m）;//输入辖区结点及辖区之间的距离
}
return1;
}
structtree{
intweizhi;
intlowcost;
};
intminimun（structtree*a,Graphg）//求出第k辖区，此时i辖区与k辖区之间的距离最短
{
inti,k,m=0;
for（i=0;i{
if（m==0&&a[i].lowcost!
=0）
{
m=1;
k=i;
}
if（m==1&&a[i].lowcost!
=0）
{
if（a[i].lowcostk=i;
}
}
returnk;
}
voidMiniSpanTree_PRIM（Graphg,chara[10]）
{
structtreeclosedge[M];
inti,j,k,money=0;
k=locatevex（&g,a）;
for（i=0;i{
if（i!
=k）
{
closedge[i].lowcost=g.R[k][i];//两辖区k，i之间的距离
closedge[i].weizhi=k;//与辖区i相邻的最近的辖区设为辖区k
}
}
closedge[k].lowcost=0;//初始化，U={u}
printf（"********根据您的输入建立邻接表为:
********\n"）;
for（i=0;i{
for（j=0;j{
printf（"|%d|",g.R[i][j]）;
}
printf（"\n\n"）;
}
printf（"****得到应建设地铁的辖区及之间权值为:
****\n"）;
for（i=1;i{
k=minimun（closedge,g）;//求出最小生成树T的下一个结点，第k结点
money+=closedge[k].lowcost;
printf（"%d:
%s%s%d\n",i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost）;//输出生成树的边
closedge[k].lowcost=0;//第k顶点并入U集
for（j=0;j{
if（g.R[k][j]{
closedge[j].weizhi=k;
closedge[j].lowcost=g.R[k][j];
}
}
}
printf（"******据统计地铁的总建设路程为：
%d*******\n",money）;
}
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语言所具有的语句简洁，使用灵活，执行效率高等特点。
特别是对图这种数据结构有了深刻的理解。
参考文献
[1]严蔚敏，吴伟民编著.北京：
清华大学出版社，2007
[2]谭浩强编著.C程序设计（第二版）.北京：
清华大学出版社，2004
[3]谭浩强编著.C程序设计题解与上机指导（第二版）.北京：
清华大学出版社，1999
[4]姚诗斌.数据库系统基础.计算机工程与应用，1981年第8期
[5]谭浩强，张基温，唐永炎编著.C语言程序设计教程.北京：
高等教育出版社，1992
[6]丁峻岭编著.C语言程序设计.中国铁道出版社，2003
成绩评定
成绩教师签字
升级会员 