数据结构培训资料课件

第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1什么是数据结构电子计算机的主要用途：早期：主要用于数值计算。解决问题的步骤：数学模型→解题算法→选择计算机语言编程→测试→最终解答关键：如何得出数学模型当今：扩大到非数值计算领域。计算机的操作对象的关系更加复杂，数据元素间的相互关系有时无法用数学方程来描述。所处理的数据量大且具有一定的关系；而对其的操作也不再是单纯的数值计算，更多地是对其进行组织、管理和检索等。电子计算机的主要用途：例1：学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息：例1：学籍档案管理假设一个学籍档案管理系统应包含如下特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；每列的数据类型一样；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入、删除、更新、按条件检索某个学生的信息等等。特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排例2：输出n个对象的全排列输出3个对象的全排列可以使用下图所示的形式描述：例2：输出n个对象的全排列输出3个对象的全排列可以使特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；对它的操作有：建立树形结构，输出最低层结点内容等等。特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所例3：制定教学计划制定教学计划时，需考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：

例3：制定教学计划制定教学计划时，需考虑各门课程的开课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11课程先后关系如图：c1c9c4c2c12c10c11c5c3特点：课程之间的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。特点：课程之间的先后关系用图结构描述；结论要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点、之间的关系，在计算机中的表示方式及各种操作的具体实现手段。因此，《数据结构》研究的主要内容是：数据元素之间的逻辑关系数据的存储结构采用何种操作实现算法的效率更高结论要使计算机能够更有效地进行这些非数值性处理，就必程序设计：为计算机处理问题编制一组指令集。算法：处理问题的策略。数据结构：问题的数学模型。程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。程序=算法+数据结构“Programs=Algorithm+DataStructures”瑞士学者NiklausWirth于1976年出版的书名。程序设计：为计算机处理问题编制一组指令集。程序=算课程任务：1.讨论现实世界中数据的各种逻辑结构及在计算机中的存储结构；

2.进行各种非数值运算的算法。课程目的：掌握数据组织、存储和处理的常用法，为进行软件开发或后续专业课程学习打下良好的基础。课程内容：数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。课程任务：1.讨论现实世界中数据的各种逻辑结构及在计算机中的第1章绪论

1.1什么是数据结构

1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1什么是数据结构1.数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机处理的符号的总称。计算机程序加工的“原料”。1.数据例：一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。还有声音、图象、视频等等通过编码都属于数据的范畴。例：一个利用数值分析方法解代数方程的程序，其处理对象2.数据元素

是数据的基本单位。数据中的一个“个体”，数据结构中讨论的基本单位。在计算机中通常作为一个整体进行考虑和处理。2.数据元素例：一个整数“5”；一个字符“N”；图中的一个顶点等。

复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。例：一个学生的基本信息就是一个数据元素，其中的学号、姓名等被称为“数据项”。

因此数据项是数据结构中讨论的最小单位。数据元素是数据项的集合，数据项是数据的不可分割的最小单位。例：一个整数“5”；一个字符“N”；图中的一个顶点等3.数据对象

性质相同的数据元素的集合。是数据的子集。例：整数数据对象是集合N={0，±1，±2，…}。英文字母数据对象是集合

C={‘A’，……，‘Z’}。如何选定数据对象将依问题而定！譬如，在学生管理系统中，可能以一个班级的学生记录作为数据对象，也可能以一个年级的学生记录作为数据对象。3.数据对象例：4.数据的逻辑结构讨论计算机系统中数据的组织形式及其相互关系。即相互之间存在一种或多种特定关系的数据元素的集合。数据逻辑结构的形式定义：数据逻辑结构是一个二元组：

Data_structure={D,R}

其中，D是数据元素的有限集，R是D上的关系的集合。4.数据的逻辑结构例：在计算机科学中，复数可取如下定义：复数数据的逻辑结构

Complex=(C,R)

其中：C是含两个实数的集合{c1,c2};R={P}，而P是定义在集合C上的一种关系{<c1,c2>}，其中有序偶<c1,c2>表示c1是复数的实部，c2是复数的虚部。

例：在计算机科学中，复数可取如下定义：复数数据的逻辑结构4数据的逻辑结构例：list=(D,S1),tree=(D,S2),graph=(D,S3)D={a,b,c,d,e}S1={<a,b>,<b,c>,<c,d>,<d,e>}S2={<a,b>,<a,c>,<b,d>,<b,e>}S3={<a,b>,<a,c>,<d,a>,<e,c>}4数据的逻辑结构例：list=(D,S1),tree=(D逻辑结构示意图<a,b>,称a是b的前驱，b是a的后继。若某结点没有前驱，则称该结点为开始结点；若某结点没有后继，则称该结点为终端结点；bacdelistaedbcgraphedbcatree（a,b,c,d,e）逻辑结构示4.数据的逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。数据的逻辑结构可归结为以下四类:

1）集合：数据元素之间除“同属于一个集合”的关系外无其它关系。2）线性结构：数据元素间存在一对一的关系。3）树形结构：数据元素间存在一对多的关系。4）图（网）状结构：数据元素间存在多对多的关系。4.数据的逻辑结构数据的逻辑结构可归结为以下四类:线性结构：一对一非线性结构树形结构：一对多图状结构：多对多逻辑结构集合线性结构：一对一非线性结构树形结构：一对多图状结构：多对多逻5.数据的存储结构（物理结构）存储结构：逻辑结构在计算机中的表示(又称映象)称为数据的物理结构，又称存储结构。包括数据元素的表示和关系的表示。计算机中表示信息的最小单位是二进制数的一位(bit)。可用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素(Element)或结点(Node)。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(DataField)。5.数据的存储结构（物理结构）5.数据的存储结构（物理结构）存储的要求：既存储各结点的数值又要存储结点与结点之间的逻辑关系。四种基本的存储结构：顺序、链接、索引、散列存储。内存空间、内存地址程序在运行期间所需存储空间都在内存中分配.……5.数据的存储结构（物理结构）存储的要求：既存储各结点的数值1.顺序存储（用数组实现）存储方法:把逻辑上相邻的结点存储在一组连续的存储单元中,其结点之间的逻辑关系由存储单元地址间的关系隐含表示。例：list的顺序存储结构如下abcde200201202203204优点：节省存储空间，可实现对各结点的随机访问。

loc（i）＝q＋（i－1）×pq是第一个结点所占存储单元的首地址；

p是每个结点所占单元数。1.顺序存储（用数组实现）存储方法:把逻辑上相邻的结点存储在缺点：不便于修改。进行插入、删除运算时可能要移动一系列的数据元素。例：若删除list结构中的第三个结点c，则list的逻辑结构变成(a,b,d,e)。

若在结点c前插入一个新的结点x，则list的逻辑结构变成(a,b,x,c,d,e)。

逻辑结构发生变化后，相应的存储结构同样发生变化baxdeab缺点：不便于修改。进行插入、删除运算时可能要移动一系列的数据2.链接存储(用指针实现)存储方法：给每个机结点附加指针字段，用于存放相邻结点的存储地址。优点：便于修改缺点：浪费存储空间例：list（a,b,c,d,e）的存储结构示意图如下c208b200a202ed206200202206208204200202206208204b208a202ed206删除结点c后(a,b,d,e)x200…c208b100a202ed206200202206208204100插入结点x后（a,b,x,c,d,e）2.链接存储(用指针实现)存储方法：给每个机结点附加指针字段3.索引存储（用数组实现）存储方法：根据结点的序号确定结点的存储地址。具体做法：建立索引表和结点表；将各结点的数值按任意顺序存放在结点表中，而将每个结点的存储地址用顺序存储方法存入索引表中。例：list（a,b,c,d,e)的索引存储结构如下200204202201203200204201203a甲85d丁90c丙67e戊55b乙78100101102103104200201202203204索引表结点表索引表100101102103104删除结点c后删除结点c前后无变化3.索引存储（用数组实现）存储方法：根据结点的序号确定结点的4.散列存储(用数组实现)存储方法：根据结点的值确定结点的存储地址。具体做法：以结点中某个字段的值为自变量，通过某个函数（称为散列函数）计算出对应的函数值i，再把i当作结点的存储地址。例：假定list结构中的5个结点数值是下列5个字符‘Wuhan’‘Nanjing’‘Shanghai’‘Xian’‘Beijing’

散列函数：Loc(key)=asc(left(key,1))mod8KeyWuhanNanjingShanghaiXianBeijingasc(key)8778838866Loc(key)76302XianBeijingShanghaiNanjingWuhan012345674.散列存储(用数组实现)存储方法：根据结点的值确定结点

数据的逻辑结构和物理结构是密切相关的两个方面，在后面的课程中我们会看到，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。

完整的数据结构概念可认为是由数据的逻辑结构、存储结构及基本操作集三个部分组成：

Data_Structure＝（D，R，P）其中D是数据元素的有限集合；R是D集上关系的有限集合，P是对D的基本操作集。数据结构研究的内容完整的数据结构概念可认为是由数据的逻辑结构、存储结构及基本操数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列

数据逻辑结构层次关系图

逻辑结构与所采用的存储结构线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般6.数据类型是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画（程序）

操作对象的特性。

数据类型：是一组性质相同的值的集合及定义于这个值集合上的一组操作的总称。6.数据类型通用的计算机高级语言常见的有整数、实数（浮点数）、枚举、字符、字符串、指针、数组、记录文件等数据类型。譬如：整数类型通常用两个字节或四个字节表示，分别表示范围：-215～215-1、-231～231-1。对其允许施加的操作通常有：单目和双目，分别是取正或取负运算；加、减、乘、除、取模、等于、不等于、大于等关系（比较）运算。通用的计算机高级语言常见的有整数、实数（浮点数）、枚依据“值”的不同特性，高级语言中数据类型可分为两类：1）原子类型

原子类型的值是不可分解。如：C语言中的基本类型（整型、实型、字符型和枚举型），指针型。2）结构类型结构类型的值是由若干成分按某种结构组成，因此可以分解，且它的成分可以是非结构的，也可以是结构的。如：数组类型。依据“值”的不同特性，高级语言中数据类型可分为两类：7.抽象数据类型（简称ADT）指一个数学模型及定义在此数学模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。

为提高软件复用率，近代程序设计方法学指出，一个软件系统的框架应建立在数据之上，而不是操作之上（后者是传统的软件设计方法所为）。即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作细节，而在模块外部使用的只是抽象的数据和操作。7.抽象数据类型（简称ADT）ADT有两个重要特征:1）数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。2）数据封装

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。ADT有两个重要特征:抽象数据类型的描述方法：三元组表示（D，S，P）其中，D是数据对象，

S是D上的关系集，

P是对D的基本操作集。抽象数据类型的描述方法：ADT抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉

}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，

基本操作的定义格式为：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉ADT抽象数据类型名{基本操作有两种参数：1）赋值参数：只为操作提供输入值2）引用参数：以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则将其省略。基本操作有两种参数：例：抽象数据类型——

复数的定义

ADTComplex{

数据对象：D＝{e1,e2｜e1,e2∈RealSet}

数据关系：R＝{<e1,e2>|e1是复数的实数部分,

e2是复数的虚数部分}

基本操作：

InitComplex(&Z,v1,v2)

操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。例：抽象数据类型——复数的定义

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。

GetImag(Z,&ImaPart)初始条件：复数已存在。操作结果：用ImgPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplexGetReal(Z,&realPart)第1章绪论

1.1什么是数据结构1.2基本概念和术语

1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1什么是数据结构抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。本课程在高级程序设计语言的虚拟层次上讨论抽象数据类型的表示和实现，采用介于伪码和Ｃ语言之间的类Ｃ语言作为描述工具，下面我们对其作一下简要说明。抽象数据类型可通过固有数据类型来表示和实现，即利用处（1）预定义常量和类型：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2Typedefintstatus

//status是函数的类型，

//其值是函数结果状态代码（1）预定义常量和类型：（2）数据结构的表示（存储结构）

用类型定义（typedef）描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。（3）基本操作的算法

用以下形式的函数描述：函数类型函数名（函数参数表）

{//算法说明语句序列

}//函数名（2）数据结构的表示（存储结构）说明：除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。当函数返回值为函数结果状态码时，函数定义为status类型。为了便于算法描述，除了值调用方式之外，增添了C++语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。说明：（4）赋值语句

简单赋值变量名=表达式；

串联赋值变量名1=变量名2=…变量名K=表达式；

成组赋值（变量名1，变量名2，…变量名K）=

（表达式1，表达式2，…表达式K）；（4）赋值语句

结构名=结构名；结构名=（值1，值2，…，值K）；变量名[]=表达式；变量名[起始下标..终止下标]=

变量名[起始下标..终止下标]；

交换赋值变量名←→变量名；

条件赋值

变量名=条件表达式？表达式T：表达式F；结构名=结构名；（5）选择语句

条件语句1if（表达式）语句；

条件语句2if（表达式）语句;else语句；（5）选择语句

开关语句1

switch（表达式）{case值1:语句序列1；break；

…case值n:语句序列n；break；

default:语句序列n+1；}

开关语句2

switch{case条件1:语句序列1；break；

…case条件n:语句序列n；break；

default:语句序列n+1；}开关语句1（6）循环语句

For语句

for（赋初值表达式序列；条件；修改表达式序列）语句序列；

While语句

while（条件）语句序列；

Do-While语句

do{语句序列；

}while（条件）（6）循环语句（7）结束语句

函数结束语句

return表达式；

return；

Case结束语句

break；

异常结束语句

exit（异常代码）；（7）结束语句（8）输入输出语句

输入语句

scanf（[格式串]，变量1，…，变量n）；

输出语句

printf（[格式串]，表达式1，…，表达式n）；通常省略格式串。（8）输入输出语句（9）注释

单行注释

//文字序列；（10）逻辑运算约定

与运算&&

：

如：A&&B，当A的值为0时，不再对B求值。

或运算||：如：A||B，当A的值为非0时，不再对B求值。（9）注释（11）基本函数

求最大值

max（表达式1，…，表达式n）；

求最小值

min（表达式1，…，表达式n）；

求绝对值

abs（表达式）；

求不足整数值

floor（表达式）；

求进位整数值

ceil（表达式）；

判定文件结束

eof（文件变量）或eof；

判定行结束

eoln（文件变量）或eoln（11）基本函数第1章绪论

1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现

1.4算法和算法分析第1章绪论1.1什么是数据结构1.算法定义

算法(Algorithm)是对特定问题求解步骤的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。计算机对数据的操作可分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等。

1.算法定义2.设计算法的基本过程1)通过对问题进行详细地分析，抽象出相应的数学模型；2)确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；3)选用某种语言将算法转换成程序；4)调试并运行这些程序。

2.设计算法的基本过程1）有穷性：对任何合法输入值，算法总是在有穷步内结束，且每一步都可在有穷的时间内完成；2）确定性：每条指令有确切的含义，不会产生二义性；只有一条执行路径，即对于相同的输入，只能得到相同的输出；3）可行性：算法中的操作都可以通过已实现的基本运算执行有限次来实现；4）有输入：有零个或多个输入；5）有输出：有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。3.算法的重要特性1）有穷性：对任何合法输入值，算法总是在有穷步内结束，且每一1）正确性：算法应当满足具体问题的需求。

“正确”一词的含义在通常的用法中有很大差别，大体可分4层次：a.程序不含语法错误；b.程序对于几组输入数据能够得出满足规格说明要求的结果；

c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能得出满足规格说明要求的结果；通常以此作为衡量一个程序是否正确的标准；d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。4.算法设计的要求1）正确性：算法应当满足具体问题的需求。4.算法设计的要求2）可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。3）健壮性：当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。4）高效率与低存储量需求：

通俗地说，效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。4.算法设计的要求2）可读性：为了便于理解、测试和修改算法，算法应该具有良好的5.一般书写算法的4种形式：1）条列式的步骤以条列式的步骤来描述解决问题的方法2）流程图/可读性以图形符号来描述解决问题的方法。3）伪码

以夹杂程序语法和自然语言（如：中文、英文）的形式描述解决问题的方法。4）程序语句

直接以程序语法来描述解决问题的方法。5.一般书写算法的4种形式：6.算法效率的衡量方法和准则事后统计法计算机内部都有计时功能，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此常采用事前分析估算法。事前分析估算法6.算法效率的衡量方法和准则与算法执行时间相关的因素：

1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的。与算法执行时间相关的因素：一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f（n）的增长率相同，则可记作：

T（n）=O（f（n））称T（n）为算法的(渐近)时间复杂度一个特定算法的“运行工作量”的大小，只依赖于问题的规一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

一个算法的执行时间可以看成是所有语句的执行时间之和T=∑(语句(i)的执行次数×语句的执行时间)

假设每条语句执行的时间相等

算法的语句频度f(n):算法中基本操作重复执行的次数之和。

算法的渐近时间复杂度T（n）=O(f(n))

这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。

渐近时间复杂度（AsymptoticTimeComplexity）一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通如何估算算法的时间复杂度？算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数

×原操作(i)的执行时间算法的执行时间与原操作执行次数之和成正比如何估算算法的时间复杂度？所以

从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。所以例一

矩阵相乘

for(i=1；i<=n；++i)for(j=1；j<=n；++j){c[i，j]=0；

for(k=1；k<=n；++k)c[i，j]+=a[i，k]×b[k，j]；

}基本操作:乘法操作，时间复杂度:O（n3）例一

矩阵相乘

例二voidselect_sort(inta[],intn){//将a中整数序列重新排列成自小至大有序的整数序列

for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}}//select_sort基本操作:比较操作；时间复杂度:O(n2)

例二例三

voidbubble_sort(inta[],intn){//将a中整数序列重新排列成自小至大有序的整数序列

for(i=n-1,change=TRUE;i>1&&change;--i){change=FALSE;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TRUE}}}//bubble_sort基本操作:赋值操作；时间复杂度:O（n2）例三

定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)如果算法的执行时间T(n)与问题规模n无关，是个常数，则记作T(n)=O(1)。 例{++x;s=0;}

将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)。以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)指数时间的关系为：

O(2n)<O(n!)<O(nn)

定理：若A(n)=amnm+am-1nm-1数据结构培训资料当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常算法的存储空间需求空间复杂度(Spacecomplexity)：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S(n)=O(g(n))其中：n为问题的规模(或大小)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:

1．输入数据所占空间

2．程序本身所占空间

3．辅助变量所占空间算法的存储空间需求例：1.sum=0;for(j=1;j<=n;j++)sum=sum+j;printf(“%d”,sum);T(n)=O(f(n))=O(2n+3)=O(n)1n+1n12.Sum=0;for(I=1;I<=n;I++)for(j=1;j<=n;j++)sum=sum+I*j;Printf(“%d”,sum);1n+1n(n+1)n21T(n)=O(f(n))=O(2n2+2n+3)=O(n2)3.x=n;y=0;while(x>=(y+1)*(y+1))y++;T(n)=O(n½)4.x=n;for(j=1;j<=100;j++) x=x+j;T(n)=O(1)例：1.sum=0;T(n)=O(f(n))=O(2n+3)若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。若输入数据所占空间只取决于问题本身，和算法无关，则只本章小结1.概念和术语数据数据元素数据对象数据结构逻辑结构存储结构抽象数据类型算法2.数据结构的研究目的和研究内容

目的：寻求有效地组织和处理非数值数据的理论、技术和方法。内容：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。3.逻辑结构的四种基本形态集合结构、线性结构、树形结构、图状结构本章小结1.概念和术语本章小结4.数据存储结构的基本组织方式顺序、链式5.数据结构引入ADT概念的优点

运用ADT的概念实际上是将数据结构的讨论分成两部分：一是其概念所涵盖的数据逻辑结构的说明和运算的定义，突出的是在某种关系的数据对象上可以做什么；一是在计算机中如何存储这些数据并具体实现定义的运算，解决怎样做的问题。它和面向对象方法的思想是一致的。本章小结4.数据存储结构的基本组织方式本章小结6.算法的五个重要特性确定性、有穷性、可行性、输入、输出7.评价算法优劣的基本标准正确性、可读性、健壮性、效率与低存储量8.算法分析的目的主要是考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间（内存）比较充足，所以把算法的时间复杂度作为分析的重点。9.算法的时间复杂度、空间复杂度本章小结6.算法的五个重要特性习题一1简要回答术语：数据，数据元素，数据结构，数据类型。2数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？3数据结构的主要运算包括哪些？4算法分析的目的是什么？算法分析的主要方面是什么？5分析以下程序段的时间复杂度，请说明分析的理由或原因。

习题一1简要回答术语：数据，数据元素，数据结构，数据作业6.设数据逻辑结构的二元组表示为s=(D,R),其中

D＝{a,b,c,d,e,f}R={<b,a>,<d,c>,<b,d>,<a,e>,<d,f>}

试画出这个逻辑结构的示意图及类别。7.求下列算法的时间复杂度及注释语句的频度⑴k=0;for(i=1;i<=n;i++)for(j=i;j<=n;j++)k++;//（2）

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]+=a[i][k]*b[k][j];//}作业6.设数据逻辑结构的二元组表示为s=(D,R),其中⑴（(3)Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}(4)Sum2(intn){intsum=0,m,t;for(m=1;m<=n;m++){p=1;for(t=1;t<=m;t++)p*=t;sum+=p;}return(sum);}(3)(4)i=1;k=0;while(i<=n-1){k=k+10*i;//i++;}i=1;j=0;while(i+j<=n)if(i>j)j++;//elsei++;3.设一维数组V中存有n个整数，（1）写一个算法，将数组中的非零元素移到前面来，零元素移到后面去，各非零元素间的相对位置不变；（2）分析所写算法的时间复杂度。i=1;演讲完毕，谢谢观看！演讲完毕，谢谢观看！第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1什么是数据结构电子计算机的主要用途：早期：主要用于数值计算。解决问题的步骤：数学模型→解题算法→选择计算机语言编程→测试→最终解答关键：如何得出数学模型当今：扩大到非数值计算领域。计算机的操作对象的关系更加复杂，数据元素间的相互关系有时无法用数学方程来描述。所处理的数据量大且具有一定的关系；而对其的操作也不再是单纯的数值计算，更多地是对其进行组织、管理和检索等。电子计算机的主要用途：例1：学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息：例1：学籍档案管理假设一个学籍档案管理系统应包含如下特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；每列的数据类型一样；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入、删除、更新、按条件检索某个学生的信息等等。特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排例2：输出n个对象的全排列输出3个对象的全排列可以使用下图所示的形式描述：例2：输出n个对象的全排列输出3个对象的全排列可以使特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；对它的操作有：建立树形结构，输出最低层结点内容等等。特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所例3：制定教学计划制定教学计划时，需考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：

例3：制定教学计划制定教学计划时，需考虑各门课程的开课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11课程先后关系如图：c1c9c4c2c12c10c11c5c3特点：课程之间的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。特点：课程之间的先后关系用图结构描述；结论要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点、之间的关系，在计算机中的表示方式及各种操作的具体实现手段。因此，《数据结构》研究的主要内容是：数据元素之间的逻辑关系数据的存储结构采用何种操作实现算法的效率更高结论要使计算机能够更有效地进行这些非数值性处理，就必程序设计：为计算机处理问题编制一组指令集。算法：处理问题的策略。数据结构：问题的数学模型。程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。程序=算法+数据结构“Programs=Algorithm+DataStructures”瑞士学者NiklausWirth于1976年出版的书名。程序设计：为计算机处理问题编制一组指令集。程序=算课程任务：1.讨论现实世界中数据的各种逻辑结构及在计算机中的存储结构；

2.进行各种非数值运算的算法。课程目的：掌握数据组织、存储和处理的常用法，为进行软件开发或后续专业课程学习打下良好的基础。课程内容：数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。课程任务：1.讨论现实世界中数据的各种逻辑结构及在计算机中的第1章绪论

1.1什么是数据结构

1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1什么是数据结构1.数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机处理的符号的总称。计算机程序加工的“原料”。1.数据例：一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。还有声音、图象、视频等等通过编码都属于数据的范畴。例：一个利用数值分析方法解代数方程的程序，其处理对象2.数据元素

是数据的基本单位。数据中的一个“个体”，数据结构中讨论的基本单位。在计算机中通常作为一个整体进行考虑和处理。2.数据元素例：一个整数“5”；一个字符“N”；图中的一个顶点等。

复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。例：一个学生的基本信息就是一个数据元素，其中的学号、姓名等被称为“数据项”。

因此数据项是数据结构中讨论的最小单位。数据元素是数据项的集合，数据项是数据的不可分割的最小单位。例：一个整数“5”；一个字符“N”；图中的一个顶点等3.数据对象

性质相同的数据元素的集合。是数据的子集。例：整数数据对象是集合N={0，±1，±2，…}。英文字母数据对象是集合

C={‘A’，……，‘Z’}。如何选定数据对象将依问题而定！譬如，在学生管理系统中，可能以一个班级的学生记录作为数据对象，也可能以一个年级的学生记录作为数据对象。3.数据对象例：4.数据的逻辑结构讨论计算机系统中数据的组织形式及其相互关系。即相互之间存在一种或多种特定关系的数据元素的集合。数据逻辑结构的形式定义：数据逻辑结构是一个二元组：

Data_structure={D,R}

其中，D是数据元素的有限集，R是D上的关系的集合。4.数据的逻辑结构例：在计算机科学中，复数可取如下定义：复数数据的逻辑结构

Complex=(C,R)

其中：C是含两个实数的集合{c1,c2};R={P}，而P是定义在集合C上的一种关系{<c1,c2>}，其中有序偶<c1,c2>表示c1是复数的实部，c2是复数的虚部。

例：在计算机科学中，复数可取如下定义：复数数据的逻辑结构4数据的逻辑结构例：list=(D,S1),tree=(D,S2),graph=(D,S3)D={a,b,c,d,e}S1={<a,b>,<b,c>,<c,d>,<d,e>}S2={<a,b>,<a,c>,<b,d>,<b,e>}S3={<a,b>,<a,c>,<d,a>,<e,c>}4数据的逻辑结构例：list=(D,S1),tree=(D逻辑结构示意图<a,b>,称a是b的前驱，b是a的后继。若某结点没有前驱，则称该结点为开始结点；若某结点没有后继，则称该结点为终端结点；bacdelistaedbcgraphedbcatree（a,b,c,d,e）逻辑结构示4.数据的逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。数据的逻辑结构可归结为以下四类:

1）集合：数据元素之间除“同属于一个集合”的关系外无其它关系。2）线性结构：数据元素间存在一对一的关系。3）树形结构：数据元素间存在一对多的关系。4）图（网）状结构：数据元素间存在多对多的关系。4.数据的逻辑结构数据的逻辑结构可归结为以下四类:线性结构：一对一非线性结构树形结构：一对多图状结构：多对多逻辑结构集合线性结构：一对一非线性结构树形结构：一对多图状结构：多对多逻5.数据的存储结构（物理结构）存储结构：逻辑结构在计算机中的表示(又称映象)称为数据的物理结构，又称存储结构。包括数据元素的表示和关系的表示。计算机中表示信息的最小单位是二进制数的一位(bit)。可用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素(Element)或结点(Node)。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(DataField)。5.数据的存储结构（物理结构）5.数据的存储结构（物理结构）存储的要求：既存储各结点的数值又要存储结点与结点之间的逻辑关系。四种基本的存储结构：顺序、链接、索引、散列存储。内存空间、内存地址程序在运行期间所需存储空间都在内存中分配.……5.数据的存储结构（物理结构）存储的要求：既存储各结点的数值1.顺序存储（用数组实现）存储方法:把逻辑上相邻的结点存储在一组连续的存储单元中,其结点之间的逻辑关系由存储单元地址间的关系隐含表示。例：list的顺序存储结构如下abcde200201202203204优点：节省存储空间，可实现对各结点的随机访问。

loc（i）＝q＋（i－1）×pq是第一个结点所占存储单元的首地址；

p是每个结点所占单元数。1.顺序存储（用数组实现）存储方法:把逻辑上相邻的结点存储在缺点：不便于修改。进行插入、删除运算时可能要移动一系列的数据元素。例：若删除list结构中的第三个结点c，则list的逻辑结构变成(a,b,d,e)。

若在结点c前插入一个新的结点x，则list的逻辑结构变成(a,b,x,c,d,e)。

逻辑结构发生变化后，相应的存储结构同样发生变化baxdeab缺点：不便于修改。进行插入、删除运算时可能要移动一系列的数据2.链接存储(用指针实现)存储方法：给每个机结点附加指针字段，用于存放相邻结点的存储地址。优点：便于修改缺点：浪费存储空间例：list（a,b,c,d,e）的存储结构示意图如下c208b200a202ed206200202206208204200202206208204b208a202ed206删除结点c后(a,b,d,e)x200…c208b100a202ed206200202206208204100插入结点x后（a,b,x,c,d,e）2.链接存储(用指针实现)存储方法：给每个机结点附加指针字段3.索引存储（用数组实现）存储方法：根据结点的序号确定结点的存储地址。具体做法：建立索引表和结点表；将各结点的数值按任意顺序存放在结点表中，而将每个结点的存储地址用顺序存储方法存入索引表中。例：list（a,b,c,d,e)的索引存储结构如下200204202201203200204201203a甲85d丁90c丙67e戊55b乙78100101102103104200201202203204索引表结点表索引表100101102103104删除结点c后删除结点c前后无变化3.索引存储（用数组实现）存储方法：根据结点的序号确定结点的4.散列存储(用数组实现)存储方法：根据结点的值确定结点的存储地址。具体做法：以结点中某个字段的值为自变量，通过某个函数（称为散列函数）计算出对应的函数值i，再把i当作结点的存储地址。例：假定list结构中的5个结点数值是下列5个字符‘Wuhan’‘Nanjing’‘Shanghai’‘Xian’‘Beijing’

散列函数：Loc(key)=asc(left(key,1))mod8KeyWuhanNanjingShanghaiXianBeijingasc(key)8778838866Loc(key)76302XianBeijingShanghaiNanjingWuhan012345674.散列存储(用数组实现)存储方法：根据结点的值确定结点

数据的逻辑结构和物理结构是密切相关的两个方面，在后面的课程中我们会看到，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。

完整的数据结构概念可认为是由数据的逻辑结构、存储结构及基本操作集三个部分组成：

Data_Structure＝（D，R，P）其中D是数据元素的有限集合；R是D集上关系的有限集合，P是对D的基本操作集。数据结构研究的内容完整的数据结构概念可认为是由数据的逻辑结构、存储结构及基本操数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列

数据逻辑结构层次关系图

逻辑结构与所采用的存储结构线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般6.数据类型是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画（程序）

操作对象的特性。

数据类型：是一组性质相同的值的集合及定义于这个值集合上的一组操作的总称。6.数据类型通用的计算机高级语言常见的有整数、实数（浮点数）、枚举、字符、字符串、指针、数组、记录文件等数据类型。譬如：整数类型通常用两个字节或四个字节表示，分别表示范围：-215～215-1、-231～231-1。对其允许施加的操作通常有：单目和双目，分别是取正或取负运算；加、减、乘、除、取模、等于、不等于、大于等关系（比较）运算。通用的计算机高级语言常见的有整数、实数（浮点数）、枚依据“值”的不同特性，高级语言中数据类型可分为两类：1）原子类型

原子类型的值是不可分解。如：C语言中的基本类型（整型、实型、字符型和枚举型），指针型。2）结构类型结构类型的值是由若干成分按某种结构组成，因此可以分解，且它的成分可以是非结构的，也可以是结构的。如：数组类型。依据“值”的不同特性，高级语言中数据类型可分为两类：7.抽象数据类型（简称ADT）指一个数学模型及定义在此数学模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。

为提高软件复用率，近代程序设计方法学指出，一个软件系统的框架应建立在数据之上，而不是操作之上（后者是传统的软件设计方法所为）。即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作细节，而在模块外部使用的只是抽象的数据和操作。7.抽象数据类型（简称ADT）ADT有两个重要特征:1）数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。2）数据封装

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。ADT有两个重要特征:抽象数据类型的描述方法：三元组表示（D，S，P）其中，D是数据对象，

S是D上的关系集，

P是对D的基本操作集。抽象数据类型的描述方法：ADT抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉

}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，

基本操作的定义格式为：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉ADT抽象数据类型名{基本操作有两种参数：1）赋值参数：只为操作提供输入值2）引用参数：以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则将其省略。基本操作有两种参数：例：抽象数据类型——

复数的定义

ADTComplex{

数据对象：D＝{e1,e2｜e1,e2∈RealSet}

数据关系：R＝{<e1,e2>|e1是复数的实数部分,

e2是复数的虚数部分}

基本操作：

InitComplex(&Z,v1,v2)

操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。例：抽象数据类型——复数的定义

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。

GetImag(Z,&ImaPart)初始条件：复数已存在。操作结果：用ImgPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplexGetReal(Z,&realPart)第1章绪论

1.1什么是数据结构1.2基本概念和术语

1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1什么是数据结构抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。本课程在高级程序设计语言的虚拟层次上讨论抽象数据类型的表示和实现，采用介于伪码和Ｃ语言之间的类Ｃ语言作为描述工具，下面我们对其作一下简要说明。抽象数据类型可通过固有数据类型来表示和实现，即利用处（1）预定义常量和类型：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2Typedefintstatus

//status是函数的类型，

//其值是函数结果状态代码（1）预定义常量和类型：（2）数据结构的表示（存储结构）

用类型定义（typedef）描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。（3）基本操作的算法

用以下形式的函数描述：函数类型函数名（函数参数表）

{//算法说明语句序列

}//函数名（2）数据结构的表示（存储结构）说明：除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。当函数返回值为函数结果状态码时，函数定义为status类型。为了便于算法描述，除了值调用方式之外，增添了C++语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。说明：（4）赋值语句

简单赋值变量名=表达式；

串联赋值变量名1=变量名2=…变量名K=表达式；

成组赋值（变量名1，变量名2，…变量名K）=

（表达式1，表达式2，…表达式K）；（4）赋值语句

结构名=结构名；结构名=（值1，值2，…，值K）；变量名[]=表达式；变量名[起始下标..终止下标]=

变量名[起始下标..终止下标]；

交换赋值变量名←→变量名；

条件赋值

变量名=条件表达式？表达式T：表达式F；结构名=结构名；（5）选择语句

条件语句1if（表达式）语句；

条件语句2if（表达式）语句;else语句；（5）选择语句

开关语句1

switch（表达式）{case值1:语句序列1；break；

…case值n:语句序列n；break；

default:语句序列n+1