《大数据结构,课程设计,校园最短路径问题》由会员分享，可在线阅读，更多相关《大数据结构,课程设计,校园最短路径问题（17页珍藏版）》请在金锄头文库上搜索。
1、一、课程设计题目： 校园最短路径问题二、课程设计目的：1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法 和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具 备的科学工作方法和作风。三、课程设计要求：1. 设计的题目要求达到一定的工作量( 300 行以上代码)，并具有一定的深度和 难度。2. 编写出课程设计报告书，内容不少于 10 页(代码不算)。四、需求分析 ：1、问题描述图的最短路径问题是指从指定的某一点
2、 v 开始，求得从该地点到图中其它各 地点的最短路径， 并且给出求得的最短路径的长度及途径的地点。 除了完成最短 路径的求解外， 还能对该图进行修改， 如顶点以及边的增删、 边上权值的修改等。校园最短路径问题中的数据元素有：a) 顶点数b) 边数c) 边的长度2、功能需求要求完成以下功能：a) 输出顶点信息：将校园内各位置输出。b) 输出边的信息：将校园内每两个位置(若两个位置之间有直接路径)的 距离输出。c) 修改：修改两个位置(若两个位置之间有直接路径)的距离，并重新输 出每两个位置(若两个位置之间有直接路径)的距离。d) 求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出 任
3、意一点与其它各点的最短路径。e) 删除：删除任意一条边。f) 插入：插入任意一条边。3、实现要点a) 对图的创建采用邻接矩阵的存储结构， 而且对图的操作设计成了模板类。 为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。b) 为了便于访问，用户可以先输出所有的地点和距离。c) 用户可以随意修改两点之间好的距离。d) 用户可以增加及删除边。e) 当用户操作错误时，系统会出现出错提示。五、概要设计 :1. 抽象数据类型图的定义如下：ADT Graph数据对象 V：V 是具有相同特性数据元素的集合，称为顶点集。 数据关系 R：R=VRVR= (v, w) | v , w V, (v , w)
4、 表示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。De
5、leteVex(&G, v)初始条件：图G存在，v和G中顶点具有相同特征。操作结果：删除G中顶点v及其相关的边。InsertArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧v,w,若G是无向的，则还增添对称弧DeleteArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧v,w，若G是无向的，则还删除对称弧 ADT Graph2. 主程序void main()初始化；while( “命令” != “退出” )Switch 语句 接受命令(输入选择项序号) ； 处理命令；否则返回。3.本程序运用函数的调用，只有两个模
6、块，它们的调用关系为: 主程序模块带权无向图模块六、详细设计(详细见下面的源代码)typedef struct/void Me nu()/void PutOutVex(MGraph *G)/void PutOutArc(MGraph *G)/void Dijkstra(MGraph * G)/void DeleteVex(MGraph *G)/void DeleteArc(MGraph *G)/void In sertArc(MGraph *G)/void mai n()/七、源程序代码#include #include #in clude#in clude#include #i nclude
7、 #defi ne MAX 10000 #defi ne MAXLEN 8 #defi ne ADJTYPE int typedef struct/ char n ame30;int num;VEXTYPE;typedef structVEXTYPE vexsMAXLEN;/ADJTYPE arcsMAXLENMAXLEN; / int vex nu m,arc num ;/MGraph;MGraph b;MGraph Ini tGraph() /*int i, j;MGraph G;G.vex num =8;/G.arcnum =13;/for(i=0;iG.vex nu m;i+)图中顶点
8、表示点，存放点名称 输出菜单输出每个顶点的信息输出每条边的信息迪杰斯特拉算法求最短路径 删除某个顶点 删除某条边插入某条边主函数图中顶点表示点，存放点名称顶点的信息邻接矩阵顶点数和边数建立无向网的邻接矩阵结构*/存放顶点数存放边点数G.vexsi.num=i; strcpy(G.vexs0.name, 第四教学楼 ); strcpy(G.vexs1.name, 第三教学楼 ); strcpy(G.vexs2.name, 图书馆 ); strcpy(G.vexs3.name, 食堂 ); strcpy(G.vexs4.name, 第一教学楼 ); strcpy(G.vexs5.name, 第二教
9、学楼 ); strcpy(G.vexs6.name, 综合实验楼 ); strcpy(G.vexs7.name, 校医院 ); for(i=0;iG.vexnum;i+) for(j=0;jG.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; f
10、or(i=0;iG.vexnum;i+)输出菜单输出每个顶点的信息for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij; return G; void Menu() / cout 需要输出顶点的信息请按 0n; cout 需要边的信息输出请按 1n; cout 需要修改请按 2n; cout 需要求出最短路径请按 3n; cout 需要删除某个顶点请按 4n; cout 需要删除某条边请按 5n; cout 需要插入某条边请按 6n; cout 需要退出请按 7n;void PutOutVex(MGraph *G)/ int v;for(v=0;vvexnum;v+)
11、coutvexsv.numvexsv.nameendl;void PutOutArc(MGraph *G) / 输出每条边的信息for(int i=0;ivexnum;i+)for(int j=0;jvexnum;j+) if(G-arcsijMAX)cout 从 vexsi.name 到 vexsj.namearcsijendl;void Change(MGraph *G) / 修改 int v0,v1,length; coutv0; cinv1;coutlength;G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G)/ 迪杰斯特拉算
12、法求最短路径int v,w,i,min,t=0,x,v0,v1;int final20, D20, p2020; coutv0;if(v0G-vexnum)coutv0;coutv1;if(v1G-vexnum)coutv1; for(v=0;vvexnum;v+)/ 初始化 final20,p2020,finalv=1 即已经求得 v0 到 v 的最短路径， /pvw=1 则是 w 从 v0 到 v 当前求得最短路径上的顶点， Dv 带权长度 finalv=0;Dv=G-arcsv0v;for(w=0;wvexnum;w+)pvw=0;if(DvMAX)pvv0=1;pvv=1;Dv0=0;finalv0=1;for(i=1;ivexnum;i+)min=MAX;for(w=0;wvexnum;w+)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;wvexnum;w+)if(!finalw&(min+G-arcsvwarcsvw;for(x=0;xvexnum;x+)pwx=pvx;pww=1;cout 从 vexsv0
