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

一、课程设计题目：校园最短路径问题二、课程设计目的：1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具备的科学工作方法和作风。三、课程设计要求：1.设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和难度。2.编写出课程设计报告书，内容不少于10页（代码不算）。四、需求分析：1、问题描述图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。校园最短路径问题中的数据元素有：a)顶点数b)边数c)边的长度2、功能需求要求完成以下功能：a)输出顶点信息：将校园内各位置输出。b)输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。c)修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离。d)求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出任意一点与其它各点的最短路径。e)删除：删除任意一条边。f)插入：插入任意一条边。3、实现要点a)对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。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和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。}ADTGraph2.主程序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()//主函数七、源程序代码#includestdio.h#includeiostream.h#includestdlib.h#includeconio.h#includemalloc.h#includestring.h#defineMAX10000#defineMAXLEN8#defineADJTYPEinttypedefstruct//图中顶点表示点，存放点名称{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;iG.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(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;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;for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[j][i]=G.arcs[i][j];returnG;}voidMenu()//输出菜单{cout需要输出顶点的信息请按0\n;cout需要边的信息输出请按1\n;cout需要修改请按2\n;cout需要求出最短路径请按3\n;cout需要删除某个顶点请按4\n;cout需要删除某条边请按5\n;cout需要插入某条边请按6\n;cout需要退出请按7\n;}voidPutOutVex(MGraph*G)//输出每个顶点的信息{intv;for(v=0;vG-vexnum;v++)coutG-vexs[v].numG-vexs[v].nameendl;}voidPutOutArc(MGraph*G)//输出每条边的信息{for(inti=0;iG-vexnum;i++)for(intj=0;jG-vexnum;j++)if(G-arcs[i][j]MAX){cout从G-vexs[i].name到G-vexs[j].nameG-arcs[i][j]endl;}}voidChange(MGraph*G)//修改{intv0,v1,length;coutchange\n;cinv0;cinv1;coutlength:;cinlength;G-arcs[v0][v1]=G-arcs[v1][v0]=length;}voidDijkstra(MGraph*G)//迪杰斯特拉算法求最短路径{intv,w,i,min,t=0,x,v0,v1;intfinal[20],D[20],p[20][20];cout请输入源顶点:\n;cinv0;if(v00||v0G-vexnum){cout此点编号不存在!请重新输入顶点编号:;cinv0;}cout请输入结束顶点:\n;cinv1;if(v10||v1G-vexnum){cout此点编号不存在!请重新输入顶点编号:;cinv1;}for(v=0;vG-vexnum;v++){//初始化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;wG-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;iG-vexnum;i++){min=MAX;for(w=0;wG-vexnum;w++)if(!final[w])if(D[w]min){v=w;min=D[w];}final[v]=1;for(w=0;wG-vexnum;w++)if(!final[w]&&(min+G-arcs[v][w]D[w])){D[w]=min+G-arcs[v][w];for(x=0;xG-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(intj=0;jG-vexnum;j++){if(p[v1][j]==1)coutG-vexs[j].nameendl;}}voidDeleteVex(MGraph*G)//删除某个顶点{introw,col;intv0;cout请输入要删除的顶点;cinv0;for(inti=v0;iG-vexnum;i++)G-vexs[i]=G-vexs[i+1];G-vexnum--;for(row=0;rowG-vexnum;row++){for(col=v0;colG-vexnum;col++)G-arcs[row][col]=G-arcs[row][col+1];}for(col=0;colG-vexnum;col++){for(row=v0;rowG-vexnum;row++)G-arcs[col][row]=G-arcs[col][row+1];}}voidDeleteArc(MGraph*G)//删除某条边{intv0,v1;cout请输入两顶点:\n;cinv0v1;G-arcs[v0][v1]=MAX;G-arcs[v1][v0]=MAX;}voidInsertArc(MGraph*G)//插入某条边{intv0,v1,l=0;cout请输入两顶点:\n;cinv0v1;cout请输入路径长度:\n;cinl;G-arcs[v0][v1]=l;G-arcs[v1][v0]=l;}voidmain()//主函数{inta;b=InitGraph();Menu();cina;while(a!=7){switch(a){case0:PutOutVex(&b);Menu();break;case1:PutOutArc(&b);Menu();break;case2:Change(&b);Menu();b