CH02,CH03-数据结构入门

1、1数据结构数据结构2Niklaus Wirth Algorithm + Data Structures = Programs算法算法: :数据结构数据结构: :数据类型数据类型: : int, float, double, char, string处理问题的策略处理问题的策略问题的数学模型问题的数学模型组织和访问组织和访问数据数据的系统方法的系统方法3例例1 1：旅馆客房的管理：旅馆客房的管理算法：算法：? ?数据结构：数据结构：? ?先进先出先进先出队列队列4例例2 2：铺设城市的煤气管道：铺设城市的煤气管道算法：算法：? ?模型：模型：? ?如何规划使得总投资花费最少？如何规划使得总投资花

2、费最少？图图56集合，线性结构（数组，动态数组），树形结构，集合，线性结构（数组，动态数组），树形结构，图状或网状结构图状或网状结构其中其中线性结构线性结构又包括：向量，链表，栈，队列等又包括：向量，链表，栈，队列等7物理结构：物理结构：物理存储方式物理存储方式 （1. 1.静态的静态的 2. 2.动态的）动态的）逻辑结构：逻辑结构：数据间的逻辑关系数据间的逻辑关系 （1. 1.线性线性 2. 2.非线性）非线性）注意：注意：线性结构：线性结构：每个元素具有唯一前驱和唯一后继的数据结构，每个元素具有唯一前驱和唯一后继的数据结构， 只有首元素无前驱，只有尾元素无后继；只有首元素无前驱，只有尾元素

3、无后继；非线性结构：非线性结构：每个元素前驱、后继元素可以不唯一。每个元素前驱、后继元素可以不唯一。 例如：树、图例如：树、图8基本类型基本类型整型整型 intint字符型字符型 charchar实型实型布尔型布尔型 true/falsetrue/false单精度单精度 floatfloat双精度双精度 doubledouble构造类型构造类型数组数组Struct/ClassStruct/ClassTypedefTypedef枚举枚举 enumenum有符号有符号无符号无符号9101112假设要在假设要在C C程序里处理一些复数。可能方式：程序里处理一些复数。可能方式：1. 1. 直接用一对直

4、接用一对doubledouble变量表示一个复数。变量表示一个复数。2. 2. 定义一种结构（类型）表示复数，在程序里使用复数定义一种结构（类型）表示复数，在程序里使用复数时直接去操作这种结构的变量。时直接去操作这种结构的变量。3. 3. 定义一种结构类型表示复数，并定义一组基本操作。定义一种结构类型表示复数，并定义一组基本操作。程序里只通过这些操作使用复数，不直接使用复数的内程序里只通过这些操作使用复数，不直接使用复数的内部表示。（抽象数据类型的方式）部表示。（抽象数据类型的方式）13 (Abstract Data Type 简称简称ADT) 是指一个数据元素集合以及在这些数是指一个数据元素

5、集合以及在这些数据上的操作。据上的操作。14例如例如: :“整数整数”是一个抽象数据类型。是一个抽象数据类型。 其数学特性和具体的计算机或语言无关。其数学特性和具体的计算机或语言无关。 “ “抽象抽象”的意义在于强调数据类型的数学特性。的意义在于强调数据类型的数学特性。15抽象数据类型还包括用户在设计软件系统时自己定义的数抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。据类型。在构造软件系统的各个相对独立的模块时，定义一组数据在构造软件系统的各个相对独立的模块时，定义一组数据和施与这些数据之上的一组操作，并在模块内部给出它们和施与这些数据之上的一组操作，并在模块内部给出它们的表示和实

6、现细节，在模块外部使用的只是抽象的数据和的表示和实现细节，在模块外部使用的只是抽象的数据和抽象的操作。抽象的操作。16例如，定义抽象数据类型例如，定义抽象数据类型“复数复数” 数据对象：数据对象： De1,e2e1,e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分是复数的实数部分, , | e2 是复数的虚数部分是复数的虚数部分 ADT Complex 17基本操作：基本操作： AssignComplex( &Z, v1, v2 ) 操作结果：构造复数操作结果：构造复数 Z,Z,其实部和虚部其实部和虚部 分别被赋以参数分别被赋以参数 v1 v1 和和 v2 v2

7、 的值。的值。 DestroyComplex( &Z) 操作结果：复数操作结果：复数Z Z被销毁。被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。初始条件：复数已存在。 操作结果：用操作结果：用realPart返回复数返回复数Z Z的实部值。的实部值。18 GetImag( Z, &ImagPart ) 初始条件：复数已存在。初始条件：复数已存在。 操作结果：用操作结果：用ImagPart返回复数返回复数Z Z的虚部值。的虚部值。 Add( z1,z2, &sum ) 初始条件：初始条件：z1, z2是复数。是复数。 操作结果：用

8、操作结果：用sum返回两个复数返回两个复数z1, z2 的和值。的和值。 ADT Complex19)34()68()34)(68(iiiiz # include # include complex.h void main() 20 complex z1,z2,z3,z4,z; float RealPart,ImagPart; InitComplex(z1,8.0,6.0); InitComplex(z2,4.0,3.0); Add(z1,z2,z3); Multiply(z1,z2,z4); if (Division (z4,z3,z) GetReal (z, RealPart); GetI

9、mag (z, ImagPart); /if21ADT 有两个重要特征有两个重要特征:数据抽象数据抽象 用用ADT描述程序处理的实体时，强调的是描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）户的接口（即外界使用它的方法）数据封装数据封装 将实体的外部特性和其内部实现细节分离，将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏并且对外部用户隐藏其内部实现细节其内部实现细节22抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用抽象数据类型可用（D，S，P）三元组表示三元组表示其中，

10、其中，D 是数据对象，是数据对象， S 是是 D 上的关系集，上的关系集， P 是对是对 D 的基本操作集。的基本操作集。 23ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名其中基本操作的定义格式为其中基本操作的定义格式为: :基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件：初始条件描述初始条件描述 操作结果：操作结果：操作结果描述操作结果描述 24赋值参数赋值参数 只为操作提供输入值；只为操作提供输入值

11、；引用参数引用参数 以以&打头，除可提供输入值外，打头，除可提供输入值外，还将返回操作结果。还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相满足的条件，若不满足，则操作失败，并返回相应出错信息。应出错信息。操作结果操作结果 说明了操作正常完成之后，数据结构说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，的变化状况和应返回的结果。若初始条件为空，则省略之。则省略之。25抽象数据类型的表示和实现抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型抽象数据类型需要

12、通过固有数据类型( (高级编高级编程语言中已实现的数据类型程语言中已实现的数据类型) )来实现。来实现。例如，对以上定义的复数例如，对以上定义的复数26typedef struct float realpart； float imagpart；complex；/ -存储结构的定义存储结构的定义/ -基本操作的函数原型说明基本操作的函数原型说明void InitComplex ( complex &Z, float realval, float imagval )；/ 构造复数构造复数 Z,其实部和虚部分别被赋以参数其实部和虚部分别被赋以参数 /realval 和和 imagval 的值

13、的值27float GetReal( cpmplex Z )； / 返回复数返回复数 Z Z 的实部值的实部值float Getimag( cpmplex Z )； / 返回复数返回复数 Z Z 的虚部值的虚部值void add( complex z1, complex z2, complex &sum )； / 以以 sum 返回两个复数返回两个复数 z1, z2 的和的和 28/ -基本操作的实现基本操作的实现void add( complex z1, complex z2, complex &sum ) / 以以 sum 返回两个复数返回两个复数 z1, z2 的和的和

14、sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 29抽象数据类型（抽象数据类型（ Abstract Data TypeAbstract Data Type，ADT ADT ）的意义）的意义ADTADT建立基于数据类型的抽象屏蔽，将程序的实现建立基于数据类型的抽象屏蔽，将程序的实现与使用部分隔开，使之相互独立。与使用部分隔开，使之相互独立。30算法分析算法分析31323334void MatrixMultiply ( int Ann, int Bnn, int Cnn

15、 ) for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) Cij = 0; for ( int k = 0; k n; k+ ) Cij = Cij + Aik * Bkj; 2n3 + 3n2 + 2n +1 n+1 n(n+1) n2 n2(n+1) n335O(1) O(logn) O(n) O(nO(1) O(logn) O(n) O(n2 2) O(2) O(2n n) )常数常数/ /对数对数/ /线性线性/ /平方平方/ /指数指数36最坏情况时间复杂性最坏情况时间复杂性 平均时间复杂性平均时间复杂性 最好情况时间复杂性（不

16、太有用）最好情况时间复杂性（不太有用）对空间复杂性也可以有类似考虑对空间复杂性也可以有类似考虑考虑考虑 ?37算法时间复杂性的计算规则算法时间复杂性的计算规则1. 1. 加法规则（顺序复合）加法规则（顺序复合）算法分为两部分时，复杂性是两部分的复杂性之和算法分为两部分时，复杂性是两部分的复杂性之和T(n) = T1(n) + T2(n) = O(f1(n) + O(f2(n) = O(max(f1(n), f2(n)2. 2. 乘法规则（循环）乘法规则（循环）循环循环T T1(1(n n) ) 次，每次次，每次T T2(2(n n) ) 时间，则时间，则T(n) = T1(n)T2(n) = O(f1(n) O(f2(n)= O(f1(n)f2(n)