哈工大数据结构1.ppt

数据结构(C语言版) Data Structure 例1_1： 书目自动检索系统 例1_2： 人机对奕问题 其中： O( f(n) )表示取函数 f(n) 的数量级。 O表示T(n) 与f(n)只相差一个常数倍。 它表示随着问题规模 n 的增大，算法执行时间的增 长率和f(n)的增长率属于同一数量级。 即算法执行时间随 f(n)的增长而增长。 由于 3 条语句均执行 1 次，此算法共执行 3 次。所以： f(n)=3 即：执行次数 f(n) 是与问题规模 n 无关的常量。所以： T(n)=O( f(n) ) =O( 3 ) =O( 1 ) 即：算法的时间复杂度为常数阶。 即：T(n)=O(1) 表示时间复杂度不随问题规模 n 的变化 而变化。 此算法共执行次数： f(n)= n2+n+2 所以：T(n)=O( f(n) ) =O( n2+n+2 ) = O(n(n+1)+2) 取T(n)的数量级阶，得最后结果为： T(n)=O(n2) 语句 1 执行的次数是：1 设语句 2 执行的次数是：f(n) 则有：i=2f(n) 因为：i=n 所以： 2f(n) =n 两边以2为底取对数并取最大值得： 则该程序段的时间复杂度为： 即: f(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2 所以： T(n)=O(n3/6+低次项) 取 T(n) 的数量级阶，得最后结果为： T(n)=O(n3) 例1_9： 分析以下程序段的时间复杂度 i=1; //语句1 while (i=n) //语句2 i=i﹡2 内循环的执行次数虽与问题规模 n 无直接关系，但 与外循环变量的取值有关。 因此从内循环向外循环分析 执行次数。 例1_10：分析以下程序段的时间复杂度 x=1; for (i=1;i=n;i++) for (j=1;j=i;j++) for (k=1;k=j;k++) x++; 在C语言中表示和实现ADT描述时，主要包括以下两个方面: (1) 通过结构体将int、 float等固有类型组合到一起, 构成一个结构类型, 再用typedef为该类型或该类型指针重新起一个名字。  (2) 用C语言函数实现各操作。 P10~11 C语言功能的回顾 定义1（简单定义）： 是相互之间存在一种或多种特定关系的数据元素的集合。 定义2（较统一的定义）： 具有某种逻辑关系的数据（或称带结构的数据元素 的集合）按一定的存储表示方式进行存储，并在其上定 义了一个运算的集合。 数据结构定义 存储结构（物理结构）： 数据元素及其关系在计算机存储器中的存储方式。是逻辑 结构用计算机语言的实现，它依赖于计算机语言。 逻辑结构： 数据元素间抽象化的相互关系（简称为数据的结构）。与 数据的存储无关，独立于计算机，它是从具体问题抽象出来的 数学模型。 算法（运算）： 是对数据加工过程的描述。 数据结构三个方面的含义： 1.2 数据的逻辑结构 线性结构： 结构中的数据元素之间存在一对一的关系。 集合： 结构中的数据元素除了同属于一种类型外，别无其它关系。 根据数据元素之间关系的不同特性，可分为 4 类基本结构： 1. 逻辑结构分类 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 树型结构 结构中的数据元素之间存在一对多的关系。 2.逻辑结构描述 数据元素之间的逻辑关系，称为数据的逻辑结构。 一个数据的逻辑结构 G 可以用二元组来表示： G=(D,R) 其中：D 是数据元素（结点）的集合。 R 是 D