导游系统课程设计报告.doc

数据结构课程设计（平顶山学院导游系统）姓 名：白明旭班 级：计算机科学与技术（一）班学 号：101210110指导教师：赵凯成 绩：完成时间：2011.12.26完成地点：软三实验室一、 设计题目（问题）描述和要求平顶山学院是一所普通本科类院校，其新校区坐落在平顶山新城区东部，学校占地2000多亩，拥有教学楼4座，学生宿舍17座，餐厅3个，体育场，足球场，超市等，现需要方便来访者参观，故设计这个导游程序以供游览帮助和参考。 要求： 1、查询各景点的相关信息。2、查询图中任意两个景点间的最短路径。3、查询图中任意两个景点间的所有路径。4、增加、删除、更新有关景点和道路的信息二、 系统分析与概要设计根据问题描述和要求，系统要求能够使游客通过终端可询问： （1）从某一景点到另一景点的最短路径。（2）游客从大门进入，选取一条最佳路线。（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。基本要求 （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择浏览路线。 （3）画出景点分布图于屏幕上。实现提示 （1）构造一个无向图G并用邻接矩阵来存储。 （2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组pi来记录，最短路径长度就用一维数组di存放；i的范围：020。 （3）一维数组have是用来记录最短路径出现顶点的顺序。 （4）根据起点和终点输出最短路径和路径长度。三、 详细设计和编码1. 数据类型定义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;2. 各模块关键算法描述（1）创建图的算法（MGraph * CreatUDN(MGraph *G) MGraph * CreatUDN(MGraph *G)/初始化图形，接受用户输入 for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) G-arcsij.adj=INFINITY; for(k=0;karcnum;k+) i=LocateVex(G,v1); j=LocateVex(G,v2); if(i=0&j=0) G-arcsij.adj=w; G-arcsji=G-arcsij; return G;（2）用狄杰斯塔拉算法查找最短路径void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020; while(flag) 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 end3. 程序关键算法流程图 (1)主函数流程(2) 某操作算法流程四、 调试分析 1.在调试过程中程序发现了不少错误，其中如类似：变量未定义就直接使用例：error C609: i : undeclared identifier在程序中中英文没有及时切换，导致标点的使用错误，定义的变量类型与实际的使用不对应，函数声明/定义/调用个数不匹配等。五、 测试结果六、 小结 通过对导游程序的设计，进一步熟悉了在学习中树的遍历问题，在应用狄杰斯科拉算法从一个源点到其余各项的最短路径和弗洛伊德求每一对顶点之间的最短路径更加清晰了。通过此次涉及不但巩固了本学期学过的主要内容，也知道了怎么应用所学的解决现实中的问题，收获很多。七、 附录（附上带详细注释的源程序）#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include#includetypedef 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;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) 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.,学校食堂); strcpy(G.roduction,新建标准化食堂，提供丰富食物); strcpy(G.,办公楼); strcpy(G.roduction,全体教师办公场所，楼高7层，各种设施齐全); strcpy(G.,14号学生教学楼); 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,小操场油很多体育设施，供同学们娱乐); strcpy(G.,扇形广场); strcpy(G.roduction,学院最大的广场，是同学们平常活动的首选场所); 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=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 endvoid 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%-56sn,G-vexsv.num,G-,G-roduction); 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+) 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 endvoid 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%-56sn,G-vexsk.num,G-,G-roduction); printf(n);/Search 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 * CreatUDN(MGraph *