第12章 数据结构课程设计

第12章绪论2011年5月11日星期三1第12章目录

12.1课程设计的目的与内容

12.2课程设计的内容

12.3A类题目

12.4B类题目

12.4C类题目

本章精选了24个与数据结构相关的典型应用题目，并按从易到难的顺序分为A、B、C三个类别，通过一周或两周的时间由学生独立完成其中一个题目。要顺利完成本章课题所规定的任务，需要复习前面各章节介绍的各种逻辑结构、存储结构及基本算法，熟练掌握并理解前面各章节的知识要点，并对部分知识点进行相互串联。由于部分课题对《计算机组成原理》和《算法分析与设计》等课程的内容稍有涉及，认真完成本章的课题任务对后续课程的学习也将不无帮助。

12.1

课程设计的目的与内容12.1.1课程设计的目的1．了解并掌握数据结构与算法的设计方法，培养独立分析问题的能力；2．综合运用所学的数据结构基本理论和方法，提高在计算机应用中解决实际问题的能力；3．初步掌握软件开发过程的问题分析、系统设计、程序编码、程序调试、数据测试等基本方法和技能；4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者应该具备的科学的工作方法和作风。5．通过课程设计完成具有一定深度和难度的题目。6．编写课程设计报告，锻炼软件开发文档撰写的基本方法。

12.2

课程设计的内容1．问题分析和任务定义根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？2．逻辑设计对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。3．详细设计定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。4．程序编码把详细设计的结果进一步转换为程序设计语言程序。同时加入一些注解，使程序逻辑概念清楚、维护方便。5．程序调试与测试程序调试采用自底向上，分模块进行。即先调试低层函数，再逐级调试上一层的函数。通过程序调试熟练掌握调试工具的各种功能；设计测试数据确定疑点，通过修改程序来证实它或绕过它。程序调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单。6．结果分析程序运行结果不但要包括正确的输入及其输出结果，而且还要人为的输入一些含有错误的数据以考察其输出结果的正确性。同时进行算法的时间复杂性和空间复杂性分析。7．编写课程设计报告。12.1.3

课程设计报告1．课题分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：（1）输入的形式和输入值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2．总体设计说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。3．详细设计实现总体设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；也可以采用流程图、N–S图或PAD图进行描述，画出函数和过程的调用关系图。4．调试分析调试分析的内容包括：（1）调试过程中遇到的问题是如何解决的，以及对程序设计与实现的讨论和分析；（2）算法的时间复杂度和空间复杂度的分析；（3）对算法的改进设想；（4）程序调试的收获和体会。5．用户使用说明用户使用说明是为了告诉用户如何使用你编写的程序，并举例列出每一步的操作步骤。6．测试结果列出测试的输入数据和程序运行以后的输出结果，测试数据应该保证完整和严格。7．参考文献列出参考资料和书籍。12.1.4课程设计的考核课程设计的成绩分三部分给定。其中：设计过程的答辩占60％，设计作品（源代码）占20％，课程设计报告占20％。成绩评定按照优秀、良好、中、及格，不及格五级或者按百分制实施。本课程需要提交归档的材料清单如下：（1）课程设计报告（电子稿和打印稿各一份）。（2）程序源代码文件夹（文件夹中只保留.c或.cpp、.dll、.lib等必须文件，编译过程中产生的各种参考文件、工程文件和Debug文件夹等提交时一律删除）。11.2

课程设计的要求1.课题的分类与选择为了使不同编程基础的同学通过课程设计都能有所提高，使所有同学都学有所获，根据课程设计题目的难度由低到高，将所有课题分为A、B、C三个类别。教师可以根据学生的学习基础，结合学生本人的意愿，先对学生进行分组，然后各个小组以抽签的方式决定具体的课程设计题目。学生也可以根据个人的能力自行选择有一定难度的其它数据结构课程设计课题，但是自选课题必须预先向指导老师提出申请，说明课题的内容、难度，以及实现的目标，经老师同意并立项以后方可进行。

2.课程设计的要求课程设计按照教学要求需要1-2周时间完成，两周中每天至少要上机3-4小时来调试程序，总共至少要上机调试程序30小时。为保证质量，要求每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。对题目中要求的功能进行分析，并且设计解决此问题的数据存储结构（有些课题中部分存