校园导游实验报告数据结构.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.21M 资料格式：doc 举报版权申诉

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第1页.png

第1页 / 共32页

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第2页.png

第2页 / 共32页

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第3页.png

第3页 / 共32页

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第4页.png

第4页 / 共32页

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第5页.png

第5页 / 共32页

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第6页.png

第6页 / 共32页

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第7页.png

第7页 / 共32页

kof707116719-5035096-校园导游实验报告&&over.doc.pdf-第8页.png

第8页 / 共32页

文本预览

校园导游实验报告学号：200930457018 姓名：熊博班级：09 计科 1 班完成日期：2010-12-21

1、问题描述制作陶瓷学院的校园导游图，游客通过终端可询问：（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(" printf("\t\t\n"); Sleep(1000); do { 欢迎您进入景德镇陶瓷学院学校园导游咨询系统\n"); while(1) { printf(" printf(" printf(" printf(" printf(" printf(" printf(" printf(" \n"); \n"); 泳馆育馆 \n"); 验楼 \n"); 院 \n"); \n"); 主要景点列表 \n"); \n"); <1> 操场 <3> 3 教 <5> 2 教 <7> 图书馆 <9> 9 实验楼 <2> 游 <4> 体 <6> 1 教 <8> 2 实 <10> 医

printf(" printf(" printf(" 宿舍楼 \n"); 三食堂 \n"); 门 \n"); printf(" printf("\t\t\n"); printf(" ━━━━━━━┓\n"); ┃\n"); ┃\n"); 短路径路径 ┃\n"); printf(" printf(" printf(" ┃\n"); printf(" ┃\n"); printf(" printf(" ━━━━━━━┛\n"); <11> 东西办 <12> 9# <13> 综合食堂 <14> 二 <15> 80 广场 <16>大 \n"); ┏━━━━━━━━━━━━━━━━ ┃ 1.查看主要景点布局图 ┃ 2.查看景点信息 ┃ 3.查看某一景点到其他景点的最 ┃ 4.查看任意两个景点之间的最短 ┃ 0.退出系统 ┗━━━━━━━━━━━━━━━━ printf("请输入您的选择选择，按回车键结束:"); scanf("%d",&k); if(k<0||k>5) { 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

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

}//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(v0<0||v0>G->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]vexnum;i++) { min=INFINITY; for(w=1;wvexnum;w++) if(!final[w]) if(D[w]vexnum;w++) if(!final[w]&&(min+G->arcs[v][w].adjarcs[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]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 总路线长%dm\n\n",D[v]); } printf("完毕，按任意键继续!\n"); getch(); }

分享到：

赞收藏

资料库

校园导游实验报告数据结构.doc

相关推荐

课程资源

热门标签

最新资料