南京工程学院
课程设计说明书(论文)
题 目 校园导航系统
课 程 名 称 数据结构
院 系 通信工程学院
专 业 信息工程
班 级
学 生 姓 名
学 号
设 计 地 点
指 导 教 师
设计起止时间：2008 年12月29 日至 年 月 日
目 录
1．课程设计题目... 1
2．软件功能描述... 1
3．软件总体设计... 1
3．1数据结构描述与定义... 1
3．2模块设计... 3
4．测试结果与分析... 4
5．课程设计总结... 5
附录：源程序清单... 6
1．课程设计题目
校园导航系统
2．软件功能描述
在近一个星期的努力下，我编写的校园导航系统软件终于能够成功完成。采用工程思想，将系统共分一下几个模块:数据结构定义模块、导航图建立模块、求最短路径模块、主菜单；
下面是具体各功能简单的实际应用：
Ø 数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩阵的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小）。
Ø 导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。包括：各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。
Ø 求最短路径模块： 本模块的基本思想是采用迪杰斯特拉算法求最短路径。次模块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功能。
Ø 主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。
以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课程设计的基本要求。由于所学知识有限，功能各个方面还有欠妥之处，希望得到指出与改正。
3．软件总体设计
3．1数据结构描述与定义
1. 节点数据结构类型：
#define MAX_V 30 //最大顶点个数
typedef struct
{
char* vexs[MAX_V]; //顶点向量
int arcs[MAX_V][MAX_V];//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;
2. 创建导航图函数：
int CreateUDN(MGraph &G)
函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储。
例：
G.vexs[0] = "小北门";
作用：使0号定点命名为“小北门”；
G.arcs[0][1] = G.arcs[1][0] =550;
作用：使0号节点到1号节点的路径赋值为550，应为是无向图，所以1号节点到0号节点的路径长度也应赋值为550；
3. 最短路径导航函数：
void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[])
函数描述：用Dijkstra算法求无向网G的V0定点到其余定点V的最短路径P[v]及其带权长度D[v]。
若P[v][w]为True，则w是从V0到V当前求得最短路径上的顶点。
Final[v]为True当且仅当V∈S，即已经求得从V0到V的最短路径。
4. 导航菜单函数声明
void menu()
函数描述：输出各个节点的编号，放便导航。
3．2模块设计
以下为迪杰斯特拉算法流程图：
4．测试结果与分析
很高兴，这次自己设计的校园导航系统能够按照预先的设想正常运行，经过反复的调试和优化程序，使得程序的源代码更规范且易于理解，程序的输出界面更为友好，操作更简便易行。
测试内容：
Ø 系统登陆界面：
Ø 导航功能1——两点最短距离导航测试结果如下
Ø 导航功能2——某点到其他所有点的距离
5．课程设计总结
经过一个学期对数据结构课程的学习，我能够掌握数据结构所教会我的对待问题的方法，以及遇到问题时如何抽象出一个合理的数据结构类型。数据结构教会我的不但是每一个算法，更多的是如何解决问题的方法。例如，在本次课程设计中我做的是校园导航系统，对于校园导航问题的关键是最短路径的问题，在教材中有算法——迪杰斯特拉求最短路径问题，在花了几天时间后，终于能够将算法的整个流程弄清楚，在对各个定点的存储上采用邻接矩阵的方法，在寻找各个点到其他所有点的关系的时候更为方便直观。在课程设计中遇到的一系列问题都能够在老师和同学的指导下及时解决。
最后，感谢一年来为我们付出努力的老师们，感谢给过我指导意见的同学们，在这一年对数据结构的学习中，真的收获颇多，为我以后继续学习计算机的基础课程打下了坚实的基础。
附录：源程序清单
type.h //定义每个顶点的结构类型
#include<stdio.h>
#define MAX_V 30 //最大顶点个数
#define INFINITY 32767 //最大值
typedef struct
{
char* vexs[MAX_V]; //顶点向量
int arcs[MAX_V][MAX_V];//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;
Creat.cpp //创建无向图
#include"type.h"
int CreateUDN(MGraph &G)
{//采用数组(邻接矩阵)表示法,构造无向网G.
int i = 0,j=0;
G.vexnum = 27;
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] = "文理楼"; G.vexs[11] ="医务室";
G.vexs[12] = "亿恒酒店"; G.vexs[13] = "艺术楼"; G.vexs[14] = "南教学楼";
G.vexs[15] = "自动化学院"; G.vexs[16] = "图书馆"; G.vexs[17] = "学海湾";
G.vexs[18] = "东区食堂"; G.vexs[19] = "东区超市"; G.vexs[20] = "东门";
G.vexs[21] = "经管楼"; G.vexs[22] = "信息楼"; G.vexs[23] = "天印湖";
G.vexs[24] = "西门"; G.vexs[25] = "行政楼"; G.vexs[26] = "南门";
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][1] = G.arcs[1][0] =550;
G.arcs[0][4] = G.arcs[4][0] =160 ;
G.arcs[0][5] = G.arcs[5][0] =600;
G.arcs[1][2] = G.arcs[2][1] =80;
G.arcs[2][3] = G.arcs[3][2] =100;
G.arcs[2][11] = G.arcs[11][2]=110;
G.arcs[2][10] = G.arcs[10][2] =130;
G.arcs[3][11] = G.arcs[11][3] = 100;
G.arcs[3][12] = G.arcs[12][3] = 220;
G.arcs[4][5] = G.arcs[5][4] = 300;
G.arcs[4][7] = G.arcs[7][4] = 300;
G.arcs[4][6] = G.arcs[6][4] = 210;
G.arcs[5][7] = G.arcs[7][5] = 300;
G.arcs[5][15] = G.arcs[15][5] = 500;
G.arcs[6][7] = G.arcs[7][6] = 60;
G.arcs[6][9] = G.arcs[9][6] = 170;
G.arcs[7][8] = G.arcs[8][7] = 230;
G.arcs[8][9] = G.arcs[9][8] = 35;
G.arcs[8][14] = G.arcs[14][8] = 35;
G.arcs[8][15] = G.arcs[15][8] = 350;
G.arcs[8][16] = G.arcs[16][8] = 200;
G.arcs[9][10] = G.arcs[10][9] = 200;
G.arcs[9][14] = G.arcs[14][9] = 100;
G.arcs[10][11]= G.arcs[11][10] = 50;
G.arcs[10][13]= G.arcs[13][10] = 50;
G.arcs[11][12]= G.arcs[12][11] = 85;
G.arcs[12][13]= G.arcs[13][12] = 160;
G.arcs[12][18]= G.arcs[18][12] = 20;
G.arcs[12][19]= G.arcs[19][12] = 130;
G.arcs[13][17]= G.arcs[17][13] = 100;
G.arcs[13][18]= G.arcs[18][13] = 230;
G.arcs[14][17]= G.arcs[17][14] = 100;
G.arcs[15][16]= G.arcs[16][15] = 310;
G.arcs[15][21]= G.arcs[21][15] = 250;
G.arcs[15][24]= G.arcs[24][15] = 400;
G.arcs[16][17]= G.arcs[17][16] = 160;
G.arcs[16][22]= G.arcs[22][16] = 200;
G.arcs[16][21]= G.arcs[21][16] = 100;
G.arcs[16][23]= G.arcs[23][16] = 200;
G.arcs[16][24]= G.arcs[24][16] = 400;
G.arcs[17][23]= G.arcs[23][17] = 140;
G.arcs[18][19]= G.arcs[19][18] = 90;
G.arcs[18][20] = G.arcs[20][18] = 320;
G.arcs[19][20] = G.arcs[20][19] = 350;
G.arcs[20][26] = G.arcs[26][20] = 570;
G.arcs[21][24] = G.arcs[24][21] = 260;
G.arcs[22][23] = G.arcs[23][22] = 85;
G.arcs[22][25] = G.arcs[25][22] = 190;
G.arcs[23][25] = G.arcs[25][23] = 100;
G.arcs[23][26] = G.arcs[26][23] = 620;
G.arcs[24][25] = G.arcs[25][24] = 130;
return 1;
}
Short_path.cpp //采用迪杰斯特拉算法，求最短路径
#include"type.h"
extern have[30];
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;
}
}
}
Menu.cpp //程序登陆界面
#include<stdio.h>
void menu()
{
printf("☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ 导航主菜单 ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n");
printf("☆ (1) 小北门 (2) 大北门 (3) 东区田径场 ☆ \n");
printf("☆ (4) 东区宿舍楼 (5) 北区宿舍楼 (6) 北区田径场 ☆ \n");
printf("☆ (7) 北区超市 (8) 北区食堂 (9) 基础实验楼 ☆ \n");
printf("☆ (10) 东西教学楼 (11) 文理楼 (12) 医务室 ☆ \n");
printf("☆ (13) 亿恒酒店 (14) 艺术楼 (15) 南教学楼 ☆ \n");
printf("☆ (16) 自动化学院 (17) 图书馆 (18) 学海湾 ☆ \n");
printf("☆ (19) 东区食堂 (20) 东区超市 (21) 东门 ☆ \n");
printf("☆ (22) 经管楼 (23) 信息楼 (24) 天印湖 ☆ \n");
printf("☆ (25) 西门 (26) 行政楼 (27) 南门 ☆ \n");
printf("☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n\n");
printf("请选择导航功能：\n");
printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
printf("≈ (1) 两点最短距离导航 ≈\n");
printf("≈ (2) 某点到其他所有点的最短距离 ≈\n");
printf("≈ (3) 退出导航系统 ≈\n");
printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
}
Main.cpp //主函数文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "type.h"
int have[30];
int CreateUDN(MGraph &G); //创建导航图函数声明
void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[]);//最短路径导航函数声明
void menu(); //导航菜单函数声明
void main()
{
MGraph G;
int v0,i,end,j;
int P[MAX_V][MAX_V];
int D[MAX_V];
int choice,choice1;
printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");
printf("\n≈≈ 欢迎光临南京工程学院，祝旅程愉快！ ≈≈\n");
printf("\n≈≈ 南京工程学院校园导游系统为你服务！ ≈≈\n");
printf("\n≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n\n"); CreateUDN(G);
while(1)
{
menu();
scanf("%d",&choice);
switch(choice)
{
case 1:
{
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;
}
}
break;
case 2:
{
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 3:
break;
default:
printf("选择错误，请重新输入！\n");
}
if(choice==3)
{
printf("欢迎再次使用校园导航系统，回车键退出。^_^\n");
getchar();
getchar();
break;
}
}
}