1、1 数据结构的概念及其研究的问题，是数据结构的概念及其研究的问题，是本章中重要的概念，它们贯穿整本书。除本章中重要的概念，它们贯穿整本书。除了数据结构研究的三个方面，我们对每种了数据结构研究的三个方面，我们对每种数据结构都会给出应用的实例。数据结构都会给出应用的实例。第第1 1章章 基础知识基础知识 2给出数据结构的概念给出数据结构的概念介绍数据抽象和抽象数据类型介绍数据抽象和抽象数据类型说明数据结构和算法描述的方法说明数据结构和算法描述的方法介绍算法和算法分析的基本方法介绍算法和算法分析的基本方法31.1 1.1 算法和数据结构算法和数据结构瑞士的瑞士的WirthWirth博士图灵奖获得者博
2、士图灵奖获得者提出：提出：程序算法程序算法+数据结构数据结构41.1 1.1 算法和数据结构算法和数据结构 数据结构和算法是计算机学数据结构和算法是计算机学科的基础之一，更是软件技术科的基础之一，更是软件技术的基础。的基础。算法设计通常建立在所处算法设计通常建立在所处理的数据之上的，精心选择的理的数据之上的，精心选择的数据结构可以带来数据结构可以带来更高效率的更高效率的算法算法。程序算法程序算法+数据结构数据结构5 精心设计的数据结构真的可以带来更高效精心设计的数据结构真的可以带来更高效率的算法吗？率的算法吗？6 图一图一7，图二8 数据在计算机中的表示和存储不能是无组织的，是有规律，有结构的
3、。9计算机加工处理的对象计算机加工处理的对象2.2.：是组成数据的基本单位，在计算机程序：是组成数据的基本单位，在计算机程序中通常作为一个整体来处理。中通常作为一个整体来处理。数据元素由若干数据项组成。数据元素由若干数据项组成。3.3.是不可再分割的。是不可再分割的。1.2 1.2 什么是数据结构什么是数据结构 1.2.1 1.2.1 基本概念基本概念10表表1.1 学生情况表学生情况表学号学号姓名姓名性别性别其他信息其他信息B02040101王小红王小红女女B02040102林悦林悦女女B02040103陈菁陈菁女女B02040104张可可张可可男男数据项数据项11l 数据结构主要是为研究和
4、解决如何使用计数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究论、技术和方法。它已成为计算机学科研究的基本课题之一。的基本课题之一。12定义定义1-数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义定义2-按某种逻辑关系按某种逻辑关系组织起来的一批数据（或组织起来的一批数据（或称带结构的数据元素的集合）应用计算机称带结构的数据元素的集合）应用计算机语言并语言并按一定的存储表示按一定的存储表示 方式方式把它们存储把它们存储在计算机的存储器中，并在计算机的存储器中，并在其上
5、定义了一在其上定义了一个运算的集合。个运算的集合。13l 数据结构包括三个方面数据结构包括三个方面 逻辑结构：数据元素间的逻辑关系；逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作运算：在数据上执行的操作14数据结构举例数据结构举例 表表1.1 学生情况表学生情况表学号学号姓名姓名性别性别其他信息其他信息B02040101王小红王小红女女B02040102林悦林悦女女B02040103陈菁陈菁女女B02040104张可可张可可男男逻辑结构，存储结构，运算逻辑结构，存储结构，运算151.2.2 1.2.2 数据的逻辑
6、结构数据的逻辑结构 数据结构的逻辑结构可以用一个二元组表示。数据结构的逻辑结构可以用一个二元组表示。即即 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的的直接后继直接后继。小圆圈代表数据。小圆圈代表数据元素，两个不同元素的序偶称为元素，两个不同元素的序偶称为边边。abcd164 4种基本的逻
7、辑结构种基本的逻辑结构 (a)(a)集合结构集合结构(b)(b)线性结构线性结构(c)(c)树形结构树形结构(d)(d)图结构图结构图图1-2 1-2 四种基本的结构关系四种基本的结构关系对数据元素间对数据元素间逻辑关系逻辑关系的描述称为数据的的描述称为数据的逻辑结构逻辑结构。根据数据结构中数据元素之间关系的不同特征，可以根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构：划分为以下四种基本逻辑结构：17 数据元素之间存在数据元素之间存在一对一的关系。一对一的关系。一个前驱，一个前驱，一个后继。一个后继。数据元素之间存在数据元素之间存在一对多的关系。一对多的关系。数据元素
8、之间存在多数据元素之间存在多对多的关系。每个结点的前对多的关系。每个结点的前驱和后继的数目都不同。驱和后继的数目都不同。结构中的数据元素之间除了结构中的数据元素之间除了“同属于一个集合同属于一个集合”的关系外，没有其它关系。的关系外，没有其它关系。四种逻辑结构也可以分成两类：线性结构和非线性结构。四种逻辑结构也可以分成两类：线性结构和非线性结构。(a)(a)集合结构集合结构(b)(b)线性结构线性结构(c)(c)树形结构树形结构(d)(d)图结构图结构图图1-2 1-2 四种基本的结构关系四种基本的结构关系18 地址信息称为链。地址信息称为链。表示空链。表示空链。1.2.3 1.2.3 数据的
9、存储表示数据的存储表示数据结构的实现形式，是数据结构在计数据结构的实现形式，是数据结构在计算机内的表示，即算机内的表示，即数据元素及其关系数据元素及其关系在计算机存在计算机存储器中的存储方式。储器中的存储方式。其中，顺序和链接是两种最基本的存储表示方法。其中，顺序和链接是两种最基本的存储表示方法。19 顺序（或称连续）表示方法需要一块连续的存储空间，顺序（或称连续）表示方法需要一块连续的存储空间，并把并把逻辑上相关逻辑上相关的数据元素一次存储在该的数据元素一次存储在该连续连续的存储区中。的存储区中。例如，例如，由由4个元素组成的线性数据结个元素组成的线性数据结构（构（a0,a1,a2,a3），
10、存储在某个连续的），存储在某个连续的存储区内，设存储区的起始地址是存储区内，设存储区的起始地址是102，假定每个元素占假定每个元素占2个存储单元。个存储单元。Loc(ak)=102+2 k20 例如，线性结构（例如，线性结构（a0,a1,a2,a3）的链接存储表示。）的链接存储表示。结点存储块分成两部分，元素本身和该元素后继元素所结点存储块分成两部分，元素本身和该元素后继元素所在结点的存储地址。在结点的存储地址。链接存储表示下，为在机内存储一个元素，除了需要存放该元链接存储表示下，为在机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放于该元素相关的其它元素的地址素本身的信息外，还需要
11、存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。信息。这两部分信息组成一个数据元素的结点。21逻辑结构逻辑结构存储结构存储结构概念概念数据元素之间逻数据元素之间逻辑关系的描述辑关系的描述数据及其关系数据及其关系在计在计算机内的组织方式算机内的组织方式面向面向面向应用问题面向应用问题面向计算机面向计算机关系关系存储结构是逻辑结构在计算机内的映像存储结构是逻辑结构在计算机内的映像22 数据结构最常见的运算数据结构最常见的运算 创建运算创建运算:创建一个数据结构；创建一个数据结构；清除运算清除运算:删除数据结构中的全部删除数据结构中的全部元素；元素；插入运算插入运算:在数据
12、结构的指定位置上在数据结构的指定位置上插入一插入一个新元素；个新元素；删除运算删除运算:将数据结构中的某个元素删除将数据结构中的某个元素删除；23 如果一个数据结构一旦创建，其结构不发如果一个数据结构一旦创建，其结构不发生改变，则称为生改变，则称为静态数据结构静态数据结构，否则成为，否则成为动态数据结构动态数据结构。24 数据结构是一门研究程序设计问题中计算机的操作对象数据结构是一门研究程序设计问题中计算机的操作对象（数据数据）以及它们之间的）以及它们之间的关系关系和和运算运算的学科的学科。251.3 1.3 数据抽象和抽象数据类型数据抽象和抽象数据类型 抽象，封装和信息隐蔽是控制软抽象，封装
13、和信息隐蔽是控制软件开发复杂度，提高软件可靠性件开发复杂度，提高软件可靠性的重要手段的重要手段 本书采用抽象数据类型的观点讨本书采用抽象数据类型的观点讨论数据结构。论数据结构。26 1.C 1.C 语言的数据类型语言的数据类型字符、整型字符、整型 数组、结构和联合数组、结构和联合例如，例如，int a;int a;变量变量a a 的取值范围是：的取值范围是：-32768-32768 3276732767对变量对变量a a执行的操作有：执行的操作有：算术运算算术运算 +、-、*、/、%关系运算关系运算 、=、=、!=!=2.2.数据类型数据类型 一个数据类型定义了一个值的集合以及作一个数据类型定
14、义了一个值的集合以及作用于该值集的操作的集合。用于该值集的操作的集合。即一组值和一组操作。即一组值和一组操作。1.3.3 1.3.3 数据类型和抽象数据类数据类型和抽象数据类型型 27抽象数据类型抽象数据类型（A Abstract Data Type,ADTbstract Data Type,ADT）是一个）是一个数据类型，其主要特征是该类型的对象及其操作的数据类型，其主要特征是该类型的对象及其操作的规规范范,与该类型对象的表示和操作的与该类型对象的表示和操作的实现实现分离，分离，实行封实行封装和信息隐蔽，装和信息隐蔽，即即使用和实现分离。使用和实现分离。使用和实现分离：使用和实现分离：使用者
15、通过使用者通过规范规范使用该类型的数据，使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。而不必考虑其实现细节；改变实现将不影响使用。例如，例如，C+C+中的整型中的整型intint就是抽象数据类型。它的就是抽象数据类型。它的实现是隐实现是隐蔽的，使用者只能通过整型上定义的一组运算对整型变量蔽的，使用者只能通过整型上定义的一组运算对整型变量 执行操作。执行操作。3.3.抽象数据类型抽象数据类型28规范指明规范指明“做什么做什么”，实现解决实现解决“怎样做怎样做”。规范是实现的准则和依据规范是实现的准则和依据29一个数据结构包含两个层次：一个数据结构包含两个层次：(1)(1)数据结构
16、的规范（抽象层）：数据结构的规范（抽象层）：逻辑结构和逻辑结构和运算的定义运算的定义组成了数据结构的规范组成了数据结构的规范(2)(2)数据结构的实现（实现层）：数据结构的实现（实现层）：存储结构和运算存储结构和运算算法实现算法实现构成了数据结构的实构成了数据结构的实现现1.3.4 1.3.4 数据结构和抽象数据类数据结构和抽象数据类型型 一种数据结构被视为一个抽象数据类型。一种数据结构被视为一个抽象数据类型。3031本书是怎样描述每种数据结构？本书是怎样描述每种数据结构？1.4 1.4 描述数据结构和算法描述数据结构和算法 首先描述数据结构的首先描述数据结构的规范规范（逻辑结构和运逻辑结构和
17、运算的定义）算的定义）然后介绍数据结构的然后介绍数据结构的实现实现（存储结构和运存储结构和运算的具体程序实现算的具体程序实现），），32 （1 1）用格式化的）用格式化的自然语言自然语言来描述数据结构的规范。来描述数据结构的规范。（2 2）用一个）用一个C+C+的的抽象模板类抽象模板类描述数据结构的规范。描述数据结构的规范。1.4.1 1.4.1 数据结构的规范数据结构的规范1.4 1.4 描述数据结构和算法描述数据结构和算法对数据结构的规范的描述：对数据结构的规范的描述：33数据结构描述举例数据结构描述举例-堆栈堆栈1.4.1 1.4.1 数据结构的规范数据结构的规范34ADT 1.1 AD
18、T 1.1 栈抽象数据类型栈抽象数据类型ADT StackADT Stack Data:Data:(描述逻辑结构描述逻辑结构)0 0个或多个元素的线性序列（个或多个元素的线性序列（a a0 0，a a1 1，a an-1n-1)，遵循遵循LIFOLIFO原则。原则。Operations:Operations:(描述运算的定义描述运算的定义)Create()Create()：创建一个空栈。：创建一个空栈。Destroy():Destroy():撤消一个栈。撤消一个栈。Push(x)Push(x)：元素：元素x x插入栈顶。插入栈顶。Pop()Pop()：删除栈顶元素。：删除栈顶元素。Top(x)
19、Top(x)：在：在x x中返回栈顶元素。中返回栈顶元素。（1 1）用）用ADTADT描述数据结构描述数据结构堆栈的例子堆栈的例子对堆栈的规范的描述：对堆栈的规范的描述：35程序程序 1.1 1.1 栈的栈的C+C+模板抽象类模板抽象类templatetemplateclass Stackclass Stack public:public:virtual void Push(T x)=0;virtual void Push(T x)=0;virtual void Pop()=0;virtual void Pop()=0;virtual T Top(T&x)const=0;virtual T T
20、op(T&x)const=0;除了构造函数，其余成员函数都是纯虚函数。顺序栈除了构造函数，其余成员函数都是纯虚函数。顺序栈类类SeqStackSeqStack是类是类StackStack在顺序存储表示下的一种实现，它在顺序存储表示下的一种实现，它是从抽象类是从抽象类StackStack派生出来的，它可以实例化。派生出来的，它可以实例化。（2）用）用C+模板抽象类描述数据结构模板抽象类描述数据结构36templatetemplatebool SeqStack:Push(T&x)bool SeqStack:Push(T&x)if(IsFull()if(IsFull()coutOverflowend
21、l;coutOverflowendl;return false;return false;s+top=x;s+top=x;return true;return true;1.4.1.4.实现数据结构实现数据结构堆栈的实现：堆栈的实现：371.5 1.5 算法分析的基本方法算法分析的基本方法 算法及其性能分析算法及其性能分析 算法的空间复杂度算法的空间复杂度 算法的时间复杂度算法的时间复杂度 渐近时间复杂度渐近时间复杂度381.1.什么是算法什么是算法 一个算法一个算法(algorithm)(algorithm)是对特定问题的求解步骤的一种描是对特定问题的求解步骤的一种描述，它是指令的有限序列；
22、此外，算法具有下列五个特征：述，它是指令的有限序列；此外，算法具有下列五个特征：(1)(1)输入输入 算法有零个或多个输入。算法有零个或多个输入。(2)(2)输出输出 算法至少产生一个输出算法至少产生一个输出 (3)(3)确定性确定性 算法的每一条指令都有确切的定义，没有算法的每一条指令都有确切的定义，没有二义性。二义性。(4)(4)能行性能行性 算法的每一条指令都足够基本，它们可以算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。通过已经实现的基本运算执行有限次来实现。(5)(5)有穷性有穷性 算法必须总能在执行有限步之后终止。算法必须总能在执行有限步之后终止。1.
23、5.1 1.5.1 算法及其性能分析算法及其性能分析 392.2.算法描述方法算法描述方法 算法可以自然语言、流程图或程序设计语言描述。算法可以自然语言、流程图或程序设计语言描述。当一个算法用程序设计语言描述时，便成为程序。当一个算法用程序设计语言描述时，便成为程序。本书中，主要使用本书中，主要使用C+C+语言描述。语言描述。3.3.算法的性能标准算法的性能标准 （正确性正确性：算法的执行结果应当满足预先规定的功能和性能：算法的执行结果应当满足预先规定的功能和性能（要求。要求。(2)(2)简明性简明性：一个算法应当思路清晰、层次分明、易读易懂。：一个算法应当思路清晰、层次分明、易读易懂。(3)
24、(3)健壮性健壮性：当输入不合法数据时，应能做适当处理，不至于：当输入不合法数据时，应能做适当处理，不至于 引起严重后果。引起严重后果。(4)(4)效效 率率：有效使用存储空间和有高的时间效率。：有效使用存储空间和有高的时间效率。(5)(5)最优性最优性：解决同一个问题可能有多种算法，应进行比较，：解决同一个问题可能有多种算法，应进行比较，选择最佳算法。选择最佳算法。401.5.2 1.5.2 算法的时间复杂度算法的时间复杂度 程序步程序步 一个程序步是指在语法上或语义上有意义一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间的程序段，该程序段的执行时间与问题实例的与问题实例的特
25、征无关特征无关。算法的时间复杂度算法的时间复杂度 是程序运行从开始到结束所需的时间。是程序运行从开始到结束所需的时间。41程序程序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+)tempsum+=listi;tempsum+=listi;return tempsum;return tempsum;程序步数为
26、程序步数为2n+32n+3。421.5.3 1.5.3 渐近时间复杂度渐近时间复杂度 大大O O记号记号 如果存在两个正常数如果存在两个正常数c c和和n n0 0，使得对所有的使得对所有的n n，n n n n0 0 ，有，有f(n)f(n)c g(n)c g(n)则有则有 f(n)=O(g(n)f(n)=O(g(n)。渐近时间复杂度渐近时间复杂度 使用大使用大O O记号表示的算法的时间复杂性，称为算法的渐近记号表示的算法的时间复杂性，称为算法的渐近时间复杂度时间复杂度,简称时间复杂度。简称时间复杂度。43渐近时间复杂度渐近时间复杂度 使用大使用大O O记号表示的算法的时间复杂性，称为算法的
27、渐近记号表示的算法的时间复杂性，称为算法的渐近时间复杂度时间复杂度,简称时间复杂度。简称时间复杂度。大大O O记号用以表达一个算法运行时间的上界，可用记号用以表达一个算法运行时间的上界，可用程序程序步步在数量级上在数量级上估计算法的执行时间。估计算法的执行时间。例如，设例如，设 T(n)=3.6nT(n)=3.6n3 3+2.5n+2.5n2 2+2.8+2.8 8.9n8.9n3 3则根据大则根据大O O记号的定义容易证明记号的定义容易证明 T(n)=O(nT(n)=O(n3 3)44例如，程序例如，程序1.21.2为为求一个数组元素的累加之和的求一个数组元素的累加之和的算法。算法。floa
28、t 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;tempsum+=listi;/n /n return tempsum;/1 return tempsum;/1（1 1）总的）总的程序步数程序步数为为2n+3 2n+3，则则渐近时间复杂性渐近时间复杂性为为O(n)O(n)。45float sum(float list
29、,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;tempsum+=listi;/n /n return tempsum;/1 return tempsum;/1（2 2）语句）语句tempsum+=listitempsum+=listi可认为是关键操作，它的执行次可认为是关键操作，它的执行次数为数为n n次，则次，则渐近时间复杂性渐近时间复杂性为为
30、O(n)O(n)。很多情况下，可以通过考察一个算法中的很多情况下，可以通过考察一个算法中的关键操作关键操作（关键操作（关键操作被认为是一个被认为是一个执行次数最多执行次数最多的程序步）的执行次数来计算算法的程序步）的执行次数来计算算法的渐近时间复杂性。的渐近时间复杂性。46 常见的渐近时间复杂性从小到大排列有：常见的渐近时间复杂性从小到大排列有：O(1)O(log2 n)O(n)O(nlog2 n)O(n2)O(n3)例如：例如：若某算法程序的总程序步为若某算法程序的总程序步为4,则其渐近时则其渐近时间复杂性为多少？间复杂性为多少？O(4)是错误写法。是错误写法。应为应为O(1)47void
31、Mult(int ann,bnn,cnn,int n)void Mult(int ann,bnn,cnn,int n)/n/n n 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)cij=0;/n cij=0;/n2 2 for(int k=0;kn;k+)/n for(int k=0;kn;k+)/n2 2（n+1)n+1)cij+=aikcij+=aik*bkj;bkj;/n /n3 3 程序步为：
32、程序步为：2n2n3 3+3n+3n2 2+2n+1+2n+1 渐近时间复杂度为：渐近时间复杂度为：T(n)=O(nT(n)=O(n3 3)再看一例：再看一例：481.5.4 1.5.4 最好、最坏和平均情况时间复杂度最好、最坏和平均情况时间复杂度 对于某些算法，即使问题实例的规模相同，如果输入对于某些算法，即使问题实例的规模相同，如果输入的数据不同，算法所需的时间开销也会不同。的数据不同，算法所需的时间开销也会不同。比如在有比如在有n n个元素的一维数组上查找一个给定元素。个元素的一维数组上查找一个给定元素。49算法的空间复杂度算法的空间复杂度 是程序运行从开始到结束所需的存储量。是程序运行
33、从开始到结束所需的存储量。1.5.5 1.5.5 算法的空间复杂度算法的空间复杂度 50程序运行所需的存储空间包括两部分：程序运行所需的存储空间包括两部分：（1 1）固定部分固定部分 这部分空间与所处理数据的大小和个数无关，或者这部分空间与所处理数据的大小和个数无关，或者称称与问题的实例的特征无关与问题的实例的特征无关。主要包括程序代码、常量、简。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。单变量、定长成分的结构变量所占的空间。（2 2）可变部分可变部分 这部分空间大小这部分空间大小与算法在某次执行中处理的特定数据与算法在某次执行中处理的特定数据的大小和规模有关的大小和规模有关。例如，分别为。例如，分别为100100个元素的两个数组相个元素的两个数组相加，与分别为加，与分别为1010个元素的两个数组相加，所需的存储空间个元素的两个数组相加，所需的存储空间显然是不同的。显然是不同的。51本章小结需要重点掌握的知识点需要重点掌握的知识点 数据结构的概念（包括三个方面）数据结构的概念（包括三个方面）渐近时间复杂度渐近时间复杂度
