数据结构课程方案——校园导游图.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:主教