当前位置：文档库 › 校园导游咨询程序

校园导游咨询程序

实验三：校园导游咨询

一、设计方案简介

设计一个校园导游程序，为来访的客人提供各种信息查询服务。

1）设计你所在学校的校园平面图，

2）为来访客人提供图中任意景点相关信息的查询。

3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

二、设计题目实现:

实际需求

1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。

2）为来访客人提供图中任意景点相关信息的查询。

3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

2）概要设计

1、校园全景一览图、显示出校园的平面图。

2、提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。

3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。

1．功能模块图；

void Map();//校园地图

void CreateGraph();//创建图

void OutputPlace();//输出景点列表

void SearchPlace();//查询景点信息

void SearchPath();//查询最短路径

void Shortpath(int i);//计算最短路径

void Output(int sight1,int sight2);//输出函数

2．各个模块详细的功能描述。

Map();//显示校园整体的地图、包含学校各景点的详细位置CreateGraph();//创建图、主要用来保存各景点信息OutputPlace();//输出景点列表、供选择景点信息查询时使用SearchPlace();//查询景点信息、景点的名称及介绍SearchPath();//查询最短路径、两景点间最短距离Shortpath(int i);//计算两景点间最短路径

Output(int sight1,int sight2);//输出两景点最短路径及信息四．详细设计

1．功能函数的调用关系图

2012年01 月

2．各功能函数的数据流程图

全局变量

Graph G;

int path[NUM][NUM];

int D[NUM];

3．重点设计及编码

重点设计：求最短路径

编码：

void Shortpath(int num)//迪杰斯特拉算法最短路径

{

int v,w,i,t;//i、w和v为计数变量//t表示景点个数

int final[NUM]; //标志数组、用来存放顶点的信息

int min;//记录权值、最终输出路径

for(v=0;v

{

final[v]=0; //假设从顶点num到顶点v没有最短路径

D[v]=G.arc[num][v].length;//将num到其余顶点的最短路径长度初始化为权值

for(w=0;w

path[v][w]=0;//初始化从v到w的路径值

if(D[v]

{

path[v][num]=1; //存在标志置为一

path[v][v]=1; //自身到自身

}

2012年01 月

D[num]=0;//初始化新路径

final[num]=1; //初始化num顶点属于final集合

//开始主循环,每一次求得num到某个顶点的最短路径，并将其加入到final集合

for(i=0;i

{

min=MAX; //当前所知离顶点num的最近距离

for(w=0;w

if(!final[w]) //w顶点在v-s中

if(D[w]

{

v=w;

min=D[w];

}

final[v]=1; //离num顶点更近的v加入到s集合

for(w=0;w

if(!final[w]&&((min+G.arc[v][w].length)

{

D[w]=min+G.arc[v][w].length;//更新路径

for(t=0;t

path[w][t]=path[v][t];

path[w][w]=1;

}

void Output(int sight1,int sight2) // 输出函数

{

int a,b,c,d,q=0;//a、b、c和d为计数变量//q控制计数变量、用于换行

a=sight2; //将景点二赋值给a

if(a!=sight1) // 如果景点二不和景点一输入重合，则进行...

{

printf("\t\t\t\t\t\t从%s到%s的最短路径是:\n\n\t\t\t\t\t",G.vertex[sight1].name,G.vertex[sight2].name);//输出提示信息

//输出sight1到sight2的最短路径长度，存放在D[]数组中

printf("\t%s",G.vertex[sight1].name); //输出景点一的名称

d=sight1; //将景点一的编号赋值给d

for(c=0;c

{

2012年01 月

gate:; //标号，可以作为goto语句跳转的位置

path[a][sight1]=0;

for(b=0;b

{

if(G.arc[d][b].length

{

printf("--->%s",G.vertex[b].name); //输出此节点的名称

q=q+1; //计数变量加一，满8控制输出时的换行

path[a][b]=0;

d=b; //将b作为出发点进行下一次循环输出，如此反复

if(q%14==0) printf("\n");

goto gate;

}

printf("\n\n\t\t\t\t\t\t最短距离为%dm.\n\n\t",D[a]);

}

五．测试数据及运行结果

系统主界面

2012年01 月

学校平面图

2012年01 月

学校景点图

2012年01 月

最短路径信息查询

2012年01 月

异常信息

2012年01 月

三、设计评述:设计者对本设计的评述及通过设计的收获

体会

1．改进方案

系统还有部分漏洞未能修复、不够绝对的稳定、还需改进！

求最短路径时可以采用比较简单的哈密尔顿算法。

本次课程设计仅完成了要求的基本功能、由于平时掌握的不够好以及时间关系未能完成选作功能、这是一大缺陷！另外通过本次课程设计也更好的掌握了平时所学的知识、通过实践学到了许多课本上没有的知识！

2．体会

以后要加强动手时间能力、多与同学交流算法精髓！

在编写程序中尽量做到独立完成、对于自己想要完成的问题要主动编程完成、这样自己是一个很大的提升、也能学到很多的知识、熟练编程！

报告最后有两部分附录

附录一：参考资料1、C语言程序设计（谭浩强版）

2、数据结构（C语言版）编著：严蔚敏、吴伟民清华大学出版社

附录二：源程序（将所有的源程序附在最后的附录中）

// 查询景点信息.cpp : Defines the entry point for the console application.

2012年01 月

#include "stdafx.h"

#include "stdio.h"

#include

#define NUM 20

#define MAX 100000

#define FALSE 0

#define TURE 1

typedef struct ArcNode

{

int length; //路径长度

} ArcNode, *ArcLink; //边结点的定义

typedef struct VertexNode

{

int number; //景点的编号

char *name; //景点的名称

char *info; //景点的简介

} VertexNode; //顶点结点的定义

typedef struct Graph

{

VertexNode vertex[NUM];

ArcNode arc[NUM][NUM];

int vexnum,arcnum; //图的顶点数，边数

} Graph; //图的定义

Graph G;

int path[NUM][NUM];

int D[NUM];

void CreateGraph();//创建图

void Map();//学校地图

void outputplace();//输出校园景点名称

void searchplace();//查询景点信息

void searchpath();//查询最短路径

void shortestpath_DIJ(int num);//迪杰斯特拉算法最短路径void output(int sight1,int sight2);//输出函数

void CreateGraph()//创建图

2012年01 月

{

int i,j;

G.vexnum=12;

G.arcnum=17;

for(i=1;i

G.vertex[i].number=i;

G.vertex[1].name="太原理工大学正门";

G.vertex[1].info="学校正门位于学校的正南方向、是进入学校前的第一道亮丽\n\t\t的风景线!\n";

G.vertex[2].name="电机馆";

G.vertex[2].info="电机馆是数学系，电子信息系，自动化，通讯等学院的学院楼!\n";

G.vertex[3].name="科学楼";

G.vertex[3].info="科学楼是我校科研机构场所，也是山西省网关所在地!\n";

G.vertex[4].name="多学科楼";

G.vertex[4].info="科学楼是计算机科学与技术学院，软件学院，电子信息学院，\n\t\t 土木，建筑的学院楼，也是我校最好的学院楼!\n";

G.vertex[5].name="图书馆";

G.vertex[5].info="太原理工图书馆经历了初创时期，发展时期，面向现代化的转型时期。\n\t\t如今，她已经发展成为资源丰富，现代化，综合性，开放式的图书馆!\n";

G.vertex[6].name="机械馆";

G.vertex[6].info="机械馆是我校百年高校最有力的体现!\n\t\t是欧式风格建筑，外观宏伟气派\n\t\t为机械学院的学院楼!\n";

G.vertex[7].name="篮球场";

G.vertex[7].info="篮球场全橡胶场，每天这里打球人员特多，我校篮球队\n\t\t在历年的CUBA联赛上取得佳绩，是我们引以为豪的校队!\n";

G.vertex[8].name="清泽餐厅";

G.vertex[8].info="清泽餐厅是我校最现代化的食堂，提供各种美食!\n";

G.vertex[9].name="学生宿舍";

G.vertex[9].info="这里是我校学生宿舍集中所在地，包括本科生，研究生宿舍，\n\t\t 是我们在学校的家!\n";

G.vertex[10].name="文体中心";

G.vertex[10].info="文体中心包括体育馆，体育场，各种体育娱乐场所，供学生\n\t\t体育锻炼的地方!\n";

G.vertex[11].name="国际交流中心";

G.vertex[11].info="国际交流中心是外国留学生居住学习科研的场所!\n";

for(i=0;i

for(j=0;j

G.arc[i][j].length=MAX;

G.arc[1][2].length=G.arc[2][1].length=60;

G.arc[1][3].length=G.arc[3][1].length=30;

G.arc[1][6].length=G.arc[6][1].length=70;

2012年01 月

G.arc[2][3].length=G.arc[3][2].length=10;

G.arc[2][4].length=G.arc[4][2].length=50;

G.arc[2][6].length=G.arc[6][2].length=100;

G.arc[4][5].length=G.arc[5][4].length=20;

G.arc[5][6].length=G.arc[6][5].length=40;

G.arc[5][7].length=G.arc[7][5].length=10;

G.arc[7][8].length=G.arc[8][7].length=15;

G.arc[8][9].length=G.arc[9][8].length=400;

G.arc[8][10].length=G.arc[10][8].length=120;

G.arc[9][10].length=G.arc[10][9].length=500;

G.arc[10][11].length=G.arc[11][10].length=80;

G.arc[11][5].length=G.arc[5][11].length=100;

G.arc[11][6].length=G.arc[6][11].length=500;

}

void Map()//学校地图

{

printf("\n\n");

system("cls");

printf("\t┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┒\n");

printf("\t┃太原理工大学校园图┃\n");

printf("\t┃注：此图按正门布局而画,方位并非上北下南左西右东! ┃\n");

printf("\t┃━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");

printf("\t┃┏————┒\n");

printf("\t┃................................ ┃学生宿舍┃\n");

printf("\t┃: : ┗------ --┛┃\n");

printf("\t┃┏--------┒┏--------┒┃\n");

printf("\t┃┃文体中心┃........┃清泽餐厅┃┃\n");

printf("\t┃┗--------┛┗--------┛┃\n");

printf("\t┃: : ┃\n");

printf("\t┃: ┍------┒┃\n");

printf("\t┃: ┃篮球场┃┃\n");

printf("\t┃: ┗------┛┃\n");

printf("\t┃: : ┃\n");

printf("\t┃┍--------┒┏------┒┏--------┒┃\n");

printf("\t┃┃国际交流┃........┃图书馆┃........┃多学科楼┃┃\n");

printf("\t┃┗--------┛┗------┛┗--------┛┃\n");

printf("\t┃: : : ┃\n");

printf("\t┃: ┏------┒: ┏------┒: ┃\n");

2012年01 月

printf("\t┃:... ┃机械馆┃.........┃电机馆┃....:.... ┃\n");

printf("\t┃┗------┛: ┗- ----┛: ┃\n");

printf("\t┃: : : ┃\n");

printf("\t┃: : ┏------┒┃\n");

printf("\t┃: : ┃科学楼┃┃\n");

printf("\t┃: : ┗------┛┃\n");

printf("\t┃┏----------------┒: ┋┃\n");

printf("\t┃┃太原理工大学大门┃''''''''''''' ┃\n");

printf("\t┃┗----------------┛┎------┓┃\n");

printf("\t┃┃北┃\n");

printf("\t┃┃西╋东┃\n");

printf("\t┃┃南┃\n");

printf("\t┃┗------┛┃\n");

printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n"); }

void outputplace()//输出校园景点名称

{

printf("\t┎━━━━━━━━━━━━━━━━━━━━━━━━┓\n");

printf("\t┃太原理工大学学校景点一览表┃\n");

printf("\t┠━━━━━━━━━━━━━┲━━━━━━━━━━┃\n");

printf("\t┃ 1.学校正门┃ 2.电机馆┃\n");