校园导游实验报告[1]_校园导游实验报告

校园导游实验报告[1]由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“校园导游实验报告”。

校园导游实验报告

学号：200930457018

姓名：熊博 班级：09计科1班 完成日期：2010-12-211、问题描述

制作陶瓷学院的校园导游图，游客通过终端可询问：（1）从某一景点到另一景点的最短路径。

（2）游客从公园进入，选取一条最佳路线3，使游客可以不重复地游览各景点，最后回到出口（出口就在入口处旁边）

2、要求

（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。

（2）把各种路径都显示给游客，由游客自己选择游览路线。（3）画出景点分布图于屏幕上。

3、实现提示

（1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。

（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。

2.概要设计：

typedef struct ArCell { int adj;

//路径长度

}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct

//图中顶点表示主要景点，存放景点的信息 { char name[30];int num;int x;int y;char introduction[500];//简介 }infotype;typedef struct { infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;MGraph b;

void dij(MGraph *);计算出起点到其他各个顶点之间的最短路径 void floyd(MGraph *);计算任意两个景点之间的最短路径 void Search(MGraph *G);查看景点信息 void jdbrowser();查看主要景点布局图

3.详细设计：

main函数： void main(){

int k;system(“color cf”);system(“mode con: cols=140 lines=130”);b=InitGraph();system(“cls”);printf(“

欢迎您进入景德镇陶瓷学院学校园导游咨询系统n”);printf(“ttn”);Sleep(1000);do {

while(1)

{

printf(“

n”);

printf(“

主要景点列表

n”);

printf(“

n”);

printf(“

操场

游泳馆

n”);

printf(“

3教

体育馆

n”);

printf(“

2教

1教

n”);

printf(“

图书馆

2实验楼

n”);

printf(“

9实验楼

医院

n”);

printf(“

东西办

9#宿舍楼 n”);

printf(“

综合食堂

二三食堂 n”);

printf(“

80广场

大门

n”);

printf(“

n”);

printf(“ttn”);

printf(“

┏━━━━━━━━━━━━━━━━━━━━━━━┓n”);

printf(“

┃

1.查看主要景点布局图

┃n”);

printf(“

┃

2.查看景点信息

┃n”);

printf(“

┃

3.查看某一景点到其他景点的最短路径

┃n”);

printf(“

┃

4.查看任意两个景点之间的最短路径

┃n”);

printf(“

┃

0.退出系统

┃n”);

printf(“

┗━━━━━━━━━━━━━━━━━━━━━━━┛n”);

printf(“请输入您的选择选择，按回车键结束:”);

scanf(“%d”,&k);

if(k5)

{

printf(“输入有误请重新输入，按回车键结束!n”);

scanf(“%d”,&k);

}

else break;} switch(k){ case 1:jdbrowser();system(“cls”);break;case 2:Search(&b);system(“cls”);break;case 3:dij(&b);system(“cls”);break;case 4:floyd(&b);system(“cls”);break;case 0:exit(0);

} }while(1);}

图形初始化函数： MGraph InitGraph(){ MGraph G;int i,j;G.vexnum=17;G.arcnum=19;for(i=0;i

G.vexs[i].num=i;strcpy(G.vexs[1].name,“操场”);strcpy(G.vexs[1].introduction,“足球场，现代化塑胶跑道,人造草坪,锻炼身体的场所”);strcpy(G.vexs[2].name,“游泳馆”);strcpy(G.vexs[2].introduction,“一般只是暑假期间开放，水不是很干净”);strcpy(G.vexs[3].name,“3教”);strcpy(G.vexs[3].introduction,“多媒体教学场所,设施先进,环境良好”);strcpy(G.vexs[4].name,“体育馆”);strcpy(G.vexs[4].introduction,“里面有篮球场还有羽毛球场，平时用作羽毛球场地”);strcpy(G.vexs[5].name,“2教”);strcpy(G.vexs[5].introduction,“学院第二大教学楼,环境较差”);strcpy(G.vexs[6].name,“1教”);strcpy(G.vexs[6].introduction,“学院最大的教学楼,共5层，环形建筑,适宜学习”);strcpy(G.vexs[7].name,“图书馆”);strcpy(G.vexs[7].introduction,“藏书60万册,设施良好，2楼为电子阅览室，环境幽雅”);strcpy(G.vexs[8].name,“2实验楼”);strcpy(G.vexs[8].introduction,“信息科学与技术学院所在地”);strcpy(G.vexs[9].name,“9实验楼”);strcpy(G.vexs[9].introduction,“学校机房所在地”);strcpy(G.vexs[10].name,“医院”);strcpy(G.vexs[10].introduction,“校医院,设施不是很齐全，收费较贵”);strcpy(G.vexs[11].name,“春晖楼”);strcpy(G.vexs[11].introduction,“全体教师办公场所，楼高12层，各种设施齐全”);strcpy(G.vexs[12].name,“9#宿舍楼”);strcpy(G.vexs[12].introduction,“装饰古朴，设施还算齐全，就是挤了点”);strcpy(G.vexs[13].name,“综合食堂”);strcpy(G.vexs[13].introduction,“新建标准化食堂，食物种类多，但是价格比较贵。”);strcpy(G.vexs[14].name,“二三食堂”);strcpy(G.vexs[14].introduction,“收费比较便宜的食堂，二楼的套餐还可以，主要是便宜，不过菜有点难吃”);strcpy(G.vexs[15].name,“80广场 ”);strcpy(G.vexs[15].introduction,“新建的广场，据说由80界校友捐赠。”);strcpy(G.vexs[16].name,“大门”);strcpy(G.vexs[16].introduction,“我们学校的大门，车辆进出的地方。设有保安。”);G.vexs[1].x=1;G.vexs[1].y=3;G.vexs[2].x=2;G.vexs[2].y=3;G.vexs[3].x=1;G.vexs[3].y=2;G.vexs[4].x=2;G.vexs[4].y=2;G.vexs[5].x=2;G.vexs[5].y=1;G.vexs[6].x=3;G.vexs[6].y=1;G.vexs[7].x=3;G.vexs[7].y=2;G.vexs[8].x=3;G.vexs[8].y=3;G.vexs[9].x=3;G.vexs[9].y=4;G.vexs[10].x=4;G.vexs[10].y=1;G.vexs[11].x=5;G.vexs[11].y=1;G.vexs[12].x=5;G.vexs[12].y=4;G.vexs[13].x=6;G.vexs[13].y=1;G.vexs[14].x=6;G.vexs[14].y=3;G.vexs[15].x=5;G.vexs[15].y=3;for(i=0;i

for(j=0;j

G.arcs[i][j].adj=INFINITY;G.arcs[1][2].adj=40;G.arcs[2][8].adj=80;

G.arcs[2][4].adj=50;G.arcs[3][4].adj=10;

G.arcs[4][7].adj=42;

G.arcs[4][5].adj=50;G.arcs[5][6].adj=40;

G.arcs[6][7].adj=50;

G.arcs[6][16].adj=20;G.arcs[6][10].adj=100;G.arcs[7][8].adj=50;G.arcs[8][9].adj=100;G.arcs[8][15].adj=200;G.arcs[10][11].adj=100;G.arcs[11][13].adj=50;

G.arcs[15][14].adj=80;G.arcs[13][14].adj=100;G.arcs[11][15].adj=100;G.arcs[12][15].adj=10;for(i=1;i

for(j=1;j

G.arcs[i][j].adj=G.arcs[j][i].adj;

return G;}//InitGraph end 迪杰斯特拉算法求一点到任意其他景点的最短路径： void dij(MGraph * G){ int v,w,w1,i,j,min,t=0,x,flag=1,v0;

int final[20], D[20], p[20][20];while(flag){

printf(“请您输入一个起始景点编号，按回车键结束:”);

scanf(“%d”,&v0);

if(v0G->vexnum)

{

printf(“景点编号不存在!请重新输入景点编号,按回车键结束:”);

scanf(“%d”,&v0);

}

if(v0>=0&&v0vexnum)

flag=0;} for(v=1;vvexnum;v++){

final[v]=0;

D[v]=G->arcs[v0][v].adj;for(w=1;wvexnum;w++)

p[v][w]=0;if(D[v]

{

p[v][v0]=1;p[v][v]=1;

} } D[v0]=1;final[v0]=1;for(i=1;ivexnum;i++){

min=INFINITY;

for(w=1;wvexnum;w++)

if(!final[w])

if(D[w]

final[v]=1;

for(w=1;wvexnum;w++)

if(!final[w]&&(min+G->arcs[v][w].adj

{

D[w]=min+G->arcs[v][w].adj;

for(x=0;xvexnum;x++)

p[w][x]=p[v][x];

p[w][w]=1;

}

} } for(v=1;vvexnum;v++){ if(v!=v0){ printf(“%s”,G->vexs[v0].name);w1=v0;} else continue;do {

flag=0;min=INFINITY;

for(w=1;wvexnum;w++)

{

if(p[v][w]&&w!=v0)

{

flag=1;

if(D[w]

}

}

if(flag)

{

if(G->vexs[w1].xvexs[j].x)

printf(“向东走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].x>G->vexs[j].x)

printf(“向西走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].yvexs[j].y)

printf(“向北走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].y>G->vexs[j].y)

printf(“向南走%dm”,G->arcs[w1][j].adj);

printf(“-->%s”,G->vexs[j].name);

w1=j;

p[v][j]=0;

}

else break;

}while(1);

printf(“n

总路线长%dmnn”,D[v]);} printf(“完毕，按任意键继续!n”);getch();Floyd算法求任意两点间的最短距离： void floyd(MGraph * G)

// 计算任意两个景点之间的最短路径 { int v,w,w1,i,j,v1,min,t=0,x,flag=1,v0;

int final[20], D[20], p[20][20];while(flag){

printf(“请您输入一个起始景点编号，按回车键结束:”);

scanf(“%d”,&v0);

if(v0G->vexnum)

{

printf(“景点编号不存在!请重新输入景点编号:”);

scanf(“%d”,&v0);

}

if(v0>=0&&v0vexnum)

flag=0;} flag=1;while(flag){

printf(“请您输入一个目的地景点编号，按回车键结束:”);

scanf(“%d”,&v1);

if(v1G->vexnum)

{

printf(“景点编号不存在!请重新输入景点编号:”);

scanf(“%d”,&v1);

}

if(v1>=0&&v1vexnum)

flag=0;} for(v=0;vvexnum;v++){

final[v]=0;

D[v]=G->arcs[v0][v].adj;

for(w=0;wvexnum;w++)

p[v][w]=0;

if(D[v]

{

p[v][v0]=1;p[v][v]=1;

} } D[v0]=0;final[v0]=1;for(i=1;ivexnum;i++){

min=INFINITY;

for(w=0;wvexnum;w++)

if(!final[w])

if(D[w]

final[v]=1;

for(w=0;wvexnum;w++)

if(!final[w]&&(min+G->arcs[v][w].adj

{

D[w]=min+G->arcs[v][w].adj;

for(x=0;xvexnum;x++)

p[w][x]=p[v][x];

p[w][w]=1;

} }

v=v1;

w1=v0;

printf(“%s”,G->vexs[v0].name);do {

flag=0;min=INFINITY;

for(w=0;wvexnum;w++)

{

if(p[v][w]&&w!=v0)

{

flag=1;

if(D[w]

}

}

if(flag)

{

if(G->vexs[w1].xvexs[j].x)

printf(“向东走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].x>G->vexs[j].x)

printf(“向西走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].yvexs[j].y)

printf(“向北走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].y>G->vexs[j].y)

printf(“向南走%dm”,G->arcs[w1][j].adj);

printf(“-->%s”,G->vexs[j].name);

w1=j;

p[v][j]=0;

}

else break;

}while(1);printf(“n

总路线长%dmnn”,D[v]);printf(“完毕，按任意键继续!n”);getch();}

查询景点信息函数： void Search(MGraph *G){ int k,flag=1;while(flag){

printf(“请您输入要查询的景点编号，按回车键结束:”);

scanf(“%d”,&k);

if(k=G->vexnum)

{

printf(“景点编号不存在!请重新输入景点编号:”);

scanf(“%d”,&k);

}

if(k>=0&&kvexnum)

flag=0;} printf(“┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓n”);printf(“┃编号┃景点名称

┃简介

┃n”);printf(“┃%-4d┃%-16s┃%-96s┃n”,G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);printf(“┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛n”);printf(“完毕，按任意键继续!n”);getch();}

主要的景点显示函数： void jdbrowser(){ printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“●

●n”);

printf(“●

(9)九实验楼

(12)九栋

●n”);

printf(“●

┃

┃

●n”);

printf(“●

┃

┃

●n”);

printf(“●

(1)操场━━(2)游泳馆━━━━(8)二实验楼━━━━━━━━━━━━━━━━━(15)80广场━━━━(14)二三食堂

●n”);printf(“●

┃

┃

┃

┃

●n”);

printf(“●

┃

┃

┃

┃

●n”);

printf(“●

(3)三教━━(4)体育馆━━━━━(7)图书馆

┃

┃

●n”);printf(“●

┃

┃

┃

┃

●n”);

printf(“●

┃

┃

┃

┃

●n”);

printf(“●

(5)二教━━━━━━(6)一教━━━━━━━━━━━━(10)医院━━━━━(11)东西办━━━━(13)综合食堂

●n”);printf(“●

┃

●n”);

printf(“●

(16)大门

●n”);

printf(“●

●n”);

printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“输出完毕，按任意键返回!n”);getch();}

4.使用说明：

（1）.查看主要景点布局图（2）.查看景点信息

（3）.查看某一景点到其他景点的最短路径（4）.查看任意两个景点之间的最短路径

（0）.退出系统

5.测试结果：

主界面

景点图

景点信息

从某点到其他点的最短路径

任意两点的最短路径

退出系统

6.参考资料：

1、《数据结构（C语言版）》 严蔚敏，吴伟民 清华大学出版社

2、《数据结构—C语言描述》 耿国华等 西安电子科技大学出版社

3、Data Structure &Program Design in C Robert L.Kruse 清华大学出版社

4、《数据结构（用面向对象方法与C++描述）》 殷人昆 清华大学出版社