校园导游咨询系统---数据结构课程设计..doc

石家庄经济学院

本科生课程设计报告书

题　 目 校园导游咨询系统
姓　　名　 颜建学
学　　号　　 410109070321
学 　院　　　 信息工程学院　
专　　业　　　 计算机方向　
指导教师　　　 XXXXXX

完成日期： 2012-07-5
校园导游咨询系统
1 需求分析
本程序的主要目的是为了提供本学校的景点的路径咨询和来访客人以及刚来报到的新生提供一个快捷方便的路径咨询，快速有效的提高了用户的熟悉度。。满足用户查询的需要：
1、从石家庄经济学院的平面地图中选取出10个有代表性的景点。
2、为来访的客人提供图中任意景点相关信息的查询。当用户输入正确时，为用户输出景点的相关信息；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。
3、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。
4、为来访客人推荐参观路线。
2 概要设计
1、抽象数据类型图的定义如下：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在路径}
基本操作P：
CreatGraph70321(&G,V,VR)
初始条件：V是图的顶点集，VR是图中边的集合。
操作结果：按V和VR的定义构造图G。
DestroyGraph70321(&G)
初始条件：图G存在。
操作结果：销毁图G。
LocateVex70321(G,u)
初始条件：图G存在，u和G中顶点有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。
GetVex70321(G,v)
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的信息。
FirstEdge70321(G,v)
初始条件：图G存在，v是G中某个顶点。
操作结果：返回依附于v的第一条边。若该顶点在G中没有邻接点，则返回“空”。 NextEdge70321(G,v,w)
初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。
操作结果：返回依附于v的（相对于w的）下一条边。若不存在，则返回“空”。 InsertVex70321(&G,v)
初始条件：图G存在，v和图中顶点有相同特征。
操作结果：在图中增添新顶点v。
DeleteVex70321(&G,v)
初始条件：图G存在，v是G中某个顶点。
操作结果：删除G中顶点v及其相关的边。
InsertEdge70321(&G,v,w)
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中增添边(v,w).
DeleteEdge70321(&G,v,w)
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除边(v,w)。
GetShortestPath70321(G,st,nd,&Path)
初始条件：图G存在，st和nd是G中两个顶点。
操作结果：若st和nd之间存在路径，则以Path返回两点之间一条最短路径，否则返回其他信息。
}ADT Graph
主程序
void main()
{初始化；
do{
接受命令（输入景点信息或输出最短路径）；
处理命令；
}while（“命令”！=“退出”）；
｝
2、　调用的函数有如下：
void CreateUDN70321(int v,int a); /* 造图函数 */
void narrate70321(); /*说明函数*/
void ShortestPath70321(int num); /*最短路径函数*/
void output70321(int sight1,int sight2); /*输出函数*/
char Menu70321(); /* 主菜单 */
void search70321(); /* 查询景点信息 */
char SearchMenu70321(); /* 查询子菜单 */
void HaMiTonian70321(int); /* 哈密尔顿图的遍历 */
void NextValue70321(int);
void display70321(); /* 显示遍历结果 */

3、运行主界面：
***************欢 迎 使 用 校 园 导 游 程 序************
******************石**家**庄**经*济**学**院********************
制作者：信息工程学院 410109070321 颜建学 ！！！欢迎您的使用！！！
————————————————————————————————
景点名称
————————————————————————————————
（0）教学主楼 （1）足球场
（2）灯光篮球场 （3）惠馨园
（4）实验楼 （5）计算机实验室

（6）地球科学博物馆 （7）学术报告厅
（8）图书馆 （9）喷泉
————————————————————————————————
┏━━━━━━━━━━━━━━━┓
┃ 1、查询景点路径 ┃
┃ 2、查询景点信息 ┃
┃ 3、推荐参观路线 ┃
┃ e、退出 ┃
┗━━━━━━━━━━━━━━━┛

子界面如下：
┏━━━━━━━━━━━━━━━┓
┃ 1、按照景点编号查询 ┃
┃ 2、按照景点名称查询 ┃
┃ e、返回 ┃
┗━━━━━━━━━━━━━━━┛

3、模块图表示如下：
主程序模块
处理功能模块
无向图存储模块
为用户输出景点信息
为用户输出两景点最佳路径
推荐参观路径

3 详细设计
从石家庄经济学院的平面地图中选取出10个有代表性的景点，将其抽象成无向带权网并用邻接矩阵来表示。以图中的顶点代表景点，存放景点名称、代号、简介等信息，权值代表两地之间的距离。
1、 图的存储结构如下：
#define Max 20000
#define NUM 9
typedef struct ArcCell{
int adj; /* 相邻接的景点之间的路程 */
}ArcCell; /* 定义边的类型 */
typedef struct VertexType70321{
int number; /* 景点编号 */
char *sight; /* 景点名称 */
char *description; /* 景点描述 */
}VertexType; /* 定义顶点的类型 */
typedef struct{
VertexType vex[NUM]; /* 图中的顶点，即为景点 /
ArcCell arcs[NUM][NUM]; /* 图中的边，即为景点间的距离 */
int vexnum,arcnum; /* 顶点数，边数 */
}MGraph; /* 定义图的类型
2、该程序的算法如下：
1)void CreateUDN70321(MGraph&G) /* 造图函数 */
{ //采用邻接矩阵表示法，构造无向网G
scanf(&G.vexnum,&G.arcnum,&IncInfo);// IncInfo为0则各弧不含其它信息
for(i=0;i< G.vexnum;++i)scanf(&G.vexs[i]);//构造顶点向量
fori=0;i< G.vexnum;++i)//初始化邻接矩阵
for(j=0;j< G.vexnum;++j)G.arcs[]i[j]={INFINITY,NULL}
for(k=0;k< G.arcnum;++k)//构造邻接矩阵
{
scanf(&v1,&v2,&w);//输入一条边依附的顶点及权值
i=LocateVex(G,v1);j= LocateVex(G,v2);//确定V1和V2在G中的位置
G.arcs[i][j].adj=w;//弧的权值
If(IncInfo)Input(*G.arcs[i][j].info);//若弧含有相关信息，则输入
Garcs[j][i]= G.arcs[i][j];//置的对称弧

}
Return OK;
}
2)void narrate70321() /* 说明函数 */
{
k=0;
printf("\n\t\t***************欢 迎 使 用 校 园 导 游 程 序*************\n");
printf("\n\t\t*******************石**家**庄**经**济**学**院************************\n");
printf("\n\t\t制作者： 信息工程学院 410109070321 颜建学 ！！！欢迎您使用！！！\n");
printf("\n\t\t__________________________________________________________________\n");
printf("\t\t\t\t\t 景点名称\t\t\n");
printf("\t\t__________________________________________________________________\n");
for(i=0;i2d)%-15s\t\t",i,G.vex[i].sight);
if(i%2==((NUM-1)%2))printf("\n");//奇数编号景点在右边，偶数编号景点在左边
k=k+1;
}
printf("\t\t_________________________________________________________________\n");
}
3) void ShortestPath70321(int num)
{ //用迪杰斯特拉算法求G的v0顶点到其余顶点的最短路径P[v]及其带权长度 D[v]
//若P[v][w]为TRUE,则 w是从v0到v当前求得最短路径上的顶点
//final[v]为TRUE当且仅当v属于S，即已经 求得从 v0到v的最短路径
for(v=0;vUE;
//开始主循环，每次求得v0到某个顶点的最短路径，并加v到S集
For(i=1;i< G.vexnum;++i)
{
Min=INFINITY;
For(w=0;w< G.vexnum;++w)
If(!final[w])
If(D[w]P[w][w]=TRUE;

}//if

}//for
}// ShortestPath

4) void output70321(int sight1,int sight2) /* 输出函数 */
{
if(sight2!=sight1) /* 如果景点二不和景点一输入重合，则进行... */
{
printf(从G.vex[sight1].sight到G.vex[sight2].sight的最短路径是:);/* 输出提示信息 */
printf(D[a]); /* 输出sight1到sight2的最短路径长度，存放在D[]数组中 */
printf(G.vex[sight1].sight); /* 输出景点一的名称 */
d=sight1; /* 将景点一的编号赋值给d */
for(c=0;c节点的名称 */
q=q+1; /* 计数变量加一，满8控制输出时的换行 */
P[a][b]=0;
d=b; /* 将b作为出发点进行下一次循环输出，如此反复 */
if(q%8==0) returnOK;
}
}
}
}
5)void main() /* 主函数 */
{
CreateUDN70321(NUM,11);
do
{
switch(Menu())
{
case '1':
narrate70321();
scanf(v0);
scanf(v1);
ShortestPath70321(v0); /* 计算两个景点之间的最短路径 */
Output70321(v0,v1); /* 输出结果 */
break;
case '2':
search();
break;
case '3':
narrate70321();
HaMiTonian(x[0]);
break;
};
}while(Menu()!='e');

}
6) char Menu() /* 主菜单 */
{
do
{
flag=1;
narrate70321();
scanf(c);
if(c=='1'||c=='2'||c=='3'||c=='e')
flag=0;
}while(flag);
return c;
}
7) char SearchMenu70321() /* 查询子菜单 */
{
do
{
flag=1;
narrate70321();
scanf(&c);

if(c=='1'||c=='2'||c=='e')
flag=0;
}while(flag);
return c;
}
8) void search70321() /* 查询景点信息 */
{
do
{
switch 70321(SearchMenu())
{
case '1':
narrate70321();
scanf(&num);
for(i=0;i{
printf(G.vex[i].description);
break;
}
}
if(i==NUM)
{
printf(没有找到！");
getchar70321();
}
break;
case '2':
narrate70321();
scanf(name);
for(i=0;i[i].description);
break;
}
}
if(i==NUM)
{
printf(没有找到！");
}
break;
}
}while(SearchMenu()!='e');
}
3、流程图如下：
开始
造图
输入您的选择
您的选择是1？
您的选择是2？
您的选择是3？
您的选择是100？
结束
输入您的第一个景点选择
输入您的第二个景点选择
您的选择是e？
符合条件？
计算最短路径
输出结果
按编号查询？
推荐最佳路径
输入景点编号
输入景点名称
输出结果
输出结果
输出结果
否
是
否
是
否
否
是
是
否
是
是
否
是
石家庄经济学院校园导游系统设计流程图
信息工程学院 计算机三班
颜建学 410109070321

4 编码调试
校园导游咨询系统主界面如下图1所示，输入1进行景点路径查询，输入2进行景点信息查询，输入3时推荐参观路线，输入e时则退出本系统。

图1
当输入1时进入一个选择子菜单（输入错误时，保持原有状态），正确输入起点（2）（灯光篮球场）和终点（4）（实验楼），屏幕将打印出两景点之间的最短路径：灯光篮球场—〉惠馨园—〉实验楼，最短路径为约430m。如下图2所示：

图2
当输入的景点代号不在（0-9）之间时，程序提示重新输入，直到输入正确。测试数据：当起点输入10终点输入12时，景点不存在，程序提示重新输入；当起点输入0（教学主楼）终点输入12时，终点景点不存在，程序提示重新输入；当起点输入0（教学楼）终点输入8（图书馆）时，景点都存在，屏幕打印出两景点最短路径：教学楼—〉喷泉—〉学术报告厅—〉图书馆，最短路径约为200m。如下图3所示：

图3
按100推出此环节，当在选择主菜单选择2时，出现如下图4所示子菜单：

图4
当输入1时，则按景点编号查询，当输入6（地球科学博物馆）时，屏幕上打印出此景点信息：里面有著名的不寻常恐龙化石；当输入4（实验楼）时，屏幕上打印出此景点信息：各专业实验的重要场地；当输入12时，此景点不存在，屏幕上显示：！！！没*有*找*到！！！；当输入20时，此景点不存在，屏幕上显示：！！！没*有*找*到！！！。如下图5所示：

图5
当输入2时，则按景点名称查询，当输入“图书馆”时，屏幕上打印出此景点信息：图书馆是莘莘学子学习的园地，里面有各科资料，每人可以任借五本书；当输入“计算机实验室”时，屏幕上打印出此景点信息：计算机专业实验实习场所；当输入“教学三号楼”时，此景点不存在，屏幕上显示：！！！没*有*找*到！！！；如下图6所示：

图6
当在选择主菜单中输入3时，则系统推荐旅游路径：
1）教学主楼—〉足球场—〉灯光篮球场—〉惠馨园—〉实验楼—〉喷泉—〉学术报告厅—〉地球科学博物馆—〉计算机实验室—〉图书馆—〉校园出口
2）教学主楼—〉足球场—〉灯光篮球场—〉惠馨园—〉实验楼—〉喷泉—〉学术报告厅—〉图书馆—〉计算机实验室—〉地球科学博物馆—〉校园出口
3）教学主楼—〉地球科学博物馆—〉计算机实验室—〉图书馆—〉学术报告厅—〉喷泉—〉实验楼—〉惠馨园—〉灯光篮球场—〉足球场—〉校园出口
如下图7所示

图7
在选择主菜单输入错误时，程序不作反应，当输入e时，则退出，如下图8所示

图8
由于本人的设计能力有限，在设计过程中难免出现错误。本程序在调试时，出现了一个很棘手的错误，出现了结构体变量G的重复定义，经过自己的多次修改，没有成功，最后在老师的帮助下，将变量的定义从函数定义里放到了函数声明里，成功的修改了那个问题。当然还有一些简单的语法错误这些错误都是比较好改的，在此就不一一列举了。

5 设计体会
本次课程设计使我提高了应用计算能力、编写代码的基本能力、绘画流程图能力，熟悉了规范和标准，同时对于本设计的课程都有了全面的复习，独立思考的能力也有了提高。
1、当写第一步需求分析时，本以为是问题的简单描述，所以写的比较简单，但是让老师验收没有通过，经过进一步改进，将问题详细化了，并正确而准确的描述了校园导游的输入输出问题，顺利通过第一步的验收。概要设计还是比较简单的，毕竟还没有到算法的描述部分，这一过程很简单的就通过了，但是自己感觉对主界面的设计不是很满意，然后几经思索，设计出了自己较为满意的界面。当前两步完成后心里便有压力了，因为算法描述对我来说真的有点难。我多次查看书籍并上网查询相关资料，终于把详细设计部分做好了。在调试程序时有一个很棘手的问题，结构体变量G出现了重复定义，最初在函数定义的文件中，后来把定义放到了函数声明那个文件中才通过了
2、 测试数据：当输入1时进入一个选择子菜单（输入错误时，保持原有状态），正确输入起点（2）（灯光篮球场）和终点（4）（实验楼），屏幕将打印出两景点之间的最短路径：灯光篮球场—〉惠馨园—〉实验楼，最短路径为约430m。当输入的景点代号不在（0-9）之间时，程序提示重新输入，直到输入正确。测试数据：当起点输入10终点输入12时，景点不存在，程序提示重新输入；当起点输入0（教学主楼）终点输入12时，终点景点不存在，程序提示重新输入；当起点输入0（教学楼）终点输入8（图书馆）时，景点都存在，屏幕打印出两景点最短路径：教学楼—〉喷泉—〉学术报告厅—〉图书馆，最短路径约为200m。当输入1时，则按景点编号查询，当输入6（地球科学博物馆）时，屏幕上打印出此景点信息：里面有著名的不寻常恐龙化石；当输入4（实验楼）时，屏幕上打印出此景点信息：各专业实验的重要场地；当输入12时，此景点不存在，屏幕上显示：！！！没*有*找*到！！！；当输入20时，此景点不存在，屏幕上显示：！！！没*有*找*到！！！。当输入2时，则按景点名称查询，当输入“图书馆”时，屏幕上打印出此景点信息：图书馆是莘莘学子学习的园地，里面有各科资料，每人可以任借五本书；当输入“计算机实验室”时，屏幕上打印出此景点信息：计算机专业实验实习场所；当输入“教学三号楼”时，此景点不存在，屏幕上显示：！！！没*有*找*到！！！；当在选择主菜单中输入3时，则系统推荐旅游路径：
1）教学主楼—〉足球场—〉灯光篮球场—〉惠馨园—〉实验楼—〉喷泉—〉学术报告厅—〉地球科学博物馆—〉计算机实验室—〉图书馆—〉出口
2）教学主楼—〉足球场—〉灯光篮球场—〉惠馨园—〉实验楼—〉喷泉—〉学术报告厅—〉图书馆—〉计算机实验室—〉地球科学博物馆—〉出口
3）教学主楼—〉地球科学博物馆—〉计算机实验室—〉图书馆—〉学术报告厅—〉喷泉—〉实验楼—〉惠馨园—〉灯光篮球场—〉足球场—〉出口
在选择主菜单输入错误时，程序不作反应，当输入e时，则退出。
本程序的时间复杂度主要发生在求最短路径时，即算法里面的for循环语句，for循环语句三层嵌套，所以时间复杂度为n3。
3、在图的存储时本程序采用的邻接矩阵，也可以采用邻接表；在求两景点之间的最短路径时本程序采用的迪杰斯特拉算法，也可以采用弗洛伊德算法。
4、在本次课程设计中让我进一步熟悉了各种算法的使用，但感到自己在算法设计中还存在很大的不足，写算法时无法脱离课本，更是需要老师、同学的帮助，甚至有的算法不得不从网上查询，今后自己将更努力学习这门语言，多接触解决各种问题的各种算法，这样才能提高自己。
6 致谢
非常高兴能和同学们一起在实验室做实验，感谢各位老师以及同学们对我的帮助，特别是老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；这次数据结构设计的每个实验细节和每个数据，都离不开老师您的细心指导。在您们的帮助下让我顺利完成了这次课程设计。平时注重的理论知识多了些，造成我上机操作遇到了很多困难，但是老师和同学都很热情的帮助我，在此我表示我诚挚的谢意。
7 参考文献
[1]. 严蔚敏．数据结构（Ｃ语言版）[M]．清华大学出版社 2008年11月
[2]. 严蔚敏．数据结构题集（Ｃ语言版）[M]．清华大学出版社 2008年11月
[3]. 何钦铭．数据结构课程设计[M]．浙江大学出版社 2007年8月1
8 源程序
//daoyouzixunxitong70321.cpp: implementation of the daoyouzixunxitong70321 class.
#include "StdAfx70321.h"
#include "daoyouzixunxitong70321.h"
int x[11]={0};
int P[NUM][NUM];
long int D[NUM];

MGraph G;
daoyouzixunxitong70321::~daoyouzixunxitong70321()
{

}
void daoyouzixunxitong70321::main2()
{

int v0,v1;
char ck;
CreateUDN70321(NUM,11); //景点个数加1 //调用CreateUNM()函数
do
{
ck=Menu70321();//调用Menu()
switch(ck)
{
case '1':
system("cls");
narrate70321();//调用narrate函数
printf("\n\n\t\tO(∩_∩)O 提示：输入100退出此环节\n");
M:printf("\n\t\t请选择起点景点(0～9)：");
scanf("%d",&v0);
if(v0==100)break;
printf("\t\t请选择终点景点(0～9)："); //景点编号
scanf("%d",&v1);
if(v0>9||v1>9)
{
printf("\n\t\tO(∩_∩)O 请重新输入v0,v1:\n");
goto M;
}
ShortestPath70321(v0); //调用ShortestPath()函数
output70321(v0,v1); //调用output()函数
goto M;
break;
case '2':
search70321();//调用search()函数
break;
case '3':
system("cls");
narrate70321();//调用 narrate()函数
x[0]=1; //此处必须为x[0]=1 实际为x[0]=true
HaMiTonian70321(1);
//调用哈密尔顿函数 遍历应该从第一个景点开始！！！如果想要修改，必须从HaMiTonian()和NextValue()内部修改
printf("\n\n\t\t\t\t请按Enter继续...\n");
getchar();
getchar();
break;
};
}while(ck!='e');
}

void daoyouzixunxitong70321::CreateUDN70321(int v, int a)
{
int i,j;
G.vexnum=v;
G.arcnum=a;
for(i=0;i].sight="教学主楼";
G.vex[0].description="学校领导， **** 办公之地";
G.vex[1].sight="足球场";
G.vex[1].description="宽阔,非常适合运动";
G.vex[2].sight="灯光篮球场";
G.vex[2].description="篮球运动的最佳活动场所";
G.vex[3].sight="惠馨园";
G.vex[3].description="石家庄经济学院惠馨园一、二楼是学生餐饮中心，三楼是教职工餐饮中心，四楼是综合办公之地，五楼是文艺文化活动中心";
G.vex[4]sight="实验楼";
G.vex[4].description="各专业试验的重要场地";
G.vex[5].sight="计算机实验室";
G.vex[5].description="计算机专业的实验实习场所";
G.vex[6].sight="地球科学博物馆";
G.vex[6].description="里面有著名的不寻常恐龙化石";
G.vex[7].sight="学术报告厅";
G.vex[7].description="学术交流中心";
G.vex[8].sight="图书馆";
G.vex[8].description="图书馆是莘莘学子学习的园地，里面有各科资料，每人可以任借五本书";
G.vex[9].sight="喷泉";
G.vex[9].description="学校的盛大节日时就可以看见";
for(i=0;i[2][3].adj=G.arcs[3][2].adj=130;
G.arcs[3][4].adj=G.arcs[4][3].adj=300;
G.arcs[0][5].adj=G.arcs[5][0].adj=50;
G.arcs[2][5].adj=G.arcs[5][2].adj=100;
G.arcs[0][6].adj=G.arcs[6][0].adj=250;
G.arcs[6][7].adj=G.arcs[7][6].adj=50;
G.arcs[4][9].adj=G.arcs[9][4].adj=500;
G.arcs[5][6].adj=G.arcs[6][5].adj=300;
G.arcs[5][8].adj=G.arcs[8][5].adj=300;
G.arcs[7][8].adj=G.arcs[8][7].adj=50;
G.arcs[7][9].adj=G.arcs[9][7].adj=100;
}

void daoyouzixunxitong70321::narrate70321()
{
int i,k=0;
printf("\n\t\t***************欢 迎 使 用 校 园 导 游 程 序*************\n");
printf("\n\t\t******************石**家**庄**经**济**学**院**********************\n");
printf("\n\t\t制作者： 信息工程学院 410109070321 颜建学 !!!欢迎您使用!!!\n");
printf("\n\t\t__________________________________________________________________\n");
printf("\t\t\t\t\t 景点名称\t\t\n");
printf("\t\t_______________\n");
for(i=0;i daoyouzixunxitong70321::ShortestPath70321(int num)
{
int v,w,i,t;
int final[NUM];
int min;
for(v=0;v