校园导航问题课程设计论文正稿.doc

.
1 / 15
摘 要
校园导航要求每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径<最短路径>。要用"邻接矩阵"来存储各点间的距离,然后用Dijkstra算法求出最短路径。所以采用工程思想,将系别用来保存创建的导航数据,和下载其它导航数据,这样这个系统才能更加实用,void createadj<>原来的函数原型为arcnode *createdj<>函数中用链表结构把adjmatrix[][]的数据都保存其中,这样就能实现数据的保存,但随之要把Ｄijkstra中的adjmatrix[][]转换成用arcnode 指针的形式进行表示,因为只有这样,下载后的数据才能使用。
参考文献
［1］《数据结构》〔C语言版〕,严蔚敏,清华大学,2005．
［2］《算法设计与分析》,王晓东主编,清华大学,2005
［3］汪诗林等译,《数据结构、算法与应用》,〔美〕Sartaj Sahni著,机械工业, 1999
［4］《数据结构与算法分析》,CLIFFORD A. SHAFFER著,X铭、X晓丹译,电子工业,1998
［5］ 谭浩强 .C程序设计［Z］.：清华大学,2001.
［6］ ［Z］.：机械工业,2000.
［7］ ［Z］.XX：XX理工大学,1993.
［8］ ［Z］.：电子工业,1993.
.
5 / 15
附 录
源程序：
#include ""
#include ""
#include ""
#include ""
#include ""
#define Max 20000
#define NUM 10
typedef struct ArcCell{
int adj; /* 相邻接的景点之间的路程 */
}ArcCell; /* 定义边的类型 */
typedef struct VertexType{
int number; /* 景点编号 */
char* sight; /* 景点名称 */
char* info; /* 景点描述 */
}VertexType; /* 定义顶点的类型 */
typedef struct{
VertexType vex[NUM]; /* 图中的顶点,即为景点 */
ArcCell arcs[NUM][NUM]; /* 图中的边,即为景点间的距离 */
int vexnum,arcnum; /* 顶点数,边数 */
}MGraph; /* 定义图的类型 */
MGraph G; /* 把图定义为全局变量 */
int P[NUM][NUM]; /* */
long int D[NUM]; /* 辅助变量存储最短路径长度 */
int x[9]={0};
void CreateUDN<int v,int a>; /* 造图函数 */
void narrate<>; /*说明函数*/
void ShortestPath<int num>; /*最短路径函数*/
void output<int sight1,int sight2>; /*输出函数*/
char Menu<>; /* 主菜单 */
void search<>; /* 查询景点信息 */
char SearchMenu<>; /* 查询子菜单 */
void HaMiTonian<int>; /* 哈密尔顿图的遍历 */
.
6 / 15
void NextValue<int>;
void display<>; /* 显示遍历结果 */
void main<> /* 主函数 */
{
int v0,v1;
char ck;
CreateUDN<NUM,11>;
do
{
ck=Menu<>;
switch<ck>
{
case '1':
system<"cls">;
narrate<>; /* 输出景点列表 */
printf<"\n\n\t\t\t请选择起点景点〔0～9〕：">;
scanf<"%d",&v0>;
printf<"\t\t\t请选择终点景点〔0～9〕：">;
scanf<"%d",&v1>;
ShortestPath<v0>; /* 计算两个景点之间的最短路径 */
output<v0,v1>; /* 输出结果 */