1、设计目的
（1）为了进一步巩固课堂上所学到的知识，深刻把握为了进一步巩固课堂上所学到的知识，深刻掌握所学重要的数据结构类型的基本概念，逻辑结构和物理结构，以及主要应用算法。锻炼选择应用合适的数据结构解决不同实际问题的能力，使用所学的一种数据结构完成一个具体项目的分析设计和开发。
（2）设计一个校园导游程序，为来访客人提供各种信息查询任务。
（3）为来访客人提供图中任意地点相关信息的查询
（4）为来访客人提供图中任意地点的问路查询，即查询任意两个地点之间的一条最短的简单路径。
2、设计内容及要求
内容：一个校园导游程序，为来访客人提供各种信息查询任务。设计我校的校园平面图，以图中顶点表示校内各景点，存放景点名称、代号，以边表示路权，存放路径长度等相关信息。
要求：
（1）从文件中读取学校的相关简介
（2）从地图文件中读取校园主要建筑信息及建筑间的距离信息。
（3）计算出给定地点的起点到终点之间距离的行进路径
（4）输出该路径及其总距离
（5）若输入错误，则给出提示信息
一、先分析课设所给要求，仔细一想，这用到的算法：Dijkstra算法和Floyd算法。
Dijkstra算法：这是一个按路径长度递增的次序产生的最短路径的算法。基本思想：设G=（V,E）是一个带权有向图，把图中的顶点集合V分成两组，第1组为以求出最短路径的顶点集合，第2组为其余未确定最短路径的顶点集合，按最短路径长度的递增次序依次把第2组的顶点加入S中。
Floyd算法：这是求所有顶点至所有顶点的最短路径的算法。基本思想：假设有向图G=（V，E）采用邻接矩阵g表示，另外设置一个二维数组A用于存放当前顶点之间的最短路径长度，即分量A[i][j]表示当前i到j的最短路径长度,即传递产生一个矩阵序列表示路径上所有经过的顶点编号的最短路径长度。
对于所求问题，将求出当前所在地到其他所有某一个地点的最短路径，用到了最适合它的Dijkstra算法，对于之后的求出任意两点之间的最短距离时用到Floyd算法将它进行算法实现，并为它列出了对应地点的邻接矩阵，并且在实现过程中为了将最短路径权值更好地展现出来，将Dijkstra算法和Floyd算法进行了对应的优化。
二、我们在做这个课设的时候分析如下
所用学校的数据
我们将所有的边赋予权值，将每一个点当做邻接矩阵的一个点进行赋值，在处理时要考虑到需要求出当前所在者到校园任意一个地点的最短路径，这时便会想到排序中找最短路径的Dijkstra算法和Floyd算法，而这两者如果是单源点正权图，就用Dijkstra算法，如果是任意两点之间的最短路径或者是赋权图则用Floyd算法，而求当前所在者到校园任意一个地点的最短路径，就是单源点正权图，所以用Dijkstra算法，而后面加入的任意两个地点的最短路径问题则用Floyd算法。用到Floyd算法时需要将每个地点进行一次赋值到邻接矩阵中去。
程序整体逻辑图
但是在最后很遗憾我们并未使用文件的方法来将地图存入，而是直接画在了程序之中
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MaxVerNum 100 //最大景点数
#define INF 99999//表示无穷 即没有路径
typedef struct
{
char name[MaxVerNum];//地点名字
char features[1000];//地点信息
} VertexType;
//图的存储结构
typedef struct
{
VertexType vexs[MaxVerNum];//每一个地点的信息
int edges[MaxVerNum][MaxVerNum];//每一个地点的邻接边的权值
int v, e;//顶点数和边数
} MGraph;
static MGraph map;
void menu1();//导航菜单
void ListSpots();//烟理工地点
void create();//创建邻接链表
void Introduce();//地点介绍函数
void Dijkstra();//查找当前地点到其他地点的最短路径
void Floyd();//查找任意两个地点之间的最短路径
void Exit();//退出系统的函数
void changepassword();
void printmap();
//主函数
int main()
{
while(1)
{
create();
printf("\n\n");
system("cls");
printf("\n\n\n\n\n");
printf("\t\t\t\t ******************************************************\n");
printf("\t\t\t\t *----------------------主界面------------------------*\n");
printf("\t\t\t\t *----------------------------------------------------*\n");
printf("\t\t\t\t *----------------1、进入导航系统---------------------*\n");
printf("\t\t\t\t *----------------------------------------------------*\n");
printf("\t\t\t\t *----------------2、退出程序-------------------------*\n");
printf("\t\t\t\t *----------------------------------------------------*\n");
printf("\t\t\t\t *----------------3、制作人---------------------------*\n");
printf("\t\t\t\t *----------------------------------------------------*\n");
printf("\t\t\t\t *----------------4、xxxx校园地图-------------*\n");
printf("\t\t\t\t *----------------------------------------------------*\n");
printf("\t\t\t\t ******************************************************\n");
int n;
printf("\n\n");
printf("请输入代号选择您的操作：\n\n");
scanf("%d",&n);
if(n==1)
{
menu1();
}
else if(n==2)
{
Exit();
}
else if(n==3)
{
system("cls"); //清屏
printf("制作人:\n");
printf("按回车键返回主界面\n");
system("pause");
getchar();
getchar();
main();
break;
}
else if(n==4)
{
printmap();
}
}
return 0;
}
//导航菜单
void menu1()
{
while(1)
{
system("cls");
printf("\t当前为操作者操作界面\n\n");
printf("\t<1>查看地点介绍\n\n");
printf("\t<2>查找当前地点到其他地点的最短路径\n\n");
printf("\t<3>查找任一两个地点之间的最短路径\n\n");
printf("\t<4>返回主界面\n\n");
printf("\t<5>退出系统！\n\n");
int n;
scanf("%d",&n);
if(n==1)
{
Introduce();
}
else if(n==2)
{
Dijkstra();
}
else if(n==3)
{
Floyd();
}
else if(n==4)
{
main();
}
else if(n==5)
{
Exit();
}
else
{
printf("您的输入有误，请重新输入！\n");
system("pause");
}
}
}
//地点介绍函数
void Introduce()
{
system("cls");
if(map.v==0)
{
printf("该地图暂时没有景点！\n\n");
system("pause");
return ;
}
ListSpots();
printf("\n请输入你要查看的景点代号：\n");
int n;
while(1)
{
scanf("%d",&n);
if(n<1||n>map.v)
{
printf("您的输入有误，请重新输入！\n");
}
else
break;
}
printf("%s：",map.vexs[n-1].name);
printf("%s\n",map.vexs[n-1].features);
int flag;
printf("\n再次查询请按1，退出查询请按任意键\n");
scanf("%d",&flag);
if(flag==1)
Introduce();
}
//查找当前景点到其他景点的最短路径
void Dijkstra()
{
system("cls");
if(map.v<=0)
{
printf("地图中没有地点，无法查询最短路径！\n");
system("pause");
return ;
}
if(map.v==1)
{
printf("地图中只有一个地点，无法查询最短路径！\n");
system("pause");
return ;
}
if(map.e<=0)
{
printf("地图中没有道路，无法查询最短路径！\n");
system("pause");
return ;
}
ListSpots();
int a;
printf("请输入您所在地点位置的代号：\n");
scanf("%d",&a);
while(a<1||a>map.v)
{
printf("您的输入有误，请重新输入！范围在1~%d之间。\n",map.v);
scanf("%d",&a);
}
int s[MaxVerNum];//存放源点和已生成的终点
int dist[MaxVerNum];//存放最短路径的长度
int path[MaxVerNum];//存放上一个路径的位置
int i,j,k,min,pre;
s[a-1]=1;
//初始化
for(i=0; i<map.v; i++)
{
dist[i]=map.edges[a-1][i];
path[i]=a-1;
s[i]=0;//这个看网上的答案是没有的 我自己加上去的，这样就正确了
}
//对当前位置进行信息更改
dist[a-1]=0;
s[a-1]=1;
path[a-1]=-1;
for(i=0; i<map.v; i++)
{
min=INF+1;
for(k=1; k<map.v; k++)
{
if(s[k]==0&&dist[k]<min)
{
j=k;
min=dist[k];
}
}
s[j]=1;
for(k=0; k<map.v; k++)
{
if(s[k]==0&&(dist[j]+map.edges[j][k]<dist[k]))
{
dist[k]=dist[j]+map.edges[j][k];
path[k]=j;
}
}
}
int flag=1;
int mid;
for(i=0; i<map.v; i++)
{
if(i!=a-1)
{
if(dist[i]!=INF)
{
flag=0;
printf("%d米: %s",dist[i],map.vexs[i].name);
pre=path[i];
mid=i;
while(pre>=0)
{
if(map.edges[mid][pre]!=INF)
{
printf(" <-%s(%d)",map.vexs[pre].name,map.edges[mid][pre]);
mid=pre;
pre=path[pre];
}
else
{
printf(" (%d)<-%s",map.edges[i][pre],map.vexs[pre].name);
mid=pre;
pre=path[pre];
}
}
printf("\n");
}
}
}
if(flag)
printf("【%s】与任何地点之间都没有可通道路！\n",map.vexs[a-1].name);
system("pause");
}
//查找任一两个地点之间的最短路径
void Floyd()
{
system("cls");
if(map.v<=0)
{
printf("地图中没有地点，无法查询最短路径！\n");
system("pause");
return ;
}
if(map.v==1)
{
printf("地图中只有一个地点，无法查询最短路径！\n");
system("pause");
return ;
}
if(map.e<=0)
{
printf("地图中没有道路，无法查询最短路径！\n");
system("pause");
return ;
}
ListSpots();
int a,b;
printf("请输入您要查询距离的两个地点代号,中间用空格隔开：\n");
scanf("%d %d",&a,&b);
while(a<1||a>map.v||b<1||b>map.v)
{
printf("您的输入有误，请重新输入！范围在1~%d之间。\n",map.v);
scanf("%d %d",&a,&b);
}
int s[MaxVerNum];//存放源点和已生成的终点
int dist[MaxVerNum];//存放最短路径的长度
int path[MaxVerNum];//存放上一个路径的位置
int i,j,k,min,pre;
s[a-1]=1;
//初始化
for(i=0; i<map.v; i++)
{
dist[i]=map.edges[a-1][i];
path[i]=a-1;
s[i]=0;
}
//对当前位置进行信息更改
dist[a-1]=0;
s[a-1]=1;
path[a-1]=-1;
int K=0,mid=a-1;
for(i=0; i<map.v; i++)
{
min=INF+1;
for(k=1; k<map.v; k++)
{
if(s[k]==0&&dist[k]<min)
{
j=k;
min=dist[k];
}
}
s[j]=1;
for(k=0; k<map.v; k++)
{
if(s[k]==0&&(dist[j]+map.edges[j][k]<dist[k]))
{
dist[k]=dist[j]+map.edges[j][k];
path[k]=j;
}
}
}
if(dist[b-1]==INF)
printf("【%s】与【%s】任何地点之间都没有可通道路！\n",map.vexs[a-1].name,map.vexs[b-1].name);
else
{
printf("【%s】->【%s】的最短距离是%d米。 \n",map.vexs[b-1].name,map.vexs[a-1].name,dist[b-1]);
pre=path[b-1];
printf("路径为：%s",map.vexs[b-1].name);
int pre1=pre;
while(pre>=0)
{
if(pre!=pre1)
{
printf(" <-%s(%d)",map.vexs[pre].name,map.edges[mid][pre]);
mid=pre;
pre=path[pre];
}
else
{
printf(" (%d)<-%s",map.edges[b-1][pre],map.vexs[pre].name);
mid=pre;
pre=path[pre];
}
}
}
printf("\n");
system("pause");
}
//烟理工地点列表
void ListSpots()
{
if(map.v==0)
{
printf("当前地图中没有地点！\n\n");
system("pause");
return ;
}
if(map.v>0)
printf("xxxx有当前地点：\n\n");
int i;
for(i=0; i<map.v; i++)
{
printf("\t<%d>%s\n",i+1,map.vexs[i].name);
}
}
//创建邻接链表
void create()
{
map.v=13;
map.e=22;
int i,j,k;
for(i=0; i<MaxVerNum; i++)
{
for(j=0; j<MaxVerNum; j++)
{
map.edges[i][j]=INF;
}
}
//顶点的名字 介绍赋值
strcpy(map.vexs[0].name, "北门口");
strcpy(map.vexs[0].features, "地点的描述，下列相同");
strcpy(map.vexs[1].name, "二号教学楼");
strcpy(map.vexs[1].features, "上课的地点，包括图书馆，自修区");
strcpy(map.vexs[2].name, "三号教学楼");
strcpy(map.vexs[2].features, "新建教学楼，里面有各种实验室以及老师办公室，湖景房");
strcpy(map.vexs[3].name, "一号教学楼");
strcpy(map.vexs[3].features, "上课的地点，旁边就是菜鸟驿站 ");
strcpy(map.vexs[4].name, "田径场");
strcpy(map.vexs[4].features, "学生跑步散步的地点，部分体育课的地点以及体测的地方");
strcpy(map.vexs[5].name, "湖");
strcpy(map.vexs[5].features, "人造湖，禁止垂钓，可以在旁边散步");
strcpy(map.vexs[6].name, "文体中心");
strcpy(map.vexs[6].features, "各种表彰大会等会议的地点，部分体育课的地点");
strcpy(map.vexs[7].name, "西门口");
strcpy(map.vexs[7].features, "重建之后的门口，旁边可以直达小吃街");
strcpy(map.vexs[8].name, "男宿舍");
strcpy(map.vexs[8].features, "学生就寝的地点");
strcpy(map.vexs[9].name, "三餐");
strcpy(map.vexs[9].features, "分为一二楼，旁边有711便利店");
strcpy(map.vexs[10].name, "女宿舍");
strcpy(map.vexs[10].features, "学生就寝的地点");
strcpy(map.vexs[11].name, "校医院");
strcpy(map.vexs[11].features, "学校的医院，旁边有天猫超市，洗浴中心");
strcpy(map.vexs[12].name, "第一二餐");
strcpy(map.vexs[12].features, "分为一二楼，一餐一楼，二餐二楼");
//边的权重赋值
map.edges[0][1]=map.edges[1][0]=350;
map.edges[0][2]=map.edges[2][0]=100;
map.edges[0][3]=map.edges[3][0]=350;
map.edges[1][2]=map.edges[2][1]=200;
map.edges[1][4]=map.edges[4][1]=200;
map.edges[2][3]=map.edges[3][2]=200;
map.edges[2][5]=map.edges[5][2]=200;
map.edges[3][6]=map.edges[6][3]=300;
map.edges[4][7]=map.edges[7][4]=60;
map.edges[4][5]=map.edges[5][4]=500;
map.edges[4][8]=map.edges[8][4]=200;
map.edges[5][9]=map.edges[9][5]=600;
map.edges[5][6]=map.edges[6][5]=100;
map.edges[6][10]=map.edges[10][6]=100;
map.edges[6][11]=map.edges[11][6]=300;
map.edges[7][8]=map.edges[8][7]=50;
map.edges[8][9]=map.edges[9][8]=800;
map.edges[8][12]=map.edges[12][8]=850;
map.edges[9][12]=map.edges[12][9]=50;
map.edges[9][10]=map.edges[10][9]=300;
map.edges[10][12]=map.edges[12][10]=400;
map.edges[10][11]=map.edges[11][10]=200;
}
void Exit()
{
printf("\n【警告】：\n退出系统之后，当前的所有操作将会恢复默认值。\n");
printf("确认退出请按1，按任意键停止当前退出操作。\n");
int flag;
scanf("%d",&flag);
if(flag==1)
{
system("cls");
exit(0);
}
}
void printmap()
{
system("cls");
printf("\n *地图一览*\n\n");
printf(" @0北校门 \n");
printf(" . | . \n");
printf(" 350 . | . 350 \n");
printf(" . |100 . \n");
printf(" . 200 | 200 . \n");
printf(" (图书馆)@1二教----------------@2三教---------------@3一教(菜鸟驿站) \n");
printf(" |300 | 200 |300 \n");
printf(" | 500 | 100 | \n");
printf(" @4田径场--------------@5湖-------------@6文体中心 \n");
printf(" 60 . |200 | | . 300 \n");
printf(" . | 800 | 600 300 |100 . \n");
printf(" @7西门口---@8男宿舍-----------@9一二餐----------@10女宿舍----@11校医院 \n");
printf(" 50 . | . 200 \n");
printf(" . | 50 . \n");
printf(" 850 . | . 400 \n");
printf(" @12三餐 \n");
printf("\n\n\n\n\n");
printf("按回车键返回主界面\n");
system("pause");
getchar();
getchar();
main();
}
测试结果就不放了，将代码的部分程序修改修改就可以了。
文章出处登录后可见！
已经登录？立即刷新
