数据结构地图导游系统含源码

数据结构地图课程设计含源码

数据结构课程设计报告

题 目： XXXX大学校园导游系统

院系名称： 专业名称： 班 级： 学生姓名： 计算机学院

软件工程 2012级01班 XX XX

学号（8位）：

指导教师： XX

设计起止时间：2013年12月16日~2013年12月27日

一. 设计目的

进一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，实现图的遍历，用邻接矩阵和邻接表的存储方式存储图。

初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。

训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。

二. 设计内容

1、设计并显示学校的校园平面图， 地点（地点名称、地点介绍）， 路线（公里数）均不少于10个。（文件存储） 2、提供图中任意地点相关信息的查询。 3、提供图中任意地点的问路查询：

1）任意两个地点之间的一条最短的简单路径； （最短路径长度——中转次数最少）

2）任意两个地点之间的一条最佳访问路线； （带权（公里数）最短路径长度） 3）任意两个地点之间的所有简单路径。 4、提供图中所有地点的最佳布网方案； 5、增加新地点和路线、撤销旧地点和路线。 三．概要设计

1.各个模块详细的功能描述。

int Locate(AdjMatrix *G,char name[]); 根据景点名称查找景点编号 int VexExit(); 判断景点是否存在 int Creat(AdjMatrix *G); 创建无向图

void Savefile(AdjMatrix *G); 将图保存到文件中

void Readfile(AdjMatrix *G); 从指定文件中读取信息并存入图中

void ShowSchool(AdjMatrix *G); 显示校园全景图 void ShowRoute(AdjMatrix *G); 显示图的所有路线

void ShowVex(AdjMatrix *G); 显示图中所含景点的信息 void Serach(AdjMatrix *G); 查找景点 void AddRoute(AdjMatrix *G); 增加新路线 void DeleteRoute(AdjMatrix *G); 删除旧路线 void AddVex(AdjMatrix *G); 增加新景点 void DeleteVex(AdjMatrix *G); 删除旧景点

void Dijkstra(AdjMatrix *G,int start,int ending,int dist[],int path[][MAXVEX]); 求起点到终点的最短路线

void Prim(AdjMatrix *G,int start); 采用Prim算法求得最短连通路线

void MiniSpanTree(AdjMatrix *G); 查询从某个景点的最短连通路线 void DFS(AdjMatrix *G,int start,int ending,int stack[],int visited[]); 深度遍历查找所有路径

void SimpleRoute(AdjMatrix *G); 查询两个景点间的最优路径 void SearchAllRoute(AdjMatrix *G); 输出两景点之间的所有路径 void menu(); 显示主菜单 void menu1(); 开始菜单界面 void menu2(); 退出菜单界面 四．详细设计

1． 功能函数的调用关系图；

调用 ShowSchool

调

Serach

用

调用 AddRoute

调用 DeleteRoute Locate 调用 DeleteVex VexExit 调用

Locate

ShortCut Dijkstra

MiniSpanTree 调用 Prim

调用 DFS SimpleRoute

SearchAllRoute 调用 DFS

Locate Locate ShowRoute VexExit

2.功能模块图： 开始 menu1 main menu choice

choice=1 choice=2 choice=3 choice=4 choice=5 choice=6 choice=7 choice=8 choice=9 choice=10 choice=11 choice=12 choice=0

menu2 Readfile Readfile Readfile Readfile Readfile Readfile Readfile Readfile Readfile Readfile Readfile Creat ShowSchool ShowVex Serach AddRoute DeleteRoute AddVex DeleteVex SimpleRoute ShortCut MiniSpanTree SerachAllRoute Savefile Savefile Savefile Savefile Savefile 结束 2． 各功能函数的数据流程图；

Creat

输入vexnum,arcnum i=0 i输入start,ending,distance 结束

Readfile

读出vexnum,arcnum

i

保存name,introduce

i

保存路线，距离 结束

Savefile 写入vexnum,arcnum

i=0 iAddRoute 输入start,ending,distance 调用 Locate 在arcs[]中存入distance 结束 AddVex 输入name,introduce 调用 Locate 在arcs[]中初始化 vexnum++ 结束 DeleteRoute 输入start,ending,distance 调用 Locate 在arcs[]中赋初值 结束 DeleteVex 输入name,introduce 调用 Locate 从图中最后一个节点依次往前覆盖 vexnum++ 结束

DFS 用for查找起点的邻接点 若是终点，直接输出 输出stack数组存放的路径 标志该点被访问 存入stack数组 stack下标往后移 3.重点设计及编码。

（1）文件的保存与读取：

1.将图的顶点数和边数写入文件

2.将图的顶点名称和介绍写入文件，用for循环控制； 3.将图中路线的起点和终点以及距离写入文件； 4.文件的读取与保存原理一样。

编码：

void Savefile(AdjMatrix *G); 将图保存到文件中

void Readfile(AdjMatrix *G); 从指定文件中读取信息并存入图中

（2）深度遍历：

用递归的方法，从某个节点出发，访问此节点，然后依次从出发节点的各个未被访问的邻接点出发深度优先搜索遍历；将走过的路径存入数组中，找到终点时输出路径。该函数模块用于查找两点之间的所有路径以及最优路径，找最优路径时，定义一个数组及最小值，每次最小值更新，就将路径值数组赋值到最优路径数组中去。

编码：void DFS(AdjMatrix *G,int start,int ending,int stack[],int visited[]);

（3）最小生成树prim算法

从图中的某一顶点v0出发，选择与它关联的具有最小权值的边，将其顶点加入到生成树的顶点集合中，以后的每一步从在生成树中的一个顶点，而另一个顶点不在生成树顶点集合中的各条边中选择权值最小的边，再把它的顶点加入到生成树顶点集合中，直到所有顶点都加入到生成树集合中

编码： void Prim(AdjMatrix *G,int start); //采用Prim算法求得最短连通路线

(4) 最短路径Dijkstra算法

用带权的邻接矩阵存储该带权有向图，借助一个辅助的一维数组dist[ ]记录从源点到其余各顶点的最短距离值，二维数组path[ ][ ]记录某顶点是否加入到集合S中，如果path[i][0]=1,则表示顶点Vi加入到集合S中，并且path[i]所在的行最终记录了从源点到Vi的最短路径上的各个顶点，否则，path[i][0]=0,则表示顶点Vi还在集合V-S中。

编码：

void Dijkstra(AdjMatrix *G,int start,int ending,int dist[],int path[][MAXVEX]); //求起点到终点的最短路线

五．测试数据及运行结果

1． 正常测试数据（3组）及运行结果；

（1） 查询景点时输入正确景点编号

（2）校园所有景点的信息

（3）查询两点之间的最优路径

2．非正常测试数据（2组）及运行结果。

（1） 输入错误的景点编号

（2）输入不存在的景点

六．调试情况，设计技巧及体会

1． 对自己的设计进行评价，指出合理和不足之处，提出改进方案；

好的地方：

（1）在文件的存储方面比较满意，先将图的顶点数目和边的数目存入文件，再将顶点信息存入，最后将路线的信息存入文件中。达到了将整个图存入文件的目的，相对于其他存储方法较为简洁且功能完善。

（2）对于查询、增加、删除部分，都先输出已有的景点路线信息，方便用户操作。并且在用户输入错误时会有相应的错误处理。 （3）代码的格式比较整齐，易读。考虑到了很多细节。

不足的地方：

（1） 每次对图进行操作，都要先从文件中读取重建一个图，比较繁琐； （2） 在查找中转路径次数最少的时候调用了查找所有路径的函数，先是

找到所有路径再对次数进行比较，并且若中转次数最少的路径不止一条时，最终只能输出一条路径，有缺陷，算法不够优化；

2． 对设计及调试过程的心得体会。

课程设计刚开始时，思路有点混乱，只知道用文件把图存起来，每次操作时将信息读入图中，具体该怎么实现，还真不知道。看了一下课本，决定用邻接矩阵存储图。图的存储方式决定好后，就开始文件的存储，个人觉得在文件的存储方面想法不错，但是在文件的写入与读取格式的地方出了一点小问题，在调试的

过程中对文件又熟悉了一点。这次课程设计不像以前马马虎虎，漏掉取址符，标点符号等，只会出现逻辑错误，在整个过程中也比较顺利。当不会一些算法的时候，我会查阅资料以及上网百度。把所有的功能实现后就开始细化自己的代码，比如对用户错误输入的错误处理，写小函数如VexExit来让程序更加模块化，以及对界面的改进，只希望自己的代码更加完美。

七．参考文献

（1）数据结构(C语言版) 严蔚敏 吴伟民 编著 清华大学出版社 2002 （2） 数据结构与算法 王曙燕 王春梅 编著 人民邮电出版社 2013

八．附录：源代码（电子版） #include #include #include #include #include #include #include #define MAXVEX 20 #define INFINITY 32768

typedef struct //顶点类型 {

int num; // 景点的编号 char name[20]; //景点的名称 char introduce[100]; // 景点的介绍 }Vextype;

typedef struct //邻接矩阵 {

int arcs[MAXVEX][MAXVEX]; //边集，存放权值 Vextype vex[MAXVEX]; //顶点集 int vexnum; //顶点的数目 int arcnum; //边的数目 }AdjMatrix;

int Locate(AdjMatrix *G,char name[]); //根据景点名称查找景点编号 int VexExit(); //判断景点是否存在 int Creat(AdjMatrix *G); //创建无向图

void Savefile(AdjMatrix *G); //将图保存到文件中

void Readfile(AdjMatrix *G); //从指定文件中读取信息并存入图中 void ShowSchool(AdjMatrix *G); //显示校园全景图 void ShowRoute(AdjMatrix *G); //显示图的所有路线

void ShowVex(AdjMatrix *G); //显示图中所含景点的信息

void Serach(AdjMatrix *G); //查找景点 void AddRoute(AdjMatrix *G); //增加新路线 void DeleteRoute(AdjMatrix *G); //删除旧路线 void AddVex(AdjMatrix *G); //增加新景点 void DeleteVex(AdjMatrix *G); //删除旧景点

void Dijkstra(AdjMatrix *G,int start,int ending,int dist[],int path[][MAXVEX]); //求起点到终点的最短路线

void Prim(AdjMatrix *G,int start); //采用Prim算法求得最短连通路线 void MiniSpanTree(AdjMatrix *G); //查询从某个景点的最短连通路线 void DFS(AdjMatrix *G,int start,int ending,int stack[],int visited[]); //深度遍历查找所有路径

void SimpleRoute(AdjMatrix *G); //查询两个景点间的最优路径 void SearchAllRoute(AdjMatrix *G); //输出两景点之间的所有路径 void menu(); //显示主菜单 void menu1(); //开始菜单界面 void menu2(); //退出菜单界面

int Locate(AdjMatrix *G,char name[]) //根据景点名称查找景点编号 {

int i;

for(i=1;i<=G->vexnum;i++)

if(!strcmp(name,G->vex[i].name)) return i; return -1; }

int VexExit(AdjMatrix *G,int index) //判断景点是否存在 {

if(index>0 && index<=G->vexnum) return 1; else {

printf(\该景点不存在！\\n\ return 0; } }

int Creat(AdjMatrix *G) //创建无向图 {

int i,j,k,weight; char name[20];

printf(\请输入校园图中的景点数目和路线数目：\\n\ scanf(\

for(i=1;i<=G->vexnum;i++) //权值数组初始化 for(j=1;j<=G->vexnum;j++)

G->arcs[i][j]=INFINITY;

printf(\请输入校园图中%d个景点的名称及介绍：\\n\ for(i=1;i<=G->vexnum;i++) {

printf(\请输入第%d个景点:\ G->vex[i].num=i; //flushall();

scanf(\ }

printf(\请输入校园图中的%d条路线:\\n\ for(k=1;k<=G->arcnum;k++) //存入路线 {

printf(\请输入第%d条路线：\\n\ printf(\起点:\ scanf(\ i=Locate(G,name); printf(\终点:\ scanf(\ j=Locate(G,name); printf(\距离:\

scanf(\ G->arcs[i][j]=weight; G->arcs[j][i]=weight; }

return 1; }

void Savefile(AdjMatrix *G) //将图保存到文件中 {

FILE *fp; int i,j;

fp=fopen(\ if(!fp) {

printf(\写文件出错，按任意键退出！\\n\ getch(); exit(1); }

fprintf(fp,\ //先将图的顶点数目和边集数目存入文件，便于控制下面程序的for循环

for(i=1;i<=G->vexnum;i++) //接着存放顶点的信息

fprintf(fp,\

for(i=1;i<=G->vexnum;i++) //最后存放边的信

息即路线信息

for(j=1;j<=i;j++)

if(G->arcs[i][j]!=INFINITY)

fprintf(fp,\

printf(\文件已成功保存，按任意键返回！\\n\ getch(); fclose(fp); }

void Readfile(AdjMatrix *G) //从指定文件中读取信息并存入图中 {

FILE *fp; int i,j;

int start,ending;

char startpoint[20],endpoint[20]; int distance;

fp=fopen(\ if(!fp) {

printf(\读文件出错，按任意键退出！\\n\ getch(); exit(1); }

fscanf(fp,\ //先读取文件中的前两个整型，存入图的顶点数目和边数目中 //对图的权值数组进行初始化 for(i=1;i<=G->vexnum;i++)

for(j=1;j<=G->vexnum;j++) G->arcs[i][j]=INFINITY; //从文件中读取顶点信息并存入图中 for(i=1;i<=G->vexnum;i++) {

G->vex[i].num=i;

fscanf(fp,\ }

//从文件中读取路线并存入图中 for(j=1;j<=G->arcnum;j++) {

fscanf(fp,\ start=Locate(G,startpoint); ending=Locate(G,endpoint); G->arcs[start][ending]=distance; G->arcs[ending][start]=distance; } }

void ShowSchool() //显示校园全景图 {

printf(\┏━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\

printf(\┃ xxxxxxxx大学校园平面图 ┃\\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫\\n\

printf(\┃┏━━━━━ ━━━━━┓ ┃\\n\

printf(\┃┃ ┃ 10.┃ ┃ \\n\

printf(\┃┃ 宿舍楼2 ┃━━━━━ ┃ 宿舍楼1 ┃ \\n\

printf(\┃┗━━━┳━┛ 15┃ ┣━━━━━┫ \\n\

printf(\┃ 11. ┃180 ┃ 10┃ 70┃ \\n\

printf(\┃ ┏┻┓ 150 ┏━━┻━━━━┓┃ ┏┻┓┃\\n\

printf(\┃ ┃体┣━━━┫ 旭日苑 ┣╝ ┃美┃┃\\n\

printf(\┃ 8.┃育┃ 9.┗━━┳━━━━┛ 7.┃食┃┃\\n\

printf(\┃ ┃馆┃ ┃ ┃广┃┃\\n\

printf(\┃ ┗┳┛ ┃ 200 ┃场┃┃\\n\

printf(\┃ ┃ ┃ ┗┳┛┃\\n\

printf(\┃ ┃60 6. ┃ ┃ \\n\

printf(\┃ ┃━━┳━━━━┻━┓ 130┃ \\n\

printf(\┃ ┃ 图书馆 ┣ ╬━━━╝ \\n\

printf(\┃ 80 ┗━━┳━━━┛ 4.┏━┻━━━┓ \\n\

printf(\┃ ┣━━┓━━╝ ┃ ┃ \\n\

printf(\┃ 5. ┃大活┃ ┏┻ ┳┛ \\n\

printf(\┃ ┃学动┃ ┃ 实验楼 ┃ \\n\

printf(\┃ ┃生中┃ ┏┻ ┳┛ \\n\

┃┃┃┃┃┃┃┃┃┃┃┃ printf(\┃ ┃ 心┃ ┃ ┃ ┃\\n\

printf(\┃ ┗┳━┛ 20 ┗━┳━━━┛ ┃\\n\

printf(\┃ ┃100 2.┏━━━┻━┓ ┃\\n\

printf(\┃ ┃ ┃ 教学楼 ┃ ┃\\n\

printf(\┃ ┏━━┻┓ 40 50 ┗━━┳━━┛┏━━━┓┃\\n\

printf(\┃ 3.┃行政楼┣━━━━━━━━━━╝ ┃ 南 ┃┃\\n\

printf(\┃ ┗━━━┛ ┃ ┃东╋西┃┃\\n\

printf(\┃ ┏━┻━━━┓ ┃ 北 ┃┃\\n\

printf(\┃ 1.┃ 北门 ┃ ┗━━━┛┃\\n\

printf(\┗━━━━━━━━┻━━━━━┻━━━━━━━━━━━┛\\n\ }

void ShowRoute(AdjMatrix *G) //显示图的所有路线 {

int i,j;

printf(\校园里一共有%d条路线.\\n\\n\ for(i=1;i<=G->vexnum;i++) for(j=1;j<=i;j++)

if(G->arcs[i][j]!=INFINITY) printf(\\\t距离为：%dm\\n\}

void ShowVex(AdjMatrix *G) //显示所有景点 {

int i;

printf(\校园共有%d个景点，编号、名称及介绍如下:\\n\\n\ for(i=1;i<=G->vexnum;i++)

printf(\}

void Serach(AdjMatrix *G) //查询景点 {

int i,n;

char name[20];

printf(\请选择你要查询的方式：\\n\

printf(\编号 2.名称\\n\ scanf(\

if(n == 1) {

printf(\请输入景点的编号(1~~%d):\ scanf(\ if(VexExit(G,n)) {

printf(\该景点情况及周围景点如下:\\n\

printf(\ %s\\n\\n\ for(i=1;i<=G->vexnum;i++) //找出与该景点相关的路线 if(G->arcs[n][i] != INFINITY)

printf(\ } }

else if(n == 2) {

printf(\该校园有以下景点，请选择:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\

printf(\请输入要查询景点的名称:\ scanf(\

n=Locate(G,name); //通过名称找到该景点的序号 if(VexExit(G,n)) {

printf(\该景点名称、介绍及可以直达的景点如下:\\n\

printf(\ %s\\n\\n\ for(i=1;i<=G->vexnum;i++)

if(G->arcs[n][i]!=INFINITY)

printf(\ if(i>G->vexnum+1)

printf(\此景点为独立的点,返回!\\n\ } } else

printf(\输入错误，返回！\\n\}

void AddRoute(AdjMatrix *G) //增加新路线 {

char name[20];

int start,ending,distance;

ShowRoute(G);

printf(\请输入要增加路线的起点和终点名称:\\n\

printf(\起点:\ scanf(\ start=Locate(G,name); printf(\终点:\ scanf(\

ending=Locate(G,name); printf(\距离:\

scanf(\

//将新路线的距离存入权值数组中 G->arcs[start][ending]=distance; G->arcs[ending][start]=distance;

G->arcnum++; //图的边集加1 printf(\添加新路线成功。\\n\}

void DeleteRoute(AdjMatrix *G) //删除路线 {

char name[20]; int start,ending;

ShowRoute(G);

printf(\请输入要删除路线的起点和终点名称:\\n\ printf(\起点: \ scanf(\ start=Locate(G,name); printf(\终点: \ scanf(\

ending=Locate(G,name);

if(G->arcs[start][ending] == INFINITY)

printf(\您要删除的路线不存在，请重新输入!\\n\ //将对应权值数组中的元素赋值，删除路线 else {

G->arcs[start][ending]=INFINITY ; G->arcs[ending][start]=INFINITY ; G->arcnum--;

printf(\删除路线成功。\\n\ } }

void AddVex(AdjMatrix *G) //增加景点 {

int i;

char name[20]; char intro[100];

printf(\该校园包含以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入增加景点的名称和介绍:\\n\ scanf(\

//图的顶点集先加1，将增加景点的信息赋值到图的末尾景点中 G->vexnum++;

G->vex[G->vexnum].num=G->vexnum; strcpy(G->vex[G->vexnum].name,name); strcpy(G->vex[G->vexnum].introduce,intro); //对新增景点的权值数组元素赋初值 for(i=1;i<=G->vexnum;i++)

G->arcs[G->vexnum][i]=INFINITY; for(i=1;i<=G->vexnum;i++)

G->arcs[i][G->vexnum]=INFINITY; printf(\增加景点成功!\\n\}

void DeleteVex(AdjMatrix *G) //删除景点 {

int i,j,count=0; char name[20];

printf(\该校园有以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入删除景点的名称:\\n\ scanf(\ i=Locate(G,name); if(VexExit(G,i)) {

for(j=1;j<=G->vexnum;j++) //找出与该景点相关的路线数目 if(G->arcs[i][j]!=INFINITY) count++;

//先找到景点在图中的位置，从后往前依次覆盖原值 for(i;i<=G->vexnum;i++) {

G->vex[i].num=G->vex[i+1].num;

strcpy(G->vex[i].name,G->vex[i+1].name);

strcpy(G->vex[i].introduce,G->vex[i+1].introduce); }

G->vexnum--; //图的顶点集减1

G->arcnum=G->arcnum-count; //图的边数目减去与删除景点有关的路线数目

printf(\删除景点成功!\\n\ } }

void Dijkstra(AdjMatrix *G,int start,int ending,int dist[],int path[][MAXVEX]) //求起点到终点的最短路线

{

//dist数组记录各条最短路径长度，path数组记录对应路径上的各顶点 int mindist,i,j,k,t=1;

for(i=1;i<=G->vexnum;i++) //初始化 {

dist[i]=G->arcs[start][i];

if(G->arcs[start][i]!=INFINITY) path[i][1]=start; }

path[start][0]=1;

for(i=2;i<=G->vexnum;i++) //寻找各条最短路线 {

mindist=INFINITY;

for(j=1;j<=G->vexnum;j++) //选择最小权值的路线 if(!path[j][0] && dist[j]

k=j;

mindist=dist[j]; }

if(mindist == INFINITY) return ;

path[k][0]=1;

for(j=1;j<=G->vexnum;j++) //修改路线 {

if(!path[j][0]&&G->arcs[k][j]arcs[k][j]

dist[j]=dist[k]+G->arcs[k][j]; t=1;

while(path[k][t]!=0) //记录最新的最短路线 {

path[j][t]=path[k][t]; t++; }

path[j][t]=k; path[j][t+1]=0; } } }

for(i=1;i<=G->vexnum;i++) if(i == ending) break; printf(\的最短路线为：从%s\ for(j=2;path[i][j]!=0;j++)

printf(\

&& \\n printf(\距离为%dm\\n\}

void Shortcut(AdjMatrix *G) //寻找最短路线 {

char name[20]; int start,ending; int i;

int dist[MAXVEX],path[MAXVEX][MAXVEX]={0}; printf(\校园里有以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入起点景点名称:\ scanf(\ start=Locate(G,name);

printf(\请输入终点景点名称:\ scanf(\

ending=Locate(G,name);

Dijkstra(G,start,ending,dist,path); }

void Prim(AdjMatrix *G,int start) //采用Prim算法求得最短连通路线 {

struct {

int adjvex; //存放顶点序号 int lowcost; //存放权值 }closedge[MAXVEX]; int i,e,k,m,mincost;

closedge[start].lowcost=0; //起始点的权值初始化为0，该顶点加入到生成树集合中

//对除了出发点以外的所有顶点初始化对应的closedge数组 for(i=1;i<=G->vexnum;i++) if(i != start) {

closedge[i].adjvex=start;

closedge[i].lowcost=G->arcs[start][i]; }

//控制选中的n-1条符合条件的边 for(e=1;e<=G->vexnum-1;e++) {

//选择最小权值的边 mincost=INFINITY;

for(k=1;k<=G->vexnum;k++) {

if(closedge[k].lowcost!=0 && closedge[k].lowcost

m=k;

mincost=closedge[k].lowcost; } }

printf(\

从%s--%s:%dm\\n\lowcost);

closedge[m].lowcost=0; //标志该顶点加入到最小生成树集合中

//更新closedge数组信息 for(i=1;i<=G->vexnum;i++)

if(i!=m && G->arcs[m][i]

//一旦发现有更小的权值边出现，则替换原有信息 {

closedge[i].lowcost=G->arcs[m][i]; closedge[i].adjvex=m; } } }

void MiniSpanTree(AdjMatrix *G) //查询从某个景点的最短连通路线 {

char name[20]; int start; int i;

for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入起始地点名称: \ scanf(\ start=Locate(G,name);

printf(\从%s开始的最短连通路线为:\\n\\n\ Prim(G,start); }

int m=1,min=INT_MAX; int path[20]={0}; int tag;

void DFS(AdjMatrix *G,int start,int ending,int stack[],int visited[]) //深度遍历查找所有路径 {

int i, j;

for(i=1; i<=G->vexnum; i++) {

if(G->arcs[start][i] != INFINITY && visited[i]==0) {

if(i == ending)//如果深搜到了终点，就输出刚才经过的路径

{

// tag用于判断找最优路径还是所有路径

if(tag==1) // 找所有路径时输出路径 { for(j=0; j

else//如果该点不是终点 {

visited[i]=1;

stack[m] = i;//将该点存起来 m++;

DFS(G,i,ending,stack,visited);//接着深搜 visited[i]=0; m--; } } } }

void SimpleRoute(AdjMatrix *G) //查询两个景点间的最优路径（中转次数最少） {

char name[20]; int i;

int start,ending; int stack[20]={0}; int visited[20]={0};

printf(\该校园包含以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\

printf(\请输入起始地点名称: \ scanf(\ start=Locate(G,name); stack[0]=start;

printf(\请输入终止地点名称: \ scanf(\

ending=Locate(G,name); visited[start]=1;

tag=0;

DFS(G,start,ending,stack,visited);

printf(\最优路径即中转次数最少的路径为：\\n\

for(i=0;i

printf(\ printf(\}

void SearchAllRoute(AdjMatrix *G) //输出两景点之间的所有路径 {

char name[20]; int start,ending; int i;

int stack[20]={0}; int visited[20]={0};

printf(\校园中有以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入起始地点名称: \ scanf(\ start=Locate(G,name); stack[0]=start;

printf(\请输入终止地点名称: \ scanf(\

ending=Locate(G,name); visited[start]=1; tag=1;

DFS(G,start,ending,stack,visited); }

void menu1() //开始菜单界面 {

system(\

printf(\~~~~~~~~~~~~~*\\n\

printf(\ *\\n\ printf(\ *\\n\

printf(\ 欢迎进入西安邮电大学校园导游系统 *\\n\

printf(\ *\\n\ printf(\ *\\n\

printf(\~~~*\\n\

Sleep(2000); }

void menu2() //退出菜单界面 {

system(\

printf(\~~~~~~~~~~~~~*\\n\

printf(\ *\\n\ printf(\ *\\n\

printf(\ 谢谢使用！\\t\\t\\t *\\n\ printf(\ *\\n\ printf(\ *\\n\

printf(\~~~*\\n\\n\\n\\n\\n\\n\\n\ Sleep(3000); }

void menu() //显示主菜单 {

system(\

printf(\欢迎使用西安邮电大学校园导游系统~~~~~~~~~~~~~~~~~~~*\\n\

printf(\ *\\n\ printf(\ 1. 浏览校园全景图 *\\n\

printf(\ 2. 显示校园所有景点以及路线 *\\n\

printf(\ 3. 查询某景点信息 *\\n\

printf(\ 4. 增加路线 *\\n\

printf(\ 5. 撤销路线 *\\n\

printf(\ 6. 增加景点 *\\n\

printf(\ 7. 删除景点 *\\n\

printf(\ 8. 查询两景点之间的简单路径（中转次数最少） *\\n\

printf(\ 9. 查询两景点之间的长度最短路线 *\\n\

printf(\ 10.查询图中景点的最佳布网方案（最小生成树） *\\n\

printf(\ 11.查询两景点之间的所有路径 *\\n\

printf(\ 12.输入校园图信息 *\\n\

printf(\ 0. 退出菜单 *\\n\

printf(\ *\\n\

printf(\~~~~~~~~~~~~*\\n\\n\ }

int main() {

AdjMatrix G; int choice; menu1();

system(\ do {

menu();

printf(\请输入你要选择项的编号：\ scanf(\

switch(choice) {

case 1: {

system(\

Readfile(&G); ShowSchool(); printf(\按任意键返回...\ getch();

system(\ } case 2: {

system(\

Readfile(&G); ShowVex(&G);ShowRoute(&G); printf(\按任意键返回...\ getch();

system(\ } case 3: {

system(\

Readfile(&G); Serach(&G); printf(\按任意键返回...\ getch();

system(\ }

case 4: {

system(\

Readfile(&G); AddRoute(&G); Savefile(&G); printf(\按任意键返回...\ getch();

system(\ } case 5: {

system(\

Readfile(&G); DeleteRoute(&G); Savefile(&G); printf(\按任意键返回...\ } case 6: {

} case 7: {

} case 8: {

} case 9: {

} case 10:{

}

getch();

system(\system(\

Readfile(&G); AddVex(&G); Savefile(&G); printf(\按任意键返回...\getch();

system(\system(\

Readfile(&G); DeleteVex(&G); Savefile(&G); printf(\按任意键返回...\getch();

system(\system(\

Readfile(&G);SimpleRoute(&G); printf(\按任意键返回...\getch();

system(\system(\

Readfile(&G); Shortcut(&G); printf(\按任意键返回...\getch();

system(\system(\Readfile(&G);

MiniSpanTree(&G);

printf(\按任意键返回...\getch();

system(\

case 11:{

system(\

Readfile(&G); SearchAllRoute(&G); printf(\按任意键返回...\ getch();

system(\ } case 12:{

system(\

Creat(&G); Savefile(&G); printf(\按任意键返回...\ getch();

system(\ } case 0: {

system(\ menu2();break; }

default: system(\ }

}while(choice);

return 0; }

本文来源：https://www.bwwdw.com/article/uhc6.html