课程设计报告参考模板.doc

PAGE PAGE 22 《创新设计》报告 ( 2008- 2009 年度第2 学期) 设计题目： 校园导航问题 学 院： 软 件 学 院 专 业： 软 件 工 程 姓 名： 黄秋萍 学 号： 220700335 指导教师： 江兰帆 日期： 2009 年 6 月 校园导航问题 [问题描述] 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 [基本要求] （1）设计福州大学新校区的校园平面图，所含景点不少于十个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个顶点之间的一条最短的简单路径。 （4）为来访客人提供多个景点的最佳路径，包括确定起始点和不确定起始点 [测试数据] 【7】北门 【7】北门 【10】素拓 【9】文楼 【3】教学区 【4】生活区 【11】体育馆 【1】图书馆 【2】行政北楼 【8】学生街 【6】东门 【5】行政南楼 20 单位：米 90 100 40 100 40 10 40 50 30 50 30 30 60 100 40 60 【12】游泳馆 30 50 一、需求分析 1．从我们学校的地图任意选取了12个景点，并给它们的距离赋值（详细见附录一） 2．本程序为用户提供了各种各样的查询信息，各种查询都可以任意选择从代号或名称，选择时的任意错误都有做处理。本题抽象看成一个无向带权图。图的结点代表景点，边代表路径。 （1）任意一个景点的相关信息。 （2）任意两个景点间的最短路径并输出了这条路径的路线。 （3）任意两个景点间的所有路径。 （4）多个景点的最佳路径 3．测试数据 二、概要设计 1.设定抽象类型定义： 顶点，边和图的类型 #define max 30 //途中顶点数的最大值 using namespace std; struct ac{ int jl; //边的权，表示路径长度 }; struct fengjing{ int num; //存放代号 string sight; //存放风景名称 string descri; //存放风景简介 }; struct zhuyao{ fengjing F[max]; //存放图中的顶点，即景点 ac H[max][max]; //存放图中的边，即为景点间的距离 int n, e; //顶点数和边数 }; struct doudian{ // 附加题最后一道题用到的，变量名为Q string name; //用于存放景点的名称 int flas; //每存入一条，就标志一下，用于判断 是否有通过该点 }; 2.全局变量类型： //用于多个景点的最短路径，两个代号的所有路径都存入这个全局变量 doudian Q[1500][max]; //把Q中所对应的路径长度存入全局变量mm数组中 long mm[1500]; //全局总变量，图的总体变量 zhuyao M; // 用于多个景点的最佳路径，给每个符合代号的所有路径总条数计数 int jj=0; //判断是多个景点的最短路径还是两个景点的所有路径调用函数 bool cc=0; //是allpath中用来存放路径的顶点 long D[max]; //存放从顶点i到j的最短路径经过的中间顶点的最大序号k int p[max][max]; 。 //用于两点间的最短路径函数中存放两个景点的最短路径 int shortest[max][max]; //是allpath中用来标记已通过的景点 bool visited[max]; 3.图的基本操作函数： void creat(); 初始条件：全局变量M存在，其中文本已有设置景点数，几条边，景点的名称，简介，矩阵表示两个景点的距离，并且如果两个景点没有直接相邻，路径用20000表示 操作结果：构造了图的基本信息，读入要设置几个顶点，几条边，图的简介，读入两个景点间的距离，如果不存在直接相邻，则赋为20000 void jieshao(); 初始条件：图已存在 操作结果：形成程序的界面，上面总有着景点的名字，他们的代号 char menu(); 初始条件：图已存在 操作结果：让用户自己选择是要用代号查询还是用名字查询 int search1(char c); 初始条件