数据结构课程设计校园最短路径问题

1、一、课程设计题目： 校园最短路径问题二、课程设计目的：1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规进行软件开发，培养软件工作者所具备的科学工作方法和作风。三、课程设计要求：1. 设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和难度。2. 编写出课程设计报告书，容不少于10页（代码不算）。四、需求分析 ：1、问题描述图的最短路径问题是指从指定的某一点v开始，求得从该地

2、点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。校园最短路径问题中的数据元素有：a) 顶点数b) 边数c) 边的长度2、功能需求 要求完成以下功能：a) 输出顶点信息：将校园各位置输出。b) 输出边的信息：将校园每两个位置（若两个位置之间有直接路径）的距离输出。c) 修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离。d) 求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出任意一点与其它各点的最短路径。e) 删除：删除

3、任意一条边。f) 插入：插入任意一条边。3、实现要点 a) 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。 b) 为了便于访问，用户可以先输出所有的地点和距离。 c) 用户可以随意修改两点之间好的距离。 d) 用户可以增加及删除边。 e) 当用户操作错误时，系统会出现出错提示。五、概要设计:1. 抽象数据类型图的定义如下：ADT Graph数据对象V：V是具有相同特性数据元素的集合，称为顶点集。数据关系R：R=VRVR=（v，w）| v , wV, (v , w)表示v和w之间存在路径基本操作P：CreatGraph(

4、&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(&

5、amp;G, v)初始条件： 图G存在，v和G中顶点具有相同特征。操作结果： 删除G中顶点v及其相关的边。InsertArc(&G, v, w) 初始条件： 图G存在，v和w是G中两个顶点。操作结果： 在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>。DeleteArc(&G, v, w)初始条件： 图G存在，v和w是G中两个顶点。操作结果： 在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>。 ADT Graph2. 主程序void main() 初始化； while(“命令”!=“退出”) Switc

6、h语句 接受命令（输入选择项序号）； 处理命令； 3. 本程序运用函数的调用，只有两个模块，它们的调用关系为：主程序模块带权无向图模块六、详细设计（详细见下面的源代码）typedef struct /图中顶点表示点，存放点名称void Menu() /输出菜单void PutOutVex(MGraph *G) /输出每个顶点的信息void PutOutArc(MGraph *G) /输出每条边的信息void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路径void DeleteVex(MGraph *G) /删除某个顶点void DeleteArc(MGraph *G) /

7、删除某条边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 8 #define ADJTYPE int typedef struct /图中顶点表示点，存放点名称 cha

8、r name30; int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /顶点的信息 ADJTYPE arcsMAXLENMAXLEN; /邻接矩阵 int vexnum,arcnum ; /顶点数和边数 MGraph;MGraph b; MGraph InitGraph() /*建立无向网的邻接矩阵结构*/ int i, j; MGraph G; G.vexnum =8; /存放顶点数G.arcnum =13; /存放边点数 for(i=0;i<G.vexnum;i+) G.vexsi.num=i; strcpy(G.vexs0.n

9、ame,"第四教学楼"); strcpy(G.,"第三教学楼"); strcpy(G.,"图书馆"); strcpy(G.,"食堂"); strcpy(G.,"第一教学楼"); strcpy(G.,"第二教学楼"); strcpy(G.,"综合实验楼"); strcpy(G.,"校医院"); for

10、(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij=MAX;G.arcs01=130;G.arcs02=80; G.arcs03=260; G.arcs13=75; G.arcs24=50; G.arcs34=120; G.arcs15=265; G.arcs35=85; G.arcs36=400; G.arcs46=350; G.arcs56=120; G.arcs47=200; G.arcs67=150; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsji=

11、G.arcsij;return G;void Menu() /输出菜单 cout<<"需要输出顶点的信息请按0n" cout<<"需要边的信息输出请按1n" cout<<"需要修改请按2n" cout<<"需要求出最短路径请按3n" cout<<"需要删除某个顶点请按4n" cout<<"需要删除某条边请按5n" cout<<"需要插入某条边请按6n" cout<&l

12、t;"需要退出请按7n" void PutOutVex(MGraph *G) /输出每个顶点的信息int v; for(v=0;v<G->vexnum;v+) cout<<G->vexsv.num<<G-><<endl; void PutOutArc(MGraph *G) /输出每条边的信息for(int i=0;i<G->vexnum;i+) for(int j=0;j<G->vexnum;j+) if(G->arcsij<MAX) cout<<

13、"从" <<G-><<"到"<<G-><<G->arcsij<<endl; void Change(MGraph *G) /修改 int v0,v1,length; cout<<"changen" cin>>v0; cin>>v1; cout<<"length:" cin>>length; G->arcsv0v1=G->arcs

14、v1v0=length;void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路径 int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; cout<<"请输入源顶点:n" cin>>v0; if(v0<0|v0>G->vexnum) cout<<"此点编号不存在!请重新输入顶点编号:" cin>>v0; cout<<"请输入结束顶点:n" cin>>v1; if(v1<0

15、|v1>G->vexnum) cout<<"此点编号不存在!请重新输入顶点编号:" cin>>v1; for(v=0;v<G->vexnum;v+) / 初始化final20,p2020,finalv=1即已经求得v0到v的最短路径， /pvw=1则是w从v0到v当前求得最短路径上的顶点，Dv带权长度 finalv=0; Dv=G->arcsv0v; for(w=0;w<G->vexnum;w+) pvw=0; if(Dv<MAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(

16、i=1;i<G->vexnum;i+) min=MAX; for(w=0;w<G->vexnum;w+) if(!finalw) if(Dw<min)v=w;min=Dw; finalv=1; for(w=0;w<G->vexnum;w+) if(!finalw&&(min+G->arcsvw<Dw) Dw=min+G->arcsvw; for(x=0;x<G->vexnum;x+) pwx=pvx; pww=1; cout<<"从"<<G->vexsv0.

17、name<<"到"<<G-><<"的最短路径长度为："<<Dv1<<endl; cout<<"路径为：" for(int j=0;j<G->vexnum;j+) if(pv1j=1) cout<<G-><<endl; void DeleteVex(MGraph *G) /删除某个顶点int row,col;int v0;cout<<"请输入要删除的顶点&

18、quot;cin>>v0;for(int i=v0;i<G->vexnum;i+)G->vexsi=G->vexsi+1;G->vexnum-;for(row=0;row<G->vexnum;row+)for(col=v0;col<G->vexnum;col+)G->arcsrowcol=G->arcsrowcol+1;for(col=0;col<G->vexnum;col+)for(row=v0;row<G->vexnum;row+)G->arcscolrow=G->arcsco

19、lrow+1;void DeleteArc(MGraph *G) /删除某条边 int v0,v1; cout<<"请输入两顶点:n" cin>>v0>>v1; G->arcsv0v1=MAX; G->arcsv1v0=MAX;void InsertArc(MGraph *G) /插入某条边 int v0,v1,l=0; cout<<"请输入两顶点:n" cin>>v0>>v1; cout<<"请输入路径长度:n" cin>>l

20、; G->arcsv0v1=l; G->arcsv1v0=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; 八、调试分析 1) 本程序在求最短路径的问题上采用迪杰斯特拉算法解决，虽然该算法与弗洛伊德算法相比时间复杂度低，但每求一条最短路径都必须重新搜索一遍，在频繁查询