《数据结构课程设计》最短路径问题实验报告

数据结构课程设计报告最短路径：拯救007专业 物联网工程学生姓名班级学号指导教师完成日期2016年1月13日目录1、课程设计目的及要求 (1)2、课题总体设计 (2)3、详细设计 (4)4、图像文件 (7)5、调试与测试 (10)6、小结 (10)7、参考文献 (16)8、源程序清单 (17)数据结构程序设计数据结构程序课程的设计1、课程设计目的及要求1）设计题目看过007系列电影的人们一定很熟悉James Bond这个世界上最著名的特工了。

在电影“Live and Let Die”中James Bond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。

这时James Bond做出了最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反应过来的时候，他又跳到了另一只鳄鱼的头上……最后他终于安全地跳到了湖岸上。

假设湖是100×100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。

湖中心的圆形小岛的圆心在（0，0），直径是15。

一些凶猛的鳄鱼分布在湖中不同的位置。

现已知湖中鳄鱼的位置（坐标）和James Bond可以跳的最大距离，请你告诉James Bond一条最短的到达湖边的路径。

他逃出去的路径的长度等于他跳的次数。

2）输入要求程序从“input.txt”文件中读取输入信息，这个文件包含了多组输入数据。

每组输入数据的起始行中包含两个整数n和d，n是鳄鱼的数量而且n≤100，d是007可以跳的最大距离而且d>0。

起始行下面的每一行是鳄鱼的坐标（x，y），其中x, y都是整数，而且没有任何两只鳄鱼出现在同一个位置。

input.txt文件以一个负数结尾。

3）输出要求程序输出结果输出到output.txt文件中。

对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标（x，y），每行一个坐标。

青岛理工大学琴岛学院设计报告课题名称：求解最优交通路径学院：计算机工程系专业班级：计算机科学与技术学号：#######学生：**指导教师：**青岛理工大学琴岛学院教务处2011 年 7 月 7日图1B.具体功能实现及相应的弗洛伊德算法首先,建立查询信息对话框，使用户能够录入需要查询的城市代号，并显示路径长度及最短路径沿途经过的城市。

并相应地添加如下变量int m_v0;int m_v1;int m_lj;CString m_zd;具体代码如下：#define MAXV 25 //最大顶点个数#define INF 32767 //用32767表示∞//以下定义邻接矩阵类型typedef struct{ int no; //顶点编号char name[10]; //顶点名称} VertexType; //顶点类型typedef struct //图的定义{ int edges[MAXV][MAXV]; //邻接矩阵int vexnum,arcnum; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息} MGraph; //图的邻接矩阵类型1.通过函数CreatUDN()存放城市路径信息，输入顶点之间的路径长度，创建带权图的邻接矩阵。

void CTDialog::CreatUDN(){MGraph *g=(MGraph*)malloc(sizeof(MGraph));int i,j;for(i=0;i<MAXV;i++) //录入权值，计算存储用for(j=0;j<MAXV;j++){g->edges[i][j]=INF;if(i==j)g->edges[i][j]=0; //初始化置任意两城市之间距离为无穷大，即两城市之间没有直接通路{if(i!=j)m_zd="没有路径";}else if(x==i&&y==j){m_lj=A[i][j];CString zfc;zfc.Format("%d",i); //输出路径上的起点m_zd+=zfc;ppath(path,i,j); //输出路径上的中间点zfc.Format("-->%d",j); //输出路径上的终点m_zd+=zfc;}}}4.输出最短路径函数，递归输出从顶点i到j的最短路径中依次经过的顶点，直到path[i][j]=-1，即没有中间顶点为止。

青岛理工大学琴岛学院
设计报告
课题名称：数据结构课程设计
学院：计算机工程系
专业班级：计算机网络技术
学号：aaaaaa
学生： aaa
指导教师： aaaaaaa
青岛理工大学琴岛学院教务处
2011 年 12 月 18日
四．调试分析（调试过程中出现的问题及处理方式）调试出现的界面
1)进入程序弹出查询信息对话框如图2：
图2
2) 输入查询信息，显示路径长度及最短路径，如果输入代号不在0~24之内，提示出错。

图3
图4
B．出现的问题及解决方式
1、在执行程序的时候不能显示最短的距离
解决方法：增加一个函数调用，调用的函数为ShortestPath(v0); /*计算两个城市之间的最短路径*/
2、不能连续查询，即查询一次完成后，必须重新运行才能就进行二次查询
解决方法：在代码中添加while( ) 语句printf("是否继续，1（继续查询），0（退出查询）");
printf("\n"); scanf("%d",&ch); 详见图5
图 5。

数据结构与算法课程设计报告书题目：导航最短路径查询班级：11101111学号：**********姓名：教师周期：2012.12.17-2012.12.21 （以下由验收教师填写）成绩：2012年12月21日《导航最短路径查询》一、课程设计的目的与要求（一）课程设计目的与任务通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。

（二）题目要求要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

二、设计正文1、系统分析和开发背景该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。

（1）把城市交通线路转化为图，从而对图进行相应的结构存储；（2）程序的输出信息主要为：起始城市到目的城市的最短路路径。

（3）程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；2 、功能详细描述先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。

甲丙相距7千米，且只有从甲到丙的单程线路。

甲丁相距4千米，且只有从甲到丁的单程线路。

乙丙相距5千米，且只有从丙到乙的单程线路。

乙丁相距3千米，且只有从丁到乙的单程线路。

丙丁相距3千米，且只有从丁到丙的单程线路。

戊甲相距6千米，且只有从戊到甲的单程线路。

戊丁相距2千米，且只有从丁到戊的单程线路。

乙己相距8千米，且只有从乙到己的单程线路。

丙己相距6千米，且只有从己到丙单程线路。

编程出能求出个一点到任一点的最短路经。

3、数据结构设计（1）typedef struct{int no; //顶点编号InfoType info; //顶点其他信息，这里用于存放边的权值}VertexType; //顶点类型typedef struct //图的定义{int edges[MAXV][MAXV]; //邻接矩阵int n,e; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息}MGraph; //图的邻接矩阵类型//以下定义邻接表类型typedef struct ANode //弧的结点结构类型{int adjvex; //该弧的终点位置struct ANode *nextarc; //指向下一个弧的指针InfoType info; //该弧的相关信息，这里用于存放权值}ArcNode;typedef int Vertex;typedef struct Vnode //邻接表头结点的类型{Vertex data; //顶点信息ArcNode *firstarc[MAXV]; //指向第一条弧}VNode;typedef VNode AdjList[MAXV];//AdjList是邻接表类型typedef struct{AdjList adjlist; //邻接表int n,e; //图中顶点数n和边数e}ALGraph; //图的邻接表类型4、主要功能逻辑过程和实现算法用到的主要函数：（1）void DispMat(MGraph g) //输出邻接矩阵（2）void ppath(int path[][MAXV],int v,int endv) //输出相应选择的起点和终点的最短路。

最短距离问题数据结构课程设计报告数据结构课程设计报告题⽬：北海公园主要游览景点之间最短距离问题⼀、课程设计题⽬：北海公园主要游览景点之间最短距离问题⼆、问题定义：（由教师指定）图的最短路径问题是指从指定的某⼀点v开始，求得从该地点到图中其它各地点的最短路径。

并且给出求得的最短路径的长度及途径的地点。

除了完成最短路径的求解外，还能对该图进⾏修改，如顶点以及边的增删、边上权值的修改等。

三、需求分析1、设计北海公园的平⾯图。

选取若⼲个有代表性的景点抽象成⼀个⽆向带权图，以图中顶点表⽰公园内各景点，边上的权值表⽰两景点之间的距离。

2、输⼊的形式：整型数字输⼊值的范围：0-103、输出的形式：由⼆元组表⽰以邻接矩阵存储的图4、程序所能达到的功能；（1）输出顶点信息：将公园内各景点输出。

（2）输出边的信息：将公园内每两个位置的距离输出。

（3）修改：修改两个位置的距离，并重新输出每两个位置的距离；（4）求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意⼀点与其他各点的最短路径。

（5）删除：删除任意⼀条边。

（6）插⼊：插⼊任意⼀条边。

5、算法涉及的基本理论分析：定义邻接矩阵adjmatrix；⾃定义顶点结构体V ertexType；定义邻接表中的边结点类型edgenode；switch算法；狄克斯特拉法（Dijkstra）求任意两结点之间的最短路径；6、题⽬研究和实现的价值。

四、算法设计1、概要设计（1）存储结构设计本系统采⽤图结构类型存储抽象北海公园地图的信息。

其中：各景点间的邻接关系⽤图的邻接矩阵类型（adjmatrix）存储；景点（顶点）信息⽤结构数组（V ertexType）存储，其中每个数组元素是⼀个结构变量，包含景点编号、景点名称两个分量；图的顶点个数由分量MaxV ertexNum表⽰，它是整型数据。

（2）主界⾯设计为了实现公园导游系统各功能的管理，⾸先设计⼀个含有多个菜单项的主控菜单⼦程序以链接系统的各项⼦功能，⽅便⽤户使⽤本系统。

目录交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。

在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。

这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。

对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。

针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。

并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

三、概要设计可以将该系统大致分为三个部分：① 建立交通网络图的存储结构；② 解决单源最短路径问题；③ 实现两个城市顶点之间的最短路径问题。

四、详细设计建立图的存储结构定义交通图的存储结构。

邻接矩阵是表示图形中顶点之间相邻关系的矩阵。

设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点V的信息）。

i邻接矩阵的存储结构：附录#include<>#include<>#defineMVNum100#defineMaxint32767enumboolean{FALSE,TRUE}; typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum];}MGraph;intD1[MVNum],p1[MVNum];intD[MVNum][MVNum],p[MVNum][MVNum]; voidCreateMGraph(MGraph*G,intn,inte){inti,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint;printf("输入%d条边的及w:\n",e);for(k=1;k<=e;k++){scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf("有向图的存储结构建立完毕！\n"); }voidDijkstra(MGraph*G,intv1,intn){intD2[MVNum],p2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){S[v]=FALSE;D2[v]=G->arcs[v1][v];if(D2[v]<Maxint)p2[v]=v1;elsep2[v]=0;}D2[v1]=0;S[v1]=TRUE;for(i=2;i<n;i++){min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}S[v]=TRUE;for(w=1;w<=n;w++)if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];p2[w]=v;}}printf("路径长度路径\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=p2[i];while(v!=0){printf("<-%d",v);v=p2[v];}printf("\n");}}voidFloyd(MGraph*G,intn){inti,j,k,v,w;for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)p[i][j]=j;elsep[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];p[i][j]=p[i][k];}}}}voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf("输入图中顶点个数和边数n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0){printf("************求城市之间最短路径************\n");printf("=========================================\n");printf("1.求一个城市到所有城市的最短路径\n");printf("2.求任意的两个城市之间的最短路径\n");printf("=========================================\n");printf("请选择:1或2，选择0退出:\n");scanf("%d",&xz);if(xz==2){Floyd(G,n);printf("输入源点（或起点）和终点:v,w:");scanf("%d,%d",&v,&w);k=p[v][w];if(k==0)printf("顶点%d到%d无路径!\n",v,w);else{printf("从顶点%d到%d最短路径路径是:%d",v,w,v);while(k!=w){printf("--%d",k);k=p[k][w];}printf("--%d",w);printf("径路长度:%d\n",D[v][w]);}}elseif(xz==1)printf("求单源路径，输入源点v:");scanf("%d",&v);Dijkstra(G,v,n);}printf("结束求最短路径，再见!\n"); }。

最短路径_数据结构课程设计报告第一篇：最短路径_数据结构课程设计报告数据结构课程设计《数据结构》课程设计报告设计题目：____医院选址____________ 姓名：__________________ 学号：________________ 专业：___________院系：____________班级：_________________ 指导教师：_________________年 1月 3 日数据结构课程设计一、问题描述(1)题目内容：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总和来说较短。

（n>=5）(2)基本要求：(3)可以输出每一对点间的路径长度；然后选取偏心度，最小的偏心度即为所求。

二、需求分析(4)本程序的功能包括找出每一对点间的路径长度。

(5)然后算出每一对点的偏心度。

(6)其中最小的偏心度即为所求。

三、概要设计操作集合：(7)public:MGraph(DataType a[],int b[][MaxSize],int n,int e);//初始化邻接矩阵和路径(8)void Floyd();//弗洛伊德算法的实现(9)void getE();//获取偏心度(10)void showdist();//把每一对顶点之间的路径权值show出来(11)~MGraph(){} //类的析构函数四、数据结构设计(1)DataType vertex[MaxSize];//存放图中顶点的数组(2)intarc[MaxSize][MaxSize];//存放图中边的数组(3)string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为//path[i][j]=“ViVj”(4)int dist[MaxSize][MaxSize];//存放求得的最短路径长度(5)int vertexNum, arcNum;//图的顶点数和边数(6)int E[MaxSize][2];//获取最小偏心度和该顶点五、算法设计1.算法分析1）对带权有向图的，调用Floyd算法，对每一对顶点间的最短路径长度的矩阵；2）对最短路径长度矩阵的每列求最大值，即得到各点的偏心度；3)具有最小偏心度的顶点即为所求。

实验报告课程名：数据结构（C语言版）实验名：迷宫问题II姓名：班级：学号：撰写时间：2014/10/10一实验目的与要求1. 了解栈的应用2. 利用栈在迷宫中找到一条路二实验内容•一个迷宫如图1所示, 是由若干个方格构成的一个矩形, 其中有唯一的一个入口(用⃝标示), 有唯一的一个出口(用△标示). 图中深色的方格无法到达, 浅色的方格都是可以到达的. 每一次只能从当前方格前进到与当前方格有公共边的方格中(因此前进方向最多有四个).•本次实验的迷宫问题要求找到从入口到出口的最短的路.图1：迷宫三实验结果与分析程序：#include <stdio.h>#include <stdlib.h>int Maze(int ox,int oy,int ex,int ey,int rnum,int cnum,int a[rnum][cnum]){int b[rnum][cnum];int i,j,Znum=0;for(i=0;i<rnum;++i){for(j=0;j<cnum;++j){b[i][j]=a[i][j];if(a[i][j]==0){Znum=Znum+1;}}}int Qx[Znum+1], Qy[Znum+1], P[Znum+1], head=0, tail=0; for(i=0;i<Znum+1;++i){Qx[i]=-10;Qy[i]=-10;P[i]=-10;}/*int dx[4] = {0,1,0,-1};int dy[4] = {-1,0,1,0};int neighbor_num = 4;*/int dx[8] = {-1, 0, 1,1,1,0,-1,-1};int dy[8] = {-1,-1,-1,0,1,1, 1, 0};int neighbor_num = 8;if(ox==ex && oy==ey){printf("(%d,%d)",ox,oy);}else{Qx[tail]=ox;Qy[tail]=oy;P[tail]=-1;++tail;b[ox][oy]=2;}int brand = -1;while(tail>head){for(i=0;i<neighbor_num;i++){int tx = Qx[head]+dx[i];int ty = Qy[head]+dy[i];if(b[tx][ty]==0){if(tx==ex && ty==ey){printf("(%d,%d), ",tx,ty);int t = head;while(t>=0){printf("(%d,%d), ",Qx[t],Qy[t]);t=P[t];}head=tail;brand=1;break;}else{Qx[tail]=tx;Qy[tail]=ty;P[tail]=head;++tail;b[tx][ty]=2;}}}++head;}return(brand);}int main(int argc, char *argv[]) {int rnum = 10;int cnum = 10;int a[10][10]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};//假设外面有一层不可到达的方块，故迷宫成了10乘10型int ox=1,oy=1,ex=rnum-2,ey=cnum-2;int brand = Maze(ox,oy,ex,ey,rnum,cnum,a);if(brand<0){printf("There is no way\n");}return 0;}图1：实验结果截图。

问题描述：若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。

试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。

基本要求：（1）从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。

（2）以用户指定的起点和终点，输出从起点到终点的花费。

一、需求分析：1、本程序需要用矩阵来存储图的各种信息。

2、测试数据输入（文件）5－1 10 3 20 －1－1 －1 －1 5 －1－1 2 －1 －1 15－1 －1 －1 －1 11－1 －1 －1 －1 －1（用户）起点 0终点 4输出18实现提示：（1）设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。

（2）此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。

（3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。

因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。

（4）考虑没有路径时的输出。

二、概要设计：抽象数据类型：为实现上述功能需建立一个二维数组和图类。

算法的基本思想：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（>>途中各点之间的距离）。

2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。

如果l1<l2，则用l1的距离替换l2。

重复上述操作n-1（n为结点数）次。

得到的即为第一个结点到其他结点的最短距离。

程序的流程程序由三个模块组成：输入模块：读入图的信息（用矩阵进行存储）。

处理模块：Dijkstra算法。