1 / 9 用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求：1、查询各景点的相关信息。2、查询图中任意两个景点间的最短路径。3、查询图中任意两个景点间的所有路径。4、增加、删除、更新有关景点和道路的信息。/*校园导游程序*/*问题描述 用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线。（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。基本要求 （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择浏览路线。（3）画出景点分布图于屏幕上。实现提示 （1）构造一个无向图G 并用邻接矩阵来存储。（2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组pi 来记录，最短路径长度就用一维数组di存放； i 的范围： 020。（3）一维数组have 是用来记录最短路径出现顶点的顺序。（4）根据起点和终点输出最短路径和路径长度。*/ #define INFINITY 10000 /*无穷大 */ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include typedef struct ArCell int adj 。 /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页2 / 9 typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息， char name30。int num 。char introduction100。/简介infotype 。typedef struct infotype vexsMAX_VERTEX_NUM。AdjMatrix arcs 。int vexnum,arcnum。MGraph 。MGraph b 。void cmd(void)。MGraph InitGraph(void)。void Menu(void)。void Browser(MGraph *G)。void ShortestPath_DIJ(MGraph * G)。void Floyd(MGraph *G)。void Search(MGraph *G)。int LocateVex(MGraph *G,char* v)。MGraph * CreatUDN(MGraph *G)。void print(MGraph *G)。/*/ void main(void) system(color 1f)。 system(mode con: cols=140 lines=130)。 cmd() 。 /*/ void cmd(void) int i 。 b=InitGraph() 。 Menu() 。 scanf(%d,&i)。 while(i!=5) switch(i) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页3 / 9 case 1:system(cls)。Browser(&b) 。Menu() 。break 。 case 2:system(cls)。ShortestPath_DIJ(&b)。Menu() 。break 。 case 3:system(cls)。Floyd(&b) 。 Menu() 。break 。 case 4:system(cls)。Search(&b) 。Menu() 。break 。 case 5:exit(1)。break 。 default:break 。 scanf(%d,&i)。 MGraph InitGraph(void) MGraph G 。 int i,j 。 G.vexnum=10。 G.arcnum=14。 for(i=0 。iG.vexnum 。i+) G.vexsi.num=i。 strcpy(G.vexs0.name,综合食堂 )。 strcpy(G.vexs0.introduction,新建标准化食堂)。 strcpy(G.vexs1.name,东西办公楼 )。 strcpy(G.vexs1.introduction,全体教师办公场所，楼高12 层，各种设施齐全)。 strcpy(G.vexs2.name,5号学生宿舍楼 )。 strcpy(G.vexs2.introduction,计算机系男生宿舍楼，苏式建筑)。 strcpy(G.vexs3.name,医院 )。 strcpy(G.vexs3.introduction,校医院 ,设施不是很齐全，只能看小病，收费较贵)。 strcpy(G.vexs4.name,图书馆 )。 strcpy(G.vexs4.introduction,藏书 60 万册 ,设施良好， 2 楼为电子阅览室，环境幽雅)。 strcpy(G.vexs5.name,足球场 )。 strcpy(G.vexs5.introduction,现代化塑胶跑道,人造草坪 ,适宜锻炼身体的场所)。 strcpy(G.vexs6.name,沁园 )。 strcpy(G.vexs6.introduction,绿树成荫 ,适宜休息和读书)。 strcpy(G.vexs7.name,主教案楼 )。 strcpy(G.vexs7.introduction,学院最大的教案楼,共 5 层，环形建筑 ,适宜学习 )。 strcpy(G.vexs8.name,西教案楼 )。 strcpy(G.vexs8.introduction,学院第二大教案楼,环境较差 )。 strcpy(G.vexs9.name,多媒体楼 )。 strcpy(G.vexs9.introduction,多媒体教案场所,设施先进 ,环境良好 )。 for(i=0 。iG.vexnum 。i+) for(j=0 。jG.vexnum 。j+) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 9 页4 / 9 G.arcsij.adj=INFINITY。 G.arcs01.adj=100。 G.arcs02.adj=200。 G.arcs06.adj=400。 G.arcs17.adj=300。 G.arcs23.adj=120。 G.arcs36.adj=220。 G.arcs34.adj=100。 G.arcs45.adj=300。 G.arcs49.adj=250。 G.arcs59.adj=350。 G.arcs67.adj=60。 G.arcs69.adj=200。 G.arcs78.adj=50。 G.arcs89.adj=20。 for(i=0 。iG.vexnum 。i+) for(j=0 。jG.vexnum 。j+) G.arcsji.adj=G.arcsij.adj。 return G 。/InitGraph end void Menu() printf(n 石家庄铁道学院导游图n)。 printf( n) 。 printf( 1.浏览校园全景n) 。 printf( 2.查看所有游览路线n) 。 printf( 3.选择出发点和目的地 n)。 printf( 4.查看景点信息n) 。 printf( 5.退出系统n) 。 printf( n) 。 printf(Option-:)。 void Browser(MGraph *G) int v 。 printf( n) 。 printf( 编号景点名称简介n) 。 for(v=0 。vvexnum。v+) printf( %-4d %-16s %-56s n,G-vexsv.num,G-vexsv.name,G-vexsv.introduction)。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页5 / 9 printf( n) 。 / 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0 为起点void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0。 int final20, D20, p2020。 while(flag) printf( 请输入一个起始景点编号:)。 scanf(%d,&v0)。 if(v0G-vexnum) printf( 景点编号不存在!请重新输入景点编号:)。 scanf(%d,&v0)。 if(v0=0&v0vexnum) flag=0 。 for(v=0 。vvexnum。v+) finalv=0 。 Dv=G-arcsv0v.adj。 for(w=0 。wvexnum 。 w+) pvw=0 。 if(DvINFINITY) pvv0=1 。pvv=1 。 Dv0=0 。finalv0=1 。 for(i=1 。ivexnum 。i+) min=INFINITY。 for(w=0 。wvexnum 。 w+) if(!finalw) if(Dwmin)v=w。min=Dw 。 finalv=1 。 for(w=0 。wvexnum。w+) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页6 / 9 if(!finalw&(min+G-arcsvw.adjarcsvw.adj。 for(x=0 。 xvexnum 。x+) pwx=pvx。 pww=1 。 for(v=0 。vvexnum。v+) if(v0!=v) printf(%s,G-vexsv0.name)。 for(w=0 。wvexnum 。 w+) if(pvw&w!=v0) printf(-%s,G-vexsw.name)。 t+ 。 if(tG-vexnum-1&v0!=v)printf( 总路线长 %dmnn,Dv) 。 /ShortestPath_DIJ end void Floyd(MGraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010。 for(v=0 。vvexnum。v+) for(w=0 。wvexnum 。 w+) Dvw=G-arcsvw.adj。 for(u=0 。uvexnum 。 u+) pvwu=0 。 if(DvwINFINITY) pvwv=1 。 pvww=1 。 for(u=0 。uvexnum。u+) for(v=0 。vvexnum 。v+) for(w=0 。wvexnum。w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw。 for(i=0 。ivexnum 。i+) pvwi=pvui|puwi。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页7 / 9 while(flag) printf( 请输入出发点和目的地的编号:)。 scanf(%d%d,&k,&j)。 if(kG-vexnum|jG-vexnum) printf( 景点编号不存在!请重新输入出发点和目的地的编号:)。 scanf(%d%d,&k,&j)。 if(k=0&kvexnum&j=0&jvexnum) flag=0 。 printf(%s,G-vexsk.name)。 for(u=0 。uvexnum。u+) if(pkju&k!=u&j!=u) printf(-%s,G-vexsu.name)。 printf(-%s,G-vexsj.name)。 printf( 总路线长 %dmn,Dkj)。/Floyd end void Search(MGraph *G) int k,flag=1 。 while(flag) printf( 请输入要查询的景点编号:)。 scanf(%d,&k)。 if(kG-vexnum) printf( 景点编号不存在!请重新输入景点编号:)。 scanf(%d,&k)。 if(k=0&kvexnum) flag=0 。 printf( n) 。 printf( 编号景点名称简介n) 。 printf( %-4d %-16s %-56s n,G-vexsk.num,G-vexsk.name,G-vexsk.introduction)。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页8 / 9 printf( n) 。/Search end int LocateVex(MGraph *G,char* v) int c=-1,i 。 for(i=0 。ivexnum 。i+) if(strcmp(v,G-vexsi.name)=0) c=i 。break 。 return c 。 MGraph * CreatUDN(MGraph *G)/初始化图形，接受用户输入 int i,j,k,w 。 char v120,v220。 printf( 请输入图的顶点数,弧数 :)。 scanf(%d%d,&G-vexnum,&G-arcnum)。 printf( 请输入景点的编号:、名称、简介:n)。 for(i=0 。ivexnum 。i+) printf( 景点编号 :)。 scanf(%d,&G-vexs-num)。 printf( 景点名称 :)。 scanf(%s,G-vexsi.name)。 printf( 景点简介 :)。 scanf(%s,G-vexs-introduction)。 for(i=0 。ivexnum 。i+) for(j=0 。jvexnum 。j+) G-arcsij.adj=INFINITY。 printf( 请输入路径长度:n)。 for(k=0 。karcnum。k+) printf( 第%d 条边 :n,k+1) 。 printf( 景点对 (x,y):) 。 scanf(%s,v1)。 scanf(%s,v2)。 printf( 路径长度 :)。 scanf(%d,&w)。 i=LocateVex(G,v1)。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页9 / 9 j=LocateVex(G,v2)。 if(i=0&j=0) G-arcsij.adj=w。 G-arcsji=G-arcsij。 return G 。 void print(MGraph *G) int v,w,t=0 。for(v=0 。vvexnum 。v+) for(w=0 。wvexnum。w+) if(G-arcsvw.adj=INFINITY) printf( )。 else printf(%-7d,G-arcsvw.adj)。 t+ 。 if(t%G-vexnum=0) printf(n) 。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页