数据结构大型实验要求

数据结构大型实验指导•面向对象的程设计（OOP）方法与一般的设计方法不同，它使编程人员可以把精力集中在操作的对象而不是软件要完成的功能上。•它将系统看作是对象的集合，通过对象之间的相互作用（消息传递）完成任务，通过类和对象把数据和处理数据的操作结合为一个整体。设计步骤•需求分析和任务定义•软件设计•编码及静态检查•测试•总结和书写大型实验报告•对复杂软件系统的设计，几乎所有的设计方法都采用某种分而治之的策略。面向对象的程序设计以对象作为设计的基础，具有一下优点：–便于重复使用已有代码，节省开发时间。–程序具有较好的结构性。–可以以类为单位独立进行程序测试。–容易根据用户的需要进行扩充。需求分析和任务定义•问题要做什么？限制条件是什么？•对所需要完成的任务作出明确的回答输入数据的要求输出数据的要求界面的要求解决问题的途径，确定具体算法•确定合法的和非合法的测试数据系统设计•在设计这一步骤中分数据结构设计、对象设计和消息设计：–数据结构设计。确定主要的数据结构，包括元素类型（对象）以及相关的操作。–对象设计。定义内部类，为类属性确定具体的数据结构，并确定类之间的关系。–消息设计。使用对象间的协作和对象-关系模型，设计消息模型。•综合考虑系统功能，对系统进行求精操作：–使得系统类结构清晰、合理、便于操作和易于测试；–对数据结构和基本操作的规格说明做出进一步的求精，补充类的属性和操作；–对操作算法进行规范性描述（用图形工具进行算法描述）。•在求精过程中，尽量避免陷入语言细节，不必过早表述辅助存储结构和局部变量。编码实现和静态检查•编码是把系统设计的结果进一步求精为程序设计语言的过程。•源代码除了要实现具体的算法外，还必须一定的组织结构和视觉效果：–每个函数体，一般不超过80行，最长不超过100行，否则应分割成较小的函数；–给源代码相应的程序段或语句加上适当的注释；–源代码采用缩格书写。•认真的静态检查是必不可少的：–源代码是否真正实现具体的算法描述；–在源代码易于理解的基础上，简化及优化源代码；–用一组测试数据手工执行程序；–通过阅读或给别人见解自己的程序而深入全面地理解程序逻辑，在这个过程中加入一些新的注释和断言。–在静态检查中对于非法的数据输入和操作要加以控制和处理。•测试的目的是为了发现软件中存在的问题，并加以修正。•面向对象的测试可以分为两个部分：–对象测试，在对象设计阶段进行测试，检查成员函数对各种输入参数能否正确完成设计的功能，得到正确的结果。–消息传递测试，测试各对象之间的函数调用与被调用联系，以确保消息传递的正确性。•测试的一般步骤包括：–设计一组或几组测试用例，包括合法的和非法的测试数据；–根据测试用例，得到预期的结果；–将测试用例作为输入数据代入软件系统并运行系统。如果运行结果与预期的结果一致，则说明算法或源代码正确；否则，要修改算法和源代码。上机准备和上机测试•上机准备包括：–高级语言文本的扩充和限制；–熟悉机器的操作系统和语言集成环境的用户手册，尤其是常用的命令的操作；–掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。•上机测试时，要带一本高级语言教材或手册。•首先，在每个对象设计时要进行对象测试；然后，在程序流程调试时要测试对象之间的关系和作用。往往整个测试过程是以上两个部分的反复迭代过程。•测试后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。实习报告规范1软件需求分析1.1软件达到的目的1.2软件功能说明1.3设计环境2系统设计2.1数据结构设计2.1.1主要数据结构类型的分析与选择（逻辑结构）2.1.2数据结构中的数据对象以及具体的操作的确定2.2对象设计2.2.1系统中的类及对象2.2.2类图设计2.3消息设计2.3.1对象之间的消息传递说明2.3.2关键算法设计2.4界面设计3系统实现3.1类的定义（存储结构）3.2关键源代码的实现3.2.1主函数源代码3.2.2主要功能的实现（功能描述、流程图或N-S图）3.3软件测试（包括有效测试数据和无效测试数据）4结果分析与总结4.1结果分析4.2总结大型实验课题•集合运算及实现•校园导游咨询系统的实现•哈夫曼编/译码器的实现•航空客运订票系统的设计与实现•小型图书管理系统的设计与实现•课程管理系统的设计与实现•内部排序算法的实现•停车场管理系统的设计与实现集合的运算及实现•【问题描述】实现集合的基本操作：并、差、交及包含判断。•【基本要求】1、集合中数据的规范约定（按字符序列排列）2、两个集合的并、差、交运算3、集合包含判断（子集判断）4、元素的包含判断5、各种操作提示明确。•【测试数据】由合法的或非法的数据产生规范的集合•【实现要求】1.用带表头结点的顺序表或链表有序存储集合中元素；2.采用合适的算法提高集合的操作，例如交集可以用差集实现；顺序表中查询可以二分查找方法，等等。校园导游咨询系统的实现•【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。各种操作提示明确。•【基本要求】1、设计你的学校的校园的平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度。2、为来访客人提供图中任意景点相关信息的查询。3、为来访客人提供图中任意景点的问路查询，即查询任意两个景点间的一条最短的简单路径。4、景点可以添加或者删除（更新后信息存入文件）。•【测试数据】根据实际情况指定（以学院为例）。•【实现要求】1.可以查询某两个景点之间的最短距离，也可以求出所有景点之间的最短距离（用Dijkstra算法）。2.用文件实现景点信息的初始化。哈夫曼编码/译码器的实现•【问题描述】设计一个哈夫曼的编码/译码器。•【基本要求】1、初始化：建立一棵哈夫曼树，并输出其树形。2、编码：利用建立好的哈夫曼树进行编码，结果存入code.txt文件中。3、利用哈夫曼树将code.txt中的代码进行译码，结果存入decode.txt文件中。4、区分译码失败的各种情况，并输出信息。5、各种操作提示明确。•【测试数据】可以利用教科书中实例调试程序•【实现要求】1、用顺序表存储哈夫曼树2、用贪心算法建立哈夫曼树航空客运订票系统的设计与实现•【问题描述】航空客运订票的业务活动包括：查询航线、预订票和退票等。•【基本要求】1、每条航线所拥有的信息有：航班号、终点、乘员定额、余票量、已订票量和已订票客户名单（包括姓名、身份证号码、电话、订票量）。2、系统主要实现的功能有：(1)初始化：输入每条航线的原始信息，订票客户名单为空；(2)查询航线和订票信息：根据客户提出的终点信息，输出相关的航班和订票信息（是两个独立的查询功能）；(3)订票：根据用户提出的要求（终点站名，订票数额）查询航班号及余票额情况，若尚有余票，则为用户办理订票手续；若余票额少于订票数额，则将该乘客安排到等票队伍。(4)退票：根据客户提出的要求，为客户办理退票手续。3、要有简明的界面，且各种操作的提示明确。【测试数据】对输入数据要有合法和非法约定•【实现要求】1.订票客户名单用链表存储，且按身份证号码升序排列2.退票后，安排等票的客户办理订票手续LineListlinenummaxSizeAirLinetypenumberfirstsellsockAirLinetypenumberfirstamountsock……passengerNodeidnamephoneamountnextpassengerNodeidnamephoneamountnextpassengerNodeidnamephoneamountnextpassengerNodeidnamephoneamountnext……LineListAirLine1nPassengerNode1n小型图书管理系统的设计与实现•【问题描述】图书管理基本业务包括：对书的采编入库、清除库存、查阅图书、以及借阅和归还等等。•【基本要求】1、每种书的登记内容至少包括：书号、书名、作者、现存量和总库存量（同一个书号的图书可以有多本）。2、系统实现的功能如下：（1）采编入库：将新书添加到图书帐目中。如果书已存在，则只增加总库存量。（2）清除库存：将指定的书从图书帐目中删除。（3）查阅图书及借阅情况：查阅指定书名的图书信息（模糊查询）；能灵活查找图书借阅情况以及读者借阅情况。（4）借阅：若现存量大于0，则登记借阅信息及改变现存量。（5）归还：注销对借阅者的登记，改变现存量。3、各种操作的提示明确。•【测试数据】对输入数据要有合法和非法约定•【实现要求】1、确定系统中所有类，以及类之间关系2、用顺序表或者链表存储图书信息（按书号有序排列）内部排序的实现及比较•【问题描述】设定随机数据比较指定排序算法的关键字比较和关键子移动次数。•【基本要求】1、对以下6中排序方法进行比较：起泡排序、快速排序、希尔排序、堆排序、归并排序以及基数排序。2、用随机函数产生不少于100个1~1000的整数关键字。3、输出排序后的序列（每行输出10个）。4、输出各排序方法的比较次数和移动次数的比较结果。•【测试数据】数据由随机产生器生成。•【实现提示】根据不同排序方法确定不同的存储结构。课程管理系统的设计与实现•【问题描述】设计一个简易的课程管理系统，有求对学生的课程成绩可以进行查询、输入以及输出。•【基本要求】1、基础信息输入。如班级信息、学生信息以及课程信息2、查询信息。以个人、班级名义查询指定或所有课程成绩，也可以查询某门课程的学生成绩。3、成绩输入。输入指定班级的某个课程成绩4、修改和撤销成绩。修改和删除个别学生的课程成绩5、统计成绩。统计统一门课程的分数分布情况6、各种操作提示明确。•【测试数据】输入数据的格式规范要求•【实现要求】1、确定系统中所有类，并确定类之间关系2、用顺序表或者链表存储相关信息3、灵活实现课程信息的查询（学生或班级---》课程成绩，课程---》学生成绩）停车场管理系统的设计与实现•【问题描述】假设停车场是个多个双向通道，设计一个简易的停车场收费系统管理车辆的进出及等候停车操作，并计算停车费用。•【基本要求】1、停车及计时：按照停车通道序号进行停车（停车的车道和车位从小到大），停车成功后开始计时（只需记录整时）；2、离开及收费：当车辆离开时，留出车位，并收取停车费用，并及时输出空车位状态；3、停车状况查询：依次输出各停车通道的停车状况；4、等候停车：如果没有停车位，车辆在等候队列排队等候停车（如果候车队列已满，则给出禁止停车信息）。如有空位后，则退出等候队列，进入停车通道，开始计费。5、各种操作提示明确。•【测试数据】对输入数据要有合法和非法约定输出格式•【实现要求】1.车道信息包括：车道号、车位数以及停车位信息2.停车位信息包括：车位号和车辆信息（包括车牌号、停车时间）3.选择合适的计时算法。