前言
课程已经过大半,相信很多小伙伴们都要迎来大作业，最近时间比较紧，没有及时更新,就先把我之前写的校园导航系统放上来供大家参考,这几天我有时间会对其优化并加上界面增加些功能。
1. 设计目的
本课程设计的目的就是要达到理论与实际应用相结合,提高我们组织数据及其编写大型程序的能力，并培养积极的,良好的程序设计内容。设计中要求综合运用所学知识，通过分析，设计，编码，调试等各环节的训练，使我们更加深刻掌握数据结构和算法设计技术。
2.设计内容与要求
2.1设计内容
本课题主要实现对校园景点的导航，具体功能有学校地图查看、查看浏览路线、查看各地点间最短路径、景点信息查询、查询各地点间可行路径、打印临接矩阵、更改图信息、退出查询等功能。
2.2课题要求
- 设计校园平面图。其中具有代表性的地点至少含有12个，平面图中顶点表示校内代表性的地点，边上的权值表示两地点之间的距离；
- 为实现校园导航系统子功能的管理，设计主控菜单；
- 为来访客人提供图中任意地点相关信息的查询；
4.为来访客人提供图中任意两地点之间最短路线的查询，指点地点到其他所有地点最短路线的 查询
3.设计思路
3.1关键问题描述
（1）数据采集与地图测绘;
（2）如何建立图信息；
（3）如何存储景点信息；
（4）如何定义邻接表类型；
（5）如何解决各地点间最短路径问题；
(6) 如何在运行界面正确输入所需查询的信息；
关键问题解决方法：
(1)数据采集与地图绘测
(2)如何建立图信息
利用邻接矩阵存储，其中图所用到的结构体为: typedef char DataType; typedef int WeightType; typedef struct //以下定义邻接矩阵类型 { int number; //顶点编号 DataType xinxi; //顶点其他信息 }VertexType; //顶点类型
(3)如何存储景点信息
Typedef int WeightType; typedef struct { WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵数组 int Nv; //顶点数 int Ne; //边数 VertexType Data[MaxVertexNum]; //存放顶点信息 }MGraph; //完整的图邻接矩阵类型
(4)如何定义邻接表类型
typedef struct ANode //定义邻接表类型 { int Adjv; //该边的邻接点编号 struct ANode *Next; //指向下一条边的指针 WeightType weight; //该边的相关信息如权值（用整形表示） }ENode; //边结点类型 typedef struct Vnode { DataType xinxi; //顶点其他信息 ENode *FirstEdge; //指向第一条边 }VNode; //邻接表头结点类型 typedef struct { VNode Adjlist[MaxVertexNum]; //邻接表头结点数组 int Nv,Ne; //图中顶点数n和边数e }LGraph;
(5)如何解决各地点间最短路径问题
void PutShortlu(MGraph g,int dist[],int path[],int S[],int z,int &Nv,int B[MaxVertexNum],char R[MaxVertexNum][MaxVertexNum]) //输出从顶点v出发的所有最短路径 { int i,j,k; int apath[MaxVertexNum],d; //存放一条最短路径(逆向)及其顶点个数 printf("输入你要到达的地点："); i=input2(Nv,B); //循环输出从顶点v到i的路径 i=i-1; if (S[i]==1 && i!=z) { printf(" 从地点%s到地点%s的最短路径长度为:%d\n 路径为:",R[z],R[i],dist[i]); d=0; apath[d]=i; //添加路径上的终点 k=path[i]; if (k==-1) //没有路径的情况 printf("无路径\n"); else //存在路径时输出该路径 { while (k!=z) { d++; apath[d]=k; k=path[k]; } d++; apath[d]=z; //添加路径上的起点 printf("%s",R[apath[d]]); //先输出起点 for (j=d-1;j>=0;j--) //再输出其他顶点 printf("->%s",R[apath[j]]); printf("\n"); } } } void Shortlu(MGraph g,int z,int &Nv,int B[MaxVertexNum],char R[MaxVertexNum][MaxVertexNum])//找寻最短路径函数 { int dist[MaxVertexNum],path[MaxVertexNum]; int S[MaxVertexNum]; //S[i]=1表示顶点i在S中, S[i]=0表示顶点i在U中 int Mindis,i,j,u; for (i=0;i<g.Ne;i++) { dist[i]=g.G[z][i]; //距离初始化 S[i]=0; //S[]置空 if (g.G[z][i]<INFINIFY) //路径初始化 path[i]=z; //顶点z到顶点i有边时，置顶点i的前一个顶点为z else path[i]=-1; //顶点z到顶点i没边时，置顶点i的前一个顶点为-1 } S[z]=1;path[z]=0; //源点编号v放入S中 for (i=0;i<g.Nv-1;i++) //循环直到所有顶点的最短路径都求出 { Mindis=INFINIFY; //Mindis置最大长度初值 for (j=0;j<g.Nv;j++) //选取不在S中（即U中）且具有最小最短路径长度的顶点u if (S[j]==0 && dist[j]<Mindis) { u=j; Mindis=dist[j]; } S[u]=1; //顶点u加入S中 for (j=0;j<g.Nv;j++) //修改不在S中（即U中）的顶点的最短路径 if (S[j]==0) if (g.G[u][j]<INFINIFY && dist[u]+g.G[u][j]<dist[j]) { dist[j]=dist[u]+g.G[u][j]; path[j]=u; } } PutShortlu(g,dist,path,S,z,Nv,B,R); //输出最短路径 }
(6) 在运行界面正确输入所需查询信息的方法
通过两个自定义函数input1和input2来正确输入所需查询的信息： input1函数： int input1() //输入函数1 { int x; char m=true; scanf("%d",&x); while(m) { if(x>8 || x<1) { printf("输入错误，请重新输入:"); scanf("%d",&x); } else m=false; } return x; }
菜单查询顺序包含8项，分别是1.地图查看、2.查看浏览路线、3.查看各地点间最近路线、4.地点信息查看、5.查询各地点间可行路径、6.打印邻接矩阵、7.修改图信息、8.退出查询，1~8分别代表相应的查询选项。通过函数if函数来确认输入的数字是否输入正确，当输入数字<1或>8时，显示“输入错误，请重新输入”。
input2函数： int input2() //输入函数2 { int x; char m=true; scanf("%d",&x); while(x!=666) { while(m) { if(x<1||x>18) { printf("输入错误，请重新输入:"); scanf("%d",&x); } else m=false; } break; } return x;}
数序1~18分别代表相应的景点建筑，当输入数字<1或>18时，显示“输入错误，请重新输入”，返回菜单输入“88”。
3.2程序处理流程图
4.实现过程
4.1功能实现
本程序主要实现了学校地图查看，查看浏览路线，查看各地点间最近路线，地点信息查看，查询各地点间可行路径，打印邻接表，修改地图信息完成了添加和删除地标功能，修改和删除路径功能暂未实现.
重要函数调用:
main()函数调用Caidan()函数来确定用户所要进行的选择。
Bestlu()函数找寻最佳浏览路线
原型:void Bestlu(LGraph *G,int z,char A[MaxVertexNum][MaxVertexNum]); 其中，G为创建的结构体对象；A为邻接表矩阵数组；
Shortlu()函数找寻最短路径
原型：void Shortlu(MGraph g,int z,int &Nv,int B[MaxVertexNum],char R[MaxVertexNum][MaxVertexNum]);
用Caidan()函数调用modify()图修改函数，modify()调用input2()和input3()等输入函数
Modify（）函数原型：
void modify(int A[MaxVertexNum][MaxVertexNum],int &Nv,int &Ne,char Q[MaxVertexNum][MaxVertexNum],int B[MaxVertexNum]) 其中包括了图的增、删。首先调用input3（）函数获取值，通过while和内置for循环判断添加的地标节点是否已经存在，若不存在，将新增节点添加进B数组，详见源代码；调用input2()函数获值，通过for循环将想要删除的节点进行初始化删除，并对存放点信息和节点编号的数组Q、B更新；
4.2 测试运行 图4.1菜单页面
图4.1菜单页面
图4.2学校地图查看
图4.3查看浏览路线
图4.4查看各地点间最短路径
图4.5景点信息查询
4.6查询各地点间可行路径
图4.7打印邻接矩阵
图4.8增加地标结点
4.9删除地标结点
图4.10退出菜单
5.代码实现
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<malloc.h> #include<string.h> #define INFINIFY 65535 //定义无穷大 #define MaxVertexNum 100 //定义最大定点数 int visited[MaxVertexNum]; char Q[MaxVertexNum][MaxVertexNum] = { {" 1 新生公寓(java) 住宿环境好，离教学楼近"}, {" 2 学二食堂 伙食好，种类多样，价格便宜"}, {" 3 f栋教学楼 计算机学院的学生上课的集中地"}, {" 4 e栋教学楼 商管学生上课的集中地"}, {" 5 图书馆 造型优美，学习氛围浓厚"}, {" 6 c栋教学楼 翻转教室和实验室的集中地"}, {" 7 报告厅 场地超级大，是举行大型学术的场所"}, {" 8 运动场 是个散步，运动，看日落的好地方" }, {" 9 B栋教学楼 计算机系办公楼"}, {" 10 A栋教学楼 是学校创建最早的教学楼之一"}, {" 11 行政楼 行政办公大楼"}, {" 12 继教公寓 很安静幽美的地方"}, {" 13 雨湖 湖水清澈周边环境很美"}, {" 14 足球场 场地不算很大，但足够给喜欢踢足球的人过过瘾"}, {" 15 D栋教学楼 国际交流办公处"}, {" 16 龙翔食堂 饭菜很农家，给人一种家的感觉"}, {" 17 继续教育学院 离公交站最近，坐车很方便"}, {" 18 国际交流中心 商务英语学生上课的地方,可以经常看到外国人"}, }; char R[MaxVertexNum][MaxVertexNum] = { {" 1 新生公寓(java) "}, {" 2 学二食堂 "}, {" 3 f栋教学楼 "}, {" 4 e栋教学楼 "}, {" 5 图书馆 "}, {" 6 c栋教学楼 "}, {" 7 报告厅 "}, {" 8 运动场 "}, {" 9 B栋教学楼 "}, {" 10 A栋教学楼 "}, {" 11 行政楼 "}, {" 12 继教公寓 "}, {" 13 雨湖 "}, {" 14 足球场 "}, {" 15 D栋教学楼 "}, {" 16 龙翔食堂 "}, {" 17 继续教育学院 "}, {" 18 国际交流中心 "}, }; int A[MaxVertexNum][MaxVertexNum] = { {0,200,250,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,800}, {200,0,50,INFINIFY,INFINIFY,INFINIFY,50,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {250,50,0,50,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,50,0,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,0,100,200,60,INFINIFY,INFINIFY,INFINIFY,1200,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,0,INFINIFY,50,900,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,50,INFINIFY,INFINIFY,200,INFINIFY,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,100,60,50,INFINIFY,0,INFINIFY,700,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,900,INFINIFY,INFINIFY,0,50,500,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,700,50,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,500,INFINIFY,0,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,1200,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,0,50,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,50,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,0,1000,INFINIFY,800,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,1000,0,500,INFINIFY,300}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,500,0,100,INFINIFY}, {INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,800,INFINIFY,100,0,INFINIFY}, {800,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,300,INFINIFY,INFINIFY,0}, }; int B[MaxVertexNum] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 }; typedef char DataType; typedef int WeightType; typedef struct //以下定义邻接矩阵类型 { int number; //顶点编号 DataType xinxi; //顶点其他信息 }VertexType; //顶点类型 typedef struct { WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵数组 int Nv; //顶点数 int Ne; //边数 VertexType Data[MaxVertexNum]; //存放顶点信息 }MGraph; //完整的图邻接矩阵类型 typedef struct ANode //定义邻接表类型 { int Adjv; //该边的邻接点编号 struct ANode* Next; //指向下一条边的指针 WeightType weight; //该边的相关信息如权值（用整形表示） }ENode; //边结点类型 typedef struct Vnode { DataType xinxi; //顶点其他信息 ENode* FirstEdge; //指向第一条边 }VNode; //邻接表头结点类型 typedef struct { VNode Adjlist[MaxVertexNum]; //邻接表头结点数组 int Nv, Ne; //图中顶点数n和边数e }LGraph; void Caidan(); //菜单函数 void map();//地图绘制 int input1(); //输入函数1 int input2(int& Nv, int B[MaxVertexNum]); //输入函数2 int input3(); //输入函数3 void place(char Q[MaxVertexNum][MaxVertexNum], int& Nv); ///景点信息查询函数 void CreateGraph(MGraph& g, int A[MaxVertexNum][MaxVertexNum], int Nv, int Ne); //创建图的邻接矩阵 void PutMGraph(MGraph g); //输出邻接矩阵g void CreateLGraph(LGraph*& G, int A[MaxVertexNum][MaxVertexNum], int Nv, int Ne); //创建地图的邻接表 void AvabilePath(LGraph* G, int Nv, char Q[MaxVertexNum][MaxVertexNum], int B[MaxVertexNum]); ///输出各地点间可行路径函数 void DestroyLGraph(LGraph* G); ///销毁图的邻接表 void Bestlu(LGraph* G, int z, char A[MaxVertexNum][MaxVertexNum]); ///找寻最佳浏览路线函数 void PutShortlu(MGraph g, int dist[], int path[], int S[], int z, int& Nv, int B[MaxVertexNum], char R[MaxVertexNum][MaxVertexNum]); //输出从顶点v出发的所有最短路径 void Shortlu(MGraph g, int z, int& Nv, int B[MaxVertexNum], char R[MaxVertexNum][MaxVertexNum]); //找寻最短路径函数 void modify(int A[MaxVertexNum][MaxVertexNum], int& Nv, int& Ne, char Q[MaxVertexNum][MaxVertexNum], int B[MaxVertexNum]); /图的修改函数 void Caidan()//菜单函数 { printf(" \t************************欢迎使用校园导航系统****************************"); printf(" \n\t** 欢迎来到广东东软学院 **"); printf(" \n\t** 菜单选择 **"); printf(" \n\t** **"); printf(" \n\t** 1、学校地图查看 2、查看浏览路线 **"); printf(" \n\t** **"); printf(" \n\t** 3 查看各地点间最短路径 4、景点信息查询 **"); printf(" \n\t** **"); printf(" \n\t** 5、查询各地点间可行路径 6、打印邻接矩阵 **"); printf(" \n\t** **"); printf(" \n\t** 7、修改地图信息 8、退出 **"); printf(" \n\t** **"); printf(" \n\t************************************************************************"); printf("\n"); printf("请输入你的选择:"); } void map()//地图查看 { printf("\n"); printf("\n"); printf("***********************************************************************************************************************\t\t\t\t\t"); printf("\n"); printf("**----------------------------------------------------------(10)a栋教学楼--------------------------------------------**\t\t\t\t\t"); printf("\n"); printf("**----------------------------------------------------------(9)b栋教学楼---------------------------------------------**\t\t\t\t\t"); printf("\n"); printf("**---(8)运动场-----------------------(6)c栋教学楼------------------------------(11)行政楼----------------------------**\t\t\t\t\t"); printf("\n"); printf("**-----------------------------------(5)图书馆---------------------------------(12)继教学院-----(13)雨湖-------------**\t\t\t\t\t"); printf("\n"); printf("**---(4)e栋教学楼-----------------------------------------------(14)足球场-------------------------------------------**\t\t\t\t\t"); printf("\n"); printf("**---(3)f栋教学楼----------------(7)报告厅---------------------------------------------------------------------------**\t\t\t\t\t"); printf("\n"); printf("**-- (1)新生公寓------------------(2)学二食堂------------------------------------------------------------------------**\t\t\t\t\t"); printf("\n"); printf("**------------------------ (18)国际交流中心--------(15)d栋教学楼-----------------(16)龙翔食堂-----(17)继续教育学院---**\t\t\t\t\t"); printf("\n"); printf("***********************************************************************************************************************\t\t\t\t\t"); printf("\n"); printf("\n"); } int input1() { //判断菜单输入的数 是否合理，不合理则再次输入 int m; char n = 1; scanf("%d", &m); while (n) { if (m < 1 || m>8) { printf("输入错误,请再次输入:"); scanf("%d", &m); } else n = 0; } return m; } void CreateLGraph(LGraph*& G, int A[MaxVertexNum][MaxVertexNum], int Nv, int Ne) //创建地图的邻接表 { int i, j; ENode* p; G = (LGraph*)malloc(sizeof(LGraph)); for (i = 0; i < Nv; i++) G->Adjlist[i].FirstEdge = NULL; //给邻接表所有头结点的指针域置初值 for (i = 0; i < Nv; i++) //检查邻接矩阵中的每一个元素 for (j = Nv - 1; j >= 0; j--) if (A[i][j] != 0 && A[i][j] != INFINIFY) //存在一条边 { p = (ENode*)malloc(sizeof(ENode)); //创建一个结点p p->Adjv = j; p->weight = A[i][j]; p->Next = G->Adjlist[i].FirstEdge; //采用头插入法插入节点p G->Adjlist[i].FirstEdge = p; } G->Nv = Nv; G->Ne = Nv; } void Bestlu(LGraph* G, int z, char R[MaxVertexNum][MaxVertexNum]) ///找寻最佳浏览路线函数 { ENode* p; int t[MaxVertexNum]; int top = -1, y, x, i; for (i = 0; i < G->Nv; i++) visited[i] = 0; ///将访问标志均置为0,代表未访问过 printf("%s", R[z]); ///访问顶点v visited[z] = 1; ///表示顶点v已被访问 top++; t[top] = z; ///将顶点v进栈 while (top > -1) ///判断栈是否为空，为空则不进入循环 { x = t[top]; ///取栈顶顶点x作为当前顶点 p = G->Adjlist[x].FirstEdge; ///找顶点x的第一个相邻点 while (p != NULL) ///判断节点是否为空 { y = p->Adjv; ///x的相邻点为y if (visited[y] == 0) ///判断顶点y是否已访问 { printf(" -> %s", R[y]); ///访问顶点y visited[y] = 1; ///重置顶点y已被访问 top++; t[top] = y; ///将顶点y进栈 break; ///退出循环，即再处理栈顶点的顶点（体现先进后出） } p = p->Next; ///找顶点x的下一个相邻点 } if (p == NULL) top--; ///若顶点x在没有相邻点，将其退栈 } printf("\n"); } int input2(int& Nv, int B[MaxVertexNum]) //输入函数2 { int m, y = 0; char n = 1; scanf("%d", &m); while (m != 88) ///判断输入是否进行循环 { while (n) ///判断输入是否进行循环 { if (m<1 || m>Nv) ///判断输入值的是否正确 { printf("该地标节点不存在请重新输入:"); scanf("%d", &m); ///判断输入错误重新输入 } if (B != NULL) ///判断一位数组B是否为空 { for (int i = 0; i < MaxVertexNum; i++) ///判断该数值是否存在于数组B if (B[i] == m) y++; ///存在则y++ if (y <= 0) ///判断该输入节点是否存在 { printf("该地标节点不存在请重新输入:"); scanf("%d", &m); ///不存在则重新输入 } else n = 0; ///如果属于上面两种情况则退出该循环 } else n = 0; } break; } return m; ///返回输入值 } void DestroyLGraph(LGraph* G)//销毁邻接表 { ENode* pre, * p; for (int i = 0; i < G->Nv; i++) { pre = G->Adjlist[i].FirstEdge; if (pre != NULL) { p = pre->Next; while (p != NULL) { free(pre); pre = p; p = p->Next; } free(pre); } } free(G); } void CreateGraph(MGraph& g, int A[MaxVertexNum][MaxVertexNum], int Nv, int Ne) //创建图的邻接矩阵 { int i, j; g.Nv = Nv; g.Ne = Ne; for (i = 0; i < g.Nv; i++) for (j = 0; j < g.Ne; j++) g.G[i][j] = A[i][j]; } void PutMGraph(MGraph g) //输出邻接矩阵g { int i, j; for (i = 0; i < g.Nv; i++) { for (j = 0; j < g.Nv; j++) if (g.G[i][j] != INFINIFY) printf("%4d", g.G[i][j]); else printf("%4s", "∞"); printf("\n"); } } void PutShortlu(MGraph g, int dist[], int path[], int S[], int z, int& Nv, int B[MaxVertexNum], char R[MaxVertexNum][MaxVertexNum]) //输出从顶点v出发的所有最短路径 { int i, j, k; int apath[MaxVertexNum], d; //存放一条最短路径(逆向)及其顶点个数 printf("输入你要到达的地点："); i = input2(Nv, B); //循环输出从顶点v到i的路径 i = i - 1; if (S[i] == 1 && i != z) { printf(" 从地点%s到地点%s的最短路径长度为:%d\n 路径为:", R[z], R[i], dist[i]); d = 0; apath[d] = i; //添加路径上的终点 k = path[i]; if (k == -1) //没有路径的情况 printf("无路径\n"); else //存在路径时输出该路径 { while (k != z) { d++; apath[d] = k; k = path[k]; } d++; apath[d] = z; //添加路径上的起点 printf("%s", R[apath[d]]); //先输出起点 for (j = d - 1; j >= 0; j--) //再输出其他顶点 printf("->%s", R[apath[j]]); printf("\n"); } } } void Shortlu(MGraph g, int z, int& Nv, int B[MaxVertexNum], char R[MaxVertexNum][MaxVertexNum])//找寻最短路径函数 { int dist[MaxVertexNum], path[MaxVertexNum]; int S[MaxVertexNum]; //S[i]=1表示顶点i在S中, S[i]=0表示顶点i在U中 int Mindis, i, j, u; for (i = 0; i < g.Ne; i++) { dist[i] = g.G[z][i]; //距离初始化 S[i] = 0; //S[]置空 if (g.G[z][i] < INFINIFY) //路径初始化 path[i] = z; //顶点z到顶点i有边时，置顶点i的前一个顶点为z else path[i] = -1; //顶点z到顶点i没边时，置顶点i的前一个顶点为-1 } S[z] = 1; path[z] = 0; //源点编号v放入S中 for (i = 0; i < g.Nv - 1; i++) //循环直到所有顶点的最短路径都求出 { Mindis = INFINIFY; //Mindis置最大长度初值 for (j = 0; j < g.Nv; j++) //选取不在S中（即U中）且具有最小最短路径长度的顶点u if (S[j] == 0 && dist[j] < Mindis) { u = j; Mindis = dist[j]; } S[u] = 1; //顶点u加入S中 for (j = 0; j < g.Nv; j++) //修改不在S中（即U中）的顶点的最短路径 if (S[j] == 0) if (g.G[u][j] < INFINIFY && dist[u] + g.G[u][j] < dist[j]) { dist[j] = dist[u] + g.G[u][j]; path[j] = u; } } PutShortlu(g, dist, path, S, z, Nv, B, R); //输出最短路径 } void place(char Q[MaxVertexNum][MaxVertexNum], int& Nv) ///景点信息查询 { int i; for (i = 0; i < Nv; i++) { printf("%s\n", Q[i]); } } void AvabilePath(LGraph* G, int Nv, char R[MaxVertexNum][MaxVertexNum], int B[MaxVertexNum]) ///输出各地点间可行路径函数 { printf("输入你所需要查询的地点坐标，返回菜单请输入(88):"); ENode* p; int i, j; i = input2(Nv, B); ///输入需要查询地标的编号 while (i != 88) ///判断输入值是否为88，是则返回主菜单 { p = G->Adjlist[i - 1].FirstEdge; ///指向需要查询地点的第一条边 printf("地点%s的可行路径:\n", R[i - 1]); if (p == NULL) ///判断该地点是否存在边 printf("不存在该地点,无可行路径"); while (p != NULL) { j = p->Adjv; printf(" 可以到达%3s路程长为%d米\n", R[j], p->weight); p = p->Next; ///指向下一条边 } printf("\n"); printf("继续查询请输入地点坐标，返回菜单请输入(88):"); i = input2(Nv, B); } } void modify(int A[MaxVertexNum][MaxVertexNum], int& Nv, int& Ne, char Q[MaxVertexNum][MaxVertexNum], int B[MaxVertexNum]) /图的修改函数 { MGraph g; int a,b,c,d,t,i=0,j; int w = 0; printf("\n"); printf("\n"); printf("\t**************修改菜单***************"); printf("\n\t** (1)增加地标节点 **"); printf("\n\t** (2)删除地标节点 **"); printf("\n\t*************************************\n"); printf("输入你需要查询的菜单选项编号:"); a = input3(); ///调用input3函数获取值 switch (a) ///对数值a进行判断 { case 1: printf("输入需要添加的地标节点的编号:"); scanf("%d", &b); while (i != Nv) ///判断是否添加的地标节点已存在 { if (B != NULL) { for (i = 0; i < Nv; i++) if (B[i] == b) { printf("该地标节点已存在请重新输入:"); scanf("%d", &b); break; } } else break; } B[b - 1] = b; ///将新增的结点添加进B数组 printf("输入地标节点的编号和名称[(编号)名称]:"); scanf("%s", &Q[Nv]); printf("输入增加的地标节点与其余地标节点直接连接的路径数目:"); scanf("%d", &c); if (b >= Nv) ///如果添加的地标节点编号超过现有的便将该数组进行扩建并将新的行与列进行初始化 { for (i = 0; i < MaxVertexNum; i++) for (j = 0; j < MaxVertexNum; j++) { if (i == Nv) A[i][j] = INFINIFY; if (j == Nv) A[i][j] = INFINIFY; if (i == Nv && j == Nv) A[i][j] = 0; } Nv = Nv + 1; Ne = Ne + c; ///将该二维数组的信息进行更新 } while (w < c) { printf("依次输入该地点能直接到达的地点编号和两地标之间的距离\n"); printf("输入格式:编号、距离之间用英文逗号隔开(x,y):"); scanf("%d,%d", &d, &t); ///输入新增地标节点的编号、距离和终止值 for (i = 0; i < MaxVertexNum; i++) ///将该节点对应的边进行添加 for (j = 0; j < MaxVertexNum; j++) { if (i == (d - 1) && j == (b - 1)) { A[i][j] = t; A[j][i] = t; w++; } } } printf("已结束输入，输出新生成的图:\n"); CreateGraph(g, A, Nv, Ne); PutMGraph(g); break; case 2: printf("请输入需要删除的地标节点："); b = input2(Nv, B) - 1; ///通过调用函数input2获取值 for (i = 0; i < MaxVertexNum; i++) ///将想要删除的节点进行初始化删除 for (j = 0; j < MaxVertexNum; j++) { if (i == b) A[i][j] = INFINIFY; if (j == b) A[i][j] = INFINIFY; } for (i = 0; i < Nv; i++) ///将存放节点信息和节点编号的数组Q、b进行更新 if (i == b || i > b) { strcpy(Q[i], Q[i + 1]); ///因为维数组存放的为字符元素所以调用函数strcpy将以删除节点后的结点信息向前覆盖 B[i] = B[i + 1]; } CreateGraph(g, A, Nv, Ne); PutMGraph(g); break; } } int input3() //输入函数3 { int x; char m = 1; scanf("%d", &x); while (m) { if (x > 2 || x < 1) ///判断数值是否输入正确 { printf("输入错误，请重新输入:"); scanf("%d", &x); } else m = 0; ///输入正确则退出循环 } return x; ///返回该输入值 } int main() { Caidan(); MGraph g; LGraph* G; int Nv = 18, Ne = 24; int x, z; x = input1(); while (1) { switch (x) { case 1: printf("\n学校地图查看:"); map(); printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n"); printf("\n"); Caidan(); x = input1(); break; case 2: printf("输入你所在的位置，为你规划浏览路线："); CreateLGraph(G, A, Nv, Ne); z = input2(Nv, B) - 1; Bestlu(G, z, R); printf("\n"); DestroyLGraph(G); printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n"); printf("\n"); Caidan(); x = input1(); break; case 3: printf("输入你所在的位置，为你规划最短路径："); CreateGraph(g, A, Nv, Ne); z = input2(Nv, B) - 1; Shortlu(g, z, Nv, B, R); printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n"); printf("\n"); Caidan(); x = input1(); break; case 4: printf("\n地点信息查看:"); printf("\n"); place(Q, Nv); printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n"); printf("\n"); Caidan(); x = input1(); break; case 5: printf("\n各地点间可行路径查看:\n"); CreateLGraph(G, A, Nv, Ne); AvabilePath(G, Nv, R, B); DestroyLGraph(G); printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n"); printf("\n"); Caidan(); x = input1(); break; case 6: printf("\n打印邻接矩阵:\n"); CreateGraph(g, A, Nv, Ne); PutMGraph(g); printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n"); printf("\n"); Caidan(); x = input1(); break; case 7: modify(A, Nv, Ne, Q, B); printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n"); printf("\n"); Caidan(); x = input1(); } if (x == 8) break; } printf("\n已退出系统，想要继续操作请重新进入！\n"); return 1; }
