《数据结构课程设计-校园导航》由会员分享，可在线阅读，更多相关《数据结构课程设计-校园导航（15页珍藏版）》请在金锄头文库上搜索。
1、课课 程程 设设 计计 报报 告告课程名称课程名称 数据结构课程设计数据结构课程设计 题题 目目 校园导航校园导航 指导教师指导教师 设计起始日期设计起始日期 学 院 计算机学院 系 别 计算机科学与工程 学生姓名 班级/学号 成 绩 一、一、需求分析需求分析本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。设计要包 括下列要求：设计你的学校的平面图，至少包括 10 个以上的场所，每两个场所间可以有不同的路， 且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径） 。本课题实现校园多个场所（至少 10 个）的最短路径求解。 （1）输入的形式和输入值的范围：本系统主
2、要数据类型为字符型 char 及整形 int,char 型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编 号进行操作。(2 ) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。(3) 程序所能达到的功能：本程序可供任何人使用，主要功能 1.浏览各单位及简介； 2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。 （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 a.首先看到的是校园导航系统的菜单：b查看浏览路线等待输入起始景点：C选择出发点与目的地 等待输入起始景点与目的地编号：d参看景点信息等待输入景
3、点编号：二、二、概要设计概要设计本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法， 查找景点信息等程序段。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信 息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。系统首先通过主程序调用 void main( );进入系统主菜单函数，根据用户的选择可分 别进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路 径；4.查看景点信息；5.退出系统。 选择“浏览各景点及简介”项，显示十个景点的有关信息，包
4、括景点编号，景点名称， 景点简介。 选择“查看所有游览路线”项，会进入输入起始景点编号的界面，输入正确编号后会 显示起始景点到其余九个景点的最短路线的方案。 选择“选择出发点和目的地”项，会进入输入起始景点与目的景点的界面，输入起始 景 点与目的景点，并有空格隔开就得到两景点之间的最佳路径。 选择“查看景点信息”项，会进入输入要查看的景点的界面，如入后会显示该景点的 有关信息。 选择“退出系统”项，就会退出程序。三、三、详细设计详细设计（1）十三个单位的图0： 前门1：图书馆 2：教二楼 3：实验楼 4：操场 5：教一楼 6：食堂 7： 水房 8：学一公寓 9：学二公寓 10：学三公寓 11：
5、学四公寓 12：后门（2）主程序流程图： （3）弗洛伊德的算法： void 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(Dvwvexnum;u+)for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)if(Dvu+Duwvexnum;i+)pvwi=pvui|puwi;while(flag)coutkj; if(kG-vexnum|
6、jG-vexnum) /判断输入的景点编号正确与否coutkj;if(k=0 coutvexsk.name; /输出景点名称for(u=0;uvexnum;u+)if(pkju cout“vexsj.name; cout#include#include using namespace std;#include typedef struct ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;
7、char introduction100;/简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;MGraph b;MGraph InitGraph(void);void Menu(void);void Browser(MGraph *G);void ShortestPath_DIJ(MGraph * G);void Floyd(MGraph *G);void Search(MGraph *G);/*主函数*/void main(void)system(“colo
8、r 1f“);system(“mode con: cols=100 lines=40“);int i;b=InitGraph();Menu();cini;while(i!=5)switch(i)case 1:system(“cls“);Browser(Menu();break;case 2:system(“cls“);ShortestPath_DIJ(Menu();break;case 3:system(“cls“);Floyd(Menu();break;case 4:system(“cls“);Search(Menu();break;case 5:exit(1);break;default:
9、break;cini;/*/*定义景点编号，名称及简介*/MGraph InitGraph(void)MGraph G;int i,j;G.vexnum=10; /十个景点G.arcnum=14; /邻接矩阵for(i=0;ivexnum;v+)coutvexsv.numvexsv.namevexsv.introductionvexnum;v+)coutvexsv.numvexsv.namevexsv.introductionv0;if(v0G-vexnum)coutv0;if(v0=0for(v=0;vvexnum;v+)finalv=0;Dv=G-arcsv0v.adj;for(w=0;w
10、vexnum;w+)pvw=0;if(Dvvexnum;i+)min=INFINITY;for(w=0;wvexnum;w+)if(!finalw)if(Dwvexnum;w+)if(!finalwfor(x=0;xvexnum;x+) pwx=pvx;pww=1;for(v=0;vvexnum;v+)if(v0!=v) coutvexsv0.name;for(w=0;wvexnum;w+)if(pvwt+;if(tG-vexnum-1v+)coutvexsv.numvexsv.namevexsv.introductionvexnum;v+)for(w=0;wvexnum;w+)Dvw=G-a
11、rcsvw.adj;for(u=0;uvexnum;u+)pvwu=0;if(Dvwvexnum;u+)for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)if(Dvu+Duwvexnum;i+)pvwi=pvui|puwi;while(flag)coutkj;if(kG-vexnum|jG-vexnum)coutkj;if(k=0coutvexsk.name;for(u=0;uvexnum;u+)if(pkjucout“vexsj.name;coutvexnum;v+)coutvexsv.numvexsv.namek;if(kG-vexnum)coutk;if(k=0coutvexsk.numvexsk.namevexsk.introductionsetw(3)“endl;cout“endl;/Search end
