数据结构第1章-新1ppt课件

1、例。例。要学会描述数据结构要学会描述数据结构和算法，分析算法的时、和算法，分析算法的时、空复杂度。空复杂度。第第1 1章章 基础知识基础知识 和算法描述的方法和算法描述的方法4 4介绍算法和算介绍算法和算法分析的基本方法法分析的基本方法1.1 1.1 算法和数据结构算法和数据结构瑞士的瑞士的WirthWirth博士图灵奖获得者博士图灵奖获得者提出：程序算法提出：程序算法+ +数据结构数据结构1.1 1.1 算法和数据结构算法和数据结构的基本的基本方法方法 数据结构和算法是计算机学科的数据结构和算法是计算机学科的基础之一，更是软件技术的基础。基础之一，更是软件技术的基础。 算法设计通常建立在所处

2、理的数算法设计通常建立在所处理的数据之上的，精心选择的数据结构可以据之上的，精心选择的数据结构可以带来更高效率的算法。带来更高效率的算法。 程序算法程序算法+数据结构数据结构 精心设计的数据结构真的可以带来更高效精心设计的数据结构真的可以带来更高效率的算法吗？率的算法吗？ 图一图一， 图二 数据在计算机中的表示和存储不能是无组织的，是有规律，有结构的。 1.2 1.2 什么是数据结构什么是数据结构 1.2.1 1.2.1 基本概念基本概念表表1.1 学生情况表学生情况表学号学号姓名姓名性别性别其他信息其他信息B02040101王小红王小红女女B02040102林悦林悦女女B02040103陈菁

3、陈菁女女B02040104张可可张可可男男数据项数据项l 数据结构包括三个方面数据结构包括三个方面l 逻辑结构：数据元素间的逻辑关系；逻辑结构：数据元素间的逻辑关系；l 存储结构：数据在计算机内的表示形式；存储结构：数据在计算机内的表示形式；l 运算：在数据上执行的操作。运算：在数据上执行的操作。数据结构举例数据结构举例 表表1.1 学生情况表学生情况表学号学号姓名姓名性别性别其他信息其他信息B02040101王小红王小红女女B02040102林悦林悦女女B02040103陈菁陈菁女女B02040104张可可张可可男男逻辑结构，存储结构，运算逻辑结构，存储结构，运算1.2.2 1.2.2 数据

4、的逻辑结构数据的逻辑结构 数据结构的逻辑结构可以用一个二元组表示。数据结构的逻辑结构可以用一个二元组表示。即即 DS = （D， R）其中，其中， D是数据元素的有限集合，是数据元素的有限集合，R是是D中数据元中数据元素序偶的集合。素序偶的集合。例如例如DS=D,R,D=a,b,c,d,R=,DS=D,R,D=a,b,c,d,R=,其中，序偶其中，序偶表示表示a a和和b b之间的关系，我们称为之间的关系，我们称为a a是是b b的直接前驱，的直接前驱，b b是是a a的直接后继。小圆圈代表数据的直接后继。小圆圈代表数据元素，两个不同元素的序偶称为边。元素，两个不同元素的序偶称为边。abcd4

5、 4种基本的逻辑结构种基本的逻辑结构 (a)(a)集合结构集合结构(b)(b)线性结构线性结构(c)(c)树形结构树形结构(d)(d)图结构图结构图图1-2 1-2 四种基本的结构关系四种基本的结构关系对数据元素间逻辑关系的描述称为数据的逻辑结构。对数据元素间逻辑关系的描述称为数据的逻辑结构。根据数据结构中数据元素之间关系的不同特征，可以根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构：划分为以下四种基本逻辑结构： 四种逻辑结构也可以分成两类：线性结构和非线性结构。四种逻辑结构也可以分成两类：线性结构和非线性结构。(a)(a)集合结构集合结构(b)(b)线性结构线性结构

6、(c)(c)树形结构树形结构(d)(d)图结构图结构图图1-2 1-2 四种基本的结构关系四种基本的结构关系 地址信息称为链。地址信息称为链。 表示空链。表示空链。1.2.3 1.2.3 数据的存储表示数据的存储表示其中，顺序和链接是两种最基本的存储表示方法。其中，顺序和链接是两种最基本的存储表示方法。 例如，例如， 由由4个元素组成的线性数据结个元素组成的线性数据结构构a0, a1, a2, a3），存储在某个连续的），存储在某个连续的存储区内，设存储区的起始地址是存储区内，设存储区的起始地址是102，假定每个元素占假定每个元素占2个存储单元。个存储单元。Loc(ak) = 102 + 2

7、k例如，线性结构（例如，线性结构（ a0, a1, a2, a3 ）的链接存储表示。）的链接存储表示。 结点存储块分成两部分，元素本身和该元素后继元素所结点存储块分成两部分，元素本身和该元素后继元素所在结点的存储地址。在结点的存储地址。 链接存储表示下，为在机内存储一个元素，除了需要存放该元链接存储表示下，为在机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放于该元素相关的其它元素的地址素本身的信息外，还需要存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。信息。这两部分信息组成一个数据元素的结点。逻辑结构逻辑结构存储结构存储结构概念概念数据元素之间逻数据元素

8、之间逻辑关系的描述辑关系的描述数据及其关系数据及其关系在计在计算机内的组织方式算机内的组织方式面向面向面向应用问题面向应用问题面向计算机面向计算机关系关系存储结构是逻辑结构在计算机内的映像存储结构是逻辑结构在计算机内的映像 数据结构最常见的运算数据结构最常见的运算 创建运算创建运算: :创建一个数据结构；创建一个数据结构； 清除运算清除运算: :删除数据结构中的全部元素；删除数据结构中的全部元素； 插入运算插入运算: :在数据结构的指定位置上插入一在数据结构的指定位置上插入一个新元素；个新元素； 删除运算删除运算: :将数据结构中的某个元素删除；将数据结构中的某个元素删除； 1.3 1.3 数

9、据抽象和抽象数据类型数据抽象和抽象数据类型 笼统，封装和信息隐蔽是控制软笼统，封装和信息隐蔽是控制软件开发复杂度，提高软件可靠性件开发复杂度，提高软件可靠性的重要手段的重要手段 本书采用抽象数据类型的观点讨本书采用抽象数据类型的观点讨论数据结构。论数据结构。 1. C 1. C 语言的数据类型语言的数据类型(1)(1)基本类型：字符、整型基本类型：字符、整型 (2)(2)构造类型：数组、结构和联合构造类型：数组、结构和联合(3)(3)指针类型：指针指针类型：指针例如，例如，int a; int a; 变量变量a a 的取值范围是：的取值范围是：-32768-327683276732767对变量

10、对变量a a执行的操作有：执行的操作有： 算术运算算术运算 + +、- -、* *、/ /、% % 关系运算关系运算 、=、=、!=!=2. 2. 数据类型数据类型 一个数据类型定义了一个值的集合以及作一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。用于该值集的操作的集合。 即一组值和一组操作。即一组值和一组操作。1.3.3 1.3.3 数据类型和抽象数据类数据类型和抽象数据类型型 抽象数据类型抽象数据类型Abstract Data Type, ADTAbstract Data Type, ADT是一个是一个数据类型，其主要特征是该类型的对象及其操作的规数据类型，其主要特征是该类型

11、的对象及其操作的规范范, ,与该类型对象的表示和操作的实现分离，实行封与该类型对象的表示和操作的实现分离，实行封装和信息隐蔽，即使用和实现分离。装和信息隐蔽，即使用和实现分离。使用和实现分离：使用者通过规范使用该类型的数据，使用和实现分离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。而不必考虑其实现细节；改变实现将不影响使用。例如，例如，C+C+中的整型中的整型intint就是抽象数据类型。它的实现是隐就是抽象数据类型。它的实现是隐蔽的，使用者只能通过整型上定义的一组运算对整型变量蔽的，使用者只能通过整型上定义的一组运算对整型变量 执行操作。执行操作。3.3.抽

12、象数据类型抽象数据类型规范指明规范指明“做什么做什么”，实现解决实现解决“怎样做怎样做”。规范是实现的准则和依据规范是实现的准则和依据一个数据结构包含两个层次：一个数据结构包含两个层次：(1)(1)数据结构的规范抽象层）：数据结构的规范抽象层）： 逻辑结构和运算的定义组成了数据结构的规范逻辑结构和运算的定义组成了数据结构的规范(2)(2)数据结构的实现实现层）：数据结构的实现实现层）： 存储结构和运算算法实现构成了数据结构的实存储结构和运算算法实现构成了数据结构的实现现1.3.4 1.3.4 数据结构和抽象数据类数据结构和抽象数据类型型 一种数据结构被视为一个抽象数据类型。一种数据结构被视为一

13、个抽象数据类型。本书是怎样描述每种数据结构？本书是怎样描述每种数据结构？1.4 1.4 描述数据结构和算法描述数据结构和算法 首先描述数据结构的规范逻辑结构和运首先描述数据结构的规范逻辑结构和运算的定义）算的定义） 然后介绍数据结构的实现存储结构和运然后介绍数据结构的实现存储结构和运算的具体程序实现），算的具体程序实现）， （1 1用格式化的自然语言来描述数据结构的规范。用格式化的自然语言来描述数据结构的规范。（2 2用一个用一个C+C+的抽象模板类描述数据结构的规范。的抽象模板类描述数据结构的规范。1.4.1 1.4.1 数据结构的规范数据结构的规范1.4 1.4 描述数据结构和算法描述数据

14、结构和算法对数据结构的规范的描述：对数据结构的规范的描述：数据结构描述举例数据结构描述举例-堆栈堆栈1.4.1 1.4.1 数据结构的规范数据结构的规范ADT 1.1 ADT 1.1 栈抽象数据类型栈抽象数据类型ADT StackADT Stack Data: Data: ( (描述逻辑结构描述逻辑结构) ) 0 0个或多个元素的线性序列个或多个元素的线性序列a0a0，a1a1， ，an-1)an-1)， 遵循遵循LIFOLIFO原则。原则。 Operations:Operations:( (描述运算的定义描述运算的定义) ) Create() Create()：创建一个空栈。：创建一个空栈。

15、 Destroy():Destroy():撤消一个栈。撤消一个栈。 Push(x)Push(x)：元素：元素x x插入栈顶。插入栈顶。 Pop()Pop()：删除栈顶元素。：删除栈顶元素。 Top(x)Top(x)：在：在x x中返回栈顶元素。中返回栈顶元素。 （1 1用用ADTADT描述数据结构描述数据结构堆栈的例子堆栈的例子对堆栈的规范的描述：对堆栈的规范的描述：程序程序 1.1 1.1 栈的栈的C+C+模板抽象类模板抽象类templatetemplateclass Stackclass Stack public: public: virtual void Push(T x)=0; vir

16、tual void Push(T x)=0; virtual void Pop()=0; virtual void Pop()=0; virtual T Top(T &x)const=0; virtual T Top(T &x)const=0; ; 除了构造函数，其余成员函数都是纯虚函数。顺序栈除了构造函数，其余成员函数都是纯虚函数。顺序栈类类SeqStackSeqStack是类是类StackStack在顺序存储表示下的一种实现，它在顺序存储表示下的一种实现，它是从抽象类是从抽象类StackStack派生出来的，它可以实例化。派生出来的，它可以实例化。（2用用C+模板抽象类描述数据结构模板抽象

17、类描述数据结构templatetemplatebool SeqStack:Push(T &x)bool SeqStack:Push(T &x) if(IsFull() if(IsFull() coutOverflowendl; coutOverflowendl; return false; return false; s+top=x; s+top=x; return true; return true; 1.4.1.4. 实现数据结构实现数据结构堆栈的实现：堆栈的实现：1.5 1.5 算法分析的基本方法算法分析的基本方法1.1.什么是算法什么是算法 一个算法一个算法(algorithm)(al

18、gorithm)是对特定问题的求解步骤的一种描是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：述，它是指令的有限序列；此外，算法具有下列五个特征： (1)(1)输入输入 算法有零个或多个输入。算法有零个或多个输入。 (2)(2)输出输出 算法至少产生一个输出算法至少产生一个输出 (3)(3)确定性确定性 算法的每一条指令都有确切的定义，没有算法的每一条指令都有确切的定义，没有二义性。二义性。 (4)(4)能行性能行性 算法的每一条指令都足够基本，它们可以算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。通过已经实现的基本运算执行有限次

19、来实现。 (5)(5)有穷性有穷性 算法必须总能在执行有限步之后终止。算法必须总能在执行有限步之后终止。 1.5.1 1.5.1 算法及其性能分析算法及其性能分析 2. 2. 算法描述方法算法描述方法 算法可以自然语言、流程图或程序设计语言描述。算法可以自然语言、流程图或程序设计语言描述。 当一个算法用程序设计语言描述时，便成为程序。当一个算法用程序设计语言描述时，便成为程序。 本书中，主要使用本书中，主要使用C+C+语言描述。语言描述。3. 3. 算法的性能标准算法的性能标准 正确性：算法的执行结果应当满足预先规定的功能和性能正确性：算法的执行结果应当满足预先规定的功能和性能 要求。要求。(

20、2)(2)简明性：一个算法应当思路清晰、层次分明、易读易懂。简明性：一个算法应当思路清晰、层次分明、易读易懂。(3)(3)健壮性：当输入不合法数据时，应能做适当处理，不至于健壮性：当输入不合法数据时，应能做适当处理，不至于 引起严重后果。引起严重后果。(4)(4)效效 率：有效使用存储空间和有高的时间效率。率：有效使用存储空间和有高的时间效率。(5)(5)最优性：解决同一个问题可能有多种算法，应进行比较，最优性：解决同一个问题可能有多种算法，应进行比较， 选择最佳算法。选择最佳算法。 1.5.2 1.5.2 算法的时间复杂度算法的时间复杂度 程序步程序步 一个程序步是指在语法上或语义上有意义一

21、个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的的程序段，该程序段的执行时间与问题实例的特征无关。特征无关。算法的时间复杂度算法的时间复杂度 是程序运行从开始到结束所需的时间。是程序运行从开始到结束所需的时间。 程序程序1.3 1.3 求一个数组元素的累加之和求一个数组元素的累加之和float sum(float list,const int n)float sum(float list,const int n) float tempsum=0.0; float tempsum=0.0; for(int i=0;in;i+) for(int i=0;in;i+) te

22、mpsum+=listi; tempsum+=listi; return tempsum; return tempsum; 程序步数为程序步数为2n+32n+3。1.5.3 1.5.3 渐近时间复杂度渐近时间复杂度 大大O O记号记号 如果存在两个正常数如果存在两个正常数c c和和n0n0，使得对所有的，使得对所有的n n，n nn0 n0 ，有，有f(n)f(n) c g(n) c g(n)则有则有 f(n)=O(g(n)f(n)=O(g(n)。渐近时间复杂度渐近时间复杂度 使用大使用大O O记号表示的算法的时间复杂性，称为算法的渐近记号表示的算法的时间复杂性，称为算法的渐近时间复杂度时间复

23、杂度, ,简称时间复杂度。简称时间复杂度。渐近时间复杂度渐近时间复杂度 使用大使用大O O记号表示的算法的时间复杂性，称为算法的渐近记号表示的算法的时间复杂性，称为算法的渐近时间复杂度时间复杂度, ,简称时间复杂度。简称时间复杂度。 大大O O记号用以表达一个算法运行时间的上界，可用程序记号用以表达一个算法运行时间的上界，可用程序步在数量级上估计算法的执行时间。步在数量级上估计算法的执行时间。 例如，设例如，设 T(n)= 3.6n3+2.5n2+2.8T(n)= 3.6n3+2.5n2+2.88.9n38.9n3则根据大则根据大O O记号的定义容易证明记号的定义容易证明 T(n)= O(n3

24、)T(n)= O(n3)例如，程序例如，程序1.21.2为求一个数组元素的累加之和的算法。为求一个数组元素的累加之和的算法。float sum(float list,const int n)float sum(float list,const int n) float tempsum=0.0; / 1 float tempsum=0.0; / 1 for (int i=0; in; i+ ) / n+1 for (int i=0; in; i+ ) / n+1 tempsum += listi; / n tempsum += listi; / n return tempsum; / 1 ret

25、urn tempsum; / 1 （1 1总的程序步数为总的程序步数为2n+3 2n+3 ，则渐近时间复杂性为，则渐近时间复杂性为O(n)O(n)。float sum(float list,const int n)float sum(float list,const int n) float tempsum=0.0; / 1 float tempsum=0.0; / 1 for (int i=0; in; i+ ) / n+1 for (int i=0; in; i+ ) / n+1 tempsum += listi; / n tempsum += listi; / n return temp

26、sum; / 1 return tempsum; / 1 （2 2语句语句tempsum+=listitempsum+=listi可认为是关键操作，它的执行次可认为是关键操作，它的执行次数为数为n n次，则渐近时间复杂性为次，则渐近时间复杂性为O(n)O(n)。很多情况下，可以通过考察一个算法中的关键操作关键操作很多情况下，可以通过考察一个算法中的关键操作关键操作被认为是一个执行次数最多的程序步的执行次数来计算算法被认为是一个执行次数最多的程序步的执行次数来计算算法的渐近时间复杂性。的渐近时间复杂性。 常见的渐近时间复杂性从小到大排列有：常见的渐近时间复杂性从小到大排列有： O(1) O(lo

27、g2 n) O(n) O(nlog2 n) O(n2) O(n3) 例如：例如： 若某算法程序的总程序步为若某算法程序的总程序步为4,则其渐近则其渐近时间复杂性为多少？时间复杂性为多少？ O(4)是错误写法。是错误写法。 应为应为O(1)void Mult(int ann, bnn, cnn, int n)void Mult(int ann, bnn, cnn, int n) / n / nn n矩阵矩阵a a与与b b 相乘得到相乘得到c c。 for (int i=0;in;i+) / n+1for (int i=0;in;i+) / n+1 for(int j=0;jn;j+) / n(n+1) for(int j=0;jn;j+) / n(n+1) c