[理学]数据结构讲义第一章绪论.ppt

数据结构 第一章 绪论 主讲：薛春艳 Algorithm + Data Structures = Programs 算法 + 数据结构 = 程序设计 一般来说，用计算机解决一个数值问题时，大致需要经过下列几个步骤： 首先要从具体问题抽象出一个适当的数学模型； 然后设计一个解此数学模型的算法； 最后编出程序，进行测试、调整至得到最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 一般来说，用计算机解决一个非数值问题时，大致需要经过下列几个步骤： 首先要从分析实际问题入手，从中提取出所要处理的数据对象，并找出这些数据对象之间的关系； 然后分析对这些数据对象所要进行的操作； 最后设计算法、编出程序，进行测试、调整至得到最终解答。 首先要从具体问题抽象出所要处理的数据对象； 在这类文档管理的数学模型中，计算机处理的数据对象之间通常存在着一种最简单的线性关系，这类数学模型可称为 线性的数据结构 。 然后分析对这些数据对象所要进行的操作； 设计对图书、借阅者、借阅情况等数据进行生成、检索、修改等操作。 最后设计算法、编出程序，测试、调整至得到最终解答。 根据选定的数据结构和要进行的操作设计算法、编写程序，测试、修改，最终应用到图书馆的借阅管理实践中。 图中所示为对弈过程中井字棋的一个棋局，从当前棋盘格局可以派生出5个格局，而从每一个新的格局又可派生出4个可能出现的格局。以此类推分析可能出现的结果，从而选择最好的位置放置棋子。 首先要从具体问题抽象出所要处理的数据对象； 若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的“树”。“树根”是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对弈的过程就是从树根沿树杈到某个叶子的过程。各棋盘数据间的关系体现为“树” 型数据结构。 然后分析对这些数据对象所要进行的操作； 对棋盘数据进行的基本操作：下棋、悔棋、判断输赢、计算得分等。 最后设计算法、编出程序，测试、调整至得到最终解答 根据选定的数据结构和要进行的操作设计算法、编写程序，测试、修改，最终应用到人机对弈实践中。 首先要从具体问题抽象出所要处理的数据对象； 连通网中的数据对象是各个城市，这些数据对象之间有着多对多的复杂的联系，这组数据对象以及它们之间的复杂关系体现的就是一种“图” 型数据结构。 然后分析对这些数据对象所要进行的操作； 对城市通讯网数据对象的操作：增加、删除、布网、修改等 最后设计算法、编出程序，测试、调整至得到最终解答 根据选定的数据结构和要进行的操作设计算法、编写程序，测试、修改，最终应用到通讯网的布网实践中。 数据的各种逻辑结构和存储结构，以及它们之间的相应关系。 并对每种结构定义相适应的各种操作。 设计出相应的算法。 分析算法的效率。 数 据（ Data ） 数据元素（ Data Element ） 数据对象（ Data Object ） 数据结构（ Data Structure） 逻辑结构（ Logical Structure） 存储结构（ Physical Structure） ADT的定义格式 算法的特性 例：求n个数的最大值问题 时间复杂度： 当问题规模n趋近于无穷时，算法耗费时间的增长率(数量级)，表示为问题规模 n 的函数： T( n )= O( f ( n ) ) 数据结构中常用的时间复杂度数量级有7个，按照数量级递增排序有: O(1) 常数型 O(log2n) 对数型 f(n)= log2n O(n) 线性型 f(n)= n O(n2) 平方型 f(n)= n2 O(n3) 立方型 f(n)= n3 O(2n) 指数型 f(n)= 2n 数据结构与其它课程关系图： 算法（Algorithm）定义 算法设计的要求 算法的特性 算法的描述方法 § 1.4 算法及其描述 算法：Algorit