课程设计的步骤

   数据结构课程设计就是综合运用本课程所学到的知识来解决实际问题。计算机解决一个具体问题一般需要经过下列几个步骤:首先要从该具体问题抽象出一个适当的数学模型,然后设计或选择一个解此数学模型的算法,最后编出程序进行调试、测试,直至得到最终的解答。课程设计也是按照这个步骤进行,下面介绍各阶段的内容。
1. 建立模型
  建立模型通常包括所描述问题中的数据对象及其关系的描述、问题求解的要求及方法等方面。将一个具体的问题转换为我们所熟悉的模型,就可以很容易进行求解。要描述群体中个体之间的关系时,可以采用《离散数学》中所介绍的图结构。例如要求解一个工程的最小代价或者关键路径时,可以采用图结构中的 AOV 网或 AOE 网等模型。数值计算问题中常用的数学模型为线性方程组(用于求解电路的电流强度或结构中的应力)或微分方程(用于预报人口增长情况或化学反应速度等)。《离散数学》及许多数学课程中就介绍了许多模型。《数据结构》课程中所介绍的各种结构也是数学模型。
  数学模型的建立是求解实际问题的基础。一般情况下,实际应用问题可能会各式各样,但有共性的问题都是同一类数学模型,例如我们所熟悉的工资表的处理问题、学生成绩管理问题、电话号码查询问题、图书管理系统等都属于‘线性表’这种模型。只要掌握‘线性表’的存储结构、操作算法我们就能解决如工资表的处理、学生成绩管理等一系列问题,学习《数据结构》这门课程的根本目的就在于此。再如:在有n个选手P1,P2,P3,…,Pn参加的单循环赛中,每对选手之间非胜即负。现要求求出一个选手序列P1′,P2′,P3′,…,Pn′,使其满足Pi′胜Pi+1′(i=1,…,N-1)。这个问题看似复杂,由于仅涉及到n个选手,并且这些选手之间的关系仅是胜负关系,因此可用图这种数学模型来表示:用顶点表示选手,用弧表示选手之间的胜负关系:当且仅当Pi′胜Pj′,有从i到j的一条弧,在这种表示下,本题问题变成了在有向图中求解出一条包含所有顶点的简单路径的问题。由此可见,正确选择数学模型是解决问题的关键,这就要求我们具有扎实的数学基础,同时熟练地掌握数据结构所介绍的线性表、队列与栈、广义表、树和图等各种结构(模型)的存储方法和操作算法。
2. 选择合适的存储结构
  在构造出求解算法之后,就需要考虑如何在计算机上实现。从算法到程序还是有一定距离的。为此,需要做两方面的工作,其一是选择合适的存储结构,其二是用指定的计算机语言来描述算法。下面先讨论第一个方面,即选择存储结构的问题。
  选择合适的存储结构首先是为了将问题所涉及到的数据(包括数据中的基本对象及对象之间的关系)存储到计算机中。此外,还需要考虑所选择的结构是否便于问题的求解,时间和空间复杂度是否符合要求。《数据结构》课程中已经对此作了许多讨论。在实际应用时,需根据问题的要求进行合理的选择及综合。不同的存储形式对问题的求解实现有较大的影响,所占用的存储空间也可能有较大的差异。例如,顺序存储结构一般来说便于直接存取,从而节省存取时间,但是在插入和删除元素时需要移动元素,从而浪费时间,而链式存储结构在插入和删除元素时无需移动元素,但需花费时间来搜索元素。线性表较多采用顺序存储结构,而非线性结构则不宜采用这种形式。
3. 构造求解算法
  在建立好模型之后,一个具体的问题就变成了一个用模型所描述的抽象的问题。借助于这一模型以及已有的知识(例如数据结构中有关图结构的基本知识),我们可以相对容易地描述出原问题的求解方法即算法。从某种意义上说,该算法不仅能实现原问题的求解,而且还能实现许多类似的具体问题的求解,尽管这些具体问题的背景及其描述形式可能存在较大的差异。
  算法设计的核心是给出问题求解的基本算法。所给出的算法并非一定要用某种计算机语言来描述,但应能较方便地转换为某种计算机语言程序。
  在建立了适当的数学模型后,某些问题就可以转换为一些经典问题或基于某些经典问题的综合或变异形式的求解。例如,如果所转换出的模型为图,则可能借助于图的深度遍历、广度遍历、求最小生成树、求最短路径、拓扑排序、关键路径、二分图的匹配、图的着色等问题的求解算法来实现。
  在问题的求解没有可借助的方法时,需要自己构思求解方法。在构造求解方法时,需要注意对时间、空间以及其它有关性能的要求。
4.编写程序
  编程是用指定的计算机语言来描述算法和数据结构,并将其转换为完整的上机程序。这包括提供必要的辅助函数,如建立和输入一个结构,显示结构等。编写出的代码一定要注重程序设计风格,提高程序的可读性。
5. 测试
  对设计者来说,很难保证所编写的程序没有错误,因此需要对原代码进行测试,以发现其中的错误和缺陷。按照软件工程的观点,测试是为了发现错误,而不是证明其正确,也就是说,即使没有发现错误,也不能证明是正确的。
6.总结
  在一个课题设计完成之后,需要写出设计报告,以对设计进行总结和讨论,包括课题的要求、模型建立和算法设计,系统组成及说明,使用说明,程序清单,总结和体会,本设计的优、缺点,时、空间性能分析,与其它可能存在的求解方法之间的比较等。通过总结,可以对问题及其求解有更全面、深入的认识,从而达到由典型到全面、由具体到一般的飞跃。