-
课程设计题目
题目0：校园最短路径问题
-
课程设计要求
GDOU是真是一个好地方，校园如一座大花园，美丽而宽广。校园有许多建筑如教学楼、饭堂、宿舍楼、图书馆、体育馆、运动场、商业街、医院等，还有一些著名的风景点。现请根据学校的平面图，找出一些重要的场所，画出学校的平面图（场所可以根据其重要性适当减少），根据实际画出不同点间的路径，并估算每两个场所间的路径长。请设计数据结构并编程，当给出一个出发点和要到达另外一个场所的信息时，请给出最佳路径，并输出路径相关信息。
- 分析
- 问题描述
图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。
校园最短路径问题中的数据元素有：
-
顶点数
- 边数
- 边的长度
- 实现要点
-
调试分析
- 本程序在求最短路径的问题上采用迪杰斯特拉算法解决，虽然该算法与弗洛伊德算法相比时间复杂度低，但每求一条最短路径都必须重新搜索一遍，在频繁查询时会导致查询效率低，而弗洛伊德算法只要计算一次，即可求得每一对顶点之间的最短路径，虽然时间复杂度为高，但以后每次查询只要查表即可，会极大地提高查询的效率，而且，弗洛伊德算法还支持带负权的图的最短路径的计算。由此可见，选用算法时必须综合各方面因素考虑。
- 由于功能函数较多，在编写程序时将函数逐个添加完成的，就是说，每增加一个函数，进行一次编译运行，此函数通过了再写下一个函数。或许这种方法比较麻烦，但当有错误时只要针对新加函数进行修改即可。同时，要充分利用软件所提供的调试功能，这也会大大减少编程人员的负担。
- 程序设计
- 概要设计
- 抽象数据类型图的定义如下：
ADT Graph{
数据对象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,sans-serif; font-size:10.5pt; font-style:normal; font-weight:normal; margin-top:0cm; margin-bottom:0pt"> 初始条件：图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,sans-serif; font-size:10.5pt; font-style:normal; font-weight:normal; margin-top:0cm; margin-bottom:0pt"> 操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,sans-serif; font-size:10.5pt; font-style:normal; font-weight:normal; margin-top:0cm; margin-bottom:0pt"> } ADT Graph
-
主程序
voidmain()
{
初始化；
while(“命令”!=“退出”)
Switch语句
接受命令（输入选择项序号）；
处理命令；
}
}
- 本程序运用函数的调用，只有两个模块，它们的调用关系为：
主程序模块
带权无向图模块
- 详细设计
typedef struct//图中顶点表示点，存放点名称
void PutOutVex(MGraph *G)//输出每个顶点的信息
void PutOutArc(MGraph *G)//输出每条边的信息
void Dijkstra(MGraph * G)//迪杰斯特拉算法求最短路径
void DeleteVex(MGraph *G)//删除某个顶点
void DeleteArc(MGraph *G)//删除某条边
void InsertArc(MGraph *G)//插入某条边
void main()//主函数
- 源程序代码
#include <stdio.h> #include <iostream.h> #include<stdlib.h> #include<conio.h> #include <malloc.h> #include<string.h> #define MAX 10000 #define MAXLEN 10 #define ADJTYPE int typedef struct //图中顶点表示点，存放点名称 { char name[30]; int num; }VEXTYPE; typedef struct { VEXTYPE vexs[MAXLEN]; //顶点的信息 ADJTYPE arcs[MAXLEN][MAXLEN]; //邻接矩阵 int vexnum,arcnum ; //顶点数和边数 }MGraph; MGraph b; MGraph InitGraph() { /*建立无向网的邻接矩阵结构*/ int i,j; MGraph G; G.vexnum =10; //存放顶点数 G.arcnum =24; //存放边点数 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," 第三饭堂"); strcpy(G.vexs[8].name," 第四饭堂"); strcpy(G.vexs[9].name," 校医院"); for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[i][j]=MAX; G.arcs[0][1]=395; G.arcs[0][2]=380; G.arcs[0][3]=504; G.arcs[0][4]=415; G.arcs[0][5]=703; G.arcs[0][6]=436; G.arcs[0][7]=840; G.arcs[0][8]=1000; G.arcs[0][9]=1100; G.arcs[1][2]=264; G.arcs[1][3]=170; G.arcs[1][4]=86; G.arcs[1][6]=81; G.arcs[2][3]=230; G.arcs[2][4]=209; G.arcs[2][5]=328; G.arcs[2][6]=310; G.arcs[3][4]=87; G.arcs[3][5]=295; G.arcs[3][6]=146; G.arcs[4][6]=102; G.arcs[5][7]=153; G.arcs[7][8]=393; G.arcs[7][9]=359; G.arcs[8][9]=645; for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[j][i]=G.arcs[i][j]; return G; } void Menu() //输出菜单 { cout<<" ********** 欢迎来到广东海洋大学 ********** \n"; cout<<" ┏━━━━━━━━━━━━━━━━━━━━┓\n"; cout<<" ┃ 0. 输出顶点(地点)的信息 ┃\n"; cout<<" ┃ 1. 输出边(路径)的信息 ┃\n"; cout<<" ┃ 2. 修改 ┃\n"; cout<<" ┃ 3. 求出最短路径 ┃\n"; cout<<" ┃ 4. 删除某个顶点(地点) ┃\n"; cout<<" ┃ 5. 删除某条边(路径) ┃\n"; cout<<" ┃ 6. 需要插入某条边(路径) ┃\n"; cout<<" ┃ 7. 退出系统 ┃\n"; cout<<" ┗━━━━━━━━━━━━━━━━━━━━┛\n"; } void PutOutVex(MGraph *G) //输出每个顶点的信息 { int v; for(v=0;v<G->vexnum;v++) cout<<G->vexs[v].num<<G->vexs[v].name<<endl; } void PutOutArc(MGraph *G) //输出每条边的信息 { for(int i=0;i<G->vexnum;i++) for(int j=0;j<G->vexnum;j++) if(G->arcs[i][j]<MAX) {cout<<" 从 " <<G->vexs[i].name<<" 到 "<<G->vexs[j].name<<"的距离是 "<<G->arcs[i][j]<<"米"<<endl; cout<<" ━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl; } } void Change(MGraph *G) //修改 { int v0,v1,length; cout<<"change\n"; cin>>v0; cin>>v1; cout<<"length:"; cin>>length; G->arcs[v0][v1]=G->arcs[v1][v0]=length; } void Dijkstra(MGraph * G) //迪杰斯特拉算法求最短路径 { int v,w,i,min,t=0,x,v0,v1; int final[40],D[40],p[40][40]; cout<<"请输入源顶点:\n"; cin>>v0; if(v0<0||v0>G->vexnum) { cout<<"此点编号不存在!请重新输入顶点编号:"; cin>>v0; } cout<<"请输入结束顶点:\n"; cin>>v1; if(v1<0||v1>G->vexnum) { cout<<"此点编号不存在!请重新输入顶点编号:"; cin>>v1; } for(v=0;v<G->vexnum;v++) {// 初始化final[40],p[40][40],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<G->vexnum;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;i<G->vexnum;i++) { min=MAX; for(w=0;w<G->vexnum;w++) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=1; for(w=0;w<G->vexnum;w++) if(!final[w]&&(min+G->arcs[v][w]<D[w])) { D[w]=min+G->arcs[v][w]; for(x=0;x<G->vexnum;x++) p[w][x]=p[v][x]; p[w][w]=1; } } cout<<" 从 "<<G->vexs[v0].name<<" 到 "<<G->vexs[v1].name<<" 的最短路径长度为："<<D[v1]<<"米"<<endl; cout<<" 路径为："; for(int j=0;j<G->vexnum;j++) { if(p[v1][j]==1) cout<<G->vexs[j].name<<endl; } } void DeleteVex(MGraph *G) //删除某个顶点 { int row,col; int v0; cout<<"请输入要删除的顶点"; cin>>v0; for(int i=v0;i<G->vexnum;i++) G->vexs[i]=G->vexs[i+1]; G->vexnum--; for(row=0;row<G->vexnum;row++) { for(col=v0;col<G->vexnum;col++) G->arcs[row][col]=G->arcs[row][col+1]; } for(col=0;col<G->vexnum;col++) { for(row=v0;row<G->vexnum;row++) G->arcs[col][row]=G->arcs[col][row+1]; } } void DeleteArc(MGraph *G) //删除某条边 { int v0,v1; cout<<"请输入两顶点:\n"; cin>>v0>>v1; G->arcs[v0][v1]=MAX; G->arcs[v1][v0]=MAX; } void InsertArc(MGraph *G) //插入某条边 { int v0,l=0; cout<<"请输入两顶点:\n"; cin>>v0>>v1; cout<<"请输入路径长度:\n"; cin>>l; G->arcs[v0][v1]=l; G->arcs[v1][v0]=l; } void main() //主函数 { int a; b=InitGraph(); Menu(); cin>>a; while(a!=7) { switch(a) { case 0:PutOutVex(&b);Menu();break; case 1:PutOutArc(&b);Menu();break; case 2:Change(&b);Menu();break; case 3:Dijkstra(&b);Menu();break; case 4:DeleteVex(&b);Menu();break; case 5:DeleteArc(&b);Menu();break; case 6:InsertArc(&b);Menu();break; case 7:exit(1);break; default:break; } cin>>a; } }
- 调试结果
输出顶点（地点）信息
输出边（路径）的信息
求出最短路径
删除某个顶点（地点）
删除某条边（路径）
需要插入某条边（路径）
退出系统
- 总结体会
课程设计是培养学生综合运用所学知识，发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。通过这次课程设计，使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，将结论用于实践，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到了很多问题，可以说得是困难重重，但这是不可避免的。在这次课程设计的过程中，我发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，知识面太窄。由于编程水平有限，其中迪杰斯特拉算法的C++程序是参考网上的资料，有关校园地图的输出也没有实现。我想在以后的学习中，我要更注重实践这一环节。
