数据结构[严蔚敏]1

1、数 据 结 构严蔚敏严蔚敏 吴伟民吴伟民 数据结构课程是本科计算机专业的一门专业基数据结构课程是本科计算机专业的一门专业基础课。它涉及在计算机中如何有效地础课。它涉及在计算机中如何有效地表示数据表示数据，如，如何合理地何合理地组织数据组织数据和和处理数据处理数据。还涉及。还涉及初步的算法初步的算法设计和算法性能分析技术设计和算法性能分析技术。学好数据结构课程，将。学好数据结构课程，将为后续的专业课程，如数据库系统、操作系统、编为后续的专业课程，如数据库系统、操作系统、编译原理等，打下良好的知识基础，而且还为软件开译原理等，打下良好的知识基础，而且还为软件开发和程序设计提供了必要的技能训练。发和

2、程序设计提供了必要的技能训练。 教材教材: 数据结构（数据结构（C C语言版）语言版） 作者作者: 严蔚敏严蔚敏 吴伟民吴伟民 出版社出版社: 清华大学出版社清华大学出版社参考书目：参考书目：l 数据结构题集（数据结构题集（C C语言版）作者语言版）作者: 严蔚敏严蔚敏 吴伟民吴伟民 清华大学出版社清华大学出版社l 数据结构与算法分析数据结构与算法分析, Clifford A. Shaffer著，著， 张张 铭，刘晓丹铭，刘晓丹 译。电子工业出版社。译。电子工业出版社。l 数据结构（数据结构（C+） 殷人昆殷人昆 清华大学出版社清华大学出版社l 数据结构（数据结构（C+） 刘大有刘大有l 数据

3、结构学习指导与典型题解数据结构学习指导与典型题解 朱站立等朱站立等 西安电子交大西安电子交大l 数据结构数据结构 习题与解析习题与解析 李春葆李春葆 清华大学出版社清华大学出版社l必须熟练地掌握必须熟练地掌握C语言程序设计与调试语言程序设计与调试!1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 算法和算法分析算法和算法分析 1.4.1 算法算法 1.4.2 算法设计的要求算法设计的要求 1.4.3 算法效率的度量算法效率的度量 1.4.4 算法的存储空间需求算法的存储空间需求学习提要1.1. 掌握本课程所涉

4、及到的基本名词、术语和概念，特别是掌握本课程所涉及到的基本名词、术语和概念，特别是数据的逻辑结构和存储结构之间的关系及性质。数据的逻辑结构和存储结构之间的关系及性质。2.2. 了解抽象数据类型的定义、表示和实现方法。了解抽象数据类型的定义、表示和实现方法。 3.3. 理解算法设计的五个要素和基本要求；掌握算法效率的理解算法设计的五个要素和基本要求；掌握算法效率的度量方法，着重学习算法的时间复杂度分析。度量方法，着重学习算法的时间复杂度分析。4.4. 掌握计算语句频度和掌握计算语句频度和估算算法时间复杂度估算算法时间复杂度的方法。的方法。第1章 绪 论 目前，计算机已深入到社会生活的各个领域，其

5、应用已不再仅仅局限于科学计算，而更多的是用于控制，管理及数据处理等非数值计算领域。p 数据结构是数据结构是一门研究用计算机进行一门研究用计算机进行信息表示和处理信息表示和处理的的科学科学。 这里面涉及到两个问题：信息的表示，信息的处理。信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。p 因此因此，必须分析待处理问题中的，必须分析待处理问题中的对象的特征对象的特征及及各对象各对象之间存在的关系之间存在的关系，这就是数据结构这门课所要研究的问，这就是数据结构这门课所要研究的问题。题。1编写

6、解决实际问题的程序的一般过程编写解决实际问题的程序的一般过程： 如何用数据形式描述问题如何用数据形式描述问题? 即由问题抽象出一个即由问题抽象出一个适当的数学模型适当的数学模型; 问题所涉及的数据量大小及数据之间的关系问题所涉及的数据量大小及数据之间的关系; 如何在计算机中存储数据及体现数据之间的关系如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好所编写的程序的性能是否良好?上面所列举的问题基本上由数据结构这门课程来回答。上面所列举的问题基本上由数据结构这门课程来回答。计算机求解问题的一般步骤计算机求解问题

7、的一般步骤21.1 数据结构数据结构 数据结构数据结构是计算机科学中的一门综合性专业基础是计算机科学中的一门综合性专业基础课课。是。是介于介于数学数学、计算机硬件计算机硬件、计算机软件计算机软件三者之间的三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。程序和大型应用程序的重要基础。3 数据结构的例子数据结构的例子姓名姓名电话号码电话号码陈海陈四锋李四例1：电话号

8、码查询系统：电话号码查询系统 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的名字和其相个人的名字和其相应的电话号码，假定按如下形式安排：应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，(an, bn)，其中其中ai, bi(i=1，2n) 分别表示某人的名分别表示某人的名字和电话号码。字和电话号码。 本问题是一种典型的表格问题本问题是一种典型的表格问题。如表如表1-1，数据与数据成简单的一对一的，数据与数据成简单的一对一的线性关系线性关系。表表1-1线性表结构线性表结构例例2：磁盘目录文件系统：磁盘目录文件系统 磁盘根目录下有很多子目录及磁盘根目录下有很

9、多子目录及文件，每个子目录里又可以包含文件，每个子目录里又可以包含多个子目录及文件，但每个子目多个子目录及文件，但每个子目录只有一个父目录，依此类推录只有一个父目录，依此类推： 本问题是一种典型的树型结本问题是一种典型的树型结构问题，如图构问题，如图1-1 ，数据与数据，数据与数据成一对多的关系，是一种典型的成一对多的关系，是一种典型的非线性关系结构非线性关系结构树形结构树形结构。树形树形4例例3：交通网络图：交通网络图 从一个地方到另外一个地方可以有多条路径从一个地方到另外一个地方可以有多条路径。本问本问题是一种典型的题是一种典型的网状结构网状结构问题，数据与数据成多对多的问题，数据与数据成

10、多对多的关系，是一种非线性关系结构关系，是一种非线性关系结构。佛山惠州广州中山东莞深圳珠海图图1-2 网状结构网状结构5 数据数据(Data) ：是客观事物的符号表示。在计算机科学：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。符号的总称。 数据元素数据元素(Data Element) ：是数据的基本单位，在程：是数据的基本单位，在程序中通常序中通常作为一个整体作为一个整体来进行考虑和处理。来进行考虑和处理。 一个数据元素可由若干个一个数据元素可由若干个数据项数据项(Data Item)组成。数组成

11、。数据项是数据的不可分割的最小单位。数据项是对客观事据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。物某一方面特性的数据描述。 数据对象数据对象(Data Object)：是性质相同的数据元素的集：是性质相同的数据元素的集合，是数据的一个子集。如字符集合合，是数据的一个子集。如字符集合C=A,B,C, 。1.2 基本概念和术语基本概念和术语6 数据结构数据结构(Data Structure)：是指相互之间具有：是指相互之间具有(存在存在)一定联系一定联系(关系关系)的数据元素的集合。元素之间的相互联的数据元素的集合。元素之间的相互联系系(关系关系)称为称为逻辑结构逻辑

12、结构。数据元素之间的逻辑结构有四。数据元素之间的逻辑结构有四种基本类型，如图种基本类型，如图1-5所示所示。 集合集合：结构中的数据元素除了：结构中的数据元素除了“同属于一个集合同属于一个集合”外，没有其它关系。外，没有其它关系。 线性结构线性结构：结构中的数据元素之间存在一对一的：结构中的数据元素之间存在一对一的关系关系。7 树型结构树型结构：结构中的数据元素之间存在一对多的：结构中的数据元素之间存在一对多的关系。关系。 图状结构或网状结构图状结构或网状结构：结构中的数据元素之间存：结构中的数据元素之间存在多对多的关系。在多对多的关系。图图1-5四类基本四类基本8 数据结构的形式定义是一个二

13、元组：数据结构的形式定义是一个二元组： Data-Structure=(D，S)其中：其中：D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限集。上关系的有限集。例例2：设数据逻辑结构：设数据逻辑结构B=（K，R） K=k1, k2, , k9 R= ， 画出这逻辑结构的图示，并确定那些是起点，那些是终点画出这逻辑结构的图示，并确定那些是起点，那些是终点1.2.1 数据结构的形式定义数据结构的形式定义9 数据元素之间的关系可以是元素之间代表某种数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人含义的自然关系，也可以是为处理问题方便而人为定义的关系，这

14、种为定义的关系，这种自然自然或或人为定义的人为定义的 “关系关系”称为数据元素之间的称为数据元素之间的逻辑关系逻辑关系，相应的，相应的结构结构称为称为逻辑结构逻辑结构。101.2.2 数据结构的存储方式数据结构的存储方式 数据结构在计算机内存中的存储包括数据结构在计算机内存中的存储包括数据元素的存数据元素的存储储和和元素之间的关系的表示元素之间的关系的表示。 元素之间的关系在计算机中有两种不同的表示方法：元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示顺序表示和非顺序表示。由此得出两种不同的存储结构：由此得出两种不同的存储结构：顺序存储结构顺序存储结构和和链式存储结构链式存储

15、结构。 顺序存储结构顺序存储结构：用数据元素在存储器中的相对位用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构置来表示数据元素之间的逻辑结构(关系关系)。 链式存储结构链式存储结构：在每一个数据元素中增加一个存在每一个数据元素中增加一个存放另一个元素地址的指针放另一个元素地址的指针(pointer )，用该指针来表，用该指针来表示数据元素之间的逻辑结构示数据元素之间的逻辑结构(关系关系)。11例例：设有数据集合设有数据集合A=3.0,2.3,5.0,-8.5,11.0 ，两种不同，两种不同的存储结构。的存储结构。 顺序结构：数据元素存放的顺序结构：数据元素存放的地址是连续的地址是连续

16、的； 链式结构：数据元素存放的链式结构：数据元素存放的地址是否连续没有要地址是否连续没有要求求。 数据的逻辑结构和物理结构是密不可分的两个方面，数据的逻辑结构和物理结构是密不可分的两个方面，一个一个算法的设计取决于算法的设计取决于所选定的所选定的逻辑结构逻辑结构，而，而算法的实算法的实现依赖于现依赖于所采用的所采用的存储结构存储结构。 在在C语言中，用语言中，用一维数组一维数组表示顺序存储结构表示顺序存储结构；用用结构结构体类型体类型表示链式存储结构。表示链式存储结构。12数据结构的三个组成部分：数据结构的三个组成部分：逻辑结构逻辑结构： 数据元素之间逻辑关系的描述数据元素之间逻辑关系的描述

17、D_S=（D，S）存储结构存储结构： 数据元素在计算机中的存储及其逻辑数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构关系的表现称为数据的存储结构或物理结构或物理结构。数据操作数据操作： 对数据要进行的运算对数据要进行的运算。113 数据类型数据类型(Data Type)：指的是：指的是一个值的集合一个值的集合和定义和定义在在该值集上的一组操作该值集上的一组操作的总称。的总称。 数据类型是和数据结构密切相关的一个概念。数据类型是和数据结构密切相关的一个概念。 在在C语言中数据类型有：基本类型和构造类型。语言中数据类型有：基本类型和构造类型。 数据结构不同于数据类型，也不同于数据对象

18、，它数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。各元素之间的相互关系。1.2.3 数据类型数据类型14 数据结构的主要运算包括：数据结构的主要运算包括： 建立建立(Create)一个数据结构；一个数据结构； 销毁销毁(Destroy)一个数据结构；一个数据结构； 从一个数据结构中删除从一个数据结构中删除(Delete)一个数据元素；一个数据元素； 把一个数据元素插入把一个数据元素插入(Insert)到一个数据结构中；到一个数据结构中； 对一个数据结构进行访问对一个数据结构进行访

19、问(Access)； 对一个数据结构对一个数据结构(中的数据元素中的数据元素)进行修改进行修改(Modify)； 对一个数据结构进行排序对一个数据结构进行排序(Sort)； 对一个数据结构进行查找对一个数据结构进行查找(Search)。1.2.4 数据结构的运算数据结构的运算15 抽象数据类型抽象数据类型(Abstract Data Type ，简称，简称ADT)：是指：是指一个数学模型以及定义在该模型上的一组操作。一个数学模型以及定义在该模型上的一组操作。 ADT的定义仅是一组逻辑特性描述，的定义仅是一组逻辑特性描述， 与其在计算机与其在计算机内的表示和实现无关。因此，不论内的表示和实现无关

20、。因此，不论ADT的内部结构如何的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。变化，只要其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：的形式化定义是三元组：ADT=(D，S，P)其中：其中：D是是数据对象数据对象，S是是D上的上的关系集关系集，P是对是对D的的基本基本操作集操作集。1.3 抽象数据类型抽象数据类型16 抽象数据类型由基本的数据模型及定义在该模型上一组相关操作组成的。 是逻辑特性的表示，与在计算机内的表示和实现细节无关。 抽象数据类型的基本特征： (1) 表示与实现分离是抽象数据类型的第一个特征。 使设计者在问题分析时先抓住反映问题本质的东西，而

21、避免陷入非本质的细节。 (2) 对数据和操作封装是抽象数据类型的第二个特征。 对于两个数据成员完全相同的数据类型，如果它们具有不同的操作，那么它们可形成不同的抽象数据类型。ADT的一般定义形式是：的一般定义形式是：ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象： 数据关系：数据关系： 基本操作：基本操作： ADT 抽象数据类型名抽象数据类型名 其中数据对象和数据关系的定义用其中数据对象和数据关系的定义用伪码伪码描述。描述。 基本操作的定义是：基本操作的定义是：()初始条件：初始条件： 操作结果：操作结果： 17 初始条件：初始条件：描述操作执行之前数据结构和参数应描述操作执行之前数据

22、结构和参数应满足的条件满足的条件;若不满足，则操作失败，返回相应的出若不满足，则操作失败，返回相应的出错信息。错信息。 操作结果：操作结果：描述操作正常完成之后，数据结构的描述操作正常完成之后，数据结构的变化状况和变化状况和 应返回的结果。应返回的结果。课后仔细阅读1.3节，并记住类C语言的书写规范。181.4.1 算法算法算法算法(Algorithm)：是对特定问题求解方法：是对特定问题求解方法(步骤步骤)的一种描的一种描述，是指令的有限序列，其中每一条指令表示一个或多述，是指令的有限序列，其中每一条指令表示一个或多个操作。个操作。算法具有以下五个特性算法具有以下五个特性 有穷性有穷性： 一

23、个算法必须总是在执行有穷步之后结一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。束，且每一步都在有穷时间内完成。 确定性确定性：算法中每一条指令必须有确切的含义。：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。不存在二义性。且算法只有一个入口和一个出口。 可行性可行性： 一个算法是能行的。即算法描述的操作一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。都可以通过已经实现的基本运算执行有限次来实现。1.4 算法分析初步算法分析初步19 输入输入： 一个算法有零个或多个输入，这些输入一个算法有零个或多个输入，这些输入

24、取自于某个特定的对象集合。取自于某个特定的对象集合。 输出输出： 一个算法有一个或多个输出，这些输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。是同输入有着某些特定关系的量。 一个算法可以用多种方法描述，主要有：使用自然一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语语言描述；使用形式语言描述；使用计算机程序设计语言描述。言描述。 算法和程序是两个不同的概念算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。 在本门课程的学习、作业练习、上机实践等

25、环节，算法都用类C语言来描述。在上机实践时，为了检查算法是否正确，应编写成完整的C语言程序。20评价一个好的算法有以下几个标准评价一个好的算法有以下几个标准 正确性正确性： 算法应满足具体问题的需求。算法应满足具体问题的需求。 可读性可读性： 算法应容易供人阅读和交流。可读性算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。好的算法有助于对算法的理解和修改。 健壮性健壮性： 算法应具有容错处理。当输入非法或算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。而不会产生莫名其妙的

26、输出结果。效率与存储量需求效率与存储量需求： 效率指的是算法执行的时间；效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。间。一般地，这两者与问题的规模有关。1.4.2 算法设计的要求算法设计的要求21 算法执行时间需通过依据该算法编制的程序在计算算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：机上运行所消耗的时间来度量。其方法通常有两种：事后统计事后统计：计算机内部进行执行时间和实际占用空间的：计算机内部进行执行时间和实际占用空间的统计。统计。 问题：

27、必须先运行依据算法编制的程序；依赖软硬问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。件环境，容易掩盖算法本身的优劣；没有实际价值。事前分析事前分析：求出该算法的一个时间界限函数。：求出该算法的一个时间界限函数。1.4.3 算法效率的度量算法效率的度量22与此相关的因素有：与此相关的因素有： 依据算法选用何种策略；依据算法选用何种策略； 问题的规模；问题的规模； 程序设计的语言；程序设计的语言； 编译程序所产生的机器代码的质量；编译程序所产生的机器代码的质量； 机器执行指令的速度；机器执行指令的速度； 撇开软硬件等有关因素，可以认为一个特定算法撇开软硬

28、件等有关因素，可以认为一个特定算法“运行工作量运行工作量”的大小，只依赖于问题的规模（通常的大小，只依赖于问题的规模（通常用用n表示），或者说，它表示），或者说，它是问题规模的函数是问题规模的函数。23算法分析应用举例算法分析应用举例 算法中算法中基本操作重复执行的次数基本操作重复执行的次数是问题规模是问题规模n的某的某个函数，其时间量度记作个函数，其时间量度记作 T(n)=O(f(n)，称作算法的渐，称作算法的渐近时间复杂度近时间复杂度(Asymptotic Time complexity)，简称，简称时间时间复杂度复杂度。 一般地，常用一般地，常用最深层循环内最深层循环内的语句中的原操作的

29、的语句中的原操作的执执行频度行频度(重复执行的次数重复执行的次数)来表示。来表示。 “O”的定义：的定义： 若若f(n)是正整数是正整数n的一个函数，则的一个函数，则 O(f(n)表示表示 C0 ，使得当，使得当n n0时，时，| f(n) | C | f(n0) | 。表示表示时间复杂度时间复杂度的阶有：的阶有： O(1) ：常量时间阶：常量时间阶 O (n)：线性时间阶：线性时间阶 O(n) ：对数时间阶：对数时间阶 O(nn) ：线性对数时间阶：线性对数时间阶24 O (nk)： k2 ，k次方时间阶次方时间阶例例 两个两个n阶方阵的乘法阶方阵的乘法 for(i=1; i=n; +i)

30、for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik*bkj ; 由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1到到n，则总次数为：，则总次数为： nnn=n3时间复杂度为时间复杂度为T(n)=O(n3)例例 +x; s=0 ; 将将x自增自增看成是基本操作，则语句频度为，即时看成是基本操作，则语句频度为，即时间复杂度为间复杂度为(1) 。25如果将如果将s=0也看成是基本操作，则语句频度为，其时也看成是基本操作，则语句频度为，其时间复杂度仍为间复杂度仍为(1)，即常量阶。，即常量阶。例例 for(i=1; i=n; +i)

31、+x; s+=x ; 语句频度为：语句频度为：2n，其时间复杂度为：，其时间复杂度为：O(n) ，即为线性阶。，即为线性阶。例例 for(i=1; i=n; +i)for(j=1; j=n; +j) +x; s+=x ; 语句频度为：语句频度为：2n2 ，其时间复杂度为：，其时间复杂度为：O(n2) ，即为平，即为平方阶。方阶。 26定理定理：若若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个是一个m次多次多项式，则项式，则A(n)=O(n m)例例 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai,j=x; 语句频度为：语句频度为：

32、1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2)/2 时间复杂度为时间复杂度为O(n2)，即此算法的时间复杂度为平方，即此算法的时间复杂度为平方阶。阶。 一个算法时间为一个算法时间为O(1)的算法，它的基本运算执行的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为零次多项式）来限界。而一个时间为O(n2)的算法则的算法则由一个二次多项式来限界。由一个二次多项式来限界。27 以下六种计算算法时间的多项式是最常用的。其关以下六种计算算法时间的多项式是最常

33、用的。其关系为：系为： O(1)O(n)O(n)O(nn)O(n2)O(n3) 指数时间的关系为：指数时间的关系为： O(2n)O(n!)O(nn) 当当n取得很大时，指数时间算法和多项式时间算法取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。在所需时间上非常悬殊。 有的情况下，算法中基本操作重复执行的次数还有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。随问题的输入数据集不同而不同。28例例6：素数的判断算法。素数的判断算法。Void prime( int n)/* n是一个正整数是一个正整数 */ int i=2 ; while ( (n% i)!=0 & i*1.0sqrt(n) )printf(“&d 是一个素数是一个素数n” , n) ;elseprintf(“&d 不是一个素数不是一个素数n” , n) ; 嵌套的最深层语句是嵌套的最深层语句是