数据结构（第一章概述）DataStructures胡学钢张晶计算机.ppt

第一章 概 述 主要内容 1.1 研究内容 1.2 术语 1.3 算法及其描述 1.4 算法分析 1.1 研究内容 数据结构课程的研究内容： 软件设计中常用的基本技术 包括哪些基本技术？ 下面从采用计算机来解决实际问题的过程中所涉及到的各步骤中的相关技术来对此作一分析： 在用计算机解决实际问题时， 一般要经过以下几个步骤： 首先，对具体问题抽象出数学模型， 然后针对数学模型设计出求解算法， 选择或设计合适的数据结构存储相关数据， 最后编出程序上机调试，直至得到最终的解答。 下面简述各环节的有关内容。 1.1 研究内容 问题求解之一：问题建模： 一般情况下，实际应用问题可能会各式各样，例如： 我们所熟悉的工资表的处理问题，学生成绩管理问题， 电话号码查询，数据加密、压缩问题等。 这些问题中，无论是所涉及到的数据，还是其操作要求， 都可能存在一定的差异。 尽管如此，许多问题间还是具有一定相似之处的。例如： 虽然工资表和学生成绩表的具体信息（栏目）不同， 但如果将两个表中的每个人的工资信息和成绩信息分别看作一个整体，则这两个表结构之间就有了某些共性。 从操作方面来看，虽然对这两种表的操作存在差异， 但也存在一些相同或相似的基本操作。 例如，查询一个人的工资信息和成绩信息，修改有关信息等。 1.1 研究内容 正因为许多不同的问题之间存在着的某些共性， 可以将一个具体问题用这些共性的形式描述出来 -----问题建模。 问题建模通常包括： 所描述问题中的数据对象的集合； 对象间关系及其描述； 问题求解的要求及方法等。 建立问题模型的好处： 通过建立模型，就可以将一个具体的问题转换为所熟悉的模型，然后借助于这一模型来实现。 数据结构、离散数学及许多数学课程中就介绍了许多模型。例如： 要描述一个群体中个体之间的关系时，可以采用”数据结构”和”离散数学”中所介绍的图结构。 要描述一个工程内的关系或进展情况时，我们可以采用”数据结构”中所介绍的AOV网或AOE网等。 即使所建立的模型没有现成的求解方法，借助于已有的模型的适当组合也相对易于构造求解方法。 1.1 研究内容 问题求解之二：构造求解算法 通过问题建模，将一个具体的问题转换成一个用模型所描述的抽象的问题。 借助于这一模型以及已有的知识 （例如数据结构中有关图结构的基本知识）， 可以相对容易地描述出原问题的求解方法，即算法。 算法设计过程中可能会涉及到多种技术， 例如：递归、分治法等。 需要更多地实践。 算法设计是计算机专业的核心能力， 是区别于其他专业的最核心能力之一。 从某种意义上说，该算法不仅能实现原问题的求解， 而且还可能实现许多类似的具体问题的求解， 尽管这些具体问题的背景及其描述形式可能存在较大的差异。 1.1 研究内容 问题求解之三：选择或设计存储结构 在构造出求解算法之后，需要考虑在计算机上实现求解了。为此，需要做两方面的工作： 选择或设计合适的存储结构， 以便将问题所涉及到的数据存储到计算机中。 （这包括数据中的基本对象及对象之间的关系） 不同的存储形式对问题的求解实现有较大的影响， 所占用的存储空间也可能有较大的差异。 设计程序，实现问题求解。 存储形式和问题要求决定了程序设计的方法。 另外，程序设计环境（如VC）的熟练掌握也是本课程的学习过程中需要注意的教学目标之一。 1.1 研究内容 问题求解之四：测试 如何认定所设计的算法及程序能正确实现预定的功能和目标？ 理论证明： 这是计算机科学领域曾经开展过的工作。 由于算法和程序的复杂性急剧增长，因而难以实用。 测试：通过对所开发的系统或模块，运行给定的测试数据，以发现存在的错误，而不是证明其正确。 这是当前软件开发领域普遍采用方法，通常要占系统开发４０％以上的工作量。详细描述可参考“软件工程”相关的描述。 所设计的算法和程序，需要经过充分的测试才能交付使用。 对程序的测试态度反映出学生的治学态度： 如果是认真、负责的态度，就会认识到，任