校园导游程序.doc

数据结构课程设计报告姓名：学号：班级：学院： 日期：一、课程设计题目: 校园导游程序二、需求分析问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求 （1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。三、概要设计主要通过无向图的算法函数来实现校园导游程序设计。即如下函数：（本程序可完成创建景点操作，但不能完成分步的增加、删除、更新有关景点和道路的信息的操作。）typedef struct 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); /无向图初始化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) 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(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.vexnum=10; G.arcnum=14; for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,体育场); strcpy(G.roduction,树胶跑道，足球场等体育用地); strcpy(G.,篮球场); strcpy(G.roduction,篮球爱好者的天堂); strcpy(G.,主教学楼); strcpy(G.roduction,高层建筑，多媒体教室，适宜学习); strcpy(G.,锅炉房); strcpy(G.roduction,长期供热水，冬日供暖); strcpy(G., 东区食堂); strcpy(G.roduction, 标准食堂建筑); strcpy(G.,实验楼); strcpy(G.roduction,实验重地，科研开发); strcpy(G., 办公楼); strcpy(G.roduction, 教师办公室和学校部门); strcpy(G., 图书馆); strcpy(G.roduction, 藏书60万册,设施良好，2楼为电子阅览室，环境幽雅); strcpy(G., 沁园); strcpy(G.roduction,绿树成荫,适宜休息和读书); strcpy(G.,西区食堂); strcpy(G.roduction, 标准食堂建筑); for(i=0;iG.vexnum;i+) for(j=0;jG.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.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;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G;/InitGraph endvoid Browser(MGraph *G) int v;printf( 编号 景点名称 简介 n); for(v=0;vvexnum;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(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+) 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-); for(w=0;wvexnum;w+) if(pvw&w!=v0) printf(-%s,G-); t+; if(tG-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=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; 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-); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-); printf(-%s,G-); printf( 总路线长%dmn,Dkj);/Floyd endint LocateVex(MGraph *G,char* v) int c=-1,i; for(i=0;ivexnum;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(请输入景点的编号、名称、简介:n); for(i=0;ivexnum;i+) printf(景点编号:); scanf(%d,&G-vexs-num); printf(景点名称:); scanf(%s,G-); 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); 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); 五、程序