设计目的
现在的大学占地面积越来越大，建筑物越来越多，功能越来越多样，校内的道路也是纵横交错，校园导航系统可以帮助用户更加快速的了解学校的路线，建筑布局及建筑物的基本信息等(用户主要是新生、家长、教职工、外来参观人员等)，在帮助用户了解校园路线、实现导航的功能的基础上，校园导航系统还录入了学校各个地点的相关信息，以供使用者更方便快捷的找到目的地。
随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本次课程设计研究的校园导航系统具有一定的使用价值和现实意义。
设计需求
1.从西南大学的平面图中选取一些有代表性的景点，抽象成一个无向带权图.
2.使用迪杰斯特拉算法提供最优路径查询
设计内容
该校园导航的使用者分为游客和管理者，功能如下：
游客
-针对游客的校园导航使用说明
-查看校园全景图，附有校园地点的所有路线情况
-输入任意地点，查询该地点的信息，包括地点介绍和相关路线
-输入任意两地点，输出两点之间的所有简单路线
-输入任意两地点，输出两点之间的一条中转次数最少的最短路线
-输入任意两地点，输出两点之间的一条带权路径最短的最有路线
-输入任意地点，输出从该点出发的最佳布网方案
管理员(除游客功能外，还有以下功能)
-使用管理员功能首先需要登录，登陆成功方可使用导航管理员功能
-可以在地图中添加新地点
-可以在地图中添加新路线
-可以在地图中撤销旧路线
-注册新的管理员帐号
各个模块详细的功能描述
导航使用说明：描述该导航应该如何使用，具有什么功能
校园平面简图：输出一张有校园所有地点的平面图，可以直观的看出校园地点的分布。这是利用了每个地点所存储的坐标，通过对矩阵元素的遍历，输出了各地点的具体方位。并且在平面图下面以这样的形式附有校园两地点相连的所有路线信息：起点<—->终点:xxx m
查看地点信息：任意输入一个地点序号，输出该地点的介绍，以及所有与该地点连通的路线及其距离
查询简单路径：任意输入两个地点，输出两地点间所有的简单路径。利用图的深度搜索遍历，用栈将经过的地点序号存起来，然后每条路线的地点逐个输出，最后得到所有简单路径
查询最短路径：任意输入两个地点，输出两地点间一条中转次数最少的路线。利用图的广度搜索遍历，用队列将要遍历的地点存起来，通过对队列的操作得到中转次数最少的路线
查询最优路径：任意输入两个地点，输出两地点间一条带权路径最短的路线。利用迪杰斯特拉算法，通过对dist和 path的操作得出最终的最短路线
最佳布网方案：任意输入一个地点，输出从该点出发的最佳布网方案。这是利用了最小生成树的思想，运用了Prim算法的思想
添加新地点：输入新地点的名称和坐标，通过对文件增删改的操作，将新地点存储到文件里，就生成了一张新地图
添加新路线：输入新路线的起点、终点 、距离，通过对文件增删改的操作，将新路线存储到文件里，就生成了一条新路线
撤销旧路线：输入要撤销路线的起点、终点、距离，通过对文件增删改的操作，将改动后的路线信息存储到文件里
管理员的登录：管理员可在此输入帐号和密码进行登录，在输入密码时也可以选择是否隐藏密码，如果输入帐号密码不对应，则可重新输入，若错误三次则自动退出系统。通过对用户输入的帐号密码和“admin.txt”文件里保存的帐号密码进行比较，如果相同则可登录
管理员的注册：管理员可在此输入帐号和密码进行注册，密码需要输入两遍，相同则注册成功。通过对“admin.txt”文件增删改的操作，将新帐号和密码存储到文件里，就生成了一个新的管理员帐号
队列的操作：有队列的判空、队列的初始化、出队、入队函数
创建无向图：采用邻接矩阵的结构，通过对“路线信息”文件和“地点介绍”文件的读取，将信息存储到邻接矩阵中，然后创建出带权无向图
游客和管理员菜单：游客和管理员可在其对应的菜单页面进行功能选择
重点设计及相关代码
数据结构类型的选择：邻接矩阵
#define MAXVEX 50
#define INFINITY 32768
#define MAXL 20
#define MAXC 66
int visited[INFINITY];
int stack[INFINITY];
int count;
struct user //保存管理员帐号密码的结构体
{
char id[20]; //管理员帐号
char passwd[20]; //管理员密码
struct user *next;
};
typedef struct //保存地点信息的结构体
{
int No; //校园地点序号
char name[20]; //校园地点名
char description[200]; //地点描述
}Vextype;
typedef struct //邻接矩阵
{
int arcs[MAXVEX][MAXVEX]; //边集
Vextype vex[MAXVEX]; //顶点集
int vexnum; //顶点数目
int arcnum; //边数目
}AdjMatrix;
typedef struct //坐标矩阵
{
int point; //该点是否为校园地点
char name[20]; //该点校园地点名
int No; //该点校园地点序号
}SchoolMap;
typedef struct Node
{
int date; //队列元素的值，存储地点序号
struct Node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front; //头指针
LinkQueueNode *fear; //尾指针
}LinkQueue;
int IsEmpty(LinkQueue *Q) //队列判空
{
if(Q->front == Q->fear)
return 1;
else
return 0;
}
int InitQueue(LinkQueue *Q)//队的初始化
{
Q->front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(Q->front != NULL) {
Q->fear = Q->front;
Q->front->next = NULL;
return 1;
}
else {
return 0;
}
}
创建带权无向图
// 采用邻接矩阵创建无向图
int Create(AdjMatrix *G,SchoolMap M[MAXL][MAXC])
{
int i,j,weight,m,n;
FILE *fp1;
fp1=fopen("路线信息.txt","r");
//从"路线信息.txt"文件中读取校园图的景点数目和路线数目
fscanf(fp1, "%d %d", &G->vexnum, &G->arcnum);
//初始化邻接矩阵
for(i = 1; i <= G->vexnum; i++)
for(j = 1; j<= G->vexnum; j++) {
G->arcs[i][j] = INFINITY;
}
//读取"路线信息.txt"文件中两点序号及距离，并赋值给邻接矩阵
while(fscanf(fp1,"%d %d %d",&i,&j,&weight) != EOF) {
G->arcs[i][j] = weight;
G->arcs[j][i] = weight;
}
fclose(fp1);
FILE *fp2;
fp2 = fopen("地点介绍.txt", "rt");
//从"地点介绍.txt"文件中读取校园图中的景点名及描述
for(i = 1; i <= G->vexnum; i++) {
G->vex[i].No = i; // 将顶点集中的地点序号设为i值
// fscanf()函数是根据数据格式(format)，从输入流(stream)中读入数据，存储到argument中，遇到空格和换行时结束。
// 数据依次是：地点名称、、、地点简介
fscanf(fp2, "%s %d %d %s", G->vex[i].name,&m,&n,G->vex[i].description);
M[m][n].point = 1;
M[m][n].No = i;
strcpy(M[m][n].name,G->vex[i].name);
}
fclose(fp2);
return 1;
}
查询所有简单路径：深度搜索遍历DFS算法
void DFS(AdjMatrix *G, int m, int i, int end)
{
int j,k;
for(j = 1; j <= G->vexnum; j++){
if(G->arcs[i][j] != INFINITY && visited[j] == 0) {
visited[j] = 1;
if(j == end) {
count++;
printf("★%d.",count);
for(k = 1; k < m; k++) {
printf("%s->", G->vex[stack[k]].name);
}
printf("%s\n", G->vex[end].name);
visited[j] = 0;
}
else {
stack[m] = j;
m++;
DFS(G, m, j, end);
m--;
visited[j] = 0;
}
}
}
}
查询中转次数最少路径：广度搜索遍历BFS算法
void BFS(AdjMatrix *G, int start, int end)
{
int vis[INFINITY];
int i, num;
int w, v;
LinkQueue *Q;
Q=(LinkQueue*)malloc(sizeof(LinkQueue));
if(start == end)
return;
memset(vis, 0, INFINITY);
vis[start] = 1;
InitQueue(Q);
EnterQueue(Q, start);
while(Q->front != Q->fear){
DeleteQueue(Q, &v);
num = v;
for(i = 1;i <= G->vexnum; i++){
if(G->arcs[num][i] != INFINITY) {
w = i; //求出当前节点的第一个邻接点（求出序号）
while(w != -1){
if(vis[w] == 0){
if(w == end){
BFS(G, start, num);
printf("%s->",G->vex[num].name);
return;
}
vis[w] = 1;
EnterQueue(Q, w);
w = NextAdjVertex(G, w, v);
//w是求的得第一个邻接点，v是相对w下一个邻接点(求出下一个邻接点的序号)
}
break;
}
}
}
}
}
查询带权路径最短：Dijkstra算法
// Dijkstra算法
void Dijkstra(AdjMatrix *G, int start, int end, int dist[], int path[][MAXVEX])
{
int mindist, i, j, k, t = 1;
for(i = 1; i <= G->vexnum; i++) {
dist[i] = G->arcs[start][i]; //对dist数组初始化
if(G->arcs[start][i] != INFINITY)
path[i][1] = start; //如果该弧存在，则path[i][1]为源点
}
path[start][0] = 1; //start加入到S中
for(i = 2; i <= G->vexnum; i++) { //寻找各条最短路径
mindist = INFINITY;
for(j = 1; j <= G->vexnum; j++)
if(!path[j][0] && dist[j] < mindist) {
k = j;
mindist = dist[j];
}
if(mindist == INFINITY)
return ;
path[k][0] = 1; //找到最短路径，将该点加入到S集合中
for(j = 1; j <= G->vexnum; j++) { //修改路径
if(!path[j][0] && G->arcs[k][j] < INFINITY && dist[k]+G->arcs[k][j] < dist[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 == end)
break;
printf("\n ★★★%s--->%s的最短路线为: 从%s",G->vex[start].name,G->vex[end].name,G->vex[start].name);
for(j = 2; path[i][j] != 0; j++) {
printf("->%s",G->vex[path[i][j]].name);
}
printf("->%s, 距离为%d m\n",G->vex[end].name,dist[i]);
printf("\n\t\t\t\t\t按任意键返回...");
getch();
}
最佳布网方案：最小生成树Prim算法
// prim算法构建最小生成树
void Prim(AdjMatrix *G, int start)
{
struct
{
int adjvex;
int lowcost;
}closedge[MAXVEX];
int i, e, k, m, min;
closedge[start].lowcost = 0;
// 对除了出发点以外deep所有顶点初始化对应的closedge数组
for(i = 1; i <= G->vexnum; i++) {
if(i != start) {
closedge[i].adjvex = start;
closedge[i].lowcost = G->arcs[start][i];
}
}
for(e = 1; e <= G->vexnum-1; e++) //控制选中的n-1条符合条件的边
{
//选择权值最小的边
min = INFINITY;
for(k = 1; k <= G->vexnum; k++) {
if(closedge[k].lowcost != 0 && closedge[k].lowcost < min) {
m = k;
min = closedge[k].lowcost;
}
}
printf("\t\t\t\t\t从%s---%s:%d m\n", G->vex[closedge[m].adjvex].name,G->vex[m].name,closedge[m].lowcost);
closedge[m].lowcost = 0;
for(i = 1; i <= G->vexnum; i++) {
if(i != m && G->arcs[m][i] < closedge[i].lowcost) {
closedge[i].lowcost = G->arcs[m][i];
closedge[i].adjvex = m;
}
}
}
printf("\n\t\t\t\t\t按任意键返回...");
getch();
}
测试结果
初始界面
游客界面
管理员登录
管理员界面
导航说明界面
校园平面简图
查询景点信息
查询简单路线
查询中转次数最少的路径
查询最优路径
查询最佳布网方案
添加新地点
添加新路线
撤销旧路线
管理员注册
写在后面
终于写完啦！！！
刚了好几个星期！！！
这个项目几乎囊括了数据结构大部分知识，在这个过程中查了不少的资料，也看了不少视频，总结了许多。虽然这个demo还有bug，后面会继续改进！
