校园导游程序

1、数据结构课程设计报告姓名：学号：班级：学院： 日期：一、课程设计题目: 校园导游程序二、需求分析问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求 （1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。三、概要设计主要通过无向图的算法函数来实现校园导游程序设计。即如下函数：（本程序可完成创建景点操作，但不能完成分步的增加、删除、更新有关景点和道路的信息的操作。）typedef struc

2、t ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;/景点名int num;/编号char introduction100;/简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;/路径int vexnum,arcnum;/结点数，弧度数MGraph; MGraph b;MGraph InitGraph(void); /无

3、向图初始化void Browser(MGraph *G);/输出图的景点信息，编号，景点名，景点信息。void ShortestPath_DIJ(MGraph * G);迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径void Floyd(MGraph *G);/计算两景点间的最短路径int LocateVex(MGraph *G,char* v);查找景点MGraph * CreateUDN(MGraph *G);创建新的图景点void print(MGraph *G);输出路径长度void main(void)/主程序 int i; b=InitGraph(); while(i!=5)

4、printf("n 太原工业导游系统 n"); printf(" 1.浏览校园全境 n"); printf(" 2.查看所有游览路径 n"); printf(" 3.选择出发地点和目的地 n"); printf(" 4.创建新的景点信息n"); printf(" 5.退出 n"); printf("Option-:"); scanf("%d",&i); switch(i) /调用操作函数 case 1:system("

5、cls");Browser(&b);break; case 2:system("cls");ShortestPath_DIJ(&b);break; case 3:system("cls");Floyd(&b);break; case 4:system("cls");CreateUDN(&b);break; case 5:exit(1);break; default:break; 四、详细设计以下为函数的内容：MGraph InitGraph(void) MGraph G; int i,j; G

6、.vexnum=10; G.arcnum=14; for(i=0;i<G.vexnum;i+) G.vexsi.num=i; strcpy(G.,"体育场"); strcpy(G.roduction,"树胶跑道，足球场等体育用地"); strcpy(G.,"篮球场"); strcpy(G.roduction,"篮球爱好者的天堂"); strcpy(G.,"主教学楼"); strcpy(G.vex

7、roduction,"高层建筑，多媒体教室，适宜学习"); strcpy(G.,"锅炉房"); strcpy(G.roduction,"长期供热水，冬日供暖"); strcpy(G.," 东区食堂"); strcpy(G.roduction," 标准食堂建筑"); strcpy(G.,"实验楼"); strcpy(G.roduction,"实

8、验重地，科研开发"); strcpy(G.," 办公楼"); strcpy(G.roduction," 教师办公室和学校部门"); strcpy(G.," 图书馆"); strcpy(G.roduction," 藏书60万册,设施良好，2楼为电子阅览室，环境幽雅"); strcpy(G.," 沁园"); strcpy(G.roduction,"绿树成荫,适宜休息和

9、读书"); strcpy(G.,"西区食堂"); strcpy(G.roduction," 标准食堂建筑"); for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij.adj=INFINITY; G.arcs01.adj=20; G.arcs12.adj=200; G.arcs23.adj=80; G.arcs24.adj=150; G.arcs34.adj=100; G.arcs35.adj=220; G.arcs36.adj=220; G

10、.arcs57.adj=140; G.arcs56.adj=100; G.arcs58.adj=350; G.arcs68.adj=80; G.arcs67.adj=170; G.arcs79.adj=70; G.arcs89.adj=70; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G;/InitGraph endvoid Browser(MGraph *G) int v;printf(" 编号 景点名称 简介 n"); for(v=0;v&l

11、t;G->vexnum;v+) printf(" %-4d %-16s %-56s n",G->vexsv.num,G->,G->roduction);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(v0<0|v0>

12、;G->vexnum) printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&v0); if(v0>=0&&v0<G->vexnum) flag=0; for(v=0;v<G->vexnum;v+) finalv=0; Dv=G->arcsv0v.adj; for(w=0;w<G->vexnum;w+) pvw=0; if(Dv<INFINITY) pvv0=1; pvv=1; Dv0=0;finalv0=1; for(i=1;i<G-

13、>vexnum;i+) min=INFINITY; for(w=0;w<G->vexnum;w+) if(!finalw) if(Dw<min)v=w;min=Dw; finalv=1; for(w=0;w<G->vexnum;w+) if(!finalw&&(min+G->arcsvw.adj<Dw) Dw=min+G->arcsvw.adj; for(x=0;x<G->vexnum;x+) pwx=pvx; pww=1; for(v=0;v<G->vexnum;v+) if(v0!=v) prin

14、tf("%s",G->); for(w=0;w<G->vexnum;w+) if(pvw&&w!=v0) printf("->%s",G->); t+; if(t>G->vexnum-1&&v0!=v)printf(" 总路线长%dmnn",Dv); /ShortestPath_DIJ endvoid Floyd(MGraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010; for(v

15、=0;v<G->vexnum;v+) for(w=0;w<G->vexnum;w+) Dvw=G->arcsvw.adj; for(u=0;u<G->vexnum;u+) pvwu=0; if(Dvw<INFINITY) pvwv=1;pvww=1; for(u=0;u<G->vexnum;u+) for(v=0;v<G->vexnum;v+) for(w=0;w<G->vexnum;w+) if(Dvu+Duw<Dvw) Dvw=Dvu+Duw; for(i=0;i<G->vexnum;i+

16、) pvwi=pvui|puwi; while(flag) printf("请输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); if(k<0|k>G->vexnum|j<0|j>G->vexnum) printf("景点编号不存在!请重新输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); if(k>=0&&k<G->vexnum&&j>=0&a

17、mp;&j<G->vexnum) flag=0; printf("%s",G->); for(u=0;u<G->vexnum;u+) if(pkju&&k!=u&&j!=u) printf("->%s",G->); printf("->%s",G->); printf(" 总路线长%dmn",Dkj);/Floyd endint LocateVex(MGraph

18、*G,char* v) int c=-1,i; for(i=0;i<G->vexnum;i+) if(strcmp(v,G->)=0) c=i;break; return c;MGraph * CreateUDN(MGraph *G)/初始化图形，接受用户输入 int i,j,k,w; char v120,v220; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum); printf("请输入景点的编号、名称、简

19、介:n"); for(i=0;i<G->vexnum;i+) printf("景点编号:"); scanf("%d",&G->vexs->num); printf("景点名称:"); scanf("%s",G->); printf("景点简介:"); scanf("%s",G->vexs->introduction); for(i=0;i<G->vexnum;i+) for(j=0;j<G->vexnum;j+) G->arcsij.adj=INFINITY; printf("请输入路径信息:n"); for(k=0;k<G->arcnum;k+) printf("第%d条边:n",k+1); printf("景点对(x,y):"); scanf("%s",v1); scanf("%s",v2); printf("路径长度:&quo