校园导航系统--2012

一、 问题描述及基本要求

【问题描述】

设计一个校园导游程序，为来访的客人提供各种信息查询服务。

【基本要求】

（1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

（3）为来访客人提供图中任意景点相关信息的查询。

【测试数据】

由读者根据实际情况指定。

【实现提示】

一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。

二、数据结构

（1）typedef struct VData

{

int num;

char name[20];

char jieshao[100];

}VData;

（2）typedef struct ANode

{

int adj;

}ANode;

（3）typedef struct

{

VData vertex[maxnum];

ANode arcs[maxnum][maxnum];

int vexnum,arcnum;

}AdjM;

三、重点设计及代码

（1）两个景点之间的全部路径

void DFS_path(AdjM g, int m,int n,int k)

{

int s;

if(pre[k]==n && k<11)

{

for(s=0;s

printf("% ->",[pre[s]].name);

printf("%s",[pre[s]].name); ，此时s==k)

printf("nn");

}

else

{

s=0;

while(s<) {

if(([pre[k]][s].adj

{

visited[s]=1;

pre[k+1]=s;

DFS_path(g,m,n,k+1);

visited[s]=0;

}

s++;

}

}

}

void all_path(AdjM g)

{

int i,m,n;

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

scanf("%d %d",&m,&n);

printf("nn");

pre[0]=m;

for(i=0;i<;i++)

visited[i]=0;

visited[m]=1;

DFS_path(g,m,n,0);

}

（2）任意两个地点之间最短路径算法

ShortestPath_Floyd(AdjM *g) {

int i,k,j,l,flag=1,path[maxnum][maxnum][maxnum],dist[maxnum][maxnum];

printf("景点编号如下：n");

for(i=0;ivexnum;i++)

printf(" %-4d %-15sn",i,g->vertex[i].name);

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

{

dist[i][j]=g->arcs[i][j].adj;

for(l=0;lvexnum;l++)

path[i][j][l]=0;

if(dist[i][j]

{

path[i][j][i]=1;path[i][j][j]=1;

}

}

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

for(l=0;lvexnum;l++)

if(dist[j][i]+dist[i][l]

{

dist[j][l]=dist[j][i]+dist[i][l];

for(k=0;kvexnum;k++)

path[j][l][k]=path[j][i][k]+path[i][l][k];

}

while(flag==1)

{

printf("请输入出发地和目的地:");

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

if(k>=0&&kvexnum&&j>=0&&jvexnum)

flag=0;

}

printf("%s",g->vertex[k].name);

for(l=0;lvexnum;l++)

if(path[k][j][l]&&k!=l&&j!=l)

printf(">>>>>%s",g->vertex[l].name);

printf(">>>>>%s",g->vertex[j].name);

printf(" 总路线长%d米n",dist[k][j]);

}

四、源代码

#include

#include

#include

#include

#define maxnum 15

#define INFINITY 32768

int pre[maxnum];

int visited[maxnum];

typedef struct VData

{

int num;

char name[20];

char jieshao[100];

}VData;

typedef struct ANode

{

int adj;

}ANode;

typedef struct

{

VData vertex[maxnum];

ANode arcs[maxnum][maxnum];

int vexnum,arcnum;

}AdjM;

AdjM CreatUDN(void)

{

int i,j;

AdjM g;

=14;

=30;

[0].num=0;

strcpy([0].name,"学校主大门");

strcpy([0].jieshao,"南京信息工程大学主大门气势恢宏，是进入大学的主要通道。");

[1].num=1;

strcpy([1].name,"综合体育中心");

strcpy([1].jieshao,"是举行篮球比赛和各种活动的地方。");

[2].num=2;

strcpy([2].name,"气象大厦");

strcpy([2].jieshao,"大气科学学院、应用气象学院、遥感学院等办公、培训、实验用楼。");

[3].num=3;

strcpy([3].name,"东苑南门");

strcpy([3].jieshao,"东苑南门是进出东苑的方便出入地。");

[4].num=4;

strcpy([4].name,"大学生活动中心");

strcpy([4].jieshao,"是团委办公，学生社团中心所在地。有一个可容纳千人的演出剧院。");

[5].num=5;

strcpy([5].name,"图书馆");

strcpy([5].jieshao,"学生上机实验、学习的场所。");

[6].num=6;

strcpy([6].name,"中苑南门");

strcpy([6].jieshao,"中苑南门是进出中苑的方便出入地。");

[7].num=7;

strcpy([7].name,"图书中心");

strcpy([7].jieshao,"拥有大量书籍可以借阅，也是学生自习的良好场所。");

[8].num=8;

strcpy([8].name,"滨江楼");

strcpy([8].jieshao,"滨江楼是滨江学生上课主要地方之一。");

[9].num=9;

strcpy([9].name,"操场");

strcpy([9].jieshao,"操场是学生上早操、体育课和平时运动的主要地方。");

[10].num=10;

strcpy([10].name,"西苑宿舍楼");

strcpy([10].jieshao,"学生住宿的地方，便宜，舒适。");

[11].num=11;

strcpy([11].name,"食堂");

strcpy([11].jieshao,"食堂的饭菜不仅难吃还贵。");

[12].num=12;

strcpy([12].name,"滨江综合楼");

strcpy([12].jieshao,"滨江综合楼是滨江学生上课主要地方之一，老师办公室也在这儿。");

[13].num=13;

strcpy([13].name,"西苑南门");

strcpy([13].jieshao,"西苑南门是学生进出西苑的方便出入地。");

for(i=0;i<;i++)

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

[i][j].adj=INFINITY;

[0][1].adj=[1][0].adj=100;

[1][2].adj=[2][1].adj=400;

[0][2].adj=[2][0].adj=400;

[2][3].adj=[3][2].adj=100;

[2][4].adj=[4][2].adj=250;

[4][5].adj=[5][4].adj=300;

[4][6].adj=[6][4].adj=700;

[5][6].adj=[6][5].adj=550;

[6][7].adj=[7][6].adj=400;

[5][7].adj=[7][5].adj=400;

[7][8].adj=[8][7].adj=700;

[8][9].adj=[9][8].adj=50;

[9][10].adj=[10][9].adj=100;

[10][11].adj=[11][10].adj=300;

[11][12].adj=[12][11].adj=400;

[12][8].adj=[8][12].adj=40;

[8][13].adj=[13][8].adj=80;

[12][13].adj=[13][12].adj=50;

return g;

}

void DFS_path(AdjM g, int m,int n,int k)

{

int s;

if(pre[k]==n && k<11)

{

for(s=0;s

printf("%s ->",[pre[s]].name);

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

printf("nn");

}

else

{

s=0;

while(s<)

{

if(([pre[k]][s].adj

{

visited[s]=1;

pre[k+1]=s;

DFS_path(g,m,n,k+1);

visited[s]=0;

}

s++;

}

}

}

void all_path(AdjM g)

{

int i,m,n;

printf("n请输入你要查询的两个景点编号:nn");

scanf("%d %d",&m,&n);

printf("nn");

pre[0]=m;

for(i=0;i<;i++)

visited[i]=0;

visited[m]=1;

DFS_path(g,m,n,0);

}

ShortestPath_Floyd(AdjM *g)

{

int i,k,j,l,flag=1,path[maxnum][maxnum][maxnum],dist[maxnum][maxnum];

printf("景点编号如下：n");

for(i=0;ivexnum;i++)

printf(" %-4d %-15sn",i,g->vertex[i].name);

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

{

dist[i][j]=g->arcs[i][j].adj;

for(l=0;lvexnum;l++)

path[i][j][l]=0;

if(dist[i][j]

{

path[i][j][i]=1;path[i][j][j]=1;

}

}

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

for(l=0;lvexnum;l++)

if(dist[j][i]+dist[i][l]

{

dist[j][l]=dist[j][i]+dist[i][l];

for(k=0;kvexnum;k++)

path[j][l][k]=path[j][i][k]+path[i][l][k];

}

while(flag==1)

{

printf("请输入出发地和目的地:");

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

if(k>=0&&kvexnum&&j>=0&&jvexnum)

flag=0;

}

printf("%s",g->vertex[k].name);

for(l=0;lvexnum;l++)

if(path[k][j][l]&&k!=l&&j!=l)

printf(" ->%s",g->vertex[l].name);

printf(" ->%s",g->vertex[j].name);

printf(" 总路线长%d米n",dist[k][j]);

}

ShortestPath_Floyd_(AdjM *g)

{

int i,k,j,l,flag=1,path[maxnum][maxnum][maxnum],dist[maxnum][maxnum];

printf("景点编号如下：n");

for(i=0;ivexnum;i++)

printf(" %-4d %-15sn",i,g->vertex[i].name);

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

{

dist[i][j]=g->arcs[i][j].adj;

for(l=0;lvexnum;l++)

path[i][j][l]=0;

if(dist[i][j]

{

path[i][j][i]=1;path[i][j][j]=1;

}

}

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

for(l=0;lvexnum;l++)

if(dist[j][i]+dist[i][l]

{

dist[j][l]=dist[j][i]+dist[i][l];

for(k=0;kvexnum;k++)

path[j][l][k]=path[j][i][k]+path[i][l][k];

}

while(flag==1)

{

printf("请输入出发地和目的地的编号:");

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

if(k>=0&&kvexnum&&j>=0&&jvexnum)

flag=0;

}

printf("%s",g->vertex[k].name);

for(l=0;lvexnum;l++)

if(path[k][j][l]&&k!=l&&j!=l)

printf(" ->%s",g->vertex[l].name);

printf(" ->%s",g->vertex[j].name);

}

shuchu(AdjM g)

{

int i;

system("cls");

for(i=0;i<;i++)

printf("%d %-15s:%-40sn",i,[i].name,[i].jieshao);

}

main()

{

AdjM h;

int c;

char t;

h=CreatUDN();

system("cls");

do

{

printf(" 欢迎使用南京信息工程大学导游系统n");

printf(" ************************************

printf(" 1.校园的全部景点及信息

printf(" 2.两景点之间的最短路径

printf(" 3.两景点之间的所有路径

printf(" 0.退出

printf(" ************************************

printf("请选择:");

scanf("%d",&c);

switch(c)

{ case 1:shuchu(h);break;

case 2:ShortestPath_Floyd(&h);break;

case 3:all_path(h);break;

default:exit(1);break;

}

printf("n是否继续:YES or NO(输入Y或N):");

scanf("%s",&t);

if(t=='y'||t=='Y') system("cls");

}while(t=='y'||t=='Y');

if(t=='n'||t=='N') printf("n谢谢使用!n");

}

n");

n");

n");

n");

n");

n");

五、运行截图

(1)界面

（2）校园全部景点与信息

（3）两景点间最短路径

（4）两景点间所有路径

六、体会及总结

通过这次课程设计了解数据结构在编写比较复杂的程序的重要作用，对数据结构中定义无向图和创建无向图的理解更加深刻，也完全理解了迪杰斯特拉算法的原理，但是对于其算法的程序编写还是不太明白。总的来说有很多收获。