校园导游系统 数据结构课程设计 简单且功能齐全

【问题描述】
　　用无向网表示南农校园景点平面图，所含景点不少于10个。图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等相关信息。
【基本要求】
　　（1） 查询各景点的相关信息；
　　（2） 查询图中任意两个景点间的最短路径。
　　（3） 查询图中任意两个景点间的所有路径。
　　（4） 增加、删除、更新有关景点和道路的信息。
【算法设计思想】
（1）图的存储结构：运用邻接矩阵来存储无向图的有关信息，各顶点的数据类型为了方便使用采用数字整形类型来标记。共有十个顶点分别记为1-10，共有11条路径，路径长度提前给出并存在邻接矩阵当中。
（2）菜单函数：为了保证能实现要求的6个功能，需要设计一个菜单函数来选择所需要的功能，同时设计一个退出功能。为了保证健壮性，还需要菜单函数自身实现递归直到使用了退出功能。
（3）查询函数算法：在菜单功能选择了功能1菜单功能后，进入到查询功能。通过switch，case来实现输入不同节点名称输出不同的介绍内容。
（4）最短路径算法：运用Floyd算法分别构建最小距离矩阵和选择路径矩阵。Floyd算法思想即为循环更新这两个矩阵。对于每一对节点u,v，循环查找是否存在一个顶点w使得u->w->v的距离比原来u->v的距离要小，如果是则更新该路径。分别设两个二位矩阵，命名为d[][]，以及path[][]，先初始化d[][]使该矩阵和邻接矩阵一样，再初始化path[][]。之后开始更新这两个矩阵，三次循环来查找是否存在路径更小的点，如果有更新这两个矩阵。最后输出结果，注意保存再矩阵中的点从0-9，但是为了方便用户所以显示出来的是1-10，因此在输出时要主要转换。
（5）所有路径算法：自身深度遍历递归。提前定义好全局start，end变量，以及两个数组stack[]（用来存储路径上的顶点）,v[]（初始全为0，为了标志是否被访问过）,为了简洁不使用栈，但为了实现栈的功能使用stack[]数组和全局变量top的组合使用。先将起点标记为访问过，并将该顶点放到数组stack中，top++，然后在该顶点的临界矩阵中找它的下一个点，如果有且未被访问过则将下一个点递归。因为要输出所有的路径，在递归结束后要将起点置为未被访问，top–，来实现所有路径的访问。
（6）插入算法：最后用临界矩阵来表示结果。要将新顶点的序号以及和其他顶点的路径信息存到邻接矩阵中，所以要新建一行。首先分析新顶点可能和其他不止一条路有路径，所以要循环询问用户是否该点与其他点有路径，用switch，case来判断何时结束，如果为1则继续修改临界矩阵的信息，如果为0则输出该邻接矩阵展示结果并结束循环。
（7）删除算法：首先要删除所有与这个被删除的节点相连的所有节点，即将这些原来存放权值的邻接矩阵信息换成32767，再将G.vexs[]数组向前移。最后将被删除节点后面以及右边的元素分别向前，向左移动。最后输出邻接矩阵。
（8）更新算法：更新两点之间权值的大小。只需要修改邻接矩阵中相应的数值即可，并用邻接矩阵来展示结果。
【源代码】

头文件：
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAXNum 20
#define MAXint 32767
#define MAXVex 10
#define MAXArc 11	
#define STACK_INIT_SIZE 20
typedef int ArcType;			//权值类型
typedef int VertexType;
typedef int SElemType;
int stack[120],v[100]={0},top=0,start,end;		//dfs
int d[100][100],path[100][100];					//shortestway
typedef struct
{
	char vexs[MAXNum];
	ArcType arcs[MAXNum][MAXNum];
	int vexnum,arcnum;
}MGraph;

函数块：
#include "h.h"
void display()												//平面图函数
{
	printf("**********欢迎使用南京农业大学校园导游系统**********\n");
	printf("                                      1北门\n");
	printf("                                      |\n");
	printf("                                      |(7)\n");
	printf("                                      |\n");
	printf("	   2西门--(5)--3教学楼--(6)--4主楼\n");
	printf("                       |              |\n");
	printf("                       |(8)           |(5)\n");
	printf("                       |              |\n");
	printf("                  5图书馆--(5)-----6操场--(4)---7足球场--(2)---8篮球场\n");
	printf("                                    |                             |\n");
	printf("                                    |(2)                          |(3)\n");
	printf("                                    |                             |\n");
	printf("                              10南大门----------(5)--------------9宿舍\n");
	
}
void CreateUDN(MGraph &G1)								//创建无向网
{
	int i,j;
	G1.arcnum=MAXArc;
	G1.vexnum=MAXVex;
	for(i=0;i<G1.vexnum;i++)
	{
		for(j=0;j<G1.vexnum;j++)
		{
			G1.arcs[i][j]=MAXint;
		}
	}
	G1.arcs[0][3]=G1.arcs[3][0]=7;
	G1.arcs[1][2]=G1.arcs[2][1]=5;
	G1.arcs[2][3]=G1.arcs[3][2]=6;
	G1.arcs[2][4]=G1.arcs[4][2]=8;
	G1.arcs[3][5]=G1.arcs[5][3]=5;
	G1.arcs[4][5]=G1.arcs[5][4]=5;
	G1.arcs[5][6]=G1.arcs[6][5]=4;
	G1.arcs[6][7]=G1.arcs[7][6]=2;
	G1.arcs[5][9]=G1.arcs[9][5]=2;
	G1.arcs[7][8]=G1.arcs[8][7]=3;
	G1.arcs[8][9]=G1.arcs[9][8]=5;
	int u=1;
	for(i=0;i<G1.vexnum;i++)
	{
		G1.vexs[i]=u++;
	}
	/*for(i=0;i<G1.vexnum;i++)						//输出无向网
	{
		for(j=0;j<G1.vexnum;j++)
		{
			printf("%d  ",G1.arcs[i][j]);
		}
		printf("\n");
	}*/
}
void introduce()
{	VertexType a;
	printf("******欢迎使用查询功能******\n");
	printf("请输入您要查询的地点前的数字序号：\n");
	scanf("%d",&a);
	switch(a)
	{
	case 1:
		printf("北门，连接中山门大街，临近地铁2号线，是南农重要的交通枢纽。门口有紫金商业街，美食购物齐全。\n");
		break;
	case 2:
		printf("西门，连接童卫路，商业街林立，周围多小区便民设施齐全。\n");
		break;
	case 3:
		printf("教学楼，是在校生主要学习的场所，教室内设施齐全，学习氛围浓厚。\n");
		break;
	case 4:
		printf("主楼，南农的标志性建筑，古风的建筑吸引游客驻足摄影。\n");
		break;
	case 5:
		printf("图书馆，藏书丰富的图书馆也是学生们自习的主阵地。\n");
	case 6:
		printf("操场，标准的操场上总是充满了青春运动的活力。\n");
		break;
	case 7:
		printf("足球场，标准的足球场能满足学生们基本的运动需求。\n");
		break;
	case 8:
		printf("篮球场，数量充足且精良的设备吸引更多学生进行运动。\n");
		break;
	case 9:
		printf("宿舍，学生们休息的场所。\n");
		break;
	case 10:
		printf("南大门，连接后标营路，是南农的正门。\n");
		break;
	default:
		break;
	}
}
void shortestway(MGraph G1)
{	int i,j,k;
	int a,b;
	for(i=0;i<G1.vexnum;i++)
	{
		for(j=0;j<G1.vexnum;j++)
		{
			d[i][j]=G1.arcs[i][j];
			path[i][j]=j+1;
		}
	}
	for(k=0;k<G1.vexnum;k++)
	{
		for(i=0;i<G1.vexnum;i++)
		{
			for(j=0;j<G1.vexnum;j++)
			{
				if(d[i][k]+d[k][j]<d[i][j])
				{
					d[i][j]=d[i][k]+d[k][j];
					path[i][j]=path[i][k];
				}
			}
		}
	}
/*	for(i=0;i<G1.vexnum;i++)						//d代表最小距离矩阵
	{
		for(j=0;j<i;j++)
		{	if(i!=j)
			printf("%d-->%d:%d   ",i+1,j+1,d[i][j]);
		}
		printf("\n");
	}
	for(i=0;i<G1.vexnum;i++)					//path代表选择路径矩阵
	{
		for(j=0;j<G1.vexnum;j++)
		{
			printf("%d   ",path[i][j]);
		}
		printf("\n");
	}*/
	printf("输入要查找距离的两个景点（数字序号并用空格隔开）：\n");
	scanf("%d %d",&a,&b);
	printf("%d到达%d的最短路径为：\n",a,b);
	printf("长度为：%d\n",d[a-1][b-1]);
	while(a!=b)
	{	
		printf("%d-->",a);
		a=path[a-1][b-1];
	}
	printf("%d\n",b);
}
void dfs(MGraph G1,int b)
{
	int i;
	if(b==end)
	{
		for(i=0;i<top;i++)
		{printf("%d-->",stack[i]);}
		printf("%d\n",end);
	}
	v[b]=1;
	stack[top++]=b;
	for(i=1;i<=G1.vexnum;i++)
	{
		if(!v[i]&&G1.arcs[b-1][i-1]<MAXNum)
			dfs(G1,i);
	}
	v[b]=0;
	top--;
}
void Insertway(MGraph G1,VertexType v)
{
	int i,a;
	int v1,w;
	int j=MAXint;			//定点关系类型
	G1.vexs[G1.vexnum]=v;
	for(i=0;i<=G1.vexnum;i++)
	{
		G1.arcs[G1.vexnum][i]=G1.arcs[i][G1.vexnum]=j;
	}
	G1.vexnum++;
	while(1)
	{
		printf("新节点与其他点是否有道路：(是为1，否为0)\n");
		scanf("%d",&a);
		switch(a)
		{
		case 1:
			printf("输入与之相连的节点序号（数字）以及路径长度：(用空格隔开)\n");
			scanf("%d %d",&v1,&w);
			G1.arcs[v1-1][v-1]=G1.arcs[v-1][v1-1]=w;		
			break;
		case 0:
			printf("添加之后的临接矩阵：\n");
			for(i=0;i<G1.vexnum;i++)						//输出无向网
			{
				for(j=0;j<G1.vexnum;j++)
				{
					printf("%d   ",G1.arcs[i][j]);
				}
				printf("\n");
			}
			printf("节点数为：%d\n",G1.vexnum);
			exit(-1);
			break;

		default:
			break;
		}
	}
}
void deletearc(MGraph G1,int v,int w)
{
	int v1,w1;
	int j=MAXint;
	v1=v-1;
	w1=w-1;
	if(G1.arcs[v1][w1]!=j)
	{
		G1.arcs[v1][w1]=G1.arcs[w1][v1]=j;
		G1.arcnum--;
	}
}
void deleteway(MGraph G1,VertexType v)
{
	int i,j,k;
	k=v-1;
	for(i=0;i<G1.vexnum;i++)
	{
		deletearc(G1,v,G1.vexs[i]);			//删除节点v的所有弧
	}
	for(j=k+1;j<G1.vexnum;j++)
	{
		G1.vexs[j-1]=G1.vexs[j];			//k后面的顶点往前移
	}
	for(i=0;i<G1.vexnum;i++)		
	{
		for(j=k+1;j<G1.vexnum;j++)
		{
			G1.arcs[i][j-1]=G1.arcs[i][j];		//移动待删除节点右面的矩阵元素
		}
	}
	for(i=0;i<G1.vexnum;i++)
	{
		for(j=k+1;j<G1.vexnum;j++)
		{
			G1.arcs[j-1][i]=G1.arcs[j][i];			//移动待删除节点后面的矩阵元素
		}
	}
	G1.vexnum--;
	for(i=0;i<G1.vexnum;i++)						//输出无向网
			{
				for(j=0;j<G1.vexnum;j++)
				{
					printf("%d   ",G1.arcs[i][j]);
				}
				printf("\n");
			}
}
void renew(MGraph G1)
{	
	int i,j,k;
	printf("输入要改变哪两点之间道路信息，以及改为多少：（例如修改4和6信息，改为2则输入：4 6 2）\n");
	scanf("%d %d %d",&i,&j,&k);
	G1.arcs[i-1][j-1]=G1.arcs[j-1][i-1]=k;
	printf("更新结果为：\n");
	for(i=0;i<G1.vexnum;i++)						//输出无向网
	{
		for(j=0;j<G1.vexnum;j++)
		{
			printf("%d  ",G1.arcs[i][j]);
		}
		printf("\n");
	}	
}
void menu(MGraph G1)
{	int a;
	printf("请选择您需要的服务:\n");
	printf("                    1.景点查询\n");
	printf("                    2.查询最短路径\n");
	printf("                    3.查询所有路径\n");
	printf("                    4.增加景点\n");
	printf("                    5.删除景点\n");
	printf("                    6.更新信息\n");
	printf("                    7.退出程序\n");
	scanf("%d",&a);
	switch(a)
	{
	case 1:
		introduce();
		menu(G1);
		break;		
	case 2:
		printf("******欢迎使用查询最小路径程序******\n");
		shortestway(G1);
		menu(G1);
		break;		
	case 3:
		printf("******欢迎使用查询所有路径程序******\n");
		printf("输入起点和终点（用空格隔开）\n");
		scanf("%d %d",&start,&end);
		dfs(G1,start);
		menu(G1);
		break;
	
	case 4:
		VertexType v;
		printf("******欢迎使用添加程序******\n");
		printf("输入新的结点序号（数字）\n");
		scanf("%d",&v);
		Insertway(G1,v);
		menu(G1);
	break;		
	case 5:
		VertexType l;
		printf("******欢迎使用删除程序******\n");
		printf("输入要删除的结点序号（数字）\n");
		scanf("%d",&l);
		deleteway(G1,l);
		menu(G1);
	break;		
	case 6:
		renew(G1);
		menu(G1);
		break;
	
	case 7:
		printf("******感谢您的使用******\n");
		exit(-1);
	default:
		break;
	}
}

主函数：
#include "hanshu.cpp"
int main()
{
	MGraph G1;
	display();
	CreateUDN(G1);
	menu(G1);
	return 0;
}

程序界面：

由于水平原因，文中如有错误还请评论区不吝赐教！

喜欢的话点个赞再走吧~