数据结构校园导航系统课程设计报告.doc

校园导航系统课程设计报告姓 名： 蒋小文 学 号：110236100123 班 级： 1班 专 业： 网络工程 指导教师：唐轶媛 蒋荣萍时 间：2012年7月5日 信息科学与工程学院目 录摘要.11. 目的.22. 要求.23. 题目.24. 任务 .2 1).需求分析.3 2).概要设计.4 3).详细设计.5 4).调试分析.85. 课设总结.186. 附录源代码.191. 目的 数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C（C+）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。2. 要求 2.1 课程设计时间为2周；2.2 设计语言C（C+）不限；2.3 课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。上机时带上源程序、数据结构教材、C语言教材。2.4 上机任务（1）选择并定义合适的数据结构；（2）根据程序所要完成的基本要求，设计出完整的算法；（3）设计出主程序（main函数），使其成为完整的程序。 2.5 上机时间：上午8:30-11:30，下午3:00-5:30 3. 题目题目：校园导航系统设计一个校园导游程序，后台操作：3.1、操作员信息管理如修改密码等3.2、能根据学校的规模进行添加景点信息、修改景点信息等功能，3.3、若临时有交通管制，能进行交通管制的设置和撤销（如某某时间段那条路进行那个方向的交通管制等）3.4、前台为来访的客人提供各种信息查询服务： 3.4.1、设计学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 3.4.2、为来访客人提供图中任意景点相关信息的查询。 3.4.3、提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。4. 任务4.1 需求分析 此系统使用者分为访客与管理员,访客按要求可直接使用本系统所具有的查询两景点间的最短距离,查询景点的相关信息.管理员按要求在输入密码的情况下,可修改登录密码,修改景点信息,添加景点,添加景点信息,交通管制,撤销交通管制,以及新建路径.4.1.1 登录:访客无需登录,首先将密码存在一个文件中,当输入的密码与从文件cipher.txt读取的密码相同,管理员方可进入后台管理员操作界面,4.1.2 修改登录密码:管理员进入后台操作管理员操作界面,若需改动当前的登录密码,首先必须要输入原密码,以确定是管理员自己修改密码.在原密码输入正确的情况下输入新密码,为了管理员更好的确人自己的新密码,必须两次输入的新密码一致(password1=password2)才可以修改成功.4.1.3 添加新的结点:若校园有新的景点出现,管理员须将新的景点的相关信息加入系统,将景点编号,名字,景点介绍这些信息写入存储景点信息的文件当中.原来已经有G.vernum个景点,是一个G.vernum行G.vernum列的矩阵,加一个景点后便是一个G.vernum+1行G.vernum+1列的矩阵,将新结点与其他存在的直接路径的结点之间的路径权值.存入邻接矩阵中,没有直接路径值的存一个无穷大的数(此系统用10000)于矩阵中,使得访客可以查询到新景点的相关信息和到达新景点的最短路径.4.1.4 修改景点信息:若学校某景点的信息有改变,管理员进入系统对景点的信息进行修改,从文件information.txt.中读取出景点信息,修改之后,再把信息存入information.txt中,使访客了解最新的景点信息.4.1.5 交通管制路径:当学校举办大型活动,或者大型考试的时候,对路进行交通管制,以确保活动的正常举行,从connect.txt 读取景点之间的邻接矩阵,将需要进行进行交通管制的路径赋值为一个无穷大的数(此系统用10000)来进行对路径的屏蔽作用.访客要到达目的地需要绕道而行.4.1.6 恢复撤销路径:在活动或者考试结束后,管理员需要对之前进行交通管制的路径进行撤销交通管制,此功能的实现过程与交通管制功能的实现过程刚好相反,将需要撤销的路径,将其路径值有10000改成其真实路径值,恢复正常的交通秩序.4.1.7 新建景点路径:学校可能考虑为了广大老师和学生的方面,可能会新建一些路径,例如国教楼和四坡食堂所建的风雨桥,管理员便需要把新建的路径加入系统,此功能的实现代码与撤销交通管制的路径完全相同,将景点的两路径值赋值为其真实值,存入connect.txt文件中.使得访客能够走最短的路径到达目的地,节省时间体力,减少不必要的麻烦.4.1.8 查询最短路径:访客无需密码可直接使用本系统,最为访客,总是希望以最少的时间和路程到达自己的目的地,利用弗洛伊德算法,求出最短路径,三维数组用来存储量景点最短路径的中间景点,二维数组用于存放两顶点间的路径长度.访客在输入自己的出发地点(或者当前所在地点),再输入目的地,方可在屏幕上显示出出发地点到达目的地的最短路径.4.1.9 查询景点信息:当访客进入广西民族大学时,当不知道该去哪个景点时,可利用本功能进行查询各景点的信息,从information.txt中将文件读取出来,然后将我们需要的景点信息显示出来,访客根据显示的信息选择自己感兴趣的景点.4.2概要设计1). 数据对象V：V具有相同特性的数组元素的集合，称为顶点集2). 数据关系R：R=VR VR=|P(x,y)(x,y属于V)ADT Graph 数据对象V：一个集合，该集合中的所有元素具有相同的特性 数据关系R：R=VR VR=|P(x,y)(x,y属于V). 基本操作:1.Void main()2.void Welcome();/开始欢迎界面3.void Select();/选择管理员和访客4.void InputPassword();/密码输入5.void Administer();/管理员操作6.int Increat_point_information();/增加景点信息7.void ChagePassword();/修改密码8.void AddPoint();/增加景点9.void DeletPath();/交通管制,删除路径10.void Cancel();/取消交通管制,恢复路径11.void NewPath();/新建路径12.int Initgraph();/初始化邻接矩阵13.void CorrectInformation();/修改景点信息14.void StartGuide();/访客界面15.int SearchPath();/查找最短路径16.void SearchInformation();/查找景点信息17.void Return();/返回主菜单18.int Read_sight_information();/读取景点信息文件19.void Remeber();/密码错误提示20.void Time();/时间停留21.void Goodbye();/退出系统4.3详细设计4.3.1校园景点路径平面图4.3.2总体流程4.3.3各主要功能伪代码;void main 1.欢迎使用本系统; 2. Select();/使用者选择自己是管理员/访客 3.退出本系统使用/密码输入Inputpassword password=从文件中读取密码 cincipher;/输入密码 if(cipher=password)coutcipher2if(cipher1=cipher2)coutpassword1;coutpassword2;if(password1=password2;)修改成功else修改失败;返回主菜单/增加景点信息int Increat_point_information()依次输入景点信息的编号,名称,信息存入number name information中;利用C+里的ios:app,在文件末尾追加信息/交通管制 void DeletPath()首先确定进行交通管制的路径相关联的两个景点编号i,j;读取矩阵文件connect.txt文件,将信息读取到二维数组中,对应于景点编号的位置的路径权值赋值为10000,用以屏蔽路径,表示进行交通管制单向交通管制:单向1 G.adjarcsij.adj=10000;单向2 G.adjarcsji.adj=10000;双向交通管制:G.adjarcsherethat.adj=G.adjarcsthathere.adj=10000存入文件即可/取消交通管制 void Cancel()实现过程与进行交通管制的实现方式正好相反,确定于取消路径相关联的两个景点标号,i j;路径长度weight;cinweight;G.adjarcsij.adj=G.adjarcsji.adj=weight;/新建路径void NewPath()实现代码与取消交通管制代码完全一致;/修改景点信息void CorrectInformation()从information中读取景点的编号,名称,介绍的相关信息outfileG.vexi.numberG.G.rmationarcsvw.adj;/把v,w路径的值放到Dvw中 v,w是，v,w路径上的景点，所以pvwv=1;pvww=1; 如果u到v,w之间的两条路径之和小于v,w之间的路径，则使Dvw=Dvu+Duw 若i是v,u上的最短路径的景点，或是u，w之间最短路径的景点，则i是v,w之间最短路径上的景点int flag=1；while(flag) 输入出发点和目的地的编号:k, jif(kG-vernum|jG-vernum)景点编号不存在!请重新输入出发点和目的地的编号:k, j if(k=0&k=0&j顶点数目) flag=0; 逐个输出最短路径上的景点名字以及总路线长/查询景点信息void SearchInformation()从information将全部的数据读取出来请输入要查询的景点编号n;if(nG.vernum)该景点不存在，请重新输入：else 根据编号输出对应的景点信息；4.4调试分析4.1.密码输入正确:4.2.密码修改成功:例:(将原密码wwww改为aaaa)4.3.添加景点和景点信息:例:把八坡侧门加入景点添加前:添加过程:添加后,information.txt和connect.txt里面的内容自动修改为:景点和景点信息添加成功4.4.交通管制:例:(对2(大礼堂)-4(图书馆)的路进行管制)交通管制前:管制过程:管制之后:4.5撤销交通管制:例(撤销(2大礼堂)-4(大礼堂)的路径管制)恢复前:撤销管制过程:撤销管制之后:4.6新建路径:例:(在1(南门)-5(科技馆)新建一条长300米的路径)新建前:connect.txt的内容:新建过程:新建后:4.7修改景点信息:例:(将0(东门)的信息改为相思湖大酒店)4.8.查询景点信息:(例:查找刚刚新修改的0相思湖大酒店信息)4.9.查询最短路径:例:(查询1(南门)-9(9坡)的最短路径:5. 课设总结: 这是第二次做课程设计了，但却使我感到什么是真正的编程，如何做一个项目，如何开始，如何进行，如何高效率的完成它。这次指导老师对我们十分的严格，要求我们按照软件工程的要求来，虽然一开始我们十分的不适应，可是我们最终坚持下来了，经历了这个过程，对这门学科有了更深入得了解。 要做好一个项目，从需求分析到数据采集到概要设计到详细设计，都要求在我的脑海里有个大概并清晰地思路和想法。同时，在这次程序设计中，我基本上能够按照正确的流程进行，没有一开始就写程序，这也是自我感觉进步最大的地方了，拿到题目的那一个早上的时间我用来整理出正确的逻辑思路，然后再进行详细的程序设计：先进行需求分析，然后概要设计，然后详细设计，最后写程序，然后调试程序。我越来越感觉到一个优秀的程序员，一定要有十分扎实的基本功，这次课程设计，我发现自己还有很多地方不是很熟练，多次查阅书本、从最基本的定义着手才完成了它。通过本次课程设计，我对图的概念有了一个新的认识，在学习了数据结构这门课程之后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。 数据结构是一门基础课，今后很多的学科都要用到它，通过这次课程设计，我发现它又对我们的编程能力要求很高，因此我认为要真正的学好它，就要经常地上机，不断地练习，只有这样，才有可能完全掌握它。现在，我才发现老师这一学期为什么对我们这么的严格，每次实验要求按时上交，并独立完成，而且每次上交实验的时候也是按照课程设计的要求,会询问我们一些有关实验的问题,对于不懂的地方,就会指出,要求我们自己查阅资料完成之后再上交,容不得半点马虎,我想就是因为老师给了我们这么多机会和作业，我们在做课程设计时才没感到束手无策。 刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。 这次课程设计，自己熟悉了很多的东西，在编写程序的过程中，自己发现了很多的问题，并通过查阅资料，反复实践予以解决，这就使得自己发现问题、解决问题的能力得到了提升。课程设计多做几次，我想它就不是那么陌生、那么可怕了，自己会在这个过程中不断上手。正如一位伟人说的那样，自己的知识越多，越是感到未知越多。这次课程设计，我发现了很多过去遗留的问题，和有待解决的问题。这些问题在期末考试中没有涉及，可并不代表我们真正掌握了。还是亲自动手可以发现问题解决问题。很多时候不亲自动手，就会忽略很多的问题。其实自己现在掌握的东西还是很少的，这次课程设计，我查阅了很多的书籍，发现要学好这门课并真正掌握它，绝非一朝一夕之事，还要下功夫学习其他相关知识。为了扩充自己的知识，更好地掌握软件专业的知识，增加知识的深度和宽度，不断完备知识的储备。除此之外，我还要学习其他与之相关的知识，只有牢牢地掌握这些，才会有更多的发展空间。 我现在越来越喜欢这门学科了，认为自己两年前的选择是没有错的，这个专业也是很有前途的，我相信只要自己的基本功扎实，就会获益匪浅。在这次课程设计中，我还是发现了自己的很多不足，我发现自己的效率不是很高，很多优秀的同学没用到半周就完成的差不多了，而自己却要用到6天左右的时间。还有一点就是，自己的耐心不足，遇到问题以解决不了，就心烦气躁，往往一下午没有很大的进展。这些暴露的问题我会在以后的学习和生活中逐渐解决，希望在以后的学习和生活中老师可以严格要求我，使我不断克服问题，提高专业技能。6. 附录源代码/headfile.h#include #include #include #include #include #include stdlib.h#include time.husing namespace std;#define max_ver_num 100#define A 10000 int Initgraph();int Increat_point_information();void Welcome();void Select();void InputPassword();void StartGuide();void Administer();void ChagePassword();void AddPoint();void Return();void CorrectInformation();void DeletPath();int Read_sight_information();void SearchInformation();void Remeber();void Time();void ShortestPath_DIJ();void Cancel();void NewPath();void Goodbye();typedef struct int data; int t; int fisrt;Node;typedef struct verdata/景点信息char number5;char name20;char information1000;po;typedef struct Arcnode/设置边的权值信息 int adj;/路径权值Arcnode;typedef struct MGr /图关系 verdata vexmax_ver_num; Arcnode adjarcsmax_ver_nummax_ver_num; int vernum;MGraph;/main.cpp#include #include #include #include #include #include stdlib.h#include headfile.hMGraph G;using namespace std;time_t now;/主函数int main()time(&now);cout现在的时间是 ctime(&now); Welcome();Select();return 0;/欢迎void Welcome() /cout现在的时间是 ctime(&now);cout-endl;cout 欢迎光临广西民族大学 endl;cout - endl;cout 广西民族大学信息科学与工程学院软件学院 endl;cout 校园导航系统为你服务 endl;cout - endl; cout - endl;cout 程序员：10网络蒋小文 endl;cout-endl; system(pause);system(cls);/开始页面void Select()char choice; cout-endl; cout 1.导航使用者 endl;cout 2.系统管理员 endl;cout 3.退出此系统 endl; cout-endl;coutchoice;system(cls);switch(choice) case 1:StartGuide(); break; case 2:InputPassword(); break; case 3: Goodbye(); break; default: cout-endl; cout你的输入有误endl; cout-endl; system(pause); system(cls); Select();/Admin.cpp#include #include #include #include #include #include stdlib.h#include headfile.hextern MGraph G;using namespace std;/后台 输入密码，加景点，加信息 改信息 改密码 删路径void InputPassword()int m=0;string password;string c; system(CLS);ifstream infile(cipher.txt);infilec; while(m3) coutpassword; if(c=password) cout-endl; cout 密码正确 进入管理系统 endl;cout-endl;cout自动跳转中.;Time();system(cls); Administer(); else cout-endl;cout密码错误！endl;cout-endl;cout还有2-m次机会endl;cout-endl;m+;cout自动跳转中.;Time();system(cls); Remeber();void Administer()char choice; Initgraph();cout-endl;cout 1.修改登录密码 endl;cout 2.添加新的景点 endl;cout 3.修改景点信息 endl;cout 4.交通管制路径 endl;cout 5.恢复撤销路径 endl;cout 6.新建景点路径 endl; cout 7.返回导航主页 endl;cout-endl;coutchoice;/system(cls);switch(choice)case 1: ChagePassword(); break;case 2: AddPoint(); break;case 3: CorrectInformation(); break; case 4: DeletPath(); break;case 5: Cancel(); break; case 6: NewPath(); break;case 7: Return(); break;default:cout-endl;cout你的输入有误endl;cout-password;infile.close();cout-endl;coutc;cout-endl;if(c=password)cout原密码输入正确endl;cout-endl;coutnewpasswrod1;cout-endl;coutnewpasswrod2;cout-endl;if(newpasswrod1=newpasswrod2) ofstream outfile(cipher.txt); outfilenewpasswrod2; outfile.close(); cout密码更改成功，登录时请用更改后的密码endl;elsecout两次输入的密码不相同endl;elsecout原密码输入错误endl;cout自动跳转中.endl;Time(); system(cls);Administer();void Remeber()cout-endl;cout你已经连续三次输入密码错误了endl;cout-endl; cout请认真核对密码，稍后再试！endl;cout-endl;Time();cout自动返回主菜单endl;Time();system(cls);Select();void AddPoint()system(cls);cout添加景点endl;Increat_point_information();G.vernum=Read_sight_information();ifstream infile(connect.txt); for(int i=0;iG.vernum-1;i+)for(int j=0;jG.adjarcsij.adj;/*for(i=0;iG.vernum-1;i+)for(int j=0;jG.vernum-1;j+)coutsetiosflags(ios:left)setw(5)G.adjarcsij.adj ;coutendl;*/infile.close();/cout每次添加景点个数为1个;for(int m=0;mG.vernum;m+)G.adjarcsmG.vernum-1.adj=10000;for(int n=0;nG.vernum;n+)G.adjarcsG.vernum-1n.adj=10000;G.adjarcsG.vernum-1G.vernum-1.adj=0;cout你正准备添加一个新结点endl;cout-endl; cout请输入此景点与其他景点存在的路径权值endl;cout-endl;char yn;doint Spots_N,Weights;coutSpots_N; coutWeights;G.adjarcsG.vernum-1Spots_N.adj=G.adjarcsSpots_NG.vernum-1.adj=Weights;cout是否与其他景点存在直接路径值(y/n)yn;while(yn=y|yn=Y); ofstream outfile0(connect.txt);for(int v=0;vG.vernum;v+)for(int w=0;wG.vernum;w+) outfile0G.adjarcsvw.adj ; outfile0endl;outfile0.close(); cout添加成功endl;Time();system(cls);Administer();int Increat_point_information()/添加景点信息 char number2,name20,information10000;coutnumber; coutname; coutinformation; ofstream outfile(information.txt,ios:app);outfileendlnumber name information;outfile.close(); return 0;void CorrectInformation()int n;char m;system(cls); G.vernum=Read_sight_information();coutn; coutG.vexn.number;coutG.;coutG.rmation;ofstream outfile(information.txt);for(int j=0;jG.vernum-1;j+)outfileG.vexj.number G. G.rmationendl;outfileG.vexG.vernum-1.number G.vexG. G.vexG.rmation;outfile.close();cout数据修改成功endl;coutm;if(m=y|m=Y)ifstream infile(information.txt);for(int i=0;iG.vexi.numberG.G.rmation;coutG.vexi.number G. G.rmationendl;infile.close();system(pause);system(cls);elsecout自动跳转中.endl; Time(); Administer();void DeletPath() system(cls);cout-endl;cout交通管制endl;cout-endl; G.vernum=Read_sight_information();ifstream infile(connect.txt); for (int i=0;iG.vernum;i+)for(int j=0;jG.adjarcsij.adj;cout你想对哪两个结点间的路径进行管制？endl;int here,that;couthere;coutthat;cout请问你是删除单项的还是双向的路径：;cout1.单向 2.双向direction;switch(direction)case 1: char choice;cout管制herethat选择 1endl;cout管制thathere选择 2choice; switch(choice) case 1:G.adjarcsherethat.adj=10000;break; case 2:G.adjarcsthathere.adj=10000;break; default:cout输入错误endl;DeletPath(); break; case 2: G.adjarcsherethat.adj=G.adjarcsthathere.adj=10000; break; default: cout输入错误endl; DeletPath();ofstream outfile(connect.txt);for(int v=0;vG.vernum;v+)for(int w=0;wG.vernum