大数据结构课程设计校园最短路径问题Word文件下载.docx
- 文档编号:4469982
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:19
- 大小:337.08KB
大数据结构课程设计校园最短路径问题Word文件下载.docx
《大数据结构课程设计校园最短路径问题Word文件下载.docx》由会员分享,可在线阅读,更多相关《大数据结构课程设计校园最短路径问题Word文件下载.docx(19页珍藏版)》请在冰点文库上搜索。
为了便于处理,对于图中的每一个顶点和每一条边都设置了初值。
b)为了便于访问,用户可以先输出所有的地点和距离。
c)用户可以随意修改两点之间好的距离。
d)用户可以增加及删除边。
e)当用户操作错误时,系统会出现出错提示。
五、概要设计:
1.抽象数据类型图的定义如下:
ADTGraph{
数据对象V:
V是具有相同特性数据元素的集合,称为顶点集。
数据关系R:
R={VR}
VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在路径}
基本操作P:
CreatGraph(&
G,V,VR)
初始条件:
V是图的顶点集,VR是图中边的集合。
操作结果:
按定义(V,VR)构造图G。
DestroyGraph(&
G)
图G已存在。
销毁图。
LocateVex(G,u)
图G存在,u和G中顶点具有相同特征。
若G中存在顶点u,则返回该顶点在图中“位置”;
否则返回
其它信息。
GetVex(G,v)
图G存在,v是G中某个顶点。
返回v的信息。
InsertVex(&
G,v)
图G存在,v和G中顶点具有相同特征。
在图G中增添新顶点v。
DeleteVex(&
G,v)
删除G中顶点v及其相关的边。
InsertArc(&
G,v,w)
图G存在,v和w是G中两个顶点。
在G中增添弧<
v,w>
,若G是无向的,则还增添对称弧<
w,v>
。
DeleteArc(&
G,v,w)
在G中删除弧<
,若G是无向的,则还删除对称弧<
}ADTGraph
2.主程序
voidmain()
{
初始化;
while(“命令”!
=“退出”)
Switch语句
接受命令(输入选择项序号);
处理命令;
}
}
3.本程序运用函数的调用,只有两个模块,它们的调用关系为:
主程序模块
带权无向图模块
六、详细设计
(详细见下面的源代码)
typedefstruct//图中顶点表示点,存放点名称
voidMenu()//输出菜单
voidPutOutVex(MGraph*G)//输出每个顶点的信息
voidPutOutArc(MGraph*G)//输出每条边的信息
voidDijkstra(MGraph*G)//迪杰斯特拉算法求最短路径
voidDeleteVex(MGraph*G)//删除某个顶点
voidDeleteArc(MGraph*G)//删除某条边
voidInsertArc(MGraph*G)//插入某条边
voidmain()//主函数
七、源程序代码
#include<
stdio.h>
iostream.h>
#include<
stdlib.h>
conio.h>
malloc.h>
string.h>
#defineMAX10000
#defineMAXLEN8
#defineADJTYPEint
typedefstruct//图中顶点表示点,存放点名称
{
charname[30];
intnum;
}VEXTYPE;
typedefstruct
VEXTYPEvexs[MAXLEN];
//顶点的信息
ADJTYPEarcs[MAXLEN][MAXLEN];
//邻接矩阵
intvexnum,arcnum;
//顶点数和边数
}MGraph;
MGraphb;
MGraphInitGraph()
{/*建立无向网的邻接矩阵结构*/
inti,j;
MGraphG;
G.vexnum=8;
//存放顶点数
G.arcnum=13;
//存放边点数
for(i=0;
i<
G.vexnum;
i++)
G.vexs[i].num=i;
strcpy(G.vexs[0].name,"
第四教学楼"
);
strcpy(G.vexs[1].name,"
第三教学楼"
strcpy(G.vexs[2].name,"
图书馆"
strcpy(G.vexs[3].name,"
食堂"
strcpy(G.vexs[4].name,"
第一教学楼"
strcpy(G.vexs[5].name,"
第二教学楼"
strcpy(G.vexs[6].name,"
综合实验楼"
strcpy(G.vexs[7].name,"
校医院"
for(j=0;
j<
j++)
G.arcs[i][j]=MAX;
G.arcs[0][1]=130;
G.arcs[0][2]=80;
G.arcs[0][3]=260;
G.arcs[1][3]=75;
G.arcs[2][4]=50;
G.arcs[3][4]=120;
G.arcs[1][5]=265;
G.arcs[3][5]=85;
G.arcs[3][6]=400;
G.arcs[4][6]=350;
G.arcs[5][6]=120;
G.arcs[4][7]=200;
G.arcs[6][7]=150;
G.arcs[j][i]=G.arcs[i][j];
returnG;
{cout<
<
"
需要输出顶点的信息请按0\n"
;
cout<
需要边的信息输出请按1\n"
需要修改请按2\n"
需要求出最短路径请按3\n"
需要删除某个顶点请按4\n"
需要删除某条边请按5\n"
需要插入某条边请按6\n"
需要退出请按7\n"
}
intv;
for(v=0;
v<
G->
vexnum;
v++)
vexs[v].num<
vexs[v].name<
endl;
for(inti=0;
for(intj=0;
if(G->
arcs[i][j]<
MAX)
{cout<
从"
<
vexs[i].name<
到"
vexs[j].name<
voidChange(MGraph*G)//修改
{intv0,v1,length;
change\n"
cin>
>
v0;
v1;
length:
length;
G->
arcs[v0][v1]=G->
arcs[v1][v0]=length;
intv,w,i,min,t=0,x,v0,v1;
intfinal[20],D[20],p[20][20];
请输入源顶点:
\n"
if(v0<
0||v0>
vexnum)
{
此点编号不存在!
请重新输入顶点编号:
}
请输入结束顶点:
if(v1<
0||v1>
for(v=0;
{//初始化final[20],p[20][20],final[v]=1即已经求得v0到v的最短路径,
//p[v][w]=1则是w从v0到v当前求得最短路径上的顶点,D[v]带权长度
final[v]=0;
D[v]=G->
arcs[v0][v];
for(w=0;
w<
w++)
p[v][w]=0;
if(D[v]<
MAX)
p[v][v0]=1;
p[v][v]=1;
D[v0]=0;
final[v0]=1;
for(i=1;
min=MAX;
if(!
final[w])
if(D[w]<
min){v=w;
min=D[w];
final[v]=1;
final[w]&
&
(min+G->
arcs[v][w]<
D[w]))
D[w]=min+G->
arcs[v][w];
for(x=0;
x<
x++)
p[w][x]=p[v][x];
p[w][w]=1;
vexs[v0].name<
vexs[v1].name<
的最短路径长度为:
D[v1]<
路径为:
j++)
{
if(p[v1][j]==1)
introw,col;
intv0;
请输入要删除的顶点"
for(inti=v0;
i++)
G->
vexs[i]=G->
vexs[i+1];
vexnum--;
for(row=0;
row<
row++)
{
for(col=v0;
col<
col++)
G->
arcs[row][col]=G->
arcs[row][col+1];
}
for(col=0;
for(row=v0;
G->
arcs[col][row]=G->
arcs[col][row+1];
intv0,v1;
请输入两顶点:
v0>
arcs[v0][v1]=MAX;
arcs[v1][v0]=MAX;
intv0,v1,l=0;
请输入路径长度:
l;
arcs[v0][v1]=l;
arcs[v1][v0]=l;
{inta;
b=InitGraph();
Menu();
a;
while(a!
=7)
switch(a)
case0:
PutOutVex(&
b);
Menu();
break;
case1:
PutOutArc(&
case2:
Change(&
case3:
Dijkstra(&
case4:
case5:
case6:
case7:
exit
(1);
default:
八、调试分析
1)本程序在求最短路径的问题上采用迪杰斯特拉算法解决,虽然该算法与弗洛伊德算法相比时间复杂度低,但每求一条最短路径都必须重新搜索一遍,在频繁查询时会导致查询效率低,而弗洛伊德算法只要计算一次,即可求得每一对顶点之间的最短路径,虽然时间复杂度为高,但以后每次查询只要查表即可,会极大地提高查询的效率,而且,弗洛伊德算法还支持带负权的图的最短路径的计算。
由此可见,选用算法时必须综合各方面因素考虑。
2)由于功能函数较多,在编写程序时将函数逐个添加完成的,就是说,每增加一个函数,进行一次编译运行,此函数通过了再写下一个函数。
或许这种方法比较麻烦,但当有错误时只要针对新加函数进行修改即可。
同时,要充分利用软件所提供的调试功能,这也会大大减少编程人员的负担。
九、调试结果
a)开始界面
b)输出顶点信息
c)输出边的信息
d)修改
e)求最短路径
f)删除某一顶点
g)删除某条边
h)插入某条边
i)退出
十、总结及体会
课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。
通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,将结论用于实践,从而提高自己的实际动手能力和独立思考的能力。
在设计的过程中当然遇到了问题,可以说得是困难重重,毕竟这是不可避免的,同时在设计的过程中发现了自己的不足之处,对以前所学过的知识理解得不够深刻,掌握得不够牢固。
当指导老师提到用动态数组和链接表来解决这一问题时,我却一头雾水,才发现自己的知识面太窄。
由于编程水平有限,其中迪杰斯特拉算法的C++程序是参考网上的资料,还有顶点的插入设计中没有体现。
我想在以后的学习中,要更注重实践这一环节。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 校园 路径 问题
![提示](https://static.bingdoc.com/images/bang_tan.gif)