第11章 数据结构课程设计.ppt

第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 * 实用数据结构基础(第四版) 数据结构课程设计 第11章 目 录 11.1 课程设计的目的与内容 11.2 课程设计的要求 11.3 课程设计题目 本章精选了28个与数据结构相关的典型应用题目，希望在理论教学过程结束后，用一到两周的时间由学生独立完成本章的一个题目，并写出相应的课程设计报告。对于学有余力的同学，也可以选做本章列出的多个课题，这对于编程实践能力的提高、数据结构各知识点的融会贯通、以及算法分析与设计能力的培养，无疑是大有裨益的。 要顺利完成本章课题所规定的任务，需要复习前面各章节介绍的各种逻辑结构、存储结构及基本算法，熟练掌握并理解前面各章节的知识要点，并对部分知识点进行相互串联。由于部分课题对“计算机组成原理”和“算法分析与设计”等课程的内容稍有涉及，认真完成本章的课题任务对后续课程的学习也将不无帮助。 通过本章学习，可以大大提高学生自主分析和解决问题的能力，使学生的编程能力得到有效地巩固和提高。 　　11.1 课程设计的目的与内容 11.1.1 课程设计的目的 (1) 了解并掌握数据结构与算法的设计方法，培养独立分析问题的能力 。 (2) 综合运用所学的数据结构基本理论和方法，提高在计算机应用中解决实际问题的能力。 (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、程序调试、数据测试等基本方法和技能。 (4) 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者应该具备的科学的工作方法和作风。 (5) 通过课程设计完成具有一定深度和难度的题目。 (6) 编写课程设计报告，锻炼软件开发文档撰写的基本方法。 11.1.2 课程设计的内容 1．问题分析和任务定义 根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么，限制条件是什么。 2．逻辑设计 为问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个功能操作的说明），划分功能模块并描述各个主要模块的算法，若各功能模块之间存在调用关系，还应画出各个模块之间的调用关系图。 3．详细设计 定义存储结构，并写出各函数算法或伪码（Pseudocode）算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义和函数形式的算法框架。 4．程序编码 把详细设计的结果进一步转换为程序设计语言程序。同时加入一些注解，使程序逻辑概念清楚、维护方便。 5．程序调试与测试 程序调试采用自底向上，分模块进行。即先调试底层被调函数，再逐级调试上层主调的函数。通过程序调试熟练掌握调试工具的各种功能；设计测试数据确定疑点，通过修改程序来证实它或绕过它。程序调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单。 6．结果分析 程序运行结果不但要包括正确的输入及其输出结果，而且还要人为的输入一些含有错误的数据以考察其输出结果的正确性。同时进行算法的时间复杂度和空间复杂度分析。 7．编写课程设计报告 11.1.3 课程设计报告 课题设计结束时要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。 课程设计的封面包括：题目、班级、学号、姓名、指导教师和完成日期。 课程设计报告的正文应大致包括以下几个方面的内容（可以根据所选课题的实际情况作适当调整或更改）。 1．课题分析 以无歧义的陈述说明程序设计的任务，强调的是程序要做什么，并明确规定： ① 输入的形式和输入值的范围。 ② 输出的形式。 ③ 程序所能达到的功能。 ④ 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2．总体设计 说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。 3．详细设计 系统详细设计包括：人机接口界面、输入界面、输出界面在内的用户界面设计；逻辑结构、存储结构设计；算法（或伪码算法）设计，也可以采用流