当前位置:天才代写 > C++/C代写 > 校园导游模拟程序的设计

校园导游模拟程序的设计

2017-09-08 08:00 星期五 所属: C++/C代写 浏览:65

程序设计实训:校园导游模拟程序的设计

 

1) 问题描述:

设计一个校园导游程序,为来访的客人提供住处查询服务。

选取苦干(多于10个)个有代表性的景点抽象成一个无向带权图,以图中顶点表示校内景点,边上的权值表示两景点间的距离。

2) 具体功能要求:

按菜单项管理的主界面

菜单项及功能要求如下

1) 学校景点介绍:由一个子函数实现,输出学校全部景点的信息,包括景点编号、名称及简介。

2) 查看浏览路线:根据用户输入的起始景点编号,求出从该景点到其他景点的最短路径线路及距离,要求用DIJKSTRA算法完成。

3) 查询景点间最短路径:两个景点间的最短路径,要求用FLOYD算法完成。

4) 景点信息查询:根据用户输入的编号,输出其相关信息。

5) 更改基本信息:新增景点,删除边,重建图等。

6) 查询景点间可行路径:显示所有符合长度限制(如路径长度不大于5)的所有路径。(可选做)

7) 打印图

8) 退出

 

本附录中为程序运行时的效果说明。

 

实训报告格式及要求:

封面:

程序设计实训报告

(分组成员名单(姓名学号) 和分工)

内容:

 

一、 题目

校园导游程序  (3)

3) 问题描述:

设计一个校园导游程序,为来访的客人提供住处查询服务。

选取苦干(多于10个)个有代表性的景点抽象成一个无向带权图,以图中顶点表示校内景点,边上的权值表示两景点间的距离。

4) 具体功能要求:

按菜单项管理的主界面

菜单项及功能要求如下

9) 学校景点介绍:由一个子函数实现,输出学校全部景点的信息,包括景点编号、名称及简介。

10) 查看浏览路线:根据用户输入的起始景点编号,求出从该景点到其他景点的最短路径线路及距离,要求用DIJKSTRA算法完成。

11) 查询景点间最短路径:两个景点间的最短路径,要求用FLOYD算法完成。

12) 景点信息查询:根据用户输入的编号,输出其相关信息。

13) 更改基本信息:新增景点,删除边,重建图等。

14) 查询景点间可行路径:显示所有符合长度限制(如路径长度不大于5)的所有路径。(可选做)

15) 打印图

16) 退出

 

二、 需求分析

学校旅游成最近热门的话题,比如“清华大学”旅游,等等,让更多的同学,老师或者外校人员来本校访问,可以很容易的在学校参观等,为了让大家不会迷路,可以更轻松自如的对学校进行参观,故设计此小型学校导航系统。

 

三、 概要设计(存储结构设计,自定义函数介绍,系统框架图)

 

 

 

在查询景点间最短路径时运用了迪杰斯特算法,查询景点间所有路径则是运用了佛罗算法来实现的。定义了一个结构体作为一个存储信息的无向图。

typedef struct //景点信息存储

Status ViewInfo(int cost[MAXSIZE][MAXSIZE]) //景点路径长度

void floyed()/*floyed算法求两个景点的最短路径*/

void display(int i,int j)/* 打印两个景点的路径及最短距离 */

void DFS(int k,int v1,int t,int cost[MAXSIZE][MAXSIZE])  

{//k为当前景点编号,v1为终点编号,t为当前已经找到的以k为终点的路径上景点的个数

Status Allpath(int cost[MAXSIZE][MAXSIZE],int v0,int v1) //两点间的所有路径

Status ShowAll(Graph p[MAXSIZE]) //显示所有信息

Status IntroduceView(Graph p[MAXSIZE]) //查询景点信息

Status DeleteView(Graph p[MAXSIZE],int cost[MAXSIZE][MAXSIZE])//删除景点,n为现有景点的个数

Status UpdateUiew(Graph p[MAXSIZE]) //更新景点信息

Status UpdatePath(int cost[MAXSIZE][MAXSIZE]) //更新道路

void main()

{/*主函数*/

 

 

 

 

 

四、 详细设计及测试结论(算法的设计,测试遇到的问题,原因及解决办法)

用到了迪杰斯特算法和佛罗算法对路径最短进行优化,其中还加入了深度优先算法。

遇到的问题:总是报错,可是又很难找到出错的地方。这是对整个结构和思路的不清晰,最后多处因为一些很小的细节,比如符号,还有函数变量等等。。

 

 

 

五、 总结

附录:程序详细清单及测试图例。

 

/*

问题描述:

设计一个校园导游程序,为来访的客人提供住处查询服务。

选取苦干(多于10个)个有代表性的景点抽象成一个无向带权图,以图中顶点表示校内景点,边上的权值表示两景点间的距离。

2)具体功能要求:

按菜单项管理的主界面

菜单项及功能要求如下

1)学校景点介绍:由一个子函数实现,输出学校全部景点的信息,包括景点编号、名称及简介。

2)查看浏览路线:根据用户输入的起始景点编号,求出从该景点到其他景点的最短路径线路及距离,要求用DIJKSTRA算法完成。

3)查询景点间最短路径:两个景点间的最短路径,要求用FLOYD算法完成。

4)景点信息查询:根据用户输入的编号,输出其相关信息。

5)更改基本信息:新增景点,删除边,重建图等。

6)查询景点间可行路径:显示所有符合长度限制(如路径长度不大于5)的所有路径。(可选做)

7)打印图

8)退出

*/

  

/*包含头文件*/

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

 

/*定义符号常量*/

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define MAXSIZE 50

#define INT_MAX 1000000

 

typedef int Status;

int cost[MAXSIZE][MAXSIZE];/* 边的值*/

int shortest[MAXSIZE][MAXSIZE];/* 两点间的最短距离*/

int path[MAXSIZE][MAXSIZE];/* 经过的景点*/

int T[MAXSIZE];

int n;

bool Visit[MAXSIZE];//访问标志数组

 

/*自定义函数原型说明*/

void introduce();

int shortestdistance();

void floyed();

void display(int i,int j);

 

typedef struct //景点信息存储

{

int  num;//景点编号

char name[40];//景点名称

char info[100];//景点信息

}Graph;

 

Status ViewInfo(int cost[MAXSIZE][MAXSIZE]) //景点路径长度

{

int i,j;

                                         

for(i=0;i<=MAXSIZE;i++) //给各景点之间的路径赋上最大值

{

for(j=0;j<=MAXSIZE;j++)

{

if(i==j)

cost[i][j]=0;

else

cost[i][j]=INT_MAX;

 

}

}

cost[1][2]=cost[2][1]=250;

cost[2][3]=cost[3][2]=160;

cost[2][4]=cost[4][2]=200;

cost[3][4]=cost[4][3]=110;

cost[1][4]=cost[4][1]=400;

cost[2][5]=cost[5][2]=300;

cost[5][10]=cost[10][5]=100;

cost[5][6]=cost[6][5]=260;

cost[6][7]=cost[7][6]=100;

cost[7][8]=cost[8][7]=360;

cost[7][9]=cost[9][7]=270;

cost[8][9]=cost[9][8]=450;

return OK;

}

 

void floyed()/*floyed算法求两个景点的最短路径*/

{

int i,j,k;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

shortest[i][j]=cost[i][j];

path[i][j]=0; //初始化

}

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

               for(j=1;j<=n;j++)

if(shortest[i][j]>shortest[i][k]+shortest[k][j])

 

{/*path[][]记录从ij的最短路径上点j的前驱景点的序号*/

shortest[i][j]=shortest[i][k]+shortest[k][j];

path[i][j]=k;

path[j][i]=k;

}

}/*floyed*/

 

void display(int i,int j)/* 打印两个景点的路径及最短距离 */

{

int a,b;

a=i;

b=j;

printf("您要查询的两景点间最短路径是:\n\n");

if(shortest[i][j]!=INT_MAX)

{

if(i<j)

{

printf("%d",b);

while(path[i][j]!=0)//i,j之间有最短路径时

{/* ij的路径上所有经过的景点按逆序打印出来*/

printf("<–%d",path[i][j]);

if(i<j)

j=path[i][j];

else

i=path[j][i];

}

printf("<–%d",a);

printf("\n\n");

printf("(%d->%d)最短距离是:%d\n\n",a,b,shortest[a][b]);

}

else

{

printf("%d",a);

while(path[i][j]!=0)

{/* ij的路径上所有经过的景点按顺序打印出来*/

printf("–>%d",path[i][j]);

if(i<j)

j=path[i][j];

else

i=path[j][i];

}

printf("–>%d",b);

printf("\n\n");

printf("(%d–>%d)最短距离是:%5d\n\n",a,b,shortest[a][b]);

}

}

else

printf("输入错误!不存在此路!\n\n");

printf("\n");

}/*display*/

 

 

int shortestdistance()

{/*要查找的两景点的最短距离*/

int i,j;

printf("请输入要查询的两个景点的编号并用','间隔):");

scanf("%d,%d",&i,&j);

if(i>n||i<=0||j>n||j<0)

{

printf("输入信息错误!\n\n");

printf("  请输入要查询的两个景点的编号并用','间隔):\n");

scanf("%d,%d",&i,&j);

}

else

{

floyed();   /*floyed算法求两个景点的最短路径*/

display(i,j);   /* 打印两个景点的路径及最短距离 */

}

return 1;

}/*shortestdistance*/

 

 

void DFS(int k,int v1,int t,int cost[MAXSIZE][MAXSIZE])  

{//k为当前景点编号,v1为终点编号,t为当前已经找到的以k为终点的路径上景点的个数

int i;

if(k==v1)//当前景点即为终点

{

for(int j=1;j<t;j++)

printf("%d–>",T[j]);

printf("%d\n",T[t]);

return ;

}

for(i=1;i<=n;i++)

if(!Visit[i]&&cost[k][i]<INT_MAX)//ik的邻接点

{

Visit[i]=true;

T[t+1]=i;           //i为路径上的第t+1个景点

DFS(i,v1,t+1,cost); //递归调用

Visit[i]=false;//释放

}

}

 

Status Allpath(int cost[MAXSIZE][MAXSIZE],int v0,int v1) //两点间的所有路径

{

int i;

 

if(v0==v1)

{

printf("输入有错,两点为同一点!\n");

return ERROR;

}

 

for(i=1;i<=n;i++)

Visit[i]=false;//初始化

Visit[v0]=true;

T[1]=v0;

DFS(v0,v1,1,cost);

return OK;

}

 

Status ShowAll(Graph p[MAXSIZE]) //显示所有信息

{

int i;

 

for(i=1;i<=n;i++)

{

printf("%-4d    ",p[i].num);

printf("%-20s    ",p[i].name);

printf("%-80s\n",p[i].info);

}

return OK;

}

 

 

 

Status IntroduceView(Graph p[MAXSIZE]) //查询景点信息

{

int t;

 

printf("请输入要查询景点的编号:");

scanf("%d",&t);

 

while(t<0||t>=n)

{

printf("您输入的景点不存在,请重新输入:");

scanf("%d",&t);

}

 

printf("%d    ",p[t].num);

printf("%s    ",p[t].name);

printf("%s\n",p[t].info);

return OK;

}

 

 

 

Status InsertView(Graph p[MAXSIZE],int cost[MAXSIZE][MAXSIZE])

{//n为导游图中已含景点个数  插入景点

int j,t;

p[n+1].num=n+1;

printf("请输入新增景点的名称:");

scanf("%s",&p[n+1].name);

printf("请输入新增景点的信息:");

scanf("%s",&p[n+1].info);

 

printf("输入与%d存在路径的景点编号及路径长度(以'0'结束)\n",n+1);

scanf("%d",&j);

while(j!=0)

{

scanf("%d",&t);

cost[n+1][j]=t;

cost[j][n+1]=t;

scanf("%d",&j);

}

n++;

return OK;

}

 

Status DeleteView(Graph p[MAXSIZE],int cost[MAXSIZE][MAXSIZE])//删除景点,n为现有景点的个数

{

int t,i,j;

 

printf("请输入要删除的景点编号:(1~%d)",n);

scanf("%d",&t);

if(t<0||t>n)

{

printf("该景点已经不存在!");

return OK;

}

for(i=t+1;i<=n;i++) //将删除的景点后面的景点向前移

{

p[i-1].num=i-1;

strcpy(p[i-1].name,p[i].name);

strcpy(p[i-1].info,p[i].info);

}

for(i=t+1;i<=n;i++)//改变删除的景点后面的景点与其余景点之间的道路长度

{

for(j=1;j<=n;j++)

cost[i-1][j]=cost[i][j];

}

for(i=1;i<=n;i++)

{

for(j=t+1;j<=n;j++)

cost[i][j-1]=cost[i][j];

}

n–;

return OK;

}

 

Status UpdateUiew(Graph p[MAXSIZE]) //更新景点信息

{

int t;

 

printf("请输入要更新景点的编号:");

scanf("%d",&t);

 

if(t<1||t>n)

{

printf("该景点不存在,无法更新!\n");

return OK;

}

 

printf("%d    ",p[t].num);

printf("%s    ",p[t].name);

printf("%s\n",p[t].info);

 

printf("请输入更新后景点的名称:");

scanf("%s",&p[t].name);

printf("请输入更新后景点的信息:");

scanf("%s",&p[t].info);

return OK;

}

 

 

Status UpdatePath(int cost[MAXSIZE][MAXSIZE]) //更新道路

{

int t,v1,v2;

 

printf("请输入要更新道路两端景点的编号并用','间隔:");

scanf("%d,%d",&v1,&v2);

 

while(v1==v2)

{

printf("两顶点为同一个顶点,请重新输入:");

scanf("%d%d",&v1,&v2);

}

 

printf("请输入道路更新后的长度:");

scanf("%d",&t);

cost[v1][v2]=t;

cost[v2][v1]=t;

return OK;

}

 

 

void main()

{/*主函数*/

Graph p[MAXSIZE]={{0,"",""},

{1,"北门", "330公交车附近"},

{2,"红楼","儿童研究中心,有5L"},

{3,"精业楼","行知学院教学大楼,9L"},

{4,"初阳湖","人造湖很漂亮"},

{5,"杏园食堂","东西一般好吃"},

{6,"艺术大楼","艺术生的圣地"},

{7,"大学生活动中心","大学生陶冶情操的地方"},

{8,"图文信息中心","豪华图书馆在学校大门附近"},

{9,"体育馆","学校体育馆,运动健儿的圣地"},

{10,"学校正大门","一楼为快餐 二楼为自助餐 三楼是乒乓球馆."},

};

char k;

int v0,v1;

n=10;

    ViewInfo(cost);

printf("—————-欢迎使用浙江师范导游系统!———————————–\n");

printf("1.景点信息查询…………请按 i (introduce)\n");

printf("2.景点间最短路径查询…请按 s (shortestdistance)\n");

printf("3.查看浏览路线…请按 w (wholedistance)\n");

printf("4.增加景点信息…………请按 a (add)\n");

printf("5.删除景点信息…………请按 d (delete)\n");

printf("6.更新景点及道路信息…请按 u (update)\n");

printf("7.显示所有景点信息……请按 p (print)\n");

printf("8.退出系统………………请按 e (exit)\n");

printf("学校景点列表:\n");

printf("》》");

printf("|1:北门|2:红楼|3:精业楼|4:初阳湖 |");

printf("|5:杏园食堂|6:艺术大楼 |7:大学生活动中心|8:图文信息中心|");

printf("|9: 体育馆|10:学校正大门|");

printf("》》");

       while(1)

{

printf("\n请选择服务:");

scanf("\n%c",&k);

switch(k)

{

case 'i':

 

printf("进入景点信息查询:");

IntroduceView(p);

break;

 

case 's':

 

printf("进入最短路径查询:");

shortestdistance();

break;

 

case 'w':

 

printf("进入所有路径查询:");

printf("请输入要查询的两个景点的编号并用','间隔");

    scanf("%d,%d",&v0,&v1);

    Allpath(cost,v0,v1);

      break;

 

case 'a':

 

printf("增加景点信息:");

InsertView(p,cost);

    break;

 

case 'd':

 

printf("删除景点信息");

DeleteView(p,cost);

    break;

 

case 'u':

 

printf("更新景点信息:");

UpdateUiew(p);  

UpdatePath(cost);

    break;

 

case 'p':

 

printf("显示所有景点信息:\n");

ShowAll(p);

break;

 

case 'e':

 

printf("退出系统!");

exit(0);

 

default:

 

printf("输入信息错误!\n请输入正确的字母来选择服务.\n");

break;

}

}

}/*main*/

 

测试图片

 

 

 

 

 

 

 

 

    关键字:


天才代写-代写联系方式