by 花满锤
本文主要是一些数据结构的基本概念
1. 第一章：数据结构的基本概念
抽象数据类型
抽象数据类型（Abstract Data Type，ADT）是将数据对象、数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式，它和工程中的应用是一致的。在工程项目中，开始编程之前，首先列出程序需要完成的功能任务，先不用管具体怎么实现，实现细节在项目后期完成，一开始只是抽象出有哪些基本操作。把这些操作项封装为抽象数据类型，等待后面具体实现这些操作。而其他对象如果想调用这些操作，只需要按照规定好的参数接口调用，并不需要知道具体是怎么实现的，从而实现了数据封装和信息隐藏。在C++中可以用类的声明表示抽象数据类型，用类的实现来实现抽象数据类型的具体操作。
抽象数据类型可以用以下的三元组来表示。
ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> } ADT抽象数据类型名
（1）为什么要使用抽象数据类型？
抽象数据类型的主要作用是数据封装和信息隐藏，让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节，从而使这些操作不会受到其他对象的影响，这就是信息隐藏。抽象数据类型独立于运算的具体实现，使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，实现了信息隐藏。
（2）为什么很多书中没有使用抽象数据类型？
既然抽象数据类型符合工程化需要，可以实现数据封装和信息隐藏，为什么很多数据结构书中的程序并没有使用抽象数据类型呢？因为很多人觉得数据结构难以理解，学习起来非常吃力，因此仅仅将数据结构的基本操作作为重点，把每一个基本操作讲解清楚，使读者学会和掌握数据结构的基本操作，便完成了数据结构书的基本任务。在实际工程中，需要根据实际情况融会贯通，灵活运用，这是后续话题。目前要掌握的就是各种数据结构的基本操作，本书也将基本操作作为重点讲述，并结合实例讲解数据结构的应用。
数据结构和算法相辅相成，密不可分，在学习数据结构之前，首先要了解什么是算法、好算法的衡量标准，以及算法复杂度的计算方法。
1.1 定义
- 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
1.2 逻辑结构
- 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的
- 数据的逻辑结构分为线性结构和非线性结构
- 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 类似于数学上的集合
- 线性结构 结构中的数据元素之间只存在一对一的关系。比如排队
- 树形结构 结构中的数据元素之间存在一对多的关系。比如家族族谱
- 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 比如地图
1.3 物理结构
- 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
- 顺序存储：存储的物理位置相邻。（p.s. 物理位置即信息在计算机中的位置。）
-
- 链接存储：存储的物理位置未必相邻，通过记录相邻元素的物理位置来找到相邻元素。
-
- 索引存储：类似于目录，以后可以联系操作系统的文件系统章节来理解。
-
- 散列存储：通过关键字直接计算出元素的物理地址（以后详解）。
-
1.4 算法的五个特征
- 1，有穷性：有限步之后结束
- 2，确定性：不存在二义性，即没有歧义
- 3，可行性：比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成。
- 4，输入：能被计算机处理的各种类型数据，如数字，音频，图像等等。
- 5，输出：一至多个程序输出结果。
1.5 算法的复杂度
1.5.1 时间复杂度：
- 它用来衡量算法随着问题规模增大，算法执行时间增长的快慢；
- 是问题规模的函数：T(n)是时间规模函数 时间复杂度主要分析T(n)的数量级
T(n)=O(f(n))f(n)是算法中基本运算的频度 一般我们考虑最坏情况下的时间复杂度
时间复杂度：
算法运行需要的时间，一般将算法基本运算的执行次数作为时间复杂度的度量标准。
//算法1-3 sum=0; //运行1次 total=0; //运行1次 for(i=1;i<=n;i++) //运行n+1次，最后依次判断条件不成立，结束 { sum=sum+i; //运行n次 for(j=1;j<=n;j++) //运行n*(n+1)次 total=total+i*j; //运行n*n次 }
把算法所有语句的运行次数加起来，即1+1+n+1+n+n×(n+1)+n×n，可以用一个函数T(n)表达：
当n足够大时，如n=105时，T(n)=2×1010+3×105+3，我们可以看到算法运行时间主要
取决于第一项，后面的基本可以忽略不计。
如果用极限来表示，则为：
c为不等于0的常数
如果用时间复杂度渐进上界表示，如图
从图可以看出，当 
时， 
，当n足够大时， 
和 
近似相等，因此我们用 
来表示时间复杂度渐近上界，通常用这种表示法衡量算法时间复杂度。算法的时间复杂度渐进上界为 
，如果用极限来表示，则为： 
还有渐近下界符号 
，如图所示。
从图中可以看出， 时， ，当n足够大时， 和 近似相等，因此用 
来表示时间复杂度渐近下界。
渐近精确界符号 
，如图所示。
从图1-3中可以看出，当 时， 
，当 
足够大时， 和 近似相等，这种两边逼近的方式，更加精确近似，时间复杂度渐近精确界用 
来表示。我们通常使用时间复杂度渐近上界 来表示时间复杂度。
常用的时间复杂度大小关系：
复杂度如何计算
- 时间复杂度计算（单个循环体）
- 直接关注循环体的执行次数，设为k
- 时间复杂度计算（多个循环体）
- 两个运算规则：乘法规则，加法规则。
1.5.2 空间复杂度：
- 它用来衡量算法随着问题规模增大，算法所需空间的快慢；
- 是问题规模的函数：S(n)=O(g(n)) ；算法所需空间的增长率和g(n)的增长率相同。
- 复杂度计算为重点
空间复杂度：算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
空间复杂度的本意是指算法在运行过程中占用了多少存储空间，算法占用的存储空间
包括如下。
（1）输入/输出数据所占空间。
（2）算法本身所占空间。
（3）额外需要的辅助空间。
输入/输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间是衡量空间复杂度的关键因素。
2. 第二章：线性表
2.1 线性表的逻辑结构
- 定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。其中n为表长。当n=0时 线性表是一个空表
- 特点：线性表中第一个元素称为表头元素；最后一个元素称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
2.2 线性表的顺序存储结构
- 线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元（比如C语言里面的数组），依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表采用顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。顺序存储方式，元素存储是连续的，中间不允许有空，可以快速定位第几个元素，但是插入和删除时需要移动大量元素。根据分配空间方法不同，顺序表可以分为静态分配和动态分配两种方法。
2.2.1 静态分配
顺序表最简单的方法是使用一个定长数组data[]存储数据，最大空间为Maxsize，用length记录实际的元素个数，即顺序表的长度。这种用定长数组存储的方法称为静态分配。静态顺序表如图所示。
顺序表的静态分配结构体定义，如图所示。采用静态分配方法，定长数组需要预先分配一段固定大小的连续空间，但是在运算的过程中，如合并、插入等操作，容易超过预分配的空间长度，出现溢出。解决静态分配的溢出问题，可以采用动态分配的方法。
2.2.2 动态分配
在程序运行过程中，根据需要动态分配一段连续的空间（大小为Maxsize），用elem记录该空间的基地址（首地址），用length记录实际的元素个数，即顺序表的长度。动态
顺序表如图2-4所示。采用动态存储方法，在运算过程中，如果发生溢出，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的。
顺序表的动态分配结构体定义
1. 简化比较复杂的类型声明
给复杂的结构体类型起一个别名，这样就可以使用这个别名等价该结构体类型，在声明该类型变量时就方便多了。
例如，不使用typedef的顺序表定义：
struct SqList { int *elem; //顺序表的基地址 int length; //顺序表的长度 };
如果需要定义一个顺序表，需要写：
struct SqList L; //定义时需要加上struct(c需要，C++不需要)，L为顺序表的名字
使用typedef的顺序表定义：
typedef struct { int *elem; //顺序表的基地址 int length; //顺序表的长度 }SqList;
如果需要定义一个顺序表，需要写：
SqList L; //不需要写struct，直接用别名定义
2. 提高程序的可移植性
例如，在程序中使用这样的语句：
typedef int ElemType; //给int起个别名ElemType
在程序中，假如有n个地方用到了ElemType类型，如果现在处理的数据变为字符型了，那么就可以将上面类型定义中的int直接改为char。
typedef char ElemType;
这样只需要修改类型定义，不需要改动程序中的代码。如果不使用typedef类型定义，就需要把程序中n个用到int类型的地方全部改为char类型。如果某处忘记修改，就会产生错误。
问题2：使用ElemType是为了让算法的通用性更好，因为使用线性表的结构体定义后，并不清楚具体问题处理的数据是什么类型，不能简单地写成某一种类型。结合typedef使用，可以提高算法的通用性和可移植性。
以int型元素为例，如果使用顺序表的动态分配结构体定义，就可以直接将ElemType写成int。
typedef struct{ int *elem; //顺序表的基地址 int length; //顺序表的长度 }SqList;
也可以使用类型定义，给int起个别名：
typedef int ElemType; //给int起个别名ElemType，两者等价 typedef struct{ ElemType *elem; //顺序表的基地址 int length; //顺序表的长度 }SqList;
显然，后一种定义的通用性和可移植性更好，当然第一种定义也没有错。
- 建立顺序表的三个属性:
- 1.存储空间的起始位置（数组名data）
- 2.顺序表最大存储容量（MaxSize）
- 3.顺序表当前的长度（length）
- 其实数组还可以动态分配空间，存储数组的空间是在程序执行过程中通过动态存储分配语句分配
- 总结：
- 1.顺序表最主要的特点是随机访问（C语言中基于数组），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。
- 2.顺序表的存储密度高，每个结点只存储数据元素。无需给表中元素花费空间建立它们之间的逻辑关系（因为物理位置相邻特性决定）
- 3.顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
2.3 顺序表的操作
2.3.1.插入
- 算法思路：
- 1.判断
i的值是否正确 - 2.判断表长是否超过数组长度
- 3.从后向前到第
i个位置，分别将这些元素都向后移动一位 - 4.将该元素插入位置
i并修改表长
- 代码
- 分析：
- 最好情况：在表尾插入（即
i=n+1），元素后移语句将不执行，时间复杂度为O(1)。 - 最坏情况：在表头插入（即
i=1），元素后移语句将执行n次，时间复杂度为O(n)。 - 平均情况：假设pi（
pi=1/(n+1)）是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为
2.3.2.删除
- 算法思路：
- 1.判断i的值是否正确
- 2.取删除的元素
- 3.将被删元素后面的所有元素都依次向前移动一位
- 4.修改表长
- 代码
- 分析
- 最好情况：删除表尾元素（即
i=n），无须移动元素，时间复杂度为O(1)。 - 最坏情况：删除表头元素（即
i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)。 - 平均情况：假设pi(
pi=1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为
2.4 线性表的链式存储结构
链表的优点：
链表是动态存储，不需要预先分配最大空间；插入删除不需要移动元素。
链表的缺点：
每次动态分配一个节点，每个节点的地址是不连续的，需要有指针域记录下一个节点的地址，指针域需要占用一个int的空间，因此存储密度低（数据所占空
间/节点所占总空间）。存取元素必须从头到尾按顺序查找，属于顺序存取。
- 线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。
- 头结点和头指针的区别？
- 不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息
- 为什么要设置头结点？
- 1.处理操作起来方便 例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了
- 2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
2.5 单链表的操作
2.5.1. 头插法建立单链表：
- 建立新的结点分配内存空间，将新结点插入到当前链表的表头
- 代码
2.5.2.尾插法建立单链表：
- 建立新的结点分配内存空间，将新结点插入到当前链表的表尾
- 代码
2.5.3.按序号查找结点
- 在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL。
- 代码
2.5.4.按值查找结点
- 从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。
- 代码
2.5.5．插入
- 插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新结点。
- 算法思路：1.取指向插入位置的前驱结点的指针① p=GetElem(L,i-1);2.令新结点*s的指针域指向*p的后继结点② s->next=p->next;3.令结点*p的指针域指向新插入的结点*s③ p->next=s;
2.5.6．删除
- 删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点，即被删结点的前驱结点，再将其删除。
- 算法思路：1.取指向删除位置的前驱结点的指针 p=GetElem(L,i-1);2.取指向删除位置的指针 q=p->next;3.p指向结点的后继指向被删除结点的后继 p->next=q->next4.释放删除结点 free(q);
2.6. 双向链表
为了向前、向后操作方便，可以给每个元素附加两个指针域，一个存储前一个元素的地址，另一个存储下一个元素的地址。这种链表称为双向链表
定义
2.6.1.插入：(方法不唯一)
① s->next=p->next;
② p->next->prior=s;
③ s->prior=p;
④ p->next=s;
2.6.2.删除：
① p->next=q->next;
② q->next->prior=p;
③ free(q);
2.7 循环链表
单链表中，只能向后，不能向前。如果从当前节点开始，无法访问该节点前面的节点，而最后一个节点的指针指向头节点，形成一个环，就可以从任何一个节点出发，访问
所有的节点，这就是循环链表。循环链表和普通链表的区别就是最后一个节点的后继指向了头节点。
- 循环单链表：循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环
- 循环双链表：类比循环单链表，循环双链表链表区别于双链表就是首尾结点构成环
- 当循环双链表为空表时，其头结点的
prior域和next域都等于Head。
2.8 静态链表
- 静态链表：静态链表是用数组来描述线性表的链式存储结构。
- 数组第一个元素不存储数据，它的指针域存储第一个元素所在的数组下标。链表最后一个元素的指针域值为-1。
- 例子
顺序表和链表的比较
2.9 线性表的应用
合并有序顺序表
题目：将两个有序（非递减）顺序表La和Lb合并为一个新的有序（非递减）顺序表。
解题思路
1）首先创建一个顺序表Lc，其长度为La和Lb的长度之和。
2）然后从La和Lb中分别取数，比较其大小，将较小者放入Lc中，一直进行下去，直到其中一个顺序表La或Lb中的数取完为止。
3）把未取完的数再依次取出放入Lc中即可。
合并有序链表
题目：将两个有序（非递减）单链表La和Lb合并为一个新的有序（非递减）单链表。
解题思路
链表合并不需要再创建空间，只需要“穿针引线”，把两个单链表中的节点按非递减的顺序串联起来即可。
注意：单链表的头指针不可以移动，一旦头指针丢失，就找不到该单链表了，因此需要辅助指针。
就地逆置单链表
题目：将带有头节点的单链表就地逆置。即元素的顺序逆转，而辅助空间复杂度为O(1)。
解题思路
充分利用原有的存储空间，通过修改指针实现单链表的就地逆置。还记得吗？头插法
创建单链表得到的序列正好是逆序，那么我们就利用头插法建表的思路，实现就地逆置。
查找链表的中间节点
题目：带有头节点的单链表L，设计一个尽可能高效的算法求L中的中间节点。
解题思路
此类题型可以使用快慢指针来解决。一个快指针，一个慢指针，快指针走两步，慢指
针走一步。当快指针指向结尾的时候，慢指针刚好指向中间节点。
删除链表中的重复元素
题目：用单链表保存m个整数，节点的结构为(data,next)，且|data| n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。
解题思路
本题数据大小有范围限制，因此可以设置一个辅助数组记录该数据是否已出现，如果
已出现，则删除；如果未出现，则标记。一趟扫描即可完成。
