数据结构课程设计地铁建设问题.docx
《数据结构课程设计地铁建设问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计地铁建设问题.docx（24页珍藏版）》请在冰点文库上搜索。
数据结构课程设计地铁建设问题
软件学院
课程设计报告书
课程名称数据结构
设计题目地铁建设问题
专业班级
学号
姓名
指导教师
2013年1月
1设计时间................................................2
2设计目的................................................2
3设计任务................................................2
4设计内容................................................2
4.1需求分析...............................................2
4.1.1程序所能达到的功能...................................2
4.1.2输入、输出的形式和输入值的范围........................2
4.1.3测试数据.............................................3
4.2总体设计...............................................3
4.2.1抽象数据类型定义.....................................3
4.2.2主程序的流程、模块之间的调用关系......................4
4.3详细设计...............................................5
4.3.1数据类型、函数的伪码算法.............................5
4.3.2函数的调用关系图.....................................9
4.4测试与分析............................................10
4.4.1测试................................................10
4.4.2分析................................................11
4.5附录.................................................11
5总结与展望.............................................16
参考文献.................................................17
成绩评定.................................................17
1设计时间
2012年1月21日——2012年1月25日
2设计目的
1.通过这次设计，在数据结构的逻辑结构和存储结构、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解
2.训练程序设计方法以及上机操作等基本技能，积累编程经验
3.培养用计算机解决实际问题的能力
3设计任务
某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。
4设计内容
4.1需求分析
4.1.1程序所能达到的功能
城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要编写程序合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。
（1）使用结构体数组，存储辖区名称
（2）建立辖区间直接距离的无向图，用邻接矩阵存储辖区间直接距离信息
（2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线
（3）输出应该建设的路线，以及所需建设的总里程信息
4.1.2输入、输出的形式和输入值的范围
输出的形式和输入值的范围
输入数字和字母，字母为辖区名，数字为辖区间直接距离，名称个数o，0<线路个数输出的形式
1：
辖区名辖区名路程
2：
辖区名辖区名路程
3：
辖区名辖区名路程
总费用为：
路程的和
4.1.3测试数据
正确输入：
辖区个数：
4
名称abcd
线路起止辖区及直接距离：
ab3、ac5、ad4、bc2、bd3、cd2、000
开始辖区：
a
输出为：
1：
ab3
2：
bc2
3：
cd2
总费用：
7
错误输入：
辖区个数：
4
名称abcd
线路及之间距离：
asb3
输出为：
没有as这个辖区
4.2总体设计
4.2.1抽象数据类型定义
1．抽象数据类型图的定义
ADTGraph{
数据对象v：
v是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：
R={VR}
VR={|v,w∈V且P（v，w），表示从v到w的弧，
谓词P（v,w）定义了弧的意义或信息}
基本操作P：
CreateGraph（&G,V,VR）；
初始条件：
V是图的顶点集，VR是图中弧的集合。
操作结果：
按V和VR的定义构造图G。
}ADTGraph
4.2.2主程序的流程、模块之间的调用关系
主程序的流程
模块之间的调用关系
（1）主函数main（）调用intcreatgraph（Graph*g）建立无向图，用邻接矩阵存储；
（2）voidMiniSpanTree_PRIM（Graphg,chara[10]）调用intminimun（structtree*a,Graphg）和intlocatevex（Graph*g,chara[10]）生成树，判断辖区名称输入是否正确；
（3）主函数main（）调用voidMiniSpanTree_PRIM（Graphg,chara[10]）计算最小生成树，输出最优线路和总里程。
4.3详细设计
4.3.1数据类型、函数的伪码算法
1．结构体类型
typedefstruct{
charV[M][10];
intR[M][M];
intvexnum;
}Graph;
2．函数算法
创建无向图
intlocatevex（Graph*g,chara[10]）
{
inti;
for（i=0;ivexnum;i++）
{
if（strcmp（a,g->V[i]）==0）
returni;
}
if（i==g->vexnum）
return-1;
}
intcreatgraph（Graph*g）
{
inti=0,j,m,k,p,o,e;
chara[10],b[10];
printf（"设置辖区的个数:
"）;//城市中辖区的个数
scanf（"%d",&o）;
for（i=0;i{
printf（"第%d个城市辖区名称为:
",i+1）;
scanf（"%s",g->V[i]）;
}
g->vexnum=o;
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）;
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=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];
closedge[i].weizhi=k;
}
}
closedge[k].lowcost=0;
for（i=1;i{
k=minimun（closedge,g）;
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;
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.2函数的调用关系图
4.4测试与分析
4.4.1测试
1．正确的输入
2．错误的输入
4.4.2分析
调试过程中遇到的问题及其解决方法
（1）问题:
用for循环语句控制输入辖区名称及输出辖区名称时候的个数名不对应
解决方法:
数组下标时从零开始的，并且在for循环语句中,循环变量的执行次数总是比循环体的执行次数多一次，所以应该注意修改使其相对应
（2）问题：
用循环控制各辖区及其之间的距离没有考虑清楚
解决方法：
用输入000判定辖区及其直接距离数据输入完毕
（3）问题：
普利姆算法理解不透彻，用其计算最小生成树输出结果的时候出现问题
解决方法：
上网查阅资料及阅读课本询问同学，并在以前程序上加以修改，最终得以运行。
4.5附录
#include
#defineINF32767
typedefintInfoType;
#defineMAXV100
typedefstruct
{
intadj;
InfoType*info;
}ArcCell,AdjMatrix[MAXV][MAXV];
typedefstruct
{
intedges[MAXV][MAXV];
intn,e;
intvexs[MAXV];
}MGraph;
typedefstructANode
{
intadjvex;
structANode*nextarc;
InfoTypeinfo;
}ArcNode;
typedefintVertex;
typedefstructVnode
{
Vertexdata;
ArcNode*firstarc;
}VNode;
typedefVNodeAdjList[MAXV];
typedefstruct
{
AdjListadjlist;
intn,e;
}ALGraph;
intsum=0;
intLocatevex（MGraphg,intA）
{
inti;
for（i=0;i{
if（A==g.vexs[i]）
returni;
}
if（i==g.n）
return-1;
}
intCreateMgraph（MGraph&g）
{
inti,j,k,w,v1,v2;
printf（"请输入辖区个数和单个路径的个数:
\n"）;
scanf（"%d%d",&g.n,&g.e）;
printf（"输入各个辖区编号:
\n"）;
for（i=0;iscanf（"%d",&g.vexs[i]）;
for（i=0;ifor（j=0;jg.edges[i][j]=INF;
printf（"输入各辖区编号间的路径长度:
"）;
for（k=0;k{
scanf（"%d%d%d",&v1,&v2,&w）;
i=Locatevex（g,v1）;
j=Locatevex（g,v2）;
g.edges[i][j]=g.edges[j][i]=w;
}
return1;
}
voidDispMat（MGraphg）//输出邻接矩阵
{
inti,j;
for（i=0;i{
for（j=0;jif（g.edges[i][j]==INF）
printf（"%3s","∞"）;
else
printf（"%3d",g.edges[i][j]）;
printf（"\n"）;
}
}
voidPrim（MGraphg,intv）
{
intlowcost[MAXV],min,n=g.n;
intclosest[MAXV],i,j,k;
for（i=0;i{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for（i=1;i{
min=INF;
for（j=0;jif（lowcost[j]!
=0&&lowcost[j]{
min=lowcost[j];
k=j;
}
printf（"应建设的辖区（%d,%d）辖区的花费为:
%d\n",closest[k],k,min）;
if（min!
=INF）
sum+=min;
lowcost[k]=0;
for（j=0;jif（g.edges[k][j]!
=0&&g.edges[k][j]{
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
printf（"建设铁路线的最低费用为:
%d\n",sum）;
}
voidmain（）
{
inti,j;
MGraphg;
CreateMgraph（g）;
printf（"\n"）;
printf（"辖区图的邻接矩阵:
\n"）;
DispMat（g）;
printf（"\n"）;
printf（"普里姆算法结果:
\n"）;
Prim（g,0）;
printf（"\n"）;
}5总结与展望
这次课程设计任务是我在大学以来的遇到的第一次课程设计，刚开始看到题目的时候看起来不是很难，但是在实际编程操作中遇到了很多的问题，不过，在不断地遇到和解决问题的过程中，学到了很多的知识。
通过这一周的课程设计，加深了我对《数据结构》这门课程所学内容的进一步的理解与掌握。
同时，通过设计程序解决地铁建设问题，让我明白学习知识不仅仅是要学习课本上的内容，还要从实际生活中学习课外的知识，把书本上的知识与现实生活好好的结合在一起。
并且在查阅资料和完成设计的同时，我初步的了解了我们所学的课本知识在实际中的应用。
同时，这次课程设计进一步锻炼了我的编写程序的能力，和同学的合作交流也让自己学到了更多，发现自己在实际问题分析中的不足。
在编写程序的过程中，我更深切的认识到了认真、仔细、耐心的重要性，比如，就不能忽略循环时的控制变量。
在本次课程设计中，主要运用了图的知识解决实际问题。
同过这次的应用实践，让我体会到了图之所以能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，也就是想要把生活中的信息用计算机表达出来，首先就得把他们数字化，具体化成计算机能够识别的信息。
所以，我需要学习更多的专业知识以便用计算机更好的解决现实生活中遇到的问题。
这次课程设计时虽然遇到了好多的问题，但是还会有意外的收获。
这次就不仅练习了动手能力、综合能力，还巩固了专业知识，收获了很多。
参考文献
[1].谭浩强.C程序设计教程.北京:
清华大学出版社.2007.07
[2].严蔚敏.数据结构（C语言）.清华大学出版社.2010.3
[3].高维春主编.C语言程序设计项目教程.北京:
人民邮电出版社.2010.05
[4].谭浩强.C程序设计题解与上机指导（第三版）[M].北京:
清华大学出版社.2007
成绩评定
成绩教师签字
升级会员 