《数据结构与算法》课程设计要求指南

《数据结构与算法》课程设计要求指南

《数据结构与算法》课程设计要求指南

一． 课程设计的目的

学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。

经过查找参考资料、技术手册和撰写文档的实践，进一步培养软件工程师的综合素质。 课程设计所安排的题目，在难度和深度方面都大于课内的上机训练。程序作业以Java完成，配有图形界面。作业要达到1000行左右的程序量。

二． 课程设计的要求

同学在处理每一个题目的时候，要从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序代码并调试的步骤完成题目，最终写出完整的分析报告。见到题目，案头工作准备不足，忙于上机敲程序不是优秀程序员的工作风格。注意设计与实现过程的经验积累，编码应尽量利用前阶段的成熟数据结构包，加大代码的重用率。

本次课程设计的具体技术要求包括：

1． 每个题目均要求至少提交同一解答的三个版本，即无图形界面的Application、有图形界面的Application和Applet。

2． 图形界面可使用AWT，也建议使用更精致的Java2 Swing(Applet 是 JSwing)技术。

3． 有自学能力的同学可以运用Java的“多线程”技术，例如超市排队的收款场景模拟，多线程会使图形界面的动画效果更逼真。

4． 在教学训练中，曾要求只使用基本的Java类型，即通过引用对象和数组对象从底层搭建数据结构。在达到基本要求之后，可以尝试运用汇集框架（Collections Framework）写程序（但要提交基本类型和汇集框架两个版本的清单）。

5． 数据的输入输出应有手动键盘和文件读写两种工作方式，但因Applet读写本地文件需要数字签名技术，Applet读写文件不是必须的要求。

6． 有条件的同学可以考虑运用动态数据结构的软件固化方案，恰当处理数据结构的存储问题。

三． 课程设计的需求分析步骤与文档格式

课程设计必须强化面向对象的思想方法，其设计的过程与步骤，就是撰写文档的主要脉络。在设计过程中进一步掌握UML建模的技术方法。主要设计步骤应包括： 分析问题归纳算法模型

应用级对象与算法的设计，构思专用的 “辅助数据结构”

《数据结构与算法》课程设计要求指南

设计ADT、interface（或abstract class）

设计类关系图的静态模型、测试主类程序的顺序图动态模型

类的细化设计与实现

类的调试与总体算法程序调试

应用级的问题本身参数调试

算法分析

收获体会

四． 验收标准

验收包括程序测试结果、类设计的合理性和文档质量三部分。程序测试分标准数据样本测试、随机输入数据测试、查看原代码和变更问题需求条件的随机数据测试。对疑似相同的代码和文档将单独严格测试考核。

在程序正确性的前提下，要兼顾界面设计和代码可重用性的质量，注重面向对象设计理念的考核。

五． 推荐的图形界面示例

参考书:

《Java编程思想》（美） 机械工业出版社 ￥99.00

《精通Java Swing 程序设计》 中国铁道出版社 ￥50.00

《Java与UML面向对象程序设计》（美） 人民邮电出版社 ￥28.00

注：同学根据本人学号的后两位数对4取模加1，所得的数字即为应做的题号。例如，某生学号是01070025，(25 MOD 4)+1=2，该同学应做“题目二（源程序相似性判断）”。 在必做题目完成后，鼓励再做其它编号的题目。