数据结构 图定义和实现 根据郑州轻工业大学的校园平面图设计一个简单的校园导航系统，设计数据结构和算法实现相应功能
题目：根据郑州轻工业大学科学校区的校园平面图设计一个简单的校园导航系统，设计数据结构和算法实现相应功能。要求所含景点不少于8个（软件学院为其中一个景点）。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。
1．根据上述信息创建一个图,使用邻接矩阵存储；
2．景点信息查询：为来访客人提供校园任意景点相关信息的介绍；
3．问路查询：为来访客人提供从软件学院到达任意其它景点之间的一条最短路径。
解决方案
1.校园平面图利用函数Map（）实现，利用printf输出一个预先写好的地图。算法实现如下：
void Map(){
printf("\n *************************************************\n");
printf(" * 校园一览图 *\n");
printf(" * *\n");
printf(" * 11.北门 *\n");
printf(" * *\n");
printf(" * 8.新餐厅 9.百度超市 10.3号寝室楼 *\n");
printf(" * *\n");
printf(" * 7.软件学院 6.图书馆 5.老餐厅 *\n");
printf(" * *\n");
printf(" * 2.工程楼 3.教学楼 4.操场 *\n");
printf(" * *\n");
printf(" * 1.南门 *\n");
printf(" * *\n");
printf(" *************************************************\n");
}
2.景点信息查询就是在一维数组中按值查询，输入对应的编号后，输出数组中对应的元素信息。算法实现如下：
void Find()
{
int id;
printf("\n 请输入要查询景点的编号:") ;
scanf("%d",&id) ;
if(id>=1&&id<=9)
{
printf("\n\t名称：%s\n",node[id-1].name) ;
printf("\t简介：%s\n",node[id-1].info) ;
}
else
printf(" 输入有误！") ;
}
3.问路查询即求顶点间最短距离，这里利用弗洛伊德算法实现。输入起点和终点，用弗洛伊德算法求出两点间最短路径，并将最短路径和最短距离输出实现导航。算法实现如下：
//Floyd算法
void Floyd()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
path[i][j]=j;
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(array[i][j]>array[i][k]+array[k][j])
{
array[i][j]=array[i][k]+array[k][j];
path[i][j]=path[i][k];
}
}
//最短路径
void Path()
{
int start,end;
printf("\n 请输入起点和终点（1-11）：");
scanf("%d-%d",&start,&end);
if(start>0&&start<=11&&end>0&&end<=11) {
printf(" \n 从%s",node[start-1].name);
printf("到%s",node[end-1].name);
Floyd();
int d=array[start-1][end-1]; //距离d
start--;end--;
printf("最短路径为：\n\n\t%s",node[start].name);
while(start!=end) {
printf("->%s",node[path[start][end]].name);
start=path[start][end];
}
printf("\n\t距离为：%d米！\n\n",d);
}
else
printf("输入的地点不存在！") ;
}
运行结果
1．校园平面图
2．景点信息查询
3．问路查询
全部代码
#include<stdio.h>
#include<stdlib.h>
#define max 32767 //表示极大值，即∞
const int n=11;
int path[n][n];
struct Node{
char name[20]; //景点名称
char info[200]; //景点信息介绍
};
//景点信息
Node node[] ={
{
"南门","南门是郑州轻工业大学的正门，所有社会车辆和人员都可以在此门出入！"},
{
"工程楼","工程楼是各个院系的实验室聚集地，并且拥有大量的大型阶梯教室！"},
{
"教学楼","教学楼自东向西分别为三一二四教，三教为阶梯教室，一二教为小教室，四教为物理实验教室！"},
{
"操场","操场有400米塑胶跑道和观众台，这里是你挥洒汗水的好地方！"},
{
"老餐厅","老餐厅总共三层，每层各有特色，因为是学校的第一个餐厅，故称老餐厅！"},
{
"图书馆","图书馆位于学校的正中间，这是知识的殿堂！"},
{
"软件学院","软件学院是河南省首批示范性公办、全日制软件学院之一，是信息产业部、教育部确定的“国家计算机应用与软件技术专业领域技能型紧缺人才培养基地”之一!"},
{
"新餐厅","新餐厅是开业较晚的一个餐厅，极大的方便了附近公寓学生就餐！"},
{
"百度超市","百度超市是学校最大的超市，物品齐全，价格实惠！"},
{
"3号寝室楼","3号寝室楼是一栋男生宿舍楼，再楼长的带领下一直是学校的优秀公寓"},
{
"北门","由于学生公寓都在北门附近，并且北门有直达附近地铁口的公交，所以北门是大家出行的最佳选择！"}
};
int array[n][n]={
{
0, 300, 100, 400, max, max, max, max, max, max, max},
{
300, 0, 100, max, max, 400, 300, max, max, max, max},
{
100, 100, 0, 200, 350, 100, 200, max, max, max, max},
{
400, max, 200, 0, 50, 250, max, max, max, max, max},
{
max, max, 350, 50, 0, 150, max, max, 500, 400, max},
{
max, 400, 100, 250, 150, 0, 50, 600, 400, 600, max},
{
max, 300, 200, max, max, 50, 0, 300, 350, max, max},
{
max, max, max, max, max, 600, 300, 0, 300, max, 250},
{
max, max, max, max, 500, 400, 350, 300, 0, 200, 50},
{
max, max, max, max, 400, 600, max, max, 200, 0, 200},
{
max, max, max, max, max, max, max, 250, 50, 200, 0}
};
//地图
void Map(){
printf("\n *************************************************\n");
printf(" * 校园一览图 *\n");
printf(" * *\n");
printf(" * 11.北门 *\n");
printf(" * *\n");
printf(" * 8.新餐厅 9.百度超市 10.3号寝室楼 *\n");
printf(" * *\n");
printf(" * 7.软件学院 6.图书馆 5.老餐厅 *\n");
printf(" * *\n");
printf(" * 2.工程楼 3.教学楼 4.操场 *\n");
printf(" * *\n");
printf(" * 1.南门 *\n");
printf(" * *\n");
printf(" *************************************************\n");
}
//查询景点信息
void Find()
{
int id;
printf("\n 请输入要查询景点的编号:") ;
scanf("%d",&id) ;
if(id>=1&&id<=9)
{
printf("\n\t名称：%s\n",node[id-1].name) ;
printf("\t简介：%s\n",node[id-1].info) ;
}
else
{
printf(" 输入有误！") ;
}
}
//Floyd算法
void Floyd()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
path[i][j]=j;
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(array[i][j]>array[i][k]+array[k][j])
{
array[i][j]=array[i][k]+array[k][j];
path[i][j]=path[i][k];
}
}
//最短路径
void Path()
{
int start,end;
printf("\n 请输入起点和终点（1-11）：");
scanf("%d-%d",&start,&end);
if(start>0&&start<=11&&end>0&&end<=11) {
printf(" \n 从%s",node[start-1].name);
printf("到%s",node[end-1].name);
Floyd();
int d=array[start-1][end-1]; //距离d
start--;
end--;
printf("最短路径为：\n\n\t%s",node[start].name);
while(start!=end)
{
printf("->%s",node[path[start][end]].name);
start=path[start][end];
}
printf("\n\t距离为：%d米！\n\n",d);
}
else{
printf("输入的地点不存在！") ;
}
}
int main(){
int choice;
while(true){
printf("");
printf("\n *************************************************\n");
printf(" 欢迎进入校园导航系统！ \n");
printf(" * *\n");
printf(" 1：校园平面图\n");
printf(" * 2：景点信息查询 *\n");
printf(" 3：问路查询\n");
printf(" * 4：退出系统 *\n");
printf("\n");
printf(" *************************************************\n\n");
printf(" 请选择：");
scanf("%d",&choice);
switch(choice){
case 1: Map();
printf("\n");
break;
case 2: Map();
Find();
break;
case 3: Map();
Path();
break;
case 4: exit(0);
default:
printf(" Error!");
break;
}
}
return 0;
}
写在末尾的话，能看到这篇文章的你应该是轻大的学生。当时学习数据结构写这个问题的时候真的是难到了我，上面的代码希望能给你提供解决问题的思路。
查看10道真题和解析
投递深圳同为数码等公司10个岗位
比亚迪工作强度 342人发布