目录
1、需求分析 ................................. 错误!未定义书签。
2、设计思路 ................................. 错误!未定义书签。
3、算法设计 .................................................................. 1
3.1 概要设计 ............................................................ 1
3.1.1 程序中包含的模块 ..................................... 1
3.1.2 模块间的调用关系 ..................................... 2
3.2 详细设计 ............................................................ 2
4、测试分析 .................................................................. 9
4.1 主程序界面 .................................................... 9
4.2 景点信息的查询 .......................................... 10
4.3 最短路径查询 ...............................................11
5、总结 .........................................................................11
6、参考文献 ................................................................ 12
7、附录 ........................................................................ 12
1、需求分析
设计一个校园导游系统程序,为来访的客人提供各种服务的信息查询。
(1).设计潍坊学院校园平面图,所含的景点不少于10个。以图中顶点表示校内各
景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关
信息。
(2).为来访客人提供图中任意景点相关信息的查询。
(3).为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条
最短的简单路径。
2、设计思路
校园旅游模型是由景点和景点之间的路径组成的,所以这完全可以用数据结
构中的图来模拟。用图的结点代表景点,用图的边代表景点之间的路径。所以首
先应设计一个图类。结点值代表景点信息,边的权值代表景点间的距离。结点值
及边的权值用顺序表存储,所以需要设计一个顺序表类。本系统需要查询景点信
息和求一个景点到另一个景点的最短路径长度及路线,为方便操作,所以给每个
景点一个代码,用结构体类型实现。计算路径长度和最短路线时可用弗洛伊德
(Floyd )算法实现。最后用switch 选择语句选择执行浏览景点信息或查询最短
路径。
3 算法设计
3.1 概要设计
3.1.1 程序中包含的模块
(1)主程序模块
主函数:void main()
打印菜单,景点,景点信息
(2)查询模块
景点信息查询:void introduce()
最短路径查询:
要查找的两景点的最短距离:int shortestdistance()
用floyd 算法求两个景点的最短路径:void floyd()
(3)打印模块
打印两个景点的路径及最短距离:void display(int i,int j)
3.1.2模块间的调用关系
主函数main()调用:
void introduce()/*景点介绍*/
int shortestdistance()/*要查找的两景点的最短距离*/
shorestdistance()调用:
void floyd()/*用floyd 算法求两个景点的最短路径*/
void display(int i,int j) /* 打印两个景点的路径及最短距离
*/
3.2 详细设计
/*定义符号变量/*
#define INT_MAX 10000
#define n 10
/*定义全局变量*/
int cost[n][n];
/* 边的值*/ /* 两点间的最短距离*/ /* 经过的景点*/ /*景点名称*/ /*景点介绍*/ int shortest[n][n]; int path[n][n]; string M[100]; string J[100];
/*自定义函数原型说明*/
void introduce();
int shortestdistance();
void floyd();
void display(int i,int j);
定义各顶点之间的距离:
for(i=0;i
for(j=0;j
cost[i][j]=INT_MAX;
cost[1][2]=cost[2][1]=3;
cost[2][3]=cost[3][2]=1;
cost[3][4]=cost[4][3]=2;
cost[4][5]=cost[5][4]=1;
cost[5][6]=cost[6][5]=1;
cost[3][6]=cost[6][3]=2;
cost[1][4]=cost[4][1]=5;
cost[1][7]=cost[7][1]=7;
cost[4][7]=cost[7][4]=1;
cost[7][5]=cost[5][7]=1;
cost[7][8]=cost[8][7]=2;
cost[8][9]=cost[9][8]=1;
cost[5][9]=cost[9][5]=2;
cost[8][5]=cost[5][8]=2;
cost[8][10]=cost[10][8]=1;
cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;
cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;
界面菜单设计:
while(1)
{
printf("-------------------欢迎使用校园导游系统!-------------------\n");
printf(" 欢迎来到潍坊学院! 祝您旅途愉快!
\n");
printf(" 菜单选择 \n");
printf("1.景点信息查询\n");
printf("2.景点最短路径查询\n");
printf("3.退出系统\n\n");
printf(" 学校景点列表(以下是您可能要去的地方):\n");
printf("1:潍坊学院大门 ");
printf("2:行政楼 ");
printf("3:餐厅 ");
printf("4:实验楼 ");
printf("5:图书馆\n");
printf("6:商业区 ");
printf("7:教学楼 ");
printf("8:篮球场 ");
printf("9:体育馆 ");
printf("10:弘德湖 \n");
printf("-----------------------------------------------------------\n");
printf("请选择服务:");
scanf("\n%c",&k);
switch(k)
{
case '1':
printf("进入景点信息查询:");
introduce();
break;
case '2':
printf("进入最短路径查询:");
shortestdistance();
break;
case '3':
printf("谢谢使用本系统!\n");
exit(0);
default:
printf("输入信息错误!\n请输入字母1或2或3.\n");
break;
}
}
介绍景点:
void introduce()
{
int a;
printf("您想查询哪个景点的详细信息?\n请输入景点编号:");
scanf("%d",&a);
getchar();
printf("\n");
switch(a)
{
case 1:
printf("1:学校大门\n\n 学校的正门,气势宏伟。\n\n");break; case 2:
printf("2:行政楼\n\n 学校的行政中心。\n\n");break;
case 3:
printf("3:餐厅\n\n 很贵,很难吃,很不实惠。\n\n");break;
case 4:
printf("4:实验楼\n\n 计算机机房及各种实验设施。\n\n");break; case 5:
printf("5:图书馆\n\n 学校信息资源中心。\n\n");break;
case 6:
printf("6:商业区\n\n 生活必需品,学习用品的天地。\n\n");break; case 7:
printf("7:教学楼\n\n 全校学生公共教学楼。\n\n");break;
case 8:
printf("8:篮球场\n\n 篮球健儿的摇篮。\n\n");break;
case 9:
printf("9:体育馆\n\n 为全运会而建,平时不让进。\n\n\n");break; case 10:
printf("10:弘德湖\n\n 美丽校园的缩影,游校园必去之地。\n\n");break; default:
printf("景点编号输入错误!\n请输入1->10的数字编号!\n\n"); break; }
}
要查找的两个景点的最短距离:
int shortestdistance()
{
int i,j;
printf("请输入要查询的两个景点的编号(1->10的数字编号并用',' 间隔):\n"); scanf("%d,%d",&i,&j);
if(i>n||in||j
{
printf("输入信息错误!\n\n");
printf(" 请输入要查询的两个景点的编号(1->10的数字编号并用',' 间隔):\n");
scanf("%d,%d",&i,&j);
floyd();
display(i,j);
}
else
{
floyd();
display(i,j);
return 1;
}
用floyd 算法求两个景点的最短路径:
void floyd()
{
int i,j,k;
for(i=1;i
for(j=1;j
{
shortest[i][j]=cost[i][j];
path[i][j]=0;
}
for(k=1;k
for(i=1;i
for(j=1;j
if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
{
/*用path[][]记录从i 到j 的最短路径上点j 的前驱景点的序号*/ shortest[i][j]=shortest[i][k]+shortest[k][j];
path[i][j]=k;
path[j][i]=k;
}
}
打印两个景点的路径及最短距离:
void display(int i,int j)
{
/* 打印两个景点的路径及最短距离 */
int a,b;
b=j;
printf("您要查询的两景点间最短路径是:\n\n");
if(shortest[i][j]!=INT_MAX)
{
if(i
{
printf("%d",b);
while(path[i][j]!=0)
{
/* 把i 到j 的路径上所有经过的景点按逆序打印出来*/ printf("
if(i
j=path[i][j];
else
i=path[j][i];
}
printf("
printf("\n\n");
printf("(%d->%d)最短距离是:%d百米\n\n",a,b,shortest[a][b]); }
else
{
printf("%d",a);
while(path[i][j]!=0)
{
/* 把i 到j 的路径上所有经过的景点按顺序打印出来*/ printf("->%d",path[i][j]);
if(i
j=path[i][j];
else
i=path[j][i];
}
printf("->%d",b);
printf("\n\n");
printf("(%d->%d)最短距离是:%d百米\n\n",a,b,shortest[a][b]); }
}
else
printf("输入错误!不存在此路!\n\n");
printf("\n");
}
4 测试分析
4.1 主程序界面
图1. 主程序界面
4.2 景点信息的查询
图2. 景点信息的查询
4.3 最短路径查询
图3. 景点最短路径查询
5 总结
经过近两周的课程设计,总的来说收获还是很大的!
首先代码能力明显提高,有了想法基本都能顺利表达出来;再者就是数据结构的选择使用能力也有了很大的提高!虽说平时的试验课我们也有用各种数据做题,但那些都是很明确的知道该做什么操作,存什么,我们的发挥空间不大一般照做就行,然而这次实习我们却在自主的选择判断,这本身就是一个很大的提高!还有就是算法方面的学习有了初步进阶,如最短路径,这样比较简单的图论算法能比较熟练的写出来。但是还是有很多的只是不了解!
收获真的很多,但是最大的收获可能就是对编程的兴趣吧,在一次次的改错,一次次的完成想要的效果后,越写越有感觉!当然还收获了无知,更确切的说是自知,原来我们现在什么也不算,还有很多有用的只是等着我们去学习!
6 参考文献
【1】 蔡明志,《数据结构---用C 语言描述》,中国水利水电出版社
【2】 李春葆,喻丹丹,《数据结构 习题与解析》,清华大学出版社
【3】 邓文华,戴大蒙,《数据结构试验与实训教程》,清华大学出版社
7 附录
文件名清单:
liuhaijiang.cpp