1.8课程设计相关知识
课程设计是对学生分析问题、解决问题能力的一种全面综合的训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
1.8.1课程设计目的与内涵
理解课程内容与较好地解决实际问题之间存在着明显差距，解决实际问题的能力与程序设计技术的培养是密切相关的。要想理解和巩固所学的基本概念、基本原理和基本方法，牢固地掌握所学的基础知识、基本技能，达到融会贯通、举一反三、触类旁通的程度，就必须多做、多练、多实践。课程设计正是着眼于理论与实践的结合点，使学生学会如何把书本上学到的知识应用于解决实际问题，培养软件工作者所需要的动手能力。课程设计是程序设计的综合训练，包括问题需求分析、总体结构设计、算法（程序）设计技术和方法，以及研究开发程序系统的工作规范和科学作风的培养。
为了达到上述目的，本书各章都安排了一个课程设计题目，每个题目都采用了统一格式，由问题描述、基本要求、测试数据、实现提示和问题拓展五个部分组成。问题描述给出问题的背景环境，指明要做什么；基本要求是对问题的进一步求精，划定问题的边界，并规定完成该题目的最低要求；测试数据是为学生静态检查和上机调试提供方便，在完成题目时，学生应设计完整的、严格的测试方案；实现提示是对实现中的难点及其解题思路等内容作了简要提示；问题拓展旨在开拓学生的思路，展现学生的创造力，使学生尽可能寻求尽善尽美的解决方案，使得数据组织形式、程序结构更加合理，具有正确性、可读性、可维护性和可扩充性。
在课程设计环节中，有些题目与书中介绍的内容相关，在书中只是应用了面向过程的某种语言进行算法设计和程序编制，重点放在解题思路与解题策略。由于计算科学发展迅猛，可以运用的语言工具和环境愈来愈丰富，对于同样的题目、同样的解题策略、同样的算法，学生可以运用各种自己熟练掌握的程序设计语言（包括面向对象语言）来实现。
1.8.2课程设计步骤
结构化系统分析和设计方法将系统研制过程划分为系统分析、系统设计、系统实施和系统维护四个阶段。这里课程设计的复杂度虽然远不如实际应用系统的复杂度，但为了培养一个软件工作者所应具备的科学工作作风，要求课程设计的步骤如下。
（1）问题分析和需求定义
对于给定的题目进行分析和理解，明确题目要做什么。对问题的描述应避开算法和所涉及的数据类型，避免过早地陷入细节，要对所需完成的任务做出明确的描述。即问题如何分解，需要输出什么，需要那些输入数据。这一步还应该考虑测试数据，包括合法数据和非法数据。
（2）数据的逻辑结构设计和运算的定义
根据问题分析和需求定义描述数据的逻辑结构，对每个基本操作给出尽可能明确具体的规格说明；并按照以数据结构为中心的原则划分模块，确定模块功能，给出模块之间的关系调用图。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于实现。
（3）数据的存储结构设计和算法设计
它是数据的逻辑结构和运算的具体实现，写出数据存储结构的类型定义和变量说明，根据每个基本操作的规格说明和模块功能设计出可读性强、结构好的算法。在这个过程中，应尽量避免过早地陷入程序设计语言细节。
（4）编码实现和静态检查
编码实现是把数据的存储结构设计和算法设计的结果进一步用某种程序设计语言进行描述，变换成可以在计算机上运行的程序。在编程过程中，对于不确定的语句（命令）功能，同样要先上机验证，再使用。把算法变换为程序时，可以适当地追求程序的执行效率。在程序中还应该适当地加一些注释，以增强程序的可读性。
在程序代码编写完成后，认真进行程序的静态检查是必不可少的。静态检查主要有两种方法：一是用一组或几组测试数据静态执行程序，这也为上机动态调试做好了准备工作；二是通过反复阅读或给别人讲解自己的程序，从而达到深入全面地理解程序的逻辑结构。
（5）设计测试方案和上机调试
确定几组输入的测试数据以及应该得到的相应结果，包括中间结果和最终结果。调试可以采取自顶向下或自底向上、分模块进行。调试过程中，经常会遇到意想不到的异常现象，这时应积极确定疑点，检查相应变量的值，寻找错误，修改程序，最终得到正确的程序。调试完毕后，认真整理源程序及其注释，记录输入数据和处理结果。
（6）总结和整理课程设计报告
1.8.3课程设计报告规范
课程设计报告的开头应给出题目、班级、姓名、学号以及完成日期等信息，并重点整理下列内容：
1.问题分析和需求定义。
2.数据的逻辑结构设计和运算的定义。
3.数据的存储结构设计和算法设计。
4.调试过程及其分析。内容包括：（1）调试过程中遇到的问题是如何解决的，以及对设计和实现的感悟；（2）算法复杂性分析和算法的改进；（3）经验、体会和收获等。
5.用户使用说明。说明如何使用你设计的程序。
6.程序运行结果。包括输入数据和输出数据。
7.附录。带注释的源程序及相关资料。
1.8.4课程设计示例
在实际应用问题中，经常会涉及到多种类型的数据结构以及它们之间的复杂操作，这就需要综合运用学过的数据结构、算法设计、编程技术等方面的知识。
解决具体问题，通常从分析问题出发，进行数据抽象、过程抽象和控制抽象，选取适当的数据结构将问题形式化，定义操作，设计相应的算法，进行编程和组装。在下面的示例中，我们仅给出完成课程设计的一般步骤，并未给出具体的程序实现。试图引导读者将解决问题的策略从以功能或信息为中心转变到以对象为中心；试图引导读者如何进行数据抽象和过程抽象分析，实现简单的封装和复用。这就要求读者学习一点面向对象的分析方法、面向对象的设计和面向对象的编程技术。
例汽车牌照的快速查找。排序和查找是信息处理中使用频率极高的操作。在汽车信息模型中，汽车牌照编码是关键字，并且是具有结构特点的一类关键字。例如，某汽车牌照编码为01B7328，它由数字和字母混编而成。为了提高按关键字的查找速度，就需要按关键字进行排序。对于这种混合编码的关键字，可选用基数排序法。对已排序的数据结构，可采用折半查找法实现对汽车牌照编码的快速查找。
（1）问题描述
①题目：对某组织的汽车牌照编码进行快速查找。
②基本要求：利用基数排序法和折半查找法完成本课程设计。
③测试数据：键盘录入或随机生成。
（2）需求分析
①本课程设计要求采用基数排序法对一批具有结构特征的汽车牌照编码为关键字的记录进行排序；并且采用折半查找法对已排序的记录集合按汽车牌照编码进行快速查找。
②测试数据的每个记录包括5个基本数据项：牌照编码、商标、颜色、注册日期和车主姓名。牌照编码为关键字，结构形式如下：
k1 k2 k3 k4 k5 k6 k7
其中，前两位k1k2的取值范围为01～31（代表地区），第3位取值范围为A～Z（代表车的类型），后4位k4k5k6k7的取值范围为0000～9999（顺序号）。这种汽车牌照编码具有多关键字的特征，处理时可以将其分成3段来考虑，即数字、字母和数字。
③建立数据模型，确定存储结构。比如，以静态链表作为存储结构。
④运行程序，应具有友好的用户界面。比如，可以进行系统初始化、数据输入与维护、排序和查找等功能选择。
⑤测试数据要求用不少于50个记录数据进行程序测试。
（3）概要设计
①静态表的抽象数据类型描述。
②程序系统包含5个模块：主模块；系统初始化模块；数据输入和维护模块；基数排序模块；折半查找模块。
③各模块之间的调用关系。
（4）详细设计
①静态链表的类型定义与变量说明。
②在进行分配和收集操作时，用到的数组类型定义和变量说明。
③输入、输出函数定义与算法设计。
④基数排序中用到的各函数定义与算法设计。
⑤折半查找中用到的各函数定义与算法设计。
⑥各函数之间的调用关系。
（5）实施编程与组装
（6）测试结果
①测试数据的录入形式，或随机产生的测试数据列表。
②输出排序结果。
③输出查找结果。
（7）调试分析
①调试过程中出现的问题与解决方法。
②时间复杂度分析与空间复杂度分析。
③课程设计总结。
（8）程序系统使用说明
（9）附录（源程序文件清单）
| 
