数据结构课程设计-校园导航

1、课程设计报告课程名称数据结构课程设计题 目校园导航指导教师设计起始日期5.95.16学 院系 别学生姓名班级/学号成 绩需求分析本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。设计要包 括下列要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。本课题实现校园多个场所（至少10个）的最短路径求解。（1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。（2 ）输出的形

2、式：输出则通过已有的信息数据，通过相关的操作输出相应信息。（3）程序所能达到的功能：本程序可供任何人使用，主要功能1.浏览各单位及简介;2. 查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。a.首先看到的是校园导航系统的菜单：北京信息科冠学大学导游图地 #的 简路目息 占需点信 旦看售绕 喬岀景系 戲-S俺滴_腿 12 3 4 5蓟 ion-：b.查看浏览路线等待输入起始景点:请输入一个起始景点编号:C.选择出发点与目的地 等待输入起始景点与目的地编号:请输入岀发点和目的地的编号（用空格隔开）:

3、d.参看景点信息等待输入景点编号:请输入要查询的景点編号=二、概要设计本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。 主程序为整系统的入口处， 菜单主要实现显示系统功能， 显示信息 主要实现显示景点信息， 弗洛伊德算法主要实现求两景点之间最短路径， 迪杰斯特拉算法实 现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。系统首先通过主程序调用 void mai n(); 进入系统主菜单函数，根据用户的选择可分别 进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径； 4.查看景点信息；5.退出系统。选择“

4、浏览各景点及简介”项，显示十个景点的有关信息，包括景点编号，景点名称， 景点简介。选择“查看所有游览路线”项，会进入输入起始景点编号的界面，输入正确编号后会显示起始景点到其余九个景点的最短路线的方案。选择“选择出发点和目的地”项，会进入输入起始景点与目的景点的界面，输入起始景点与目的景点，并有空格隔开就得到两景点之间的最佳路径。选择“查看景点信息”项，会进入输入要查看的景点的界面，如入后会显示该景点的有关信息。选择“退出系统”项，就会退出程序。15三、详细设计(1 )十三个单位的图0:前门1 :图书馆2 :教二楼3:实验楼4 :操场5:教一楼6 :食堂7:水房&学一公寓9 :学二公寓1

5、0:学三公寓11:学四公寓12:后门(2 )主程序流程图:(3)弗洛伊德的算法：void Floyd(MGraph *G)in t v,u,i,w,k,j,flag=1,p101010,D1010;定义参数for(v=0;v<G->vex nu m;v+)for(w=0;w<G->vex nu m;w+)Dvw=G->arcsvw.adj;for(u=0;u<G->vex num ;u+)Pvwu=0;if(Dvw<INFINITY)pvwv=1;pvww=1;for(u=0;u<G->vex num ;u+)for(v=0;v<

6、;G->vex nu m;v+)for(w=0;w<G->vex nu m;w+)if(Dvu+Duw<Dvw)Dvw=Dvu+Duw;for(i=0;i<G->vex nu m;i+)pvwi=pvui|puwi;while(flag)cout<<"请输入出发点和目的地的编号(用空格隔开)："；cin> >k»j;if(k<0|k>G->vex nu m|j<0|j>G->vex num)/判断输入的景点编号正确与否cout<<"景点编号不存在！

7、请重新输入出发点和目的地的编号:"cin> >k»j;if(k>=0&&k<G->vex num&&j>=0&&j<G->vex num)flag=0;输出景点名称输出路线输出总路线长度cout<<G->vexsk. name;/for(u=0;u<G->vex num ;u+)if(pkju &&k!=u&&j!=u)/cout<<"->"<<G->vexsu.

8、 name; cout<<"->"<<G->vexsj. name; cout<<"总路线长"<<Dkj<<endl; / 四、调试分析(1)在程序设计中遇到了输出景点信息的表不整齐，用setw ()解决了；默认的界面太小，不能完整的看到输出信息，用了system("mode con: cols=100 lin es=40")命令语句设置了行数和列数。(2)经验和体会经过一段时间来的努力，终于初步实现系统功能，但肯定还存在不少漏洞。这是我们第三次做课程设计，也是第

9、三次编写一个比较完整和具有一定功能的的系统代码，第二次几个人合作制作系统， 制作过程中存在储多的不足，遇到过许多的困难，曾经灰心丧气过，但是最终还是坚持了下来，虽然做得不怎么样，但我们已经努力地去做了，由于基础也不怎么扎实，所以困难会比其它组更多更艰巨。刚开始做系统缺乏全局观念，分工也不是很合理， 做得很零碎，所以在组合的时候也出现了很多问题。五、使用说明和测试结果打开系统，首先会进入系统的主菜单：1. 浏览各景点及简介2. 查看所有游览路线3. 选择出发点和目的地4. 查看景点信息5. 退出系统用户可以进行如下操作：1、 如果你想浏览各景点及简介的话，请输入“1”，并回车。此时界面上将显示出

10、各景 点的编号、名称及其简介。2、如果你想查看某一景点的所有游览路线，可选择 2操作。输入“ 2”，并回车。此时， 系统会提示你输入某景点的编号。输入编号后，回车，便可以看到该景点的所有游览路线。若输入的景点编号错误就会有提示重新输入。3、 如果你想查看两个景点之间的最短路线的，可选择3操作。输入“ 3”，并回车。此 时，系统会提示你要输入起始景点与终点的编号。输入编号后，回车，此时，便可以见到这 两个景点之间的最短路径。4、 如果你想查看具体某些景点的简介及信息，可以选择4操作。输入“ 4”，并回车。此 时，系统会提示全部景点的对应的编号，选择你要查看的景点信息，输入其编号，回车，此时，屏幕

11、上将会显示出该景点的各种信息。若输入的景点编号错误就会有提示重新输入。5、在主菜单键入“ 5” ，退出程序。测试结果1、菜单界面北京信息科技大学大学导游图g的 简路目和息 点游点信 旦看售绕出最系 s看出 胡倍遥佶.$ 12 3 4 5pt ion：2、进入“浏览各景点及简介”后，输出景点信息的界面。3、进入“查看所有游览路线”，显示输出景点编号为 0的景点到其余九个景点的最佳 路线。请图图E图图图图图图输frrrrr-Trrrfrn-、rr个一始是点编号曲 M门十歸线畑总路线长阴4路线长讯-教一楼总路线长"0总路线长凶 冰届息卫靠戋长盹_那展 _学1給寓帛蹈线任盹一赫馬、-厂圧?公

12、寓一2学二荃鬣忌路线长4、进入“选择出发点和目的地”，输入出发点1和目的点9后输出的的最佳路线的界 面。轉岀瞬瞬地魅綢彎豐二決.公寓一注金寓总路线炖5、进入“查看景点信息”，输入要查看的景点编号，输出景点信息的界面。请输入要查询的景点编号汐翹名称1$自动卅系统6、输入要查询的景点编号错误，提示重新输入。7、退出程序界面。六、心得体会做一个系统之前还应该做好全面的安排，对一个系统的整个流程及功能实现有一个很好的统筹，几个人合作的功能可拆才拆，不可则由一个人主要负责，其它人帮忙思考，出意见，做系统之前几个人必须先做对系统做一次较详细的探讨研究，然后才开始分工，一个阶段后组员应互相交流情况，以达到一

13、致。另在遇到困难时组员不能解决，应查资料或问其它懂的同学，参考一下意见，再结合自己的想法，最后实现自己想实现的功能。七、附录#define INFINITY 10000/* 无穷大 */#define MAX_VERTEX_NUM 40#define MAX 40#include <stdlib.h>#include <string.h>#include <iostream>using namespace std;#include <iomanip>typedef struct ArCellint adj; /路径长度ArCell,AdjMatr

14、ixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction100; / 简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;MGraph b;MGraph lnitGraph( void );void Menu( void );void Browser(MGraph *G);void Shortes

15、tPath_DIJ(MGraph * G);void Floyd(MGraph *G);void Search(MGraph *G);*/* void main( void ) system( "color 1f");system( "mode con: cols=100 lines=40" );int i;b=InitGraph();Menu();cin>>i;while (i!=5)switch (i)case 1:system("cls" );Browser(&b);Menu();break;case 2:s

16、ystem("cls" );ShortestPath_DIJ(&b);Menu();breakcase 3:system("cls" );Floyd(&b);Menu();break;case 4:system("cls" );Search(&b);Menu();break;case 5:exit(1);break;default : break ;cin»i;/*定义景点编号，名称及简介*/MGraph lnitGraph( void )MGraph G;int i,j;G.vexnum=10;/

17、十个景点G.arcnum=14;/ 邻接矩阵for （i=0;i<G.vexnum;i+）G.vexsi.num=i;/各景点的代码，名称及简介strcpy（G., "前门 "）;strcpy（G.roduction,"面南.对面为北京外国专家大厦"）;strcpy（G.,"图书馆”）；strcpy（G.roduction,"藏书几十万册，设施良好，一二楼均有阅览室"）;strcpy（G.,"教二楼”）；strcp

18、y（G.roduction,"学校的主要教学楼，共六层，有多个专业实验"）;strcpy（G.,"实验楼"）;strcpy（G.roduction,"紧邻教二楼，共七层，主要为公共实验室，六层有通宵自习室”）;strcpy（G.,"操场 "）;strcpy（G.roduction,"全新塑胶跑道，中间为人工草皮足球场，排球场和篮球场"）;strcpy（G., "教一楼”）；strcp

19、y（G.roduction,"学校各机关单位办公楼和双语教室"）;strcpy（G.,"食堂"）;strcpy（G.roduction,"标准食堂，两层，清洁卫生"）;strcpy（G.,"水房 "）;strcpy（G.roduction,"配备自动刷卡系统"）;strcpy（G.,"学一公寓”）；strcpy（G.roduction,"光电通信

20、学院男生公寓"）;strcpy（G.,"学二公寓”）；strcpy（G.roduction,"女生公寓"）;strcpy（G., "学三公寓”）；strcpy（G.roduction,"计算机学院男生公寓"）;strcpy（G.,"学四公寓”）；strcpy（G.roduction,"大一新生公寓"）;strcpy（G.,"后门"）;

21、strcpy（G.roduction,"面北，对面有便利的小超市"）;for （i=0;i<G.vexnum;i+）for （j=0;j<G.vexnum;j+）G.arcsij.adj=INFINITY;/各景点之间的距离，没有的均为无穷大G.arcs01.adj=50;G.arcs02.adj=100;G.arcs15.adj=20;G.arcs16.adj=75;G.arcs23.adj=10;G.arcs25.adj=60;G.arcs34.adj=20;G.arcs411.adj=30;G.arcs5 6.adj=30;G.arcs

22、 67.adj=10;G.arcs78.adj=20;G.arcs89.adj=10;G.arcs910.adj=20;G.arcs1012.adj=120;G.arcs1112.adj=150;for （i=0;i<G.vexnum;i+）for （j=0;j<G.vexnum;j+）G.arcsji.adj=G.arcsij.adj;return G;/*/主菜单（显示输入提示）/*11"vve ndl;1 1.浏览各景点及简介| "vvendl;1 2.查看所有游览路线| "vvendl;1 3.选择出发点和目的地| "vvendl;1

23、 4.查看景点信息| "vvendl;1 5.退出系统| "vvendl;11"vve ndl;北京信息科技大学大学导游图" vvendl;显示景点编号、名称、简介简介void Menu()coutvv"coutvv"coutvv"coutvv"coutvv"coutvv"coutvv"coutvv"coutvv "Option-:"/*void Browser(MGraph *G)int v;coutvv"-i " vvendl;co

24、utvv" |编号|景点名称"vvendl;for (v=O;vvG->vexnum;v+)coutvv" | "vvG->vexsv.numvvsetw(5)vv "vvG->roductionvvsetw(3)vv"| " vvG->vvsetw(10)vv " |"| "vvendl;coutvv""vvendl;/*迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径，v0为起点*void ShortestP

25、ath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0;int final20, D20, p2020;coutvv"-i " vvendl;coutvv" |编号|景点名称简介"vvendl;for (v=0;vvG->vexnum;v+)coutvv" | " vvG->vexsv.numvvsetw(5)vv"vvG->roductionvvsetw(3)vv"| " vvG->vvsetw(1

26、0)vv " |"| "vvendl;coutvv""vvendl;while (flag)coutvv "请输入一个起始景点编号："；cin»vO;if (vO<O|vO>G->vexnum)coutvv"景点编号不存在！请重新输入景点编号cin>>vO;if (vO>=O&&vO<G->vexnum)flag=O;for (v=O;v<G->vexnum;v+)finalv=0;Dv=G->arcsvOv.adj;for

27、 (w=O;w<G->vexnum;w+)pvw=0;if (Dv<INFINITY)pvv0=1;pvv=1;Dv0=0;finalv0=1;for (i=1;i<G->vexnum;i+)min=INFINITY;for (w=O;w<G->vexnum;w+)if (!finalw)if (Dw<min)v=w;min=Dw;finalv=1;for (w=O;w<G->vexnum;w+)if (!finalw&&(min+G->arcsvw.adj<Dw) Dw=min+G->arcsvw.

28、adj;for (x=O;x<G->vexnum;x+)pwx=pvx;pww=1;for (v=O;v<G->vexnum;v+)if (vO!=v) cout<<G->vexsvO.name;for (w=O;w<G->vexnum;w+)if (pvw&&w!=vO) coutvv"->" v<G->;t+；if (t>G->vexnum-1 &&v0!=v) coutvv总路线长"vvDvvvendl;/* Floydp函

29、数 */void Floyd(MGraph *G)int v,u,i,w,k,j,flag=1,p101010,D1010;coutvv"-i " vvendl;coutvv" |编号丨景点名称"vvendl;简介for (v=0;vvG->vexnum;v+)coutvv" | "vvG->vexsv.numvvsetw(5)vv"vvG->roductionvvsetw(3)vvcoutvv" 111I " vvG->vvsetw(10)v

30、v " |I "vvendl;"vvendl;for (v=0;vvG->vexnum;v+)for (w=0;wvG->vexnum;w+)Dvw=G->arcsvw.adj;for (u=0;uvG->vexnum;u+)Pvwu=0;if (DvwvlNFINITY)pvwv=1;pvww=1;for (u=0;uvG->vexnum;u+)for (v=0;vvG->vexnum;v+)for (w=0;wvG->vexnum;w+) if (Dvu+DuwvDvw)Dvw=Dvu+Duw;for (i=0;ivG

31、->vexnum;i+)P【v【w【i=p【v【u【i|p【u【w【i;while (flag)coutvv "请输入出发点和目的地的编号(用空格隔开) ："cin»k»j;if (k<O|k>G->vexnum|j<O|j>G->vexnum)coutvv "景点编号不存在！请重新输入出发点和目的地的编号cin>>k>>j;if (k>=0&&k<G->vexnum&&j>=0&&j<G->vex