数据结构 校园导游系统课程设计
- 格式：doc
- 大小：499.00 KB
- 文档页数：20
滨江学院 《数据结构》课程设计 题 目 校园导游咨询程序设计 学 号 学生姓名 院 系 专 业 指导教师
二Ｏ一二 年 月 日 1、题目的内容及要求 设计一个校园导游程序，为来访的客人提供各种信息查询服务。
2、需求分析 （1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 （3）为来访客人提供图中任意景点相关信息的查询。
3、概要设计 1．功能模块图； void CreateUDN();//创建无向网 void Search();//查询景点信息 void Shortestpath(int i);//计算最短路径 void Output(int sight1,int sight2);//输出函数
2．各个模块详细的功能描述。 CreateUDN();//创建无向网、主要用来保存各景点信息 Search();//查询景点信息、景点的名称及介绍 Shortestpath(int i);//计算两景点间最短路径 Output(int sight1,int sight2);//输出两景点最短路径及信息 3.模块图 4、详细设计 一、图的储存结构 #define Max 30000 #define NUM 10 typedef struct ArcCell { int adj; /* 相邻接的景点之间的路程 */ }ArcCell; /* 定义边的类型 */ typedef struct VertexType { int number; /* 景点编号 */ char *sight; /* 景点名称 */ char *description;/* 景点描述 */ }VertexType; /* 定义顶点的类型 */
typedef struct { VertexType vex[NUM]; /* 图中的顶点，即为景点 */ ArcCell arcs[NUM][NUM];/* 图中的边，即为景点间的距离 */ int vexnum,arcnum;/* 顶点数，边数 */ }MGraph; /* 定义图的类型
二、算法 1.主程序 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); /* 计算两个景点之间的最短路径 */ printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; case '2':search(); break; case '3': system("cls"); //narrate(); x[0]=1; HaMiTonian(1); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; }; }while(ck!='e');
}
2.输出程序 void output(int sight1,int sight2) { int a,b,c,d,q=0; a=sight2; if(a!=sight1) /* 如果景点二不和景点一输入重合，则进行 */ { printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);/* 输出提示信息 */ printf("\t(最短距离为 %dm.)\n\n\t",D[a]); printf("\t%s",G.vex[sight1].sight); d=sight1; /* 将景点一的编号赋值给d */ for(c=0;c { gate:; P[a][sight1]=0; for(b=0;b { if(G.arcs[d][b].adj<30000&&P[a][b]) /* 如果景点一和它的一个临界点之间存在路径且最短路径 */ { printf("-->%s",G.vex[b].sight); /* 输出此节点的名称 */ q=q+1; /* 计数变量加一，满8控制输出时的换行 */ P[a][b]=0; d=b; /* 将b作为出发点进行下一次循环输出，如此反复 */ if(q%9==0) printf("\n"); goto gate; } } } }
}
3.求最短路径 void ShortestPath(int num) { int v,w,i,t; int final[NUM]; int min; for(v=0;v { final[v]=0; D[v]=G.arcs[num][v].adj; for(w=0;w P[v][w]=0; if(D[v]<30000) { P[v][num]=1; P[v][v]=1; } }
D[num]=0; final[num]=1;
for(i=0;i { min=Max; for(w=0;w if(!final[w]) if(D[w] { v=w; min=D[w]; } final[v]=1; for(w=0;w if(!final[w]&&((min+G.arcs[v][w].adj) { D[w]=min+G.arcs[v][w].adj; for(t=0;t P[w][t]=P[v][t]; P[w][w]=1; } } }
4.说明函数 void narrate() { int i,k=0; printf("\n\t\t*****************欢迎使用校园导游程序***************\n"); printf("\n\t\t********************南京信息工程大学*******************\n"); printf("\t__________________________________________________________________\n"); printf("\t\t景点名称\t\t|\t景点描述\n");
printf("\t________________________________|_________________________________\n"); for(i=0;i { printf("\t (%2d)%-10s\t\t\t|\t%-25s\n",i,G.vex[i].sight,G.vex[i].description); k=k+1; }
printf("\t________________________________|_________________________________\n"); } 5、查询景点信息 void search() { int num; int i; char c; char name[20];
do { system("cls"); c=SearchMenu(); switch (c) { case '1': system("cls"); narrate(); printf("\n\n\t\t请输入您要查找的景点编号："); scanf("%d",&num); for(i=0;i { if(num==G.vex[i].number) { printf("\n\n\t\t\t您要查找景点信息如下:"); printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description); printf("\n\t\t\t按任意键返回..."); getchar();
