完美升级版校园导航系统数据结构毕业论文报告书Word文件下载.docx
《完美升级版校园导航系统数据结构毕业论文报告书Word文件下载.docx》由会员分享，可在线阅读，更多相关《完美升级版校园导航系统数据结构毕业论文报告书Word文件下载.docx（21页珍藏版）》请在冰点文库上搜索。
4设计内容
4.1需求分析
1．程序所能达到的功能：
（1）map——输出山东科技大学平面图。
（2）init（）——按相应编号输入各个节点内容，对相应路径赋值的函数。
（3）floyd（）----弗洛伊德求最短路径
（4）information（）——输出简介的函数
（5）Path（）——最短路径的输出函数
（6）shortestpath（）——调用弗洛伊德和最短路径输出的函数
（7）main（）——主函数
2．输入的形式和输入值的范围：
输入数字和字母：
字母：
以s查询最短路径；
以i查询信息；
以e退出程序。
数字：
从1到9输入。
3．输出的形式：
从A到B得最短路径为：
A-到-C-到-D-到-B
最短距离为：
xxx米。
4．测试数据包括在正确的输入及输出结果及含有错误的输入及输出结果：
Input：
s
Output:
Pleaseenterthenumbertwotoquery:
17
Output：
TheshortestpathfromAreaCdormitorybuildingtolibraryis:
AreaCdormitorybuilding--AreaCrestaurant--library;
Theshortestdistanceis:
150meters.
i
Pleaseenterthenumberofquerysite:
3
@name:
AreaBdormitorybuilding
@introduction:
AreaBstudentrestarea
input：
e
output：
Thankyouforyouuse
4.2总体设计
1．抽象数据类型定义
typedefstruct
{
charname[100];
intnumber;
charintroduce[100];
}Vertex;
2．主程序模块的整体流程
1、进入主函数，调用init（），map（）。
2、选择“s”，调用shortestpath函数，并同时调用floyd和way函数。
3、选择“i”，调用information函数
4、选择“e”，退出。
3.各模块调用关系如下：
4.3详细设计
1.有向网节点结构体类型定义：
2.主程序和其它主要函数伪码算法
1）主程序
intmain（）
chari;
printf（"
Welcometousetheshandonguniversityofscienceandtechnologyofnavigationsystem\n\n\n\n"
）;
init（）;
map（）;
charc;
do
{
printf（"
Pleaseenterthe'
s'
toquerytheshortestpath\n"
i'
toqueryinformation\n"
Pleaseinput'
e'
toexittheprogram\n\n\n"
loop:
scanf（"
%c"
&
c）;
if（c>
='
A'
&
&
c<
Z'
）
{
c+=32;
}
if（c=='
\n'
gotoloop;
}
if（c!
shortestpath（）;
continue;
elseif（c=='
{
Information（）;
\n\n\n\t\t\t\tThankyouforyouuse\n\n\n"
return0;
else
inputerror!
!
\n"
}while
（1）;
}
2）赋值init函数
voidinit（）
inti,j;
vertex[1].number=1;
strcpy（vertex[1].name,"
AreaCdormitorybuilding"
strcpy（vertex[1].introduce,"
AreaCstudentrestarea"
vertex[2].number=2;
strcpy（vertex[2].name,"
AreaAdormitorybuilding"
strcpy（vertex[2].introduce,"
AreaAstudentrestarea"
vertex[3].number=3;
strcpy（vertex[3].name,"
AreaBdormitorybuilding"
strcpy（vertex[3].introduce,"
AreaBstudentrestarea"
vertex[4].number=4;
strcpy（vertex[4].name,"
AreaCrestaurant"
strcpy（vertex[4].introduce,"
AreaCstudentdiningarea"
vertex[5].number=5;
strcpy（vertex[5].name,"
AreaArestaurant"
strcpy（vertex[5].introduce,"
AreaAstudentdiningarea"
vertex[6].number=6;
strcpy（vertex[6].name,"
AreaBrestaurant"
strcpy（vertex[6].introduce,"
AreaBstudentdiningarea"
vertex[7].number=7;
strcpy（vertex[7].name,"
library"
strcpy（vertex[7].introduce,"
Studentborrowingbooksarea"
*vertex[7].number=8;
*
vertex[8].number=8;
strcpy（vertex[8].name,"
No.1teachingbuilding"
strcpy（vertex[8].introduce,"
Studentsinclassarea"
vertex[9].number=9;
strcpy（vertex[9].name,"
No.13teachingbuilding"
strcpy（vertex[9].introduce,"
Informationinstitute,collegebuilding"
for（i=1;
i<
MAX_VERTEX_NUM;
++i）
for（j=1;
j<
++j）
dist[i][j]=INFINITY;
dist[i][i]=0;
dist[1][2]=dist[2][1]=20;
dist[2][3]=dist[3][2]=40;
dist[1][4]=dist[4][1]=50;
dist[2][5]=dist[5][2]=30;
dist[3][6]=dist[6][3]=50;
dist[4][5]=dist[5][4]=70;
dist[5][6]=dist[6][5]=90;
dist[4][7]=dist[7][4]=100;
dist[5][8]=dist[8][5]=120;
dist[6][9]=dist[9][6]=80;
dist[7][8]=dist[8][7]=60;
dist[8][9]=dist[9][8]=120;
3）输出山东科技大学平面图的map函数
voidmap（）
thescienceandtechnologyofShandonguniversitymap\n"
\n\n"
（1）AreaCdormitorybuilding---
（2）AreaAdormitorybuilding---（3）AreaBdormitorybuilding\n"
|||\n"
（4）AreaCrestaurant------（5）AreaAprintf（"
\n\n\n"
4）输出地点信息的information函数
voidInformation（）
while
（1）
"
scanf（"
%d"
number）;
if（number<
MAX_VERTEX_NUM&
number>
0）
return;
else
printf（"
5）最短路径floyd函数
voidfloyd（）*弗洛伊德算法*
inti,j,u;
shortest[i][j]=dist[i][j];
path[i][j]=0;
for（u=1;
u<
++u）
for（i=1;
for（j=1;
{
if（shortest[i][j]>
（shortest[i][u]+shortest[u][j]））
{
shortest[i][j]=shortest[i][u]+shortest[u][j];
path[i][j]=path[j][i]=u;
}
}
6）输出路径Path算法
voidPath（inti,intj）*最短路径的输出*
intu=0;
inta,b;
a=i;
b=j;
if（shortest[i][j]!
=INFINITY）
\nTheshortestpathfrom%sto%sis:
vertex[i].name,vertex[j].name）;
%s"
vertex[i].name）;
while（path[i][j]!
=0）
u=path[i][j];
while（path[i][u]!
u=path[i][u];
--%s"
vertex[u].name）;
i=u;
--%s;
vertex[j].name）;
\nTheshortestdistanceis:
%dmeters.\n"
shortest[a][b]）;
7）调用floyd和Path的最短路径shortestpath算法
voidshortestpath（）
%d%d"
&
i,&
j）;
if（i>
0&
j>
MAX_VERTEX_NUM）
floyd（）;
==========\n"
Path（i,j）;
3.函数的调用关系
4.4测试与分析
4.4.1测试
1）打开程序后，出现我校平面图和菜单选项，如图所示
2）
2）选“i”，查询对应地点的信息，如输入“3”，而后会继续输出菜单，如图所示
3）选“s”，查询两点之间的信息，如输入“17”，而后会继续输出菜单，如图所示
4）选“e”，推出程序，如图所示
4.4.2分析
1.本次作业的核心是利用弗洛伊德算法计算给定图中两点最短距离；
给出图中所要求点的信息。
在调试过程中，除了简单语法错误外，就是对弗洛伊德算法的理解和实现，以及菜单的设置，这是我以前没有实现过的。
出于简单化，并没有对有向图中各个点进行输入，而是在程序中直接赋值。
2.在对各个功能操作的实现上，由于有弗洛伊德算法时间复杂度大多数是O（n3），空间上增加了二维数组，空间复杂度为O（n+s）。
4.5附录
Map."
restaurant\n"
building\n"
（shortest[i][u]+shortest[u][j]）
升级会员 