数据结构课程设计_城市最短路径求解

西南交通大学数据结构A程序实习作业(周荣辉老师)实验八最短路径实验---------------------------------更新时间2013/6/6(后有持续更新敬请关注)Echo did this for you#include <stdio.h>#include <conio.h>#include <string.h>#define CityNum 40 //最大城市结点数#define NameLenght 12 //城市名字长度#define Infinity 10000 //若城市间没有路径距离设定为Infinitytypedef char Vextype[NameLenght];typedef int Arctype;typedef struct{Vextype vexs[CityNum]; // 顶点数组Arctype arcs[CityNum][CityNum]; //边矩阵，权值wijint vexnum,arcnum; //顶点数,边数} Mgraph;char *CityNameFile="cityname.txt"; //城市名数据文件char *CityPathFile="citypath.txt"; //城市边数据文件char *MinPathDataFile="shortpath.txt"; //最短路径数据文件/*-----------确定城市名城的位置------------*/int search(Mgraph G,char *p){int i=0;while(i<G.vexnum){if(!strcmp(G.vexs[i],p)) return(i);i++;}return(-1);}/*-----------输入城市名称数据------------*/int InputCityNode(Mgraph *G){int i;FILE *fp;if(!(fp=fopen(CityNameFile,"r"))){printf("城市数据文件不存在\n");getch();return(0);}fscanf(fp,"%d",&(G->vexnum));if(!G->vexnum){printf("文件中无城市数据!\n");getch();return(0);}for(i=0;i<G->vexnum;i++)fscanf(fp,"%s",G->vexs[i]);fclose(fp);return(1);}/*-----------输读入城市边数据------------*/int InputCityArc(Mgraph *G){int i,j,k,val;;FILE *fp;char city1[NameLenght],city2[NameLenght];//（学生完成）for(i=0;i<CityNum;i++)for(j=0;j<CityNum;j++)G->arcs[i][j]=Infinity;if(!(fp=fopen(CityPathFile,"r"))){printf("\n打开文件失败\n");getch();return 0;}//printf("打开文件成功\n");fscanf(fp,"%d",&(G->arcnum));if(G->arcnum==0){fclose(fp);return 0;}for(i=0;i<G->arcnum;i++){fscanf(fp,"%s %s %d",city1,city2,&val);j=search(*G,city1);k=search(*G,city2);if(j==-1||k==-1)break;G->arcs[j][k]=G->arcs[k][j]=val;}fclose(fp);return 1;}int InputMinPath(int dist[][CityNum],int Path[][CityNum],int *NodeNum) {int i,j,n;FILE *fp;if(!(fp=fopen(MinPathDataFile,"rb"))){printf("最小路径数据文件不存在!\n");getch();return(0);}fread(&n,sizeof(int),1,fp);for(i=0;i<n;i++)fread(dist[i],sizeof(int),n,fp);for(i=0;i<n;i++)fread(Path[i],sizeof(int),n,fp);fclose(fp);*NodeNum=n;return(1);}void shorttestpath(){int i,j,k,NodeNum,EgeNum,val;Mgraph G;int dist[CityNum][CityNum]; //最短路径长度矩阵int Path[CityNum][CityNum]; //最短路径矩阵char city1[NameLenght],city2[NameLenght];FILE *fp;if(InputCityNode(&G)==0)return;if(InputCityArc(&G)==0)return;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){dist[i][j]=G.arcs[i][j];if(dist[i][j]<Infinity)Path[i][j]=i;elsePath[i][j]=-1;}dist[i][i]=0;}//计算最短路径for(k=0;k<G.vexnum;k++)for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];Path[i][j]=Path[k][j];}if(!(fp=fopen(MinPathDataFile,"wb")))return;fwrite(&G.vexnum,sizeof(int),1,fp);for(i=0;i<G.vexnum;i++)fwrite(dist[i],sizeof(int),G.vexnum,fp);for(i=0;i<G.vexnum;i++)fwrite(Path[i],sizeof(int),G.vexnum,fp);fclose(fp);return;// （学生完成）}/*----------------------------------------------------*//* 求一个城市到其它城市的最短路径 *//*----------------------------------------------------*/void One_To_Other_Path(){int i,j,k,NodeNum,StartNode;Mgraph G;int dist[CityNum][CityNum]; //最短路径长度矩阵int Path[CityNum][CityNum]; //最短路径矩阵int top,PathStack[CityNum];char city[NameLenght];if(InputCityNode(&G)==0)return;if(InputMinPath(dist,Path,&NodeNum)==0)return;do{scanf("%s",city);StartNode=search(G,city);if(StartNode!=-1)break;}while(1);for(i=0;i<NodeNum;i++){if(i==StartNode)continue;if(dist[StartNode][i]==Infinity)printf("城市不可达");j=i;top=0;PathStack[top++]=i;while( Path[StartNode][j]!=-1 && Path[StartNode][j]!=StartNode ){PathStack[top]=Path[StartNode][j];j=PathStack[top];top++;}printf("路径长度:%d\n",dist[StartNode][i]);printf("路径:%s",G.vexs[StartNode]);for(top--;top>=0;top--)printf("%15s ",G.vexs[PathStack[top]]);printf("\n");}// （学生完成）}/*----------------------------------------------------*/ /* 求一个城市到另一个城市的最短路径 */ /*----------------------------------------------------*/ void One_To_One_Path(){int i,j,k,NodeNum,StartNode,EndNode;Mgraph G;int dist[CityNum][CityNum]; //最短路径长度矩阵int Path[CityNum][CityNum]; //最短路径矩阵int top,PathStack[CityNum];char city1[NameLenght],city2[NameLenght];// （学生完成）if(InputCityNode(&G)==0)return;if(InputMinPath(dist,Path,&NodeNum)==0)return;do{scanf("%s",city1);scanf("%s",city2);EndNode=search(G,city2);StartNode=search(G,city1);if(StartNode!=-1&&EndNode!=-1)break;}while(1);//for(i=0;i<NodeNum;i++)//{// if(i==StartNode)// continue;// if(dist[StartNode][i]==Infinity)// printf("城市不可达");// j=i;// top=0;// PathStack[top++]=i;// while( Path[StartNode][j]!=-1 && Path[StartNode][j]!=StartNode ) // {// PathStack[top]=Path[StartNode][j];// j=PathStack[top];// top++;// }// printf("路径长度:%d\n",dist[StartNode][i]);// printf("路径:%s",G.vexs[StartNode]);// for(top--;top>=0;top--)// printf("%15s ",G.vexs[PathStack[top]]);// printf("\n");//}if(dist[StartNode][EndNode]==Infinity)printf("城市不可达");top=0;j=EndNode;PathStack[top++]=EndNode;while(Path[StartNode][j]!=-1&&Path[StartNode][j]!=StartNode){PathStack[top]=Path[StartNode][j];j=Path[StartNode][j];top++;}printf("路径长度:%d\n",dist[StartNode][EndNode]);printf("路径:%s",G.vexs[StartNode]);for(top--;top>=0;top--)printf("%15s ",G.vexs[PathStack[top]]);}int nemu(){int num;printf("\n ************* shortest path program **************\n");printf(" *%15c1---Initial%23c\n",' ','*');printf(" *%15c2---One to Other Cities%11c\n",' ','*');printf(" *%15c3---One to Another City%11c\n",' ','*');printf(" *%15c4---Quit%26c\n",' ','*');printf(" **************************************************\n");printf("%15cSelcet 1,2,3,4: ",' ');do{scanf("%d",&num);}while(num<1 ||num>4);return(num);// （学生完成）。

数据结构课程设计报告----旅游咨询系统设计目录一、需求分析二、系统分析三、概要设计一、系统划分二、邻接矩阵建立流程图：三、迪杰斯特拉算法流图四、详细设计五、调试分析一、运行结果二、改进设想六、课设总结旅游咨询系统设计一、需求分析在交通网络日益发达的今天，人们出行有很多种方式、路线，而如何选择符合需要的方式路线成为大家的一大难题。

所以，在此我利用计算机建立一个旅游咨询系统。

在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的路线，所带权值为两个城市间的路程、时间或车费等。

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

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

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

旅客可以在同一个系统中综合考虑自己的各目标城市，选择一个最佳的旅游路线和出行方式。

针对最短路径问题，在本系统中采用图的相关知识，采用了迪杰斯特拉算法，解决在实际情况中的最短路径问题，而迪杰斯特拉算法的时间复杂度为O(n2,空间复杂度为O(n。

本系统使用邻接矩阵存储无向图。

其中，建立矩阵的时间复杂度为O(n2,但是利用其查找一条边的时间复杂度为O(1。

本系统中包括了利用邻接矩阵建立图的存储结构和单源最短问题两大部分，使用指针数组实现利用一个程序实现最短路径和最短时间的运算。

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

三、概要设计一、系统划分该系统可以划分为三个部分：1、利用邻接矩阵建立图的存储结构；2、利用迪杰斯特拉算法解决单源最短路径问题；3、实现城市之间的最短路径问题和最短时间问题。

二、邻接矩阵建立流程图：四、详细设计本课程设计的源程序如下所示：#include#include#define MVNum 100#define Maxint 9999 /*将无穷大的数值设为9999*/ typedef char vertextype;/*建立无向图*/typedef int adjmatrix;typedef struct{vertextype vexs[MVNum];adjmatrix arcs[MVNum][MVNum];}mgraph;mgraph *G[2]; /*设置指针数组用以实现距离和时间最小值求取*/void city_number( /*输出城市代表序号*/{ printf("************************************************************************ *\n";printf(" 1、北京 2、上海 3、香港 4、天津 5、重庆 6、澳门 7、哈尔滨 8、石家庄";printf(" \n 9、兰州 10、昆明 11、成都 12、长春 13、沈阳 14、长沙 15、海口 16、西安";printf("\n************************************************************************ *\n";}void Createmgraph(int a,int n,int e /*建立无向邻接矩阵*/{int i,j,k;int w;for(i=1;i<=n;i++for(j=1;j<=n;j++if(i==j G[a]->arcs[i][j]=0; /*邻接矩阵对角线初始值设为0*/else G[a]->arcs[i][j]=Maxint; /*其他元素设为无穷大*/for(k=1;k<=e;k++ /*读入e条边数的信息*/{printf("\n输入图中各起点终点及其权值i,j,w:"; /*读入无向边及其权值*/scanf("%d,%d,%d",&i,&j,&w;G[a]->arcs[i][j]=w;G[a]->arcs[j][i]=w;}}void Dijkstra(int a,int v0,int N/*Dijkstra算法的实现和打印*/{enum boolean S[MVNum];/*终点集合*/int dist[MVNum],path[MVNum];/*dist表示源点v0到图中其余顶点的最短长度，path表示其对应的路径*/int i,wmin,u,num=1,k;for(i=1;i<=N;i++ /*数组dist和集合S付初值*/{dist[i]=G[a]->arcs[v0][i]; /*数组dist初值为邻接矩阵*/S[i]=0; /*集合S初值设为空集*/if(dist[i]else path[i]=0;}S[v0]=1; /*源点v0放入集合S中*/path[v0]=0;do{wmin=Maxint; /*wmin最小值设为无穷大*/u=v0;for(i=1;i<=N;i++if(S[i]==0 /*选择不在S中且距离最小的顶点u*/if((dist[i]{u=i;wmin=dist[i];}S[u]=1; /*把距离最小的顶点u放入集合S中*/for(i=1;i<=N;i++ /*修改不在S中的顶点距离*/if(S[i]==0if(dist[u]+G[a]->arcs[u][i]{dist[i]=dist[u]+G[a]->arcs[u][i];path[i]=u;}num++;}while(num<=N;printf("\n\t输出带权无向图的单元最短路径为:\n\t";/*打印v0到其他顶点的最短路径*/ for(i=1;i<=N;i++{if(S[i]==1{k=i;printf("\n\t顶点%d到%d之间的路径为:",v0,i;while(k!=v0{printf("%d<--",k; /*输出后继顶点*/k=path[k]; /*继续寻找下一个后继顶点*/}printf("%d",k; /*输出终点*/printf(",最短路径长度为%d\n",dist[i]; /*输出最短路径*/}else printf("\n\t顶点%d到%d之间没有路径！",v0,i;}printf("\n\t求一个城市到所有城市的最短路径结束，谢谢！\n\n\t\t";}void main( /*旅游咨询系统*/{int n,e,v,u,i,x;int z=0;G[1]=(mgraph *malloc(sizeof(mgraph; /*建立类型为mgraph的十字链表结构*/G[2]=(mgraph *malloc(sizeof(mgraph;printf("****************欢迎使用旅游咨询系统****************\n";printf("输入图中顶点个数和边数n,e:";scanf("%d,%d",&n,&e;city_number(;for(i=1;i<=n;i++ /*输入顶点信息*/{printf("\n请输入图的所有顶点i=";scanf("%d",&x;G[1]->vexs[i]=x; /*将顶点信息输入一维数组中*/G[2]->vexs[i]=x;}printf("\n请输入距离矩阵的数值\n";Createmgraph(1,n,e; /*建立距离矩阵*/ printf("\n距离矩阵建立完毕\n请输入时间矩阵的数值";Createmgraph(2,n,e; /*建立时间矩阵*/printf("\n无向图的存储结构建立完毕！\n";do{printf("\n\n\n************进行最短查询************\n";printf("=========================================\n";printf("1.求一个城市到所有城市的最短路径\n";printf("2.求一个城市到所有城市的最短时间\n";printf("3.退出\n";printf("=========================================\n";printf("请输入选择:";scanf("%d",&z; /*输入选择选择矩阵*/city_number(;if(z==1{printf("\n选择1 求一个城市到所有城市的最短路径\n";printf("求单源路径,输入源点v :"; /*输入源点v0*/scanf("%d",&v;Dijkstra(1,v,n; /*计算最短距离*/}else if(z==2{printf("\n选择2 求一个城市到所有城市的最短时间\n"; printf("求单源路径,输入源点,u :";scanf("%d",&u;Dijkstra(2,u,n; /*计算最短时间*/}else if(z==3printf("\n结束查询!谢谢使用!!\n";else printf("输入错误!!\n"; /*输入不为1-3则重新选择*/ }while(z!=3; /*输入3则退出*/printf("谢谢您的使用,再见!!!!\n";}五、调试分析一、运行结果1、输入顶点总数为6，边的总数为10，并输入顶点信息。

数据结构课程设计报告题目交通旅游图的最短路径问题学生姓名*****指导教师*****学院******专业班级******完成时间********摘要数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的关系和操作等的学科。

数据结构在计算机科学与技术中是一门综合性的专业基础课，其研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系。

不论是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配问题。

在计算机科学与技术中，数据结构不仅是一般程序性的基础，而且也是其他系统程序和大型程序的重要基础。

在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。

对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。

图中顶点表示站点之间的交通关系。

这个交通系统可以回答旅客提出的各种问题。

比如任意一个站点到其他站点的最短路径，任意两个站点之间的最短路径问题。

本次设计的交通咨询系统主要是运用C语言来完成交通图的存储、图中顶点的最短路径和任意一对顶点间的最短路径问题。

关键字：数据结构课程设计交通咨询系统目录前言 (1)第一章设计要求 (2)1.1设计内容 (2)1.2设计目的 (3)1.3设计分析 (4)第二章系统功能模块的设计 (5)2.1 系统功能分析与设计 (5)2.1.1系统简介 (5)2.1.2 系统流程图 (5)2.2 各功能模块简介 (6)2.2.1结构体的建立 (6)2.2.2 图的建立与初始化 (6)2.2.3 邻接矩阵的输出 (8)2.2.4 显示函数 (8)2.2.5 最短路径算法 (9)2.2.6主函数 (10)第三章实践结果与调试 (12)3.1运行结果 (12)3.1.1主界面 (12)3.1.2查询站点编号模块 (12)3.1.3邻接矩阵查询模块 (12)3.1.4最短路径查询模块 (13)3.2运行调试及发现问题 (15)3.2.1调试过程 (15)3.2.2发现问题 (15)第四章设计总结与心得 (16)附录：程序源代码 (18)前言乘汽车旅行的人总希望找出到目的地的尽可能短的行程。

青岛理工大学琴岛学院
设计报告
课题名称：数据结构课程设计
学院：计算机工程系
专业班级：计算机网络技术
学号：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。

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

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

这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从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)具有最小偏心度的顶点即为所求。

数据结构课程设计—省会城市最短路径求解一、类关系图说明：Graph类继承Form类，同时嵌入了CityInf结构体和List类。

Graph类的几个重要函数、类、结构体private void Init()//初始化函数private void ShowMap_Paint(object sender, PaintEventArgs e) //绘制地图private bool GetMinDistanceFun(int entry) //采用迪杰斯特拉算法获得最短路径private void BFS(int StartPoint, int[] visited, string name) //广度优先遍历函数private void DFS(int StartPoint, int[] visited, string name)//深度优先遍历函数private void Prim()//求解最小生成树 Prim算法private class List //广度优先遍历用到的队列类public struct CityInf//存放城市信息：城市名称、城市坐标、状态值二、流程图三、主要算法的实现1．用迪杰斯特拉算法实现省会城市间最短路径的求解private bool GetMinDistanceFun(int entry){int inputnodenum = CityData.citysum;int[] Mark = new int[inputnodenum]; //标志位数组标记数据在哪个集合int mindis = 0, nextnode = 0;//最短路径，下一个城市结点int i, j;//第一轮距离数组记录从起始点到其他所有点的边权值for (i = 0; i < inputnodenum; i++){Distance[i] = GetCityWeight(entry, i);//所有标志位清零Mark[i] = 0;//如果起始结点可以抵达某个结点if (i != entry && Distance[i] < MaxWeight){RoutePath[i] = entry; //则把该结点首先放入路径数组}else{RoutePath[i] = -1;//表示该路径不通}}//初始状态下集合存放找到最短路径顶点集合的中只包含源点entry 所以把它在Mark 中标记出来Mark[entry] = 1;//在还没有找到最短路径的结点集合中选取最短距离结点nextnodefor (i = 1; i < inputnodenum; i++){//设定每轮的初始最小距离为无穷大mindis = MaxWeight;for (j = 0; j < inputnodenum; j++){//保证每次循环mindis是到entry的最小值if (Mark[j] == 0 && Distance[j] < mindis)//如果没有进入最短路径且距离小于最小距离{nextnode = j;mindis = Distance[j];//记录本次循环的最短路径}}if (mindis == MaxWeight)//不存在最短路径退出{return false;}//把nexinode在集合mark中标记成已在最短路径集合中Mark[nextnode] = 1;//每加入一个元素都要修改entry到最短路径集合都要再修改entry到剩余顶点的最短路径长度值for (j = 0; j < inputnodenum; j++)//修改结点v0到其他的结点最短的距离{//找到新的最短路径if (Mark[j] == 0 && GetCityWeight(nextnode, j) < MaxWeight&& Distance[nextnode] + GetCityWeight(nextnode, j) < Distance[j]) {//新的最短路径Distance[j] = Distance[nextnode] + GetCityWeight(nextnode, j);//把该点加入路径RoutePath[j] = nextnode;}}}return true;}this.MinTreeEdges[i, j] = 0;}}//辅助数组初始化权值数组赋值for (i = 1; i < this.CityData.citysum; ++i){WeightArrays[i] = this.Edges[0, i];NodeArrays[i] = 0;}//某个顶点加入集合UWeightArrays[0] = 0;NodeArrays[0] = 0;//判断最小的权值通过的顶点的循环就此开始for (i = 0; i < this.CityData.citysum; ++i){k = 1;j = 1;mincost = this.MaxWeight;//选取权值最小的边和相应的顶点while (j < this.CityData.citysum){if (WeightArrays[j] < mincost && WeightArrays[j] != 0){mincost = WeightArrays[j];k = j;}j++;}//新顶点加入集合UWeightArrays[k] = 0;this.MinTreeEdges[k, NodeArrays[k]] = this.Edges[k, NodeArrays[k]];this.MinTreeEdges[NodeArrays[k], k] = this.Edges[k, NodeArrays[k]];//重新计算该顶点到其余顶点的边的权值for (j = 1; j < this.CityData.citysum; j++){if (this.Edges[k, j] < WeightArrays[j]){WeightArrays[j] = this.Edges[k, j];NodeArrays[j] = k;}}}this.Default();this.showmintree = true;this.ShowMap.Refresh();}四、程序测试结果求解两个城市最短路径显示所有城市到“北京”的最短路径求解全国省会城市的公路网的最小生成树“增删”功能“网络地图”功能五、总结本次课程设计收获很大，使用了多种算法：迪杰斯特拉算法、Prim 算法。

数据结构课程设计报告题目：北海公园主要游览景点之间最短距离问题一、课程设计题目：北海公园主要游览景点之间最短距离问题二、问题定义：（由教师指定）图的最短路径问题是指从指定的某一点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）主界面设计为了实现公园导游系统各功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。

数据结构最短路径课程设计一、课程目标知识目标：1. 理解图的基本概念，掌握图的表示方法及其特性；2. 掌握最短路径的两种经典算法：Dijkstra算法和Floyd算法；3. 能够运用所学算法解决实际生活中的最短路径问题。

技能目标：1. 能够运用数据结构中的图，进行实际问题的建模；2. 能够编写并实现Dijkstra算法和Floyd算法，解决最短路径问题；3. 能够通过分析、比较两种算法，选择合适的算法解决特定问题。

情感态度价值观目标：1. 培养学生面对复杂数据结构问题时，保持积极探究、解决问题的态度；2. 培养学生的团队协作能力，学会在团队中分享、交流、互助；3. 通过解决实际生活中的问题，培养学生将所学知识应用于实践的意识。

课程性质分析：本课程为数据结构中的图部分，以最短路径为具体实例，帮助学生理解图的概念及其在实际中的应用。

学生特点分析：学生已具备一定的编程能力和数据结构基础知识，但对图的相关概念和算法掌握不足，需要通过具体案例和实际操作，提高理解和应用能力。

教学要求：1. 以实际问题引入，激发学生的学习兴趣；2. 采用任务驱动法，引导学生自主探究、实践；3. 结合课堂讲解和实际操作，使学生在实践中掌握知识；4. 注重团队合作，培养学生的沟通与协作能力。

二、教学内容1. 图的基本概念：图的定义、图的表示方法（邻接矩阵、邻接表）、图的遍历（深度优先搜索、广度优先搜索）。

2. 最短路径问题：最短路径的定义、最短路径算法的应用场景。

3. Dijkstra算法：算法原理、算法步骤、实例分析、编程实现。

4. Floyd算法：算法原理、算法步骤、实例分析、编程实现。

5. 算法比较与分析：Dijkstra算法与Floyd算法的优缺点比较、适用场景分析。

6. 实践项目：设计一个实际场景的最短路径问题，要求学生运用所学算法进行解决。

教学内容安排与进度：第一课时：图的基本概念、图的表示方法、图的遍历。

第二课时：最短路径问题、Dijkstra算法原理与实例分析。