数据结构校园导游咨询系统课程设计报告及课程总结.doc
《数据结构校园导游咨询系统课程设计报告及课程总结.doc》由会员分享，可在线阅读，更多相关《数据结构校园导游咨询系统课程设计报告及课程总结.doc（20页珍藏版）》请在冰点文库上搜索。
姓名：
班级：
学号：
指导教师：
2012年12月
目录
1、需求分析 1
1.1系统简介 1
1.2系统功能模块介绍 1
2、概要设计 2
2.1系统功能结构图 2
2.2系统流程图 2
2.3主要函数概要设计 3
2.3.1主函数概要设计 3
2.3.2初始化图函数InitGraph（） 4
2.3.4查询景点信息函数设计SearchGraph（） 4
2.3.5显示图中信息函数设计ShowGraph（） 4
2.3.6弗洛伊德算法函数设计Floyd（） 5
3、详细设计 5
3.1主函数详细设计 5
3.2初始化图函数详细设计InitGraph（） 6
3.3查询景点信息函数详细设计SearchGraph（） 7
3.4弗洛伊德算法函数详细设计Floyd（） 8
4、调试分析 9
4.1显示主界面函数测试 9
4.2查找两景点间最短路径测试 10
4.3查看景点信息测试 11
5.课程设计总结 12
6、附录 13
18
1、需求分析
1.1系统简介
随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。
考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“江西农业大学校园咨询系统”。
开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。
本系统界面友好，提示信息充分，在实际使用过程中运行良好。
1.2系统功能模块介绍
本系统主要分为以下三大功能模块：
1、查询两景点最短路径：
用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。
若输入信息合法，则回车后系统将给出最短路径，显示于屏幕上方；
2、查询景点信息：
用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入想要查询的景点的编号，回车后系统将在已存储的景点中进行匹配，若该景点信息尚未存储则将提示错误；若找到对应信息则系统将输出景点信息，显示于幕上方；
3、退出系统：
用户在使用完本系统后，选择此功能模块，系统提示“欢迎再次使用”后，按任意键系统将自动退出。
2、概要设计
2.1系统功能结构图
2.2系统流程图
开始
创建无向图
写入信息至无向图中
Case1
Case2
Case3
查询路径
查询景点息
T
T
F
F
T
end
F
退出系统
2.3主要函数概要设计
2.3.1主函数概要设计
主函数首先是调用初始化图函数InitGraph（）函数创建一个图，而后调用显示主界面函数显示一个可视化主界面，内容包含本系统LOGO以及景点信息及操作编号的提示信息。
之后，当用户成功输入操作编号后，使用一个switch（）函数，判断用户所需操作，匹配成功后，调用相关函数实现用户所需功能。
2.3.2初始化图函数InitGraph（）
InitGraph（）函数首先使用MyGraph结构体声明一个用于存储图中信息的结构体，而后定义结构体中的景点数量以及路径数量，然后使用循环为景点信息和路径长度赋值，其中赋值景点信息时使用strcpy（）函数将字符串复制给G.siteArray[i].siteName以及G.siteArray[i].siteInfo两个数组。
2.3.3显示主界面函数设计MainGraph（）
MainGraph（）函数主要用于显示主界面，函数中设计了本系统LOGO,同时，界面还提示了景点名称及其对应编号。
主界面下方以列表方式提示用户系统可进行的操作及其对应编号，最后提示用户进行输入。
2.3.4查询景点信息函数设计SearchGraph（）
该函数首先定义了一个变量k（用于接收用户输入的查询编号）和一个标记位flag（初始值设为1），而后使用while（）循环，判断条件为flag=1,当输入编号不合法时提示错误，当输入合法时标记位flag置为0，此时跳出循环，调用MyGraph结构体对应编号的景点信息，以列表方式输出。
2.3.5显示图中信息函数设计ShowGraph（）
ShowGraph（）函数主要功能为用循环将存储于图中的景点信息以列表方式输出，方便用户对应着进行输入，同时提示用户进行输入。
2.3.6弗洛伊德算法函数设计Floyd（）
本算法在设计时参考了《数据结构C语言版》一书中有关Floyd算法的介绍，同时借鉴了如今网上流行的设计方式。
之所以选择本算法来实现计算最短路径，原因在于本算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
但是，本算法缺点在于时间复杂度过高，不适合用于计算大量数据。
Floyd算法首先将两景点间路径长度数据存储于数组D[v][w]中，而后使用一个三维数组用于存放最短路径所经过的顶点，接下来使用三重循环判断两景点之间直接路径是否大于间接路径，若大于，则将三维数组中存放的顶点信息更改为简介路径所经过的顶点信息。
以上部分完成后，当用于标记输入数据是否合法的flag=1时，输出错误信息，提示用户重新输入，当输入数据合法时，输出以上程序得到结果。
3、详细设计
3.1主函数详细设计
#defineInfiniteNum10000//定义一个无穷大数
#defineMaxInfoNum100//定义景点数据最大容量
#include
#include
#include
#include"MyGraph.h"//调用头文件
voidmain（void）
{MGraphg;//创建图
inti;
g=InitGraph（）;//初始化校园地图
MainGraph（&g）;//调用显示主界面函数
scanf（"%d",&i）;
while（i!
=3）
{
switch（i）
{
case1:
ShowGraph（&g）;Floyd（&g）;MainGraph（&g）;break;
case2:
ShowGraph（&g）;SearchGraph（&g）;MainGraph（&g）;break;
case3:
exit（0）;break;
default:
break;
}
scanf（"%d",&i）;
}
printf（"欢迎下次继续使用!
\n\n"）;
}
3.2初始化图函数详细设计InitGraph（）
MGraphInitGraph（void）//初始化图中的信息
{
MGraphG;
inti,j;
G.siteNumber=6;//景点数量
G.pathNumber=8;//路径数量
for（i=1;i<=G.siteNumber;i++）
G.siteArray[i].siteIdentifier=i;//对景点进行对应编号
strcpy（G.siteArray[1].siteName,"一教"）;
strcpy（G.siteArray[1].siteInfo,"最有历史的教学楼"）;
strcpy（G.siteArray[2].siteName,"软件学院"）;
strcpy（G.siteArray[2].siteInfo,"规模庞大，师资雄厚，全校第二大院"）;
strcpy（G.siteArray[3].siteName,"老图书馆"）;
strcpy（G.siteArray[3].siteInfo,"说实话，太破了！
"）;
strcpy（G.siteArray[4].siteName,"校门"）;
strcpy（G.siteArray[4].siteInfo,"有点小家子气，规模太小"）;
strcpy（G.siteArray[5].siteName,"新图书馆"）;
strcpy（G.siteArray[5].siteInfo,"邵逸夫先生捐赠的,设施较为完备,最常去的地方"）;
strcpy（G.siteArray[6].siteName,"南区食堂"）;
strcpy（G.siteArray[6].siteInfo,"价格尚算公道，但卫生状况较为堪忧，已经吃出好几次头发了"）;
for（i=1;i<=G.siteNumber;i++）//使用循环对路径进行赋值，对于没有直接路径的，赋值为无穷大
for（j=1;j<=G.siteNumber;j++）
G.pathArray[i][j].path=InfiniteNum;
G.pathArray[1][2].path=200;
G.pathArray[1][3].path=100;
G.pathArray[1][4].path=400;
G.pathArray[2][4].path=300;
G.pathArray[4][5].path=100;
G.pathArray[4][6].path=500;
G.pathArray[5][6].path=500;
for（i=1;i<=G.siteNumber;i++）//所构造的图为无向图，故相反方向路径相同
for（j=1;j<=G.siteNumber;j++）
G.pathArray[j][i].path=G.pathArray[i][j].path;
returnG;
}
3.3查询景点信息函数详细设计SearchGraph（）
voidSearchGraph（MGraph*G）//用于查询景点信息，以列表方式输出
{
intk,flag=1;
while（flag）
{
printf（"请输入要查询的景点编号:
"）;
scanf（"%d",&k）;
if（k<=0||k>G->siteNumber）//输入景点编号不合法时提示错误
{
printf（"景点编号不存在!
请重新输入景点编号:
"）;
scanf（"%d",&k）;
}
if（k>0&&k<=G->siteNumber）//输入合法时将falg置为0
flag=0;
}
printf（"\n"）;
printf（"编号景点名称简介\n"）;
printf（"%-4d%-16s%-62s\n",G->siteArray[k].siteIdentifier,G->siteArray[k].siteName,G->siteArray[k].siteInfo）;//输出景点信息
}
3.4弗洛伊德算法函数详细设计Floyd（）
voidFloyd（MGraph*G）//使用弗洛伊德算法2求出最短路径
{
intv,u,i,w,k,j;
intflag=1;//用于标记输入数据是否正确，若输入数据符合要求，则将flag置为0
intp[7][7][7],D[7][7];
for（v=1;v<=G->siteNumber;v++）
for（w=1;w<=G->siteNumber;w++）
{
D[v][w]=G->pathArray[v][w].path;//将路径数据存放至数组D[v][w]中
for（u=1;u<=G->siteNumber;u++）
p[v][w][u]=0;//该三维数组用于存放两景点之间是否有直接路径，若有则记为1，无则记为0
if（D[v][w] {
p[v][w][v]=1;p[v][w][w]=1;
}
}
for（u=1;u<=G->siteNumber;u++）
for（v=1;v<=G->siteNumber;v++）
for（w=1;w<=G->siteNumber;w++）
if（D[v][u]+D[u][w] {
D[v][w]=D[v][u]+D[u][w];
for（i=1;i<=G->siteNumber;i++）
p[v][w][i]=p[v][u][i]||p[u][w][i];//获取两点之间路径所经过的景点编号
}
while（flag）
{
printf（"请输入出发点和目的地的编号:
"）;
scanf（"%d%d",&k,&j）;
if（k<=0||k>G->siteNumber||j<=0||j>G->siteNumber）
{
printf（"景点编号不存在!
请重新输入:
"）;
scanf（"%d\n%d",&k,&j）;
}
if（k==j）
{
printf（"出发点和目的地一样!
请重新输入:
"）;
scanf（"%d\n%d",&k,&j）;
}
if（k>0&&k<=G->siteNumber&&j>0&&j<=G->siteNumber）
flag=0;//输入的数据合法，故将flag=0
}
printf（"\n最短游览路线：
%s",G->siteArray[k].siteName）;
if（k>j）{
for（u=G->siteNumber;u>0;u--）
if（p[k][j][u]&&k!
=u&&j!
=u）
printf（"-->%s",G->siteArray[u].siteName）;}
if（k for（u=1;u<=G->siteNumber;u++）
if（p[k][j][u]&&k!
=u&&j!
=u）
printf（"-->%s",G->siteArray[u].siteName）;}
printf（"-->%s",G->siteArray[j].siteName）;
printf（"总路线长%dm\n",D[k][j]）;
}
4、调试分析
4.1显示主界面函数测试
显示主界面函数必须实现提示景点名称及其对应编号，主界面下方以列表方式提示用户系统可进行的操作及其对应编号，最后提示用户进行输入。
经测试结果如下：
4.2查找两景点间最短路径测试
本功能模块要求在按照景点信息列表中提示的信息用户输入起点编号和终点标号后输出最短路径，经测试后该功能能够实现，没有何错误。
测试结果如下图：
输入起点和终点：
输出最短路径：
4.3查看景点信息测试
本功能模块要求在用户输入景点编号后，系统和已存储的景点信息进行配对，如果景点不存在，则提示错误，若景点存在则输出景点信息，经测试，达到了预期效果，且容错处理正常运行。
测试结果如下：
5.课程设计总结
经过这次课程设计，我对程序中算法的概念理解的更加透彻。
算法是程序中必不可少的部分，它是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
同时，在选择算法时必须考虑算法的时间复杂度和空间复杂度，这样才能让程序正常，高效的运行。
在系统设计时也碰到了很多问题，比如在设计InitGraph（）函数时，首先我想到的是使用数组来保存信息，但发现这种设计无法方便的让程序中各个独立算法访问存储的景点信息，编写代码时十分复杂，后来，在出查阅相关书籍和阅读了网上其它相关算法后，我选择了使用结构体数组来保存信息，这种方式顺利地将信息保存到了图中，同时其它函数模块也可以方便的访问这部分信息，达到了我想要实现的功能。
《数据结构》在计算机科学中是一门综合性的专业基础课.数据结构的研究不仅涉及到计算机的硬件（特别是编码理论、存储装置和存取方法等）的研究范围,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据元素在存储器中的分配问题.在研究信息检索时也必须考虑如何组织数据,以便查找和存取数据元素更为方面.因此,可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程.在计算机科学中,数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础,而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。
6、附录
源程序清单：
//以下保存在头文件“MyGraph.h”中
typedefstruct//定义用于存放权值的结构体
{
intpath;//路径长度
}ArCell,AdjMatrix[MaxInfoNum][MaxInfoNum];
typedefstruct
{
charsiteName[30];//用于存放景点名称
intsiteIdentifier;//用于存放景点编号
charsiteInfo[200];//用于存放景点信息
}infoType;
typedefstruct
{
infoTypesiteArray[MaxInfoNum];//景点数组,用于存放景点名及景点信息
AdjMatrixpathArray;//路径数组
intsiteNumber;//景点数量
intpathNumber;//路径总数量
}MGraph;
MGraphInitGraph（void）//初始化图中的信息
{
MGraphG;
inti,j;
G.siteNumber=6;//景点数量
G.pathNumber=8;//路径数量
for（i=1;i<=G.siteNumber;i++）
G.siteArray[i].siteIdentifier=i;//对景点进行对应编号
strcpy（G.siteArray[1].siteName,"一教"）;
strcpy（G.siteArray[1].siteInfo,"最有历史的教学楼"）;
strcpy（G.siteArray[2].siteName,"软件学院"）;
strcpy（G.siteArray[2].siteInfo,"规模庞大，师资雄厚，全校第二大院"）;
strcpy（G.siteArray[3].siteName,"老图书馆"）;
strcpy（G.siteArray[3].siteInfo,"说实话，太破了！
"）;
strcpy（G.siteArray[4].siteName,"校门"）;
strcpy（G.siteArray[4].siteInfo,"有点小家子气，规模太小"）;
strcpy（G.siteArray[5].siteName,"新图书馆"）;
strcpy（G.siteArray[5].siteInfo,"邵逸夫先生捐赠的,设施较为完备,最常去的地方"）;
strcpy（G.siteArray[6].siteName,"南区食堂"）;
strcpy（G.siteArray[6].siteInfo,"价格尚算公道，但卫生状况较为堪忧，已经吃出好几次头发了"）;
for（i=1;i<=G.siteNumber;i++）//使用循环对路径进行赋值，对于没有直接路径的，赋值为无穷大
for（j=1;j<=G.siteNumber;j++）
G.pathArray[I][j].path=Infinite;
G.pathArray[1][2].path=200;
G.pathArray[1][3].path=100;
G.pathArray[1][4].path=400;
G.pathArray[2][4].path=300;
G.pathArray[4][5].path=100;
G.pathArray[4][6].path=500;
G.pathArray[5][6].path=500;
for（I=1;i<=G.siteNumber;i++）//所构造的图为无向图，故相反方向路径相同
for（j=1;j<=G.siteNumber;j++）
G.pathArray[j][i].path=G.pathArray[i][j].path;
returnG;
}
voidFloyd（MGraph*G）
升级会员 