本科毕业论文---校园导航系统设计.doc

课 程 设 计

课程名称
数据结构
题目名称
校园导航系统
专业班级

学生姓名

二○一五年六月一日

目录

1 引 言 4
1.1 问题的提出 4
1.2国内外研究的现状 5
1.3任务与分析 5
2 程序的主要功能 5
3 程序运行平台 5
4 总体设计 5
4.1数据结构类型定义 5
4.2函数声明 5
4.3创建导航图，即无向图 5
4.4最短路径导航函数 5
5 程序方法的说明 5
5.1主菜单 6
5.2主函数 6
5.3迪杰斯特拉算法实现 9
6 模块分析 10
7 系统测试 10
7.1系统登录界面 10
7.2功能一：学校简介 10
7.3功能二：两点最短距离导航 10
7.4功能三：某点到其他所有点的最短距离 11
7.5功能四：显示全校地图 11
7.5退出导航系统 12
8 结论 12
附录： 13

蚌埠学院计算机科学与技术系本科课程设计成绩评定表
项目
权重
分值
具体要求
得分
文献阅读与调查论证
0.20
100
能独立查阅文献和从事其它调研；有收集、加工各种信息的能力

设计质量
0.30
100
设计合理、功能齐备，程序运行正常，实验数据准确可靠；有较强的实际动手能力

论文撰写质量
0.20
100
设计说明书完全符合规范化要求，用A4复印纸打印成文

学习态度
0.20
100
学习态度认真，科学作风严谨，严格按要求开展各项工作，按期完成任务

学术水平与创新
0.10
100
设计有创意，有一定的学术水平或实用价值

总分

评语：

等级：
指导教师：

年 月 日

附件4 分工协作说明（以列表形式具体说明每个人所做的工作）；
课题名称
学生姓名
学号
所做的工作
校园导航系统
张小蒙
51302041036
算法设计、程序调试、课程设计报告撰写
张 浩
51302041045
算法设计、程序调试、课程设计报告排版
王威风
51302041011
算法设计、程序调试、课程设计报告撰写
柏祝林
51302033026
算法设计、程序调试、资料查询
鲍金林
51302041041
部分算法设计、程序调试
张红伟
51302041043
部分算法设计、程序调试、资料查询
杨伟平
51302041006
部分算法设计、程序调试

1 引 言
1.1 问题的提出
设计一个校园导航系统，为来访的客人提供各种信息查询服务。
1.2国内外研究的现状
这个问题一直是国内外研究的热门话题。
1.3任务与分析
设计你的学校的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）

2 程序的主要功能
（1）设计校园平面图，在校园景点选8个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。

3 程序运行平台
计算机 windows7 Virtual c++ 6.0

4 总体设计
4.1数据结构类型定义

#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_V 30 //最大顶点个数
#define INFINITY 32767 //最大值

typedef struct
{
char* vexs[MAX_V]; //顶点向量
int arcs[MAX_V][MAX_V];//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;
4.2函数声明
int CreateUDN(MGraph &G); //创建导航图函数声明
extern have[30];
void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[]);//最短路径导航函数声明
int have[30];
void menu(); //导航菜单函数声明
void show1(); //显示全校面貌
int jianjie();//读取文件

4.3创建导航图，即无向图
int CreateUDN(MGraph &G)
函数描述：主要将每个节点进行命名，每个定点到其他所有定点的路径值用邻接矩阵进行存储。
例如：
G.vexs[0] = "小池塘";
G.vexs[1] = "东门";
作用：使0号定点命名为“小池塘”，1号节点命名为“东门”。
G.arcs[1][4] = G.arcs[4][1] =260 ;
作用：使1号定点到4号定点的路径赋值为260，同时4号定点到1号定点的路径长度也为260.
4.4最短路径导航函数
void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[])
函数描述：用迪杰斯特拉算法求最短路径。

5 程序方法的说明
5.1主菜单
void menu()
{
printf("\t\t\t\t☆ ☆ ☆ ☆ 学院各区名称 ☆ ☆ ☆ ☆ \n");
printf("\t\t\t\t☆ (1) 小池塘 (2) 东门 (3) 西门 ☆ \n");
printf("\t\t\t\t☆ (4) 北门 (5) 东区宿舍楼 (6) 西南宿舍楼☆ \n");
printf("\t\t\t\t☆ (7) 北区田径场 (8) 南区田径场 (9) 一号食堂 ☆ \n");
printf("\t\t\t\t☆ (10) 二号食堂 (11) A B C教学楼 (12) 重行楼 ☆ \n");
printf("\t\t\t\t☆ (13) 行政楼 (14) 艺术楼 (15) 图书馆 ☆ \n");
printf("\t\t\t\t☆ (16) 超市 (17) 医务室 (18) 没有了 ☆ \n");
printf("\t\t\t\t\t\t\t请选择导航功能：\n");
printf("\t\t\t\t\t≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
printf("\t\t\t\t\t≈ (1) 学校简介 ≈\n");
printf("\t\t\t\t\t≈ (2) 两点最短距离导航 ≈\n");
printf("\t\t\t\t\t≈ (3) 某点到其他所有点的最短距离 ≈\n");
printf("\t\t\t\t\t≈ (4) 显示全校地图 ≈\n");
printf("\t\t\t\t\t≈ (5) 退出导航系统 ≈\n");
printf("\t\t\t\t\t≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
}
描述：程序主菜单显示。
5.2主函数
void main()
{
//system("color 09"); /*修改控制台的颜色信息,改为白字蓝底的模式*/
system("mode con: cols=140 lines=130"); /*设置运行时窗口大小*/
MGraph G;
int v0,i,end,j;
int P[MAX_V][MAX_V];
int D[MAX_V];
int choice,choice1;
printf("\t\t\t\t ≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
printf("\n\t\t\t\t≈≈欢迎光临蚌埠学院，祝您旅程愉快！≈≈\n");
printf("\n\t\t\t\t≈≈蚌埠学院校园导游系统为你服务 ≈≈\n");
printf("\n\t\t\t\t≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n\n");
CreateUDN(G);
while(1){
menu();
scanf("%d",&choice);
switch(choice){
case 1: jianjie();
break;
case 2: {
while(1)
{
printf("分别输入起点和终点代号以空格分开\n");
scanf("%d%d",&v0,&end);
ShortPath(G,v0,P,D);
printf("最短路径:\n ");
for(i=0;i<G.vexnum;i++)
{
if(P[end-1][have[i]]==1)
printf("-->%s",G.vexs[have[i]]);
}
printf("\n路径长度:%d\n",D[end-1]);
printf("^_^ 本次导航结束:\n1.继续导航 2.返回主菜单\n");
scanf("%d",&choice1);
if(choice1==2)
break;
}
else if(choice1<1||choice1>2){
printf("你输入选项有误，请继续导航！！！\n");
}
}
break;
case 3: {
printf("请输入出发点：");
scanf("%d",&v0);
ShortPath (G,v0,P,D);
printf("v0到其他所有点的最短路径为：\n");
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
if(P[i][have[j]]==1)
printf("-->%s",G.vexs[have[j]]);
printf("\n路径长度:%d\n",D[i]);
}
}
break;

case 4:
show1();
break;
case 5:
break;
default:
printf("选择错误，请重新输入！\n");
}
if(choice==5)
{
system("cls");
printf("\n\n\n\n\n\n");
printf(" \t\t\t ┏━━━━━━━━━━━━━━━━━━━━┓\n");
printf(" \t\t\t ┃ 感谢使用 ┃\n");
printf(" \t\t\t ┃ 蚌埠学院 ┃\n");
printf(" \t\t\t ┃ 智能导航系统 ┃\n");
printf(" \t\t\t ┗━━━━━━━━━━━━━━━━━━━━┛\n");
printf("\n\n");
printf(" \t\t\twelcom to bengbu college,Good Bay!!!回车键退出。^_^\n");
break;
}
}
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
}

5.3迪杰斯特拉算法实现
void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[]) {
//迪杰斯特拉发求最短路径
int v,w,i,j,min;
int final[MAX_V];
int k=1;
for(v=0;v<G.vexnum;++v)
{//初始化
final[v]=0;
d[v]=G.arcs[v0-1][v];
for(w=0;w<G.vexnum;++w)
p[v][w]=0;
if(d[v]<INFINITY)
{
p[v][v0-1]=1;
p[v][v]=1;
}
}
d[v0-1]=0;
final[v0-1]=1;
have[0]=v0-1;
for(i=1;i<G.vexnum;++i)
{
//其余的vexnum-1个顶点
min=INFINITY;
for(w=0;w<G.vexnum;++w)
if(!final[w])
if(d[w]<min) //如有W点离更近
{
v=w;
min=d[w];
}
final[v]=1;
have[k]=v;
k++;
for(w=0;w<G.vexnum;++w)//更新当前最短路径及距离
if(!final[w]&&(min+G.arcs[v][w]<d[w]))
{
d[w]=min+G.arcs[v][w];
for(j=0;j<G.vexnum;j++)
p[w][j]=p[v][j];
p[w][w]=1;
}
}
}
描述：迪杰斯特拉算法求最短路径。
6 模块分析。

7 系统测试
7.1系统登录界面

7.2功能一：学校简介

7.3功能二：两点最短距离导航

7.4功能三：某点到其他所有点的最短距离

7.5功能四：显示全校地图

7.5退出导航系统

8 结论
在本次课程设计所做的校园导航系统中，最关键的问题是最短路径问题，在教材中有具体的算法——迪杰斯特拉算法求最短路径问题。但是想一次性就把程序调试出来是不可能的，我们组也是经过多次讨论才把程序完整的调试出来。通过这次的课程设计，我们学到了很多知识，也认识到很多不足，那就是知识的不足和经验的缺乏。但是我们相信自己可以在以后的学习中不断进步。
附录：
源代码：#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_V 30 //最大顶点个数
#define INFINITY 32767 //最大值

typedef struct
{
char* vexs[MAX_V]; //顶点向量
int arcs[MAX_V][MAX_V];//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;

int CreateUDN(MGraph &G); //创建导航图函数声明
extern have[30];
void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[]);//最短路径导航函数声明
int have[30];
void menu(); //导航菜单函数声明
void show1(); //显示全校面貌
int jianjie();//读取文件
void main()
{
// system("color F2"); /*修改控制台的颜色信息,改为白字蓝底的模式*/
system("mode con: cols=140 lines=130"); /*设置批处理运行时窗口大小的*/
MGraph G;
int v0,i,end,j;
int P[MAX_V][MAX_V];
int D[MAX_V];
int choice,choice1;
printf("\t\t\t\t ≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
printf("\n\t\t\t\t≈≈ 欢迎光临蚌埠学院，祝您旅程愉快！ ≈≈\n");
printf("\n\t\t\t\t≈≈ 蚌埠学院校园导游系统为你服务！ ≈≈\n");
printf("\n\t\t\t\t≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n\n");
CreateUDN(G);
while(1){
menu();
scanf("%d",&choice);
switch(choice){
case 1: jianjie();
system("cls");
break;
case 2: {
while(1)
{
printf("分别输入起点和终点代号以空格分开\n");
scanf("%d%d",&v0,&end);
ShortPath(G,v0,P,D);
printf("最短路径:\n ");
for(i=0;i<G.vexnum;i++)
{
if(P[end-1][have[i]]==1)
printf("-->%s",G.vexs[have[i]]);
}
printf("\n路径长度:%d\n",D[end-1]);
printf("^_^ 本次导航结束:\n1.继续导航 2.返回主菜单\n");
scanf("%d",&choice1);
if(choice1==2){
system("cls");
break;
}
else if(choice1<1||choice1>2){
printf("你输入选项有误，请继续导航！！！\n");
}
}
}
break;
case 3: {
printf("请输入出发点：");
scanf("%d",&v0);
ShortPath (G,v0,P,D);
printf("v0到其他所有点的最短路径为：\n");
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
if(P[i][have[j]]==1)
printf("-->%s",G.vexs[have[j]]);
printf("\n路径长度:%d\n",D[i]);
}
system("pause");
}
system("cls");
break;

case 4:
system("cls");
printf("\n\n\n\n");
show1();
system("cls");
break;
case 5:
break;
default:
printf("选择错误，请重新输入！\n");
}

if(choice==5)
{
system("cls");
printf("\n\n\n\n\n\n");
printf(" \t\t\t ┏━━━━━━━━━━━━━━━━━━━━┓\n");
printf(" \t\t\t ┃ 感谢使用 ┃\n");
printf(" \t\t\t ┃ 蚌埠学院 ┃\n");
printf(" \t\t\t ┃ 智能导航系统 ┃\n");
printf(" \t\t\t ┗━━━━━━━━━━━━━━━━━━━━┛\n");
printf("\n\n");
printf(" \t\t\t welcom to BengBu college,Good Bay!!!回车键退出。^_^\n");
break;
}
}
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");

}
//创建无向图
int CreateUDN(MGraph &G)
{//采用数组(邻接矩阵)表示法,构造无向网G.
int i = 0,j=0;
G.vexnum = 17; //图的定点数
G.arcnum = 51; //图的弧数
G.vexs[0] = "小池塘";
G.vexs[1] = "东门";
G.vexs[2] = "西门";
G.vexs[3] = "北门";
G.vexs[4] = "东区宿舍楼";
G.vexs[5] = "西南宿舍楼";
G.vexs[6] = "北区田径场";
G.vexs[7] = "南区田径场";
G.vexs[8] = "一号食堂";
G.vexs[9] = "二号食堂";
G.vexs[10] = "A B C教学楼";
G.vexs[11] ="重行楼";
G.vexs[12] = "行政楼";
G.vexs[13] = "艺术楼";
G.vexs[14] = "图书馆";
G.vexs[15] = "超市";
G.vexs[16] = "医务室";
for(i=0;i<G.vexnum;i++) //初始化路径长度
for(j=0;j<G.vexnum;j++)
{
if(i==j)
G.arcs[i][j]=0;
else
G.arcs[i][j]=INFINITY; //初始化最大值 默认不邻接
}
//为每一条边赋权 即路径长度 因为边是对称的
G.arcs[0][13] = G.arcs[13][0] = 50;
G.arcs[0][7] =G.arcs[7][0]= 90;
G.arcs[1][4] = G.arcs[4][1] =260 ;
G.arcs[4][7] = G.arcs[7][4] =100;
G.arcs[5][7] = G.arcs[7][5] =200;
G.arcs[4][14] = G.arcs[14][4] =50;
G.arcs[6][14] = G.arcs[14][6] =100;
G.arcs[7][14] = G.arcs[14][7] =70;
G.arcs[7][14] =G.arcs[14][7] =70;
G.arcs[4][10] = G.arcs[10][4]=100;
G.arcs[3][4] = G.arcs[4][3] =200;
G.arcs[3][10] = G.arcs[10][3] =100 ;
G.arcs[4][8] = G.arcs[8][4] =60;
G.arcs[4][9] = G.arcs[9][4] =50;
G.arcs[8][9] = G.arcs[9][8] =150;
G.arcs[10][14] = G.arcs[14][10] =100;
G.arcs[8][15] = G.arcs[15][8] =70 ;
G.arcs[9][15] = G.arcs[15][9] =70;
G.arcs[4][16] = G.arcs[16][4]=150;
G.arcs[9][16] = G.arcs[16][9] =50;
G.arcs[11][12] = G.arcs[12][11] =200;
G.arcs[11][14] = G.arcs[14][11] =220;
G.arcs[12][13] = G.arcs[13][12] =50;
G.arcs[12][14] = G.arcs[14][12] =70;
G.arcs[13][16] = G.arcs[16][13] =120;
G.arcs[2][14] = G.arcs[14][2] =100;
return 1;
}

void menu()
{
printf("\n\n\n\n");
printf("\t\t\t\t☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ 学院各区名称 ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n");
printf("\t\t\t\t☆ (1) 小池塘 (2) 东门 (3) 西门 ☆ \n");
printf("\t\t\t\t☆ (4) 北门 (5) 东区宿舍楼 (6) 西南宿舍楼☆ \n");
printf("\t\t\t\t☆ (7) 北区田径场 (8) 南区田径场 (9) 一号食堂 ☆ \n");
printf("\t\t\t\t☆ (10) 二号食堂 (11) A B C教学楼 (12) 重行楼 ☆ \n");
printf("\t\t\t\t☆ (13) 行政楼 (14) 艺术楼 (15) 图书馆 ☆ \n");
printf("\t\t\t\t☆ (16) 超市 (17) 医务室 (18) 没有了 ☆ \n");
printf("\t\t\t\t☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n\n");
printf("\n\n");
printf("\t\t\t\t\t\t\t请选择导航功能：\n");
printf("\t\t\t\t\t≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
printf("\t\t\t\t\t≈ (1) 学校简介 ≈\n");
printf("\t\t\t\t\t≈ (2) 两点最短距离导航 ≈\n");
printf("\t\t\t\t\t≈ (3) 某点到其他所有点的最短距离 ≈\n");
printf("\t\t\t\t\t≈ (4) 显示全校地图 ≈\n");
printf("\t\t\t\t\t≈ (5) 退出导航系统 ≈\n");
printf("\t\t\t\t\t≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
printf("\n\n\n\n");
}

//采用迪杰斯特拉算法，求最短路径
void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[]) {
//迪杰斯特拉发求最短路径
int v,w,i,j,min;
int final[MAX_V];
int k=1;
for(v=0;v<G.vexnum;++v)
{//初始化
final[v]=0;
d[v]=G.arcs[v0-1][v];
for(w=0;w<G.vexnum;++w)
p[v][w]=0;
if(d[v]<INFINITY)
{
p[v][v0-1]=1;
p[v][v]=1;
}
}
d[v0-1]=0;
final[v0-1]=1;
have[0]=v0-1;
for(i=1;i<G.vexnum;++i)
{
//其余的vexnum-1个顶点
min=INFINITY;
for(w=0;w<G.vexnum;++w)
if(!final[w])
if(d[w]<min) //如有W点离更近
{
v=w;
min=d[w];
}
final[v]=1;
have[k]=v;
k++;
for(w=0;w<G.vexnum;++w)//更新当前最短路径及距离
if(!final[w]&&(min+G.arcs[v][w]<d[w]))
{
d[w]=min+G.arcs[v][w];
for(j=0;j<G.vexnum;j++)
p[w][j]=p[v][j]; //凡是到v经过的顶点，到w也要经过
p[w][w]=1;
}
}
}

void show1(){
printf("\t\t\t\t\t\t ★★ 欢迎使用蚌埠学院智能导航系统 ★★\n");
printf("\t\t\t\t\t\t\t蚌埠学院校区平面图\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 ┃ 重行楼 ┃ ┃\n");
printf("\t\t\t\t ┃ ┃ ┃\n");
printf("\t\t\t\t ┃ A B C教学楼 ┃ ┃\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 ┃ ┃ . ┃\n");
printf("\t\t\t\t ┃ 行政楼 ┃ . ┃\n");
printf("\t\t\t\t 西门 小池塘 ┃ . ┃\n");
printf("\t\t\t\t ┃━┃ 艺术楼 ┃ . ┃\n");
printf("\t\t\t\t ┃ ┃ . ┃\n");
printf("\t\t\t\t ┃ ┃ 8 ┃\n");
printf("\t\t\t\t