数据结构课程设计作业(校园导游)

1数据结构课程设计CourseDesignofDataStructure计算机科学与技术082姓名：******学号：08422137指导老师：******2010年7月9日2目录1．需求分析说明2．概要设计说明3．详细设计说明4．调试分析5．课程设计总结6．参考书目7．致谢3需求分析说明随着高校校园的逐渐扩展，来访校园的人士逐渐增多，随着校园透明度的提高，各界人士对学术氛围的追求，越来越多的人走进了大学校园，走进了象牙塔，这片静土也以它崭新的面貌，迎接着所有的到来者，以前封闭以及半封闭的校园状况随之改变，派生的是它积极的迎接挑战的状态。高等院校，历来以其悠久的历史、深厚的文化底蕴、优美的自然和人文景观吸引着人们的目光。高校校园旅游在掀起“羞答答的头盖“后，正悄然走向市场，当今高校在确立了旅游的市场可行性之后，随之而来的导游系统是势在必行，高校的旅游可以让人陶冶情操，也可以让人对学术产生浓厚的兴趣。那么如何更好的更科学的更科学的组织好高校导游，如何更方便更便捷的把高校的校园展示给世人，就成为了一个需要解决的问题。利用计算机建立一个自动的导游系统，可以很好的解决这个问题。当客人来访时，系统可以根据客人指定的景点给予相关的信息，游客可以方便的了解到每个景点的详细信息，同时可以通过系统找到起始点和终点的多条路径，通过系统的分析后，能得出一条最短路径。各个景点的全景图、局部图可以在景点浏览中找到，付予语音、图片以及相关文字说明，让游客轻轻松松掌握景点信息。概要设计说明用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能：（1）查询各景点的相关信息。4（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。用图的结点代表景点，用图的边代表景点意见的路径，首先设计一个图类，结点值代表景点的信息，边的权值代表景点之间的距离，结点值及边的权值用顺序表存储，所以需要设计一个顺序表类，本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个编号，用结构体类型来实现。计算路径长度和最短路线是可以用Dijkstra(迪杰斯特拉)算法实现，在主函数中用switch选择语句执行浏览景点信息或查询最短路径typedefstructArCell{intadj;//路径长度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct//图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{charname[30];intnum;charintroduction[200];//简介}infotype;typedefstruct{5infotypevexs[MAX_VERTEX_NUM];//景点AdjMatrixarcs;//路径数组intvexnum,arcnum;//景点数，路径长度记录}MGraph;voidcmd(void);//在主函数中用来调用其他应用子函数的函数声明MGraphInitGraph(void);//用来构造学校地图的子函数返回MGraph类型voidMenu(void);//菜单函数；voidBrowser(MGraph*G);//调用MGraph类型的地址，进行voidShortestPath_DIJ(MGraph*G);//迪杰斯特拉算法求最短路径的子函数voidFloyd(MGraph*G);//佛洛伊德算法voidSearch(MGraph*G);//寻找要查询的景点，并输出该景点的信息intLocateVex(MGraph*G,char*v);//定点位置MGraph*CreatUDN(MGraph*G);////初始化图形，接受用户输入voidprint(MGraph*G);//打印输出子函数详细设计说明#defineINFINITY10000/*无穷大*/#defineMAX_VERTEX_NUM40#defineMAX40#includestdlib.h#includestdio.h#includeconio.h#includestring.htypedefstructArCell{intadj;//路径长度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct//图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{charname[30];6intnum;charintroduction[200];//简介}infotype;typedefstruct{infotypevexs[MAX_VERTEX_NUM];//景点AdjMatrixarcs;//路径数组intvexnum,arcnum;//景点数，路径长度记录}MGraph;MGraphb;//全局变量voidcmd(void);//在主函数中用来调用其他应用子函数的函数声明MGraphInitGraph(void);//用来构造学校地图的子函数返回MGraph类型voidMenu(void);//菜单函数；voidBrowser(MGraph*G);//调用MGraph类型的地址，进行voidShortestPath_DIJ(MGraph*G);//迪杰斯特拉算法求最短路径的子函数voidFloyd(MGraph*G);//佛洛伊德算法voidSearch(MGraph*G);//寻找要查询的景点，并输出该景点的信息intLocateVex(MGraph*G,char*v);//定点位置MGraph*CreatUDN(MGraph*G);////初始化图形，接受用户输入voidprint(MGraph*G);//打印输出子函数/******************************************************/voidmain(void){system(color1f);//设置调试窗口背景和字体颜色system(modecon:cols=140lines=130);//设置调试窗口的大小cmd();//用该函数来调用其他需要用到的函数}/******************************************************/voidcmd(void)//用来调用其他需要用到的函数的子函数{inti;b=InitGraph();//构造校园地图Menu();//调用菜单函数scanf(%d,&i);while(i!=5){switch(i){case1:system(cls);Browser(&b);Menu();break;case2:system(cls);ShortestPath_DIJ(&b);Menu();break;case3:system(cls);Floyd(&b);Menu();break;case4:system(cls);Search(&b);Menu();break;case5:exit(1);break;7default:break;}scanf(%d,&i);}}//************************************************************************MGraphInitGraph(void)//构造校园地图{MGraphG;inti,j;G.vexnum=10;//景点数量G.arcnum=14;//路径数量for(i=0;iG.vexnum;i++)G.vexs[i].num=i;//对景点进行对应编号/*对对应的景点编号进行命名，输入简介*/strcpy(G.vexs[0].name,行政楼);strcpy(G.vexs[0].introduction,学校的行政机构);strcpy(G.vexs[1].name,图书馆);strcpy(G.vexs[1].introduction,藏书200万册,设施良好，环境幽雅);strcpy(G.vexs[2].name,新理科楼);strcpy(G.vexs[2].introduction,学校最气派的教学楼，里面的设施比较好);strcpy(G.vexs[3].name,川味府);strcpy(G.vexs[3].introduction,里面有南方各种美食，就餐环境幽雅);strcpy(G.vexs[4].name,洗浴中心);strcpy(G.vexs[4].introduction,学校唯一的澡堂，在川味府旁边);strcpy(G.vexs[5].name,中心体育场);strcpy(G.vexs[5].introduction,化塑胶跑道,人造草坪,适宜锻炼身体的场所);strcpy(G.vexs[6].name,会堂);strcpy(G.vexs[6].introduction,学校有大型的晚会都在这里举行);strcpy(G.vexs[7].name,钟楼广场);strcpy(G.vexs[7].introduction,是连大学子展现才华的地方，旁有邮局);strcpy(G.vexs[8].name,新文科楼);strcpy(G.vexs[8].introduction,里面包含几个学院);strcpy(G.vexs[9].name,清缘超市);strcpy(G.vexs[9].introduction,学校最大的超市，里面有很多学生使用的商品);//对有路的各景点之间的路径长度进行设置,没路的设置为无穷大for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[i][j].adj=INFINITY;G.arcs[0][1].adj=100;G.arcs[0][2].adj=150;G.arcs[0][6].adj=200;G.arcs[1][7].adj=150;G.arcs[2][3].adj=50;8G.arcs[3][6].adj=50;G.arcs[3][4].adj=20;G.arcs[4][5].adj=200;G.arcs[4][9].adj=150;G.arcs[5][9].adj=350;G.arcs[6][7].adj=60;G.arcs[6][9].adj=80;G.arcs[7][8].adj=50;G.arcs[8][9].adj=20;//无向图的路径是相互的for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[j][i].adj=G.arcs[i][j].adj;returnG;}//InitGraphend//*****************************************************************************//菜单函数，打印出导游项目菜单voidMenu(){printf(\n大连大学校园导游图\n);printf(┏━━━━━━━━━━━━━━━━━━━━┓\n);printf(┃1.浏览校园全景┃\n);printf(┃2.查看所有游览路线┃\n);printf(┃3.选择出发点和目的地┃\n);printf(┃4.查看景点信息┃\n);printf(┃5.退出系统┃\n);printf(┗━━━━━━━━━━━━━━━━━━━━┛\n);printf(Option--:);}//********************************************************************************//输出所有景点信息voidBrowser(MGraph*G){intv;printf(┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n);pri