校园导游咨询

西安郵電

数据结构设计报告

题 目： 校园导游咨询系统

院系名称：

计算机学院

设计起止时间：2011年11月28日~2011年12月9日

一. 设计目的

1.设计一个校园导游系统，为来客查询校园的各种信息 2.熟练掌握图的知识、加深课堂所学用于实践

二. 设计内容

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

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

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

三．概要设计

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．功能函数的调用关系图

Main() CreateGraph()

Map() SearchPath() SearchPlace() Outputplace() Shortpath(i); Output(i,j); 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;vfinal[v]=0; //假设从顶点num到顶点v没有最短路径 D[v]=G.arc[num][v].length;//将num到其余顶点的最短路径长度初始化为权值 for(w=0;wvoid Output(int sight1,int sight2) // 输出函数 { int a,b,c,d,q=0;//a、b、c和d为计数变量//q控制计数变量、用于换行 a=sight2; //将景点二赋值给a if(a!=sight1) // 如果景点二不和景点一输入重合，则进行... {

printf(\"\\\\\\从%s到%s的最短路径是:\\n\\n\\\\\\.vertex[sight2].name);//输出提示信息 //输出sight1到sight2的最短路径长度，存放在D[]数组中 printf(\"\%s\ //输出景点一的名称 d=sight1; //将景点一的编号赋值给d for(c=0;cgate:; //标号，可以作为goto语句跳转的位置 path[a][sight1]=0; for(b=0;b%s\.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\\\\\\最短距离为 %dm.\\n\\n\\ } }

五．测试数据及运行结果

1．正常测试数据和运行结果 1、系统主界面

2、校园全景浏览

3、景点信息查询

4、最短路径查询

2．异常测试数据及运行结果

1、异常数据①

2、异常数据②

六．调试情况，设计技巧及体会

1．改进方案

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

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

2．体会

以后要加强动手时间能力、多与同学交流算法精髓！ 在编写程序中尽量做到独立完成、对于自己想要完成的问题要主动编程完成、这样自己是一个很大的提升、也能学到很多的知识、熟练编程！

七．参考文献

1、数据结构-----C语言描述（主编：耿国华）高等教育出版社

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

八．附录：

#include #include #include #include #include #define MAX 100000 #define NUM 30

#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; //图的定义

void Map();//校园地图

void CreateGraph();//创建图

void OutputPlace();//输出景点列表 void SearchPlace();//查询景点信息 void SearchPath();//查询最短路径 void Shortpath(int i);//计算最短路径

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

Graph G;

int path[NUM][NUM]; int D[NUM];

void CreateGraph()//创建图 { int i,j; G.vexnum=14; G.arcnum=28; for(i=1;iG.vertex[6].info=\"大学生活动中心是我校专为学生设计、展现自己各种特长才艺的地方!\\n\\\\\\每周这里都会有非常精彩的活动、晚会;乃才艺高人的聚集地!\\n\"; G.vertex[7].name=\"图书馆\"; G.vertex[7].info=\"图书馆内设多种书库，有几百万的丰富藏书!平时这里学习氛围浓重、\\n\\\\\\是知识的天堂!\\n\"; G.vertex[8].name=\"洗浴中心\"; G.vertex[8].info=\"洗浴中心是学生洗浴的地方!\\n\"; G.vertex[9].name=\"体育馆\"; G.vertex[9].info=\"体育馆是一个室内的小型体育场;内设有篮球场，羽毛球场及乒乓球场等\\n\"; G.vertex[10].name=\"体育场\"; G.vertex[10].info=\"体育场是举行大型赛事的地点，平时主要各种足球训练、比赛使用;\\n\\\\\\也是同学们跑步健身的好场所!\"; G.vertex[11].name=\"土操场\"; G.vertex[11].info=\"土操场主要供学生平时运动、跑步使用;其侧面还有乒乓球、网球场地;\\n\\\\\\是同学们课外活动的地点之一!\\n\"; G.vertex[12].name=\"篮球场\"; G.vertex[12].info=\"篮球场是同学们篮球课程及锻炼球技的地方,也是篮球比赛的重要场所!\\n\"; G.vertex[13].name=\"美食广场\"; G.vertex[13].info=\"美食广场是学校的两大食堂之一、饭菜美味可口!\\n\"; G.vertex[14].name=\"旭日苑\"; G.vertex[14].info=\"旭日苑是学校的另一食堂;共分三层,饭菜种类繁多,可品尝到各种美味!\\n\"; for(i=0;iG.arc[6][10].length=G.arc[10][6].length=150; G.arc[7][10].length=G.arc[10][7].length=100; G.arc[12][8].length=G.arc[8][12].length=50; G.arc[10][9].length=G.arc[9][10].length=30; G.arc[9][12].length=G.arc[12][9].length=70; G.arc[13][8].length=G.arc[8][13].length=30; G.arc[13][12].length=G.arc[12][13].length=40; G.arc[11][12].length=G.arc[12][11].length=20; G.arc[11][14].length=G.arc[14][11].length=30; G.arc[13][14].length=G.arc[14][13].length=120; G.arc[10][14].length=G.arc[14][10].length=120; }

void Map()//学校地图 { printf(\"\\n\\n\"); system(\"cls\"); printf(\"\\\\\\┏━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\"\\\\\\┃ 西安邮电学院校园图 ┃\\n\"); printf(\"\\\\\\┃ 注：此图按正门布局而画,方位并非上北下南左西右东! ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃ ┏━━━┓ ┃\\n\"); printf(\"\\\\\\┃ ╔═══╦══┫旭日苑┣═══════╗ ┃\\n\"); printf(\"\\\\\\┃ ║ ║ ┗┳━┳┛ ║ ┃\\n\"); printf(\"\\\\\\┃ ║ ║ ║ ║ ║ ┃\\n\"); printf(\"\\\\\\┃ ┏┻┓ ┏┻┓ ║┏┻━━━━┓ ┏━┻━┓ ┃\\n\"); printf(\"\\\\\\┃ ┃体┃ ┃体┃ ║┃ 土操场 ┃ ┃ 美食 ┃ ┃\\n\"); printf(\"\\\\\\┃ ┃育┣═┫育┃ ║┃ ┃ ┃ 广场 ┃ ┃\\n\"); printf(\"\\\\\\┃ ┃场┃ ┃馆┣══╬╋━━━━━┫ ┃ ┃ ┃\\n\"); printf(\"\\\\\\┃ ┗┳┛ ┗┳┛ ║┃ 篮球场 ┣═┻━┳━┛ ┃\\n\"); printf(\"\\\\\\┃ ║ ║ ║┃ ┃ ║ ┃\\n\"); printf(\"\\\\\\┃ ║ ║ ║┗━━━━━┛ ║ ┃\\n\"); printf(\"\\\\\\┃ ║┏━━╩━━┓║ ┏━┻━━┓ ┃\\n\"); printf(\"\\\\\\┃ ╔╩┫ 图书馆 ┣╬══════╦═┫洗浴中心┃ ┃\\n\"); printf(\"\\\\\\┃ ║ ┗━━┳━━┛║ ║ ┗━━━━┛ ┃\\n\"); printf(\"\\\\\\┃┏┻━┓ ║ ║ ┏━┻━━━┓ ┃\\n\"); printf(\"\\\\\\┃┃大学┃ ║ ║ ┃ 实 ┃ ┃\\n\"); printf(\"\\\\\\┃┃生活┃ ║ ║ ┃ 验 ┃ ┃\\n\"); printf(\"\\\\\\┃┃动中┣══╬═══╬════┫ 楼 ┃ ┃\\n\"); printf(\"\\\\\\┃┃ 心 ┃ ║ ║ ┗━━┳━━┛ ┃\\n\"); printf(\"\\\\\\┃┗━┳┛ ║ ║ ║ ┃\\n\"); printf(\"\\\\\\┃ ║ ┏┻━┓ ║ ┏━━┻━━┓ ┃\\n\"); printf(\"\\\\\\┃ ║ ┃喷泉┣═╬════┫ 教学楼 ┃ ┃\\n\"); printf(\"\\\\\\┃ ║ ┗┳━┛ ║ ┗━━┳━━┛ ┃\\n\");

printf(\"\\\\\\┃┏━┻━┓ ║ ║ ║ ┏━━━┓ ┃\\n\"); printf(\"\\\\\\┃┃行政楼┣═╩═══╬═══════╝ ┃ 南 ┃ ┃\\n\"); printf(\"\\\\\\┃┗━━━┛ ┏━━┻━━┓ ┃东╋西┃ ┃\\n\"); printf(\"\\\\\\┃ ┃ 学校正门 ┃ ┃ 北 ┃ ┃\\n\"); printf(\"\\\\\\┃ ┗━━━━━┛ ┗━━━┛ ┃\\n\"); printf(\"\\\\\\┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\"); }

void Outputplace()//输出校园景点名称 { printf(\"\\\\\\┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\"\\\\\\┃ 西安邮电学院学校景点一览表 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━┳━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃1.学校正门 ┃2.行政楼 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃3.教学楼 ┃4.喷泉 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃5.实验楼 ┃6.大学生活动中心 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃7.图书馆 ┃8.洗浴中心 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃9.体育馆 ┃10.体育场 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃11.土操场 ┃12.篮球场 ┃\\n\"); printf(\"\\\\\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\\\\\┃13.美食广场 ┃14.旭日苑 ┃\\n\"); printf(\"\\\\\\┗━━━━━━━━━━━━┻━━━━━━━━━━━━┛\\n\"); }

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

int i,num; char c='y'; while(c=='y') { system(\"cls\"); Outputplace(); printf(\"\\\\\\请输入您要查找的景点编号：\"); scanf(\"%d\ getchar(); system(\"cls\"); if(num>0 && num<=G.vexnum) //判定信息输入正确

{ for(i=1;i<=G.vexnum;i++) if(num==G.vertex[i].number) { printf(\"\\n\\\\\\景点编号:%d\\n\ printf(\"\\\\\\景点名称:%s\\n\ printf(\"\\\\\\景点简介:%s\\n\\n\ } } else printf(\"\\\\\\信息输入有误!\\n\"); num=0; printf(\"\\n\\\\\\是否继续查询景点信息(y/n):\"); c=getchar(); getchar(); }

system(\"cls\"); }

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

int i,j; char c='y'; while(c=='y') { system(\"cls\"); Outputplace(); printf(\"\\n\\n\\\\\\初始景点编号(1->14):\"); scanf(\"%d\ printf(\"\\\\\\最终景点编号(1->14):\"); scanf(\"%d\ getchar(); if(i>G.vexnum || i<=0 || j>G.vexnum || j<0 || i==j) printf(\"\\\\\\输入信息错误!\\n\\n\"); else { Shortpath(i); Output(i,j); } printf(\"\\n\\\\\\是否继续查询最短路径(y/n):\"); c=getchar(); getchar();

}

system(\"cls\"); }

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

int v,w,i,t;//i、w和v为计数变量//t表示景点个数 int final[NUM]; //标志数组、用来存放顶点的信息 int min;//记录权值、最终输出路径 for(v=0;vpath[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(\"\\\\\\从%s到%s的最短路径是:\\n\\n\\\\\\.vertex[sight2].name);//输出提示信息 //输出sight1到sight2的最短路径长度，存放在D[]数组中 printf(\"\%s\ //输出景点一的名称 d=sight1; //将景点一的编号赋值给d for(c=0;cgate:; //标号，可以作为goto语句跳转的位置 path[a][sight1]=0; for(b=0;b%s\.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\\\\\\最短距离为 %dm.\\n\\n\\ } }

void main() {

int x; system(\"color 2B\"); system(\"mode con: cols=170 lines=160\");//调整屏幕显示大小 CreateGraph(); printf(\"\\n\\n\\n\\n\\n\\\\\\\欢迎使用西安邮电学院校园导游系统\\n\\n\\n\"); while(1) { //Map(); printf(\"\\n\\n\"); printf(\"\\\\\\\┏━━━━━━━━━━┓\\n\"); printf(\"\\\\\\\┃1. 校园全景浏览 ┃\\n\"); printf(\"\\\\\\\┃2. 景点信息查询 ┃\\n\"); printf(\"\\\\\\\┃3. 最短路径查询 ┃\\n\"); printf(\"\\\\\\\┃0. 退出系统 ┃\\n\"); printf(\"\\\\\\\┗━━━━━━━━━━┛\\n\"); printf(\"\\n\\\\\\\请选择您需要的操作(0-3):\"); scanf(\"%d\ getchar(); switch(x) { case 1: system(\"cls\");printf(\"\\\\\\\校园全景浏览:\"); Map();break; case 2: system(\"cls\");printf(\"\\\\\\\景点信息查询:\"); SearchPlace();break; case 3: system(\"cls\");printf(\"\\\\\\\最短路径查询:\"); SearchPath();break; case 0: printf(\"\\n\\\\\\\\");exit(0); default: system(\"cls\");printf(\"\\\\\\\输入信息错误,请重新输入!\\n\"); break; } } }