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

《数据结构课程设计报告校园导游系统.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告校园导游系统.doc（24页珍藏版）》请在三一办公上搜索。

1、经济管理学院本科课程设计论文数据结构课程设计学 号： 10051701089 姓 名： 班 级： 管理101 专 业： 信息管理与信息系统 系 别: 指导教师： 目 录目 录I第1章 校园导游问题- 1 -1.1需求分析- 1 -1.1.1课程设计的目的- 1 -1.1.2程序的主要功能体现- 1 -1.1.3数据测试- 1 -1.2概要设计- 1 -1.2.1功能设计- 2 -1.2.2抽象数据类型定义- 5 -1.3系统的主要界面设计及运行说明：- 6 -1.3.1界面设计- 6 -1.3.2调试分析- 9 -1.4总结- 9 -第2章 约瑟夫问题- 10 -2.1需求分析- 10 -2.

2、1.1课程设计的目的- 10 -2.1.2程序的主要功能体现- 10 -2.1.3数据测试- 10 -2.2概要设计- 11 -2.2.1用循环链表存储结构解决约瑟夫问题- 11 -2.2.2用线性表存储结构解决约瑟夫问题- 13 -2.2.3用循环队列储存结构解决约瑟夫问题- 15 -2.3系统的主要界面设计及运行说明：- 17 -2.4.实验总结：- 19 -参考文献- 20 -第1章 校园导游问题1.1需求分析1.1.1课程设计的目的此次课程设计的主要内容是校园导游系统，所谓系统其实也不尽然，只不过是个小小的提示，为来访的客人提供各种信息查询服务。现在大多数的学校由于不断的扩张，这也就使

3、得学校不得不建立的更大。这也就为人们拜访学校造成了很大的不便。人们往往不熟悉学校，找个东西，或某处带来了极大的不便。往往要花很多时间在这一方面。然而要是有一个学校导游系统这将给乘客带来极大的方便，使人们一下就能了解到这个学校的大致情况主要包括：查看学校的全景图各个景点的简介学校主要景点的分布查看某一景点到其它所有景点的最短路径查询任意两个景点之间的最短路径。1.1.2程序的主要功能体现对于功能的输入形式是没什么要求的，主要就是根据菜单的提示输入相应的数字选择相应的功能；对于功能的输入形式的要求也比较简单，要查询某一景点的简介直接输入其对应的编号即可；对于功能的输入形式的要求同功能；对于功能只需

4、要输入想要查看的起始景点的编号即可；对于功能只需要输入起始景点和目的景点的编号即可。此程序在输入形式上都没什么特殊的要求只是一些简单的数字就可以搞定一切。功能就是输出由字符构成的一幅简易图，形式比较单一；景点的简介方面输出景点的简单信息就可以了；要查询最短路径的话输出的自然是从起始景点到目的地的最短路径中所途经的各个景点及距离。本程序所能达到的功能就是前面所提到的中的功能。1.1.3数据测试当选择i时进行的是查询系统；当选择5号所代表的景点时所显示的主要内容为：当选择s时进行的是最短路径的查询；当选择5和4所代表的景点时所显示出的最短路径为：1.2概要设计1.2.1功能设计该校园导游问题我总共

5、设计了八个旅游景点分别为校园北门、主楼、二教、三教、三食堂、体育馆、石头楼、大学生活动中心，每个景点间之间相连的距离已知，通过计算来得出各个景点之间要到达所需要的最短距离，又或是在某条路径上走过所经过的所有景点。并且对各个景点有做了一些相关的介绍以便旅游观光者能更好地选择自己感性趣的景点进行游赏。不论你目前在哪个景点哪道路上,都可以通过校园导游查询到达你所想去的任何一个地方！为了方便把路径分为三个部分，从进入校园开始在，再以走出校园为止。而这部分的描述会在下面给出！具体景点示意图如下：图1-1校园主要景点示意图1.学校北门3.三教5.三食堂2.体育馆4.二教6.大学生活动中心7.石头楼8.主楼

6、 为了使广大朋友更能清楚明析的了解本校的主要景点之间的连接，距离绘出了下面的表格，该表格主要是为了描述各个景点之间的最短距离： 表1-1校园各景点之间最短距离起点终点最短距离1.校园北门 2.体育馆25 3.三教104.二教345.三食堂156.大学生活动中心537.石头楼478主楼552.体育馆 3.三教354.二教495.三食堂406.大学生活动中心487.石头楼428主楼393.三教4.二教245.三食堂256.大学生活动中心637.石头楼578主楼654.二教5.三食堂496.大学生活动中心507.石头楼568主楼685.三食堂6.大学生活动中心387.石头楼328主楼446.大学生活

7、动中心7.石头楼68主楼187.石头楼8主楼12在本题中我主要设置了三个路径，都是以校园北门为首得到的，因此各个路径上所经过的景点如下表： 图1-2途经的景点路径编号途经的景点（1）校园北门三教二教大学生活动中心石头楼三食堂校园北门（2）校园北门体育馆主楼石头楼三食堂校园北门（3）校园北门三教二教大学生活动中心石头楼主楼体育馆校园北门1.2.2抽象数据类型定义各景点的相关数据定义#define MaxVertexNum 50 /*景点个数最大50*/#define MAXCOST 1200 /*定义路径的无穷大*/#define T 8 /*目前景点个数*/typedef struct cha

8、r name20; /*景点名称*/ char number15; /*景点代号*/ char introduce100; /*景点简介*/Elemtype;typedef struct int num; /*顶点编号*/ Elemtype date; /*顶点信息*/Vertex; /*定义顶点*/typedef struct Vertex vexsMaxVertexNum; /*存放顶点的一维数组,数组第零个单元没有用上*/ unsigned int edgesMaxVertexNumMaxVertexNum; /*存放路径的长度*/ int n,e;MGraph;MGraph MGr;

9、/*全局变量,定义MGr为MGraph类型*/int shortestMaxVertexNumMaxVertexNum; /*定义全局变量存贮最小路径*/int pathMaxVertexNumMaxVertexNum; /*定义存贮路径*/对于校园导游问题，在本程序中主要定义了几个主要类型，有上述代码可见其主要类型如下：（1）定义了景点个数最大值！本程序中假设为50。（2）定义路径的无穷大！在本程序中假设为1200。（3）定义了目前景点个数！在本程序中主要设计了8个景点。（4）定义景点，主要是定义了各个景点的名称代码简介等。（5）定义了各个代表景点顶点的编号信息和顶点的定义。1.3系统的主要

10、界面设计及运行说明：1.3.1界面设计 这次的运行是运用了Vissual C+进行检测的！因此当进入用户界面时会显示出查询的方法，通过进行选择不同的字母进行不同的选择，当选择i时进行的是信息查询！当通过选择s时进行的是最短路径查询！当通过选择两个不同的（1到8）数字时进行的是两个景点之间的最短路径查询！通过选择e退出查询！在本次的运行中，我的主要运行过程在下面也会体现。该程序的主要运行界面如下： 当将程序输入后点击F5在没有错误的前提下就进入查询系统，如下就是进入该系统的界面：主要显示了各个选择，你想要查找那个想知道的信息时，就可以根据不同的选择达到你的要求！ 当选择i时进行信息查询主要显示如

11、下： 当选择序号5所所代表的景点时所显示的查询结果如下： 当选择s时进行的是最短路径查询 当选择5与4所代表的景点时所显现出的最短路径的查询结果如下：1.3.2调试分析 整个程序的运行还算良好！经过几次的调试运行使得整体来看较成功不过有许多的知识还是需要我们自己去查找的！总之就是一句话“耐心加细心再加上灵活”就能很好地完成你所想做的事情！1.4总结 这次课程设计给我的感触很多，课程设计没开始之前我总是在想今年的课程设计会不会象去年那样辛苦，但是这两周下来我当然也感到累，也有心情烦躁的时候，体会到调试成功使的那种喜悦。 课程设计之前老师让我们自己先将设计思路写好，都做了哪些模块，第一天要检查。我

12、当时是在电脑上写了，那天下午编了一下午，没什么成就弄得我很心烦，再想到快要考试，那种急于求成的心更迫切，自己很难平静。第二天老师检查时我什麽都没有看到同学的程序我开始着急了，但那会我只有一个念头我得从新开始，由于对图不是很了解，我就从读写模块开始，就使用简单的C语知识，那天早上将那两个模块给拿下了。下机后我在寝室开始编程，开始进入真正的图部分，边思考怎样可以将它们联系起来，边进行调试。对编程兴趣很浓，直到晚上十点我已经将老师的要求完成差不多。 我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构。这些日子是很辛苦，但我学到了很多东西，

13、和同学一起分享调试成功的那种喜悦，我完成的早，同学有问题会让我帮助，在帮他们的过程中我也学会了很多种不同的思想，让我对图有了更深刻的理解。数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。从课程性质上讲，数据结构是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确意读，符合软件工程的规范。如果说高级语言程序设计的训练过程

14、，要进行了结构化的程序设计的初步训练的话，那么数据结构就要培养我们的数据抽象能力。本次设计其实就是数据结构中图类的问题。将校园景点作为图的结点，将景点间的路径作为图的边，路径距离作为边的权值。这样一来，求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。这也是计算机代替人工的一个实例，也是软件工程必不可少的基础。第2章 约瑟夫问题2.1需求分析2.1.1课程设计的目的 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5

15、时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。2.1.2程序的主要功能体现 系统结构图本程序有四个功能模块，包括三个解决约瑟夫问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。图1-1 约瑟夫问题循环单链表储存结构线性表储存结构循环队列储存结构退出2.1.3数据测试 当选择不同（1到4）的序号时进行了不同的方法运算，在此次运行中分别选择了不同的方法进行了测试！假设士兵的人数n=10时，死亡人数到5为

16、止时运行的结果的为：2.2概要设计2.2.1用循环链表存储结构解决约瑟夫问题2.2.1.1 功能设计具体简介如下：以单循环链表为存储结构，包含三个模块： 1.主程序模块 包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。2.构造链表并初始化构造链表，给每个结点赋值，给队员编号。3删除当报数到死亡数字时队员出列去执行任务，删除该节点。2.2.1.2抽象数据类型定义创建循环链表 typedef struct node int data; struct node *next;LNode;/* 定义结点类型 */LNode* CREAT(int n) /* 创建循环链表 */ LNode

17、*s,*q,*T; int i; if(n!=0) T=q=(LNode *)malloc(sizeof(LNode); q-data=1;/* 生成第一个结点并使其data值为1 */ for(i=2;inext=s; q-next-data=i;/*赋值*/ q=q-next; q-next=T; return T;2.2.1.3 算法流程图开始声明类型定义变量并初始化初始化单链表循环模块输入敢死队员总数剩下的队员数1?队员报数报数值=死亡数?队员出列输出结果2.2.2用线性表存储结构解决约瑟夫问题2.2.2.1功能设计具体简介如下：功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数

18、据结构,并运用模块化的程序设计思想,算法的实现是这样的:定义类类型1. 定义变量并初始化2. 线性表初始化3. 当队员数小于等于1时,输出结果2.2.2.2抽象数据类型定创建线性表函数typedef struct KList /*定义数据结构体类型*/ElemType *elem; /*存储空间基址*/int length; /*当前长度*/int listsize; /*当前分配的存储容量(以sizeof(ElemType)为单位)*/SqList;int InitList_Sq(SqList &L) /*创建线性表函数*/L.elem=(ElemType *)malloc(LIST_INI

19、T_SIZE * sizeof(ElemType); if(!L.elem)printf(存储分配失败);return ERROR; elseL.length=0; /*空表长度为0*/L.listsize=LIST_INIT_SIZE;return OK;/*初始存储容量*/2.2.2.3 算法流程图开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数队员人数线性表长度队员报数报数值=5？队员出列剩下的队员数1?输出增加存储分配2.2.3用循环队列储存结构解决约瑟夫问题2.2.3.1功能设计具体简介如下：本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计

20、思想,算法的实现是这样的:这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。2.2.3.2抽象数据类型定义创建循环队列#define QueueSize 1000 /假定预分配的队列空间最多为1000个元素ypedef struct int dataQueueSize; int front;int rear; int count;

21、 /计数器，记录队中元素总数CirQueue;void Initial(CirQueue *Q) /将顺序队列置空Q-front=Q-rear=0; Q-count=0; /计数器置 2.2.3.3 算法流程图开始声明数据类型定义变量并初始化初始化循环队列输入敢死队员总数队列满？队员报数报数值=5?队员出列即清零剩下的队员数1?输出增加存储分配编号=1？给队员编号入队列2.3系统的主要界面设计及运行说明：本程序是运用tc20进行检测运行的当点击运行时进入了用户主界面，该界面主要显示了三种可以运用进行程序的方法，如果不需要运行可以选择4号退出该程序，选择者可以通过不同的选择实现自己的目的！实现结

22、果的方法 当选择第1项功能时进行的是运用循环链表存储结构解决约瑟夫问题，假设对员共有十个人，因此进行的是10个队员，死亡数字设为5来运行，其显示的结果如下面的界面所示； 当选择第2项功能，是运用线性表储存结构进行解决约瑟夫问题，假设对员共有十个人，因此进行的是10个队员，死亡数字设为5来运行，其显示的结果如下面的界面所示；选择第3项功能，是运用循环队列的存储结构来解决约瑟夫问题实现结果进行，假设对员共有十个人，因此进行的是10个队员，死亡数字设为5来运行，其显示的结果如下面的界面所示；2.4.实验总结：通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的

23、理解和学会了如何在实际中应用数据结构。在做程序之前，觉得敢死队这个问题，很难解决。在通过自己一次次的画图，推算结果时，明白了该程序的主要思路。本程序其实质是约瑟夫环问题，在明白程序的实质后开始，选择数据的存储结构类型，最开始想到的是循环队列，但是队列是在队头进行出队列操作，队尾入队列，不能进行任意删除元素的操作，没有多想就放弃了。后来在查阅资料时，发现可以通过，对队头的元素删除后又入队列，将头指针移到要删除的元素的位置。通过这次课设，我们感觉自己的水平还是有待提高。我们有很多的灵感和创意非常好，但技术上却无法将它变成实物变成画面呈现在观众面前。以前总是不清楚数据结构它有什么用途。通过这此课程设计，明白我们所学的虽然只是课本知识，但很多时候，我们可以利用所学的来解决生活中碰到的一些问题。同一个问题往往可以用不同的方法来解决。参考文献1C/C+语言程序设计 王曙燕等 科学出版社2数据结构使用C/C+语言 陈一华等电子科技大学出版社3数据结构C/C+语言描述 耿国华高等教育出版社4数据结构（C/C+语言版 严蔚敏，吴伟民清华大学出版社