数据结构课程方案——校园导游图.doc

羂Forpersonaluseonlyinstudyandresearch;mercialuse膂艿景德镇陶瓷学院袆信息工程学院蚄班级:12计科(2)班羁学号:201210510216荿姓名:乐升平芇指导老师:林卫中肂时间:2014年6月18号蚀题目:、需求分析:肈需求:螃(1)将导游图看作一张带权无向图,顶点表示公园的各个景点,边表示各景点之间的道路,边上的权值表示距离。为此图选择适当的数据结构。螃(2)把各种路径都显示给游客,由游客自己选择游览路线。聿(3)画出景点分布图于屏幕上。薅分析:螅完成对整个导游图系统的功能实现,需要对的每一项功能都有清楚的设想和认识,了解并明确每一项功能的实现需要解决的问题,选择正确并且高效的算法把问题逐个解决,最终实现程序的正确调试运行。有以下设计思路:袃(1).结合本校的实际情况,选出10个景点;葿(2).人为手工为选出的10个景点赋上相关信息(名称、代号、简介信息、以及路权等等);芇(3).根据选出来的10个景点用邻接矩阵存储校园图。薄(4).依照景点的相关信息创建校园图。羃(5).把纸质上的内容,利用C++编程语言编写查找景点相关信息的程序。袀(6).根据人为赋值的路权,迪杰斯特拉算法计算任意两点之间的最短路径。螅(7).综上所诉,用一个主函数把这些板块合成,生产一个菜单界面呈现在用户面前。、设计与实现:肃选出本校10个景点芁结合景德镇陶瓷学院实际情况,我选出以下10个景点,从1到10编号:蒇编号莆名称膂编号蒈名称腿编号膅名称节编号衿名称薇1袄研究生楼节2芀二食堂荿3蚃10#宿舍莂4蚁主教学楼螆5蚆毕业礼堂蒂6螈主阶蒈7蒄一食堂薂8膈A系列楼羆9芃B系列楼蚂10蕿图书馆蚈11芆科艺楼螂12羀科阶膆13篮球场 14田径场15游泳池16体育馆肅17翠湖18校门口袁图的初始化莁由于邻接矩阵特殊的存储方式,它非常便于快速的查找两个顶点之间的边上的权值。所以,图采用带权的邻接矩阵存储。袈决定了图的存储方式后,以华南农业大学18个景点的游览地图作为蓝本,把校园地图抽象化成顶点与边构成的图形式,如图所示螄袁10#、模块的划分芆含有四个模块:(1)陶院地图信息蚆(2)陶院景点信息芁(3)查找两点间最短路径莂(4)退出蚇模板功能肄(1)将陶院的地图显示在程序运用上;芄(2)输入一个景点,运用程序上能够显示该景点的信息;莂(3)可以给游客提供两个景点的最短路径;肈(4)给游客提供方便。螆#defineN18肃#defineMAX25蒂#defineMAXedg50葿#include<>芄#include<>袂#include<>薁#include<>薆羆voidclrscr()薁{蚁 system("cls");羇}莄蚄typedefintAdjMatrix[MAX][MAX];螁莈typedefstruct膆{莃 intvexs[MAX];袁AdjMatrixarcs;蝿}Matrix_Graph;袇蒆膅typedefstruct膀{蕿 charname[18];膄 charinformation[1010];芅 structedgenode*link;薀}vexnode;肇芇typedefstructedgenode莅{羁 intadjvex;蝿 intlength;羆 charinfo[18];蒅 charinfo2[1010];莂 structedgenode*next;膇}edgenode,*Node;螅薄typedefstructEdge螃{衿 intlengh;袈 intivex,jvex;薄 structEdge*next;袀}EdgeType;蚁薇typedefstruct蚄{芁 intnum;聿 charname[18];莆}vertex;螄螂typedefstruct螁{膅 vertexvexs[MAX];袄 intedges[MAX][MAX];膃}adjmax;芈膇voidName(inti)羄{艿 羀 switch(i)羆{肄 case1:蚀 printf("1:研究生楼\n\n");break;蒈 case2:蚅 printf("2:二食堂\n\n");break;膄 case3:肁 printf("3:10#宿舍\n\n");break;膀 case4:螈 printf("4: