数据结构大型实验要求.ppt

1、大型实验指导,面向对象的程设计（OOP）方法与一般的设计方法不同，它使编程人员可以把精力集中在操作的对象而不是软件要完成的功能上。 它将系统看作是对象的集合，通过对象之间的相互作用（消息传递）完成任务，通过类和对象把数据和处理数据的操作结合为一个整体。,对复杂软件系统的设计，几乎所有的设计方法都采用某种分而治之的策略。面向对象的程序设计以对象作为设计的基础，具有一下优点：,便于重复使用已有代码，节省开发时间。 程序具有较好的结构性。 可以以类为单位独立进行程序测试。 容易根据用户的需要进行扩充。,设计步骤,需求分析和任务定义 软件设计 编码及静态检查 测试 总结和书写大型实验报告,需求分析 和

2、 任务定义,问题要做什么？限制条件是什么？ 对所需要完成的任务作出明确的回答 输入数据的要求 输出数据的要求 界面的要求 解决问题的途径，确定具体算法 确定合法的和非合法的测试数据,系统设计,在设计这一步骤中分数据结构设计、对象设计和消息设计： 数据结构设计。确定主要的数据结构，包括元素类型（对象）以及相关的操作。 对象设计。定义内部类，为类属性确定具体的数据结构，并确定类之间的关系。 消息设计。使用对象间的协作和对象-关系模型，设计消息模型。,综合考虑系统功能，对系统进行求精操作： 使得系统类结构清晰、合理、便于操作和易于测试； 对数据结构和基本操作的规格说明做出进一步的求精，补充类的属性和

3、操作； 对操作算法进行规范性描述（用图形工具进行算法描述）。 在求精过程中，尽量避免陷入语言细节，不必过早表述辅助存储结构和局部变量。,编码实现和静态检查,编码是把系统设计的结果进一步求精为程序设计语言的过程。 源代码除了要实现具体的算法外，还必须一定的组织结构和视觉效果：,每个函数体，一般不超过80行，最长不超过100行，否则应分割成较小的函数； 给源代码相应的程序段或语句加上适当的注释； 源代码采用缩格书写。,认真的静态检查是必不可少的： 源代码是否真正实现具体的算法描述； 在源代码易于理解的基础上，简化及优化源代码； 用一组测试数据手工执行程序； 通过阅读或给别人见解自己的程序而深入全面

4、地理解程序逻辑，在这个过程中加入一些新的注释和断言。 在静态检查中对于非法的数据输入和操作要加以控制和处理。,测试的目的是为了发现软件中存在的问题，并加以修正。 面向对象的测试可以分为两个部分： 对象测试，在对象设计阶段进行测试，检查成员函数对各种输入参数能否正确完成设计的功能，得到正确的结果。 消息传递测试，测试各对象之间的函数调用与被调用联系，以确保消息传递的正确性。,测试的一般步骤包括： 设计一组或几组测试用例，包括合法的和非法的测试数据； 根据测试用例，得到预期的结果； 将测试用例作为输入数据代入软件系统并运行系统。如果运行结果与预期的结果一致，则说明算法或源代码正确；否则，要修改算法

5、和源代码。,上机准备和上机测试,上机准备包括： 高级语言文本的扩充和限制； 熟悉机器的操作系统和语言集成环境的用户手册，尤其是常用的命令的操作； 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。 上机测试时，要带一本高级语言教材或手册。 首先，在每个对象设计时要进行对象测试；然后，在程序流程调试时要测试对象之间的关系和作用。往往整个测试过程是以上两个部分的反复迭代过程。 测试后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。,实习报告规范,1 软件需求分析 1.1 软件达到的目的 1.2 软件功能说明 1.3 设计环境 2 系统设计 2.1 数据结构设计

6、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 （其他功能源代码实现） 3.3 软件测试 4 结果分析与总结 4.1 结果分析 4.2 总结,大型实验课题,集合运算及实现 校园导游咨询系统的实现 哈夫曼编/译码器的实现 航空客运订票系统的设计与实现 小型图书管理系统的设计与实现 内部排序的实现

7、及比较 课程管理系统的设计与实现 停车场管理系统的设计与实现,集合的运算及实现,【问题描述】 实现集合的基本操作：并、差、交及包含判断。 【基本要求】 1、集合中数据的规范约定（按字符序列排列） 2、两个集合的并、差、交运算 3、集合包含判断（子集判断） 4、元素的包含判断 5、各种操作提示明确。 【测试数据】 由合法的或非法的数据产生规范的集合 【实现提示】 1.用带表头结点的顺序表或链表有序存储集合中元素； 2.采用合适的算法提高集合的操作，例如交集可以用差集实现；顺序表中查询可以二分查找方法，等等。,校园导游咨询系统的实现,【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询

8、服务。各种操作提示明确。 【基本要求】 1、设计你的学校的校园的平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度。 2、为来访客人提供图中任意景点相关信息的查询。 3、为来访客人提供图中任意景点的问路查询，即查询任意两个景点间的一条最短的简单路径。 4、景点可以添加或者删除。 【测试数据】 根据实际情况指定（以学院为例）。 【实现提示】 一般情况下，校园的单路是双向通的，为了简化设计，可设校园平面图是一个有向网。顶点和边均含有相关信息。,哈夫曼编码/译码器的实现,【问题描述】 设计一个哈夫曼的编码/译码器。 【基本要求】 1、

9、初始化：建立一棵哈夫曼树。 2、 编码：利用建立好的哈夫曼树进行编码，结果存入字符串code中。 3、利用哈夫曼树将code中的代码进行译码，结果存入字符串text中。 4、区分译码失败的各种情况。 5、各种操作提示明确。 【测试数据】 可以利用教科书中实例调试程序 【实现提示】 1、用顺序表存储哈夫曼树 2、用二叉链表存储哈夫曼树,航空客运订票系统的设计与实现,【问题描述】 航空客运订票的业务活动包括：查询航线、预订票和退票等。 【基本要求】 1、 每条航线所拥有的信息有：航班号、终点、乘员定额、余票量、已订票量和已订票客户名单（包括姓名、身份证号码、电话、订票量）。 2、 系统主要实现的功

10、能有： (1) 初始化：输入每条航线的原始信息，订票客户名单为空； (2) 查询航线和订票信息：根据客户提出的终点，输出相关信息； (3) 订票：根据用户提出的要求（终点站名，订票数额）查询航班号及余票额情况，若尚有余票，则为用户办理订票手续；若余票额少于订票数额，则不予办理; (4) 退票 ：根据客户提出的要求，为客户办理退票手续。 3、要有简明的界面，且各种操作的提示明确。 【 测试数据】 对输入数据要有合法和非法约定 【实现提示】 航线信息基本不变，可以用顺序表实现，而订票客户名单可以考虑用有序链表实现，便于插入和删除和查询。,小型图书管理系统的设计与实现,【问题描述】 图书管理基本业务

11、包括：对一本书的采编入库、清除库存、借阅和归还等等。 【基本要求】 1、 每种书的登记内容至少包括：书号、书名、作者、现存量和总库存量。 2、 系统实现的功能如下： （1）采编入库：将新书添加到图书帐目中。如果书已存在，则只增加总库存量。 （2）清除库存：将指定的书从图书帐目中删除。 （3）借阅：若现存量大于0，则登记借阅信息及归还日期。 （4）归还：注销对借阅者的登记，改变现存量。 3、各种操作的提示明确。 【测试数据】 对输入数据要有合法和非法约定 【实现提示】 1、确定系统中所有类，并确定类之间关系； 2、用顺序表或者链表存储相关信息； 3、根据具体信息的存储结构确定相关操作算法。,内部

12、排序的实现及比较,【问题描述】 设定随机数据比较指定排序算法的关键字比较和关键子移动次数。 【基本要求】 1、对以下6中排序方法进行比较： 起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、 用随机函数产生不少于100个11000的整数关键字。 3、输出排序后的序列（每行输出10个）。 4、输出各排序方法的比较次数和移动次数的比较结果。 【测试数据】 数据由随机产生器生成。 【实现提示】 根据不同排序方法确定不同的存储结构。,课程管理系统的设计与实现,【问题描述】 设计一个简易的课程管理系统，有求对学生的课程成绩可以进行查询、输入以及输出。 【基本要求】 1、输入基本信息

13、，如班级信息、学生信息以及课程信息 2、可以以个人或班级名义查询指定或所有课程成绩 3、输入指定班级的某个课程成绩 4、修改个别学生的课程成绩 5、如学生退学或别的原因，可以删除学生信息或课程成绩 6、各种操作提示明确。 【测试数据】 输入数据的格式规范要求 【实现提示】 1、确定系统中所有类，并确定类之间关系； 2、用顺序表或者链表存储相关信息； 3、根据具体信息的存储结构确定相关操作算法。,停车场管理系统的设计与实现,【问题描述】 假设停车场是个多个单向通道，设计一个简易的停车场收费系统管理车辆的进出及等候停车操作，并计算停车费用。 【基本要求】 1、停车及计时：按照停车通道序号进行停车，停车成功后开始计时（只需记录整时） 2、离开