408考研数据结构与算法之数组、链表、队列、栈知识点和算法详细教程（更新中）_考研数据结构顺序表和链表

第一章：数据结构与算法概述

因为数据结构作为计算机专业的专业基础课程，是计算机考研的必考科目之一，如果打算报考计算机专业的研究生，你必须学好它。

数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一，想要顺利通过这些考试，你也必须学好它。数据结构是其它计算机课程的基础，如操作系统、编程原理、数据库管理系统、软件工程、人工智能等；

1.1 数据结构的基本概念

什么是数据？

数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。

数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象:数据对象是具有相同性值的数据元素的集合，是数据的一个子集。

数据类型概念

数据类型：数据类型是一个值的集合和定义再此集合上的一组操作的总称。

1）原子类型。其值不可再分的数据类型。如 bool 和 int 等某些基本数据类型。
2）结构类型。其值可以再分解为若干成分（分量）的数据类型。
3）抽象数据类型。抽象数据组织及与之相关的操作。
1
2
3

补充说明下：字符串不是原子类型。C语言没有原生字符串类型，很多高级语言像 java、C# 等就有字符串类型，有个 String 来表示字符串，用法和 int 这些很像，可以 String str = "linux"; 来定义字符串类型的变量。但是 C语言没有 String 类型，C语言中的字符串是通过字符指针来间接实现的。

数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

1.2 逻辑结构、物理结构

逻辑结构

数据结构分为逻辑结构和物理结构。逻辑结构分为集合结构、线性结构、树形结构、图形结构；

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素：一是数据元素；二是关系。

物理结构 / 存储结构

物理结构：数据的逻辑结构在计算机中(内存)的存储形式。

存储结构常见类型：顺序存储结构、链式存储结构、索引存储结构、散列存储结构。

顺序存储结构

顺序存储结构是把数据元素存放在连续的存储单元里，数据元素之间的逻辑关系是通过数据元素的位置。（在前面的数据元素就存在前面；在后面的数据元素就存在后面）C语言用数组来实现顺序存储结构。

链式存储结构

用一组任意的存储单元存储数据元素（可能连续也可能不连续），数据元素之间的逻辑关系用指针来表示（用指针存放后继元素的存储地址）

索引存储结构

在存储节点信息的同时，还建立附加索引，索引表中的每一项称为一个索引项，索引项的一般形式是：（关键字，地址），关键字是能唯一标识一个结点的那些数据项。

散列存储结构

散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。

1.3 数据结构的三要素

三要素：数据的逻辑结构，数据的存储结构，数据运算

第 1 要素 数据的逻辑结构

• 集合结构：结构中的数据元素之间除“同属一个集合”外，别无其它关系。
• 线性结构：结构中的数据元素之间只存在一对一的关系，除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
• 树形结构：结构中数据元素之间存在一对多的关系。
• 图状结构：数据元素之间是多对多的关系。

第 2 要素 数据的存储结构（物理结构）

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。

存储结构包括：（1.2小节已经提到，继续说明下）

顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）
散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
1
2
3
4

第 3 要素 数据的运算

施加在数据上的运算包括运算的定义何实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

具体解释：

运算的定义是对于逻辑结构的，就是说我们定义了一个运算，这个运算的作用对象是逻辑结构（比如对于线性结构定义增删查改）

运算的实现是对于存储结构的，就是说我们实现运算时针对于特定的存储结构的，同一个逻辑结构的不同的存储结构运算的实现是不同的。

1.4 算法的基本概念

算法，在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法是有效方法，包含一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。

算法的 5 个特性（特点）

1. 有穷性：算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。

2. 确定性：算法中每条指令必须有确切的含义，不会产生二义性，对于相同的输入只能得出相同的输出。

3. 可行性：算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

4. 输入：算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

5. 输出：算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

优秀算法的其他特性：

• 正确性：能够正确地解决问题。

• 可读性：可以让人们读懂。

• 健壮性：在输入错误的信息和执行错误地操作时，算法能够做出反应或对其进行处理。

1.5 时间复杂度、空间复杂度

衡量不同算法的优劣，主要还是根据算法所占的空间和时间两个维度去考虑。但是，世界上不会存在完美的代码，既不消耗最多的时间，也不占用最多的空间，鱼和熊掌不可得兼，那么我们就需要从中去寻找一个平衡点，使得写出一份较为完美的代码。

Big-O notation 的渐进表示法

Big-O notation：（Big-O complexity）是用于描述函数渐进行为的数学符号。

时间复杂度概念

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。

但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

常见的时间复杂度

按数量级递增排列，常见的时间复杂度有：常数阶O($1$)，对数阶O($log2n$)，线性阶O($n$)，线性对数阶O($nlog2n$)，平方阶O($n^2$)，立方阶O($n^3$)，$k$ 次方阶O($n^k$), 指数阶O($2^n$) 。

其中 O($n$)，O($n^2$)， 立方阶O($n^3$)， ···，$k$ 次方阶O($n^k$) 为多项式阶时间复杂度，分别称为一阶时间复杂度，二阶时间复杂度。

在分析算法时，存在几种可能的考虑：

算法完成工作最少需要多少基本操作，即最优时间复杂度
算法完成工作最多需要多少基本操作，即最坏时间复杂度
算法完成工作平均需要多少基本操作，即平均时间复杂度 
1
2
3

最优时间复杂度：其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。

平均时间复杂度：是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。

最坏时间复杂度：提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。

注意点：因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。

空间复杂度的概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用 Big-O notation 渐进表示法。

注意：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

同样在工程实践中，计算机的内存空间也不是无限的，需要工程师对软件运行时所使用的内存有一个大体评估，这都需要用到算法空间复杂度的分析。

递归空间复杂度

如何求递归空间复杂度，这里给大家提供一个公式：

$$递归算法的空间复杂度=每次递归的空间复杂度\ast 递归深度$$

为什么要求递归的深度呢？

因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

第二章：数据结构 - 顺序表与链表

知识框架：线性表分类

2.1 线性表的基本概念

线性表（List）：零个或多个数据元素的有限序列。线性表是具有相同数据类型的 n(n>0) 个数据元素的有限序列，其中 n 为表长，当 n=0 时线性表是一个空表。

线性表的数据集合为 {a1,a2,…,an}，假设每个元素的类型均为 DataType。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

2.2 静态顺序表的介绍

静态顺序表（SeqList）基本概念

概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

特点：逻辑上相邻的数据元素，物理次序也是相邻的。

只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。

【百度百科】顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

顺序表类别：

• 静态顺序表：使用定长数组存储元素。
• 动态顺序表：使用动态开辟的数组存储。

静态顺序表存储结构

注意：线性表的顺序存储结构为随机存储结构

创建静态顺序表的结构体：

typedef struct
{
    ElemType *elem; //存储空间的基地址
    int length;     //当前长度
} Sqlist;           //顺序表的结构类型为 Sqlist
1
2
3
4
5

建立空表，初始化数据：

Status InitList(Sqlist &L) //建立一个空表
{
    L.elem = new ElemType[MAXSIZE];
    if (!L.length)
    {
        exit(OVERFLOW); // OVERFLOW需要重定义
    }
    L.length = 0;
    return 0;
}
1
2
3
4
5
6
7
8
9
10

2.3 静态顺序表的基本操作

静态顺序表插入操作 ：平均时间复杂度 O(n)

bool ListInsert(SqList &L, int i, int e)
{

    if (i < 1 || i > L.length + 1) //判断i的范围是否有效
        return false;
    if (L.length > MaxSize) //当前存储空间已满，不能插入
        return false;

    for (int j = L.length; j >= i; j--)
    {
        L.data[j] = L.data[j - 1]; //将第i个元素及其之后的元素后移
    }
    L.data[i - 1] = e; //在位置i处放入e
    L.length++;        //长度加1
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

静态顺序表删除操作：平均时间复杂度 O(n)

bool LisDelete(SqList &L, int i, int &e)
{ 
    if (i < 1 || i > L.length) //判断i的范围是否有效
        return false;

    e = L.data[i - 1] //将被删除的元素赋值给e

    for (int j = L.length; j >= i; j--)
    {
        L.data[j - 1] = L.data[j]; //将第i个后的元素前移
    }
    L.length--; //长度减1
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

静态顺序表按位查找(获取 L 表中第 i 个位置的值)：平均时间复杂度 O(1)

ElemType GetElem(SqList L, int i){
    if (i < 1 || i > L.length) //判断i的范围是否有效
        return false;
    return L.data[i-1]; //注意是i-1
}
1
2
3
4
5

静态顺序表按值查找：平均时间复杂度 O(n)

int LocateElem(SqList L, ElemType e)
{
    for (int i = 0; i < L.lengthl i++)
        if (L.data[i] == e)
            return i + 1; //数组下标为i的元素值等于e，返回其位序i+1
    return 0;             //推出循环，说明查找失败
}
1
2
3
4
5
6
7

2.4 动态链表的介绍

何为链表？

链表和数组一样同属于线性表，即一种线性存储结构,线性存储结构又可分成两种。

其一，为 顺序存储结构（即 数组的存储方式）其特点是是逻辑关系上相邻的两个元素在物理位置上也相邻，即在连续的地址块中存储一系列数据。

其二，为链式存储结构（链表的存储方式）其特点为不需要逻辑上相邻的元素在物理位置上也相邻，即在不连续的地址中存储一系列数据 ，所以链表不能向数组一样通过下标随机访问。那么链表之间的元素又是如何相互关联的呢？它是由一系列的存储数据元素的单元通过指针串接来确定元素之间相互关系的,因此每个单元至少都有两个域—数据域和指针域，这样的单元也被称为节点(node)。

定义： 线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

链表分类

1.单链表（最普通的链表）
2.双向链表（有两个指针域）
3.循环链表（首尾相接）
4.静态链表（链表的数组表示法）
1
2
3
4

链表的优缺点

链表优点：

(1)插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可。
(2)没有空间限制,存储元素无上限,只与内存空间大小有关。
(3)动态分配内存空间，不用事先开辟内存。

链表缺点：

(1)占用额外的空间以存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多。
(2) 查找速度比较慢，因为在查找时，只能顺序查找，需要循环链表。

头指针，头节点，首元节点

头指针：指向链表第一个节点的指针（不一定是头节点，因为……链表要是没有头节点呢？），没有实际开辟空间 （即没有用malloc等动态分配内存） 而且必须存在，因为头指针不存在，就不便于对链表进行操作。

头节点：不是必须存在（若存在则为链表的第一个节点）其主要作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行（还是挺有用的）。其数据域可以不储存任何数据，若储存则通常是链表的长度啥的。

首元节点：第一个数据域中储存有效数据的节点，若头节点不存在，则其为链表的第一个节点，是一定要存在的（除非是空表）

链表（动态顺序表）：使用动态开辟的数组存储元素

动态顺序表优点：动态顺序表可根据我们的需要分配空间大小

size 表示当前顺序表中已存放的数据个数
capacity 表示顺序表总共能够存放的数据个数
typedef int SLDataType; 类型重命名，后续要存储其它类型时方便更改
1
2
3

创建动态顺序表（链表）结构体

typedef struct SeqList
{
    SLDataType *a;   //指向动态开辟的数组
    size_t size;     //有效数据个数
    size_t capacity; //容量大小
} SeqList;
1
2
3
4
5
6

带头结点和不带头结点的比较

不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑；头指针指向的结点用于存放实际数据；

带头结点：头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据；

2.5 单链表的创建与算法

malloc 函数原型

extern void *malloc(unsigned int num_bytes);
1

作用：分配长度为 num_bytes 字节的内存块，malloc 函数头文件 #include<malloc.h>

malloc 函数返回值：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。

创建节点 Node 结构体

typedef struct Node
{
	int data;		   // 存储链表数据
	struct Node *next; //  存储结点的地址
} LNode, *Linklist;
1
2
3
4
5

顺序建立链表（尾插法）

尾插法含义：该方法是从一个空表开始，读取数组的元素，生成新节点，将读取的数据放到存放在新节点的数据域中，然后将该节点插入到链表的表头上，直到结束为止。

由于：头插法会让顺序与数组原顺序相反，所以这里要定义一个尾指针 rail 才可让顺序不变。

Linklist Creat_list(Linklist head)
{
	head = (Linklist)malloc(sizeof(LNode)); //  为头指针开辟内存空间
	Linklist node = NULL;					//  定义结点
	Linklist end = NULL;					//  定义尾结点
	head->next = NULL;						//  初始化头结点指向的下一个地址为 NULL
	end = head;								//  未创建其余结点之前，只有一个头结点
	int count = 0;							//  结点个数
	printf("Input node number: ");
	scanf("%d", &count);
	for (int i = 0; i < count; i++)
	{
		node = (Linklist)malloc(sizeof(LNode)); //  为新结点开辟新内存
		node->data = i;							//  新结点的数据域赋值
		end->next = node;
		end = node;
	}
	end->next = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

头插法创建链表

Linklist Creat_list(Linklist head)
{
	head = (Linklist)malloc(sizeof(LNode)); //  为头指针开辟内存空间
	LNode *node = NULL;						//  定义新结点
	int count = 0;							//  创建结点的个数
	head->next = NULL;
	node = head->next; //  将最后一个结点的指针域永远保持为NULL
	printf("Input the node number: ");
	scanf("%d", &count);
	for (int i = 0; i < count; i++)
	{
		node = (Linklist)malloc(sizeof(LNode)); //  为新结点开辟内存空间
		node->data = i;							//  为新结点的数据域赋值
		node->next = head->next;				//  将头指针所指向的下一个结点的地址，赋给新创建结点的next
		head->next = node;						//  将新创建的结点的地址赋给头指针的下一个结点
	}
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

由上面的例子以及比较，我们可以看见：

• 头插法相对简便，但插入的数据与插入的顺序相反。
• 尾插法操作相对复杂，但插入的数据与插入顺序相同。

2.6 双链表和创建与算法

目前，我们了解到的链表，无论是动态链表还是静态链表，表中的每个节点仅包含一个指针(游标)，并且全部指向直接后继节点，即通常称为单向链表(或单链表)。

尽管使用单链接列表可以100％解决逻辑上关系的数据存储问题，但是当解决某些特殊问题时，单链接列表并不是最有效的存储结构。例如，如果算法需要查找指定节点的大量前任节点，则单链接列表的使用无疑是灾难性的。

为了能够有效解决类似问题，在本节中，我们将研究双向链表(简称双链表)

双链表的结构体

typedef struct List{
	int data;			// 数据域
	struct List *next;	// 向后的指针
	struct List *front;	// 向前的指针
};
1
2
3
4
5

双向链表的创建

在创建双向链表的时候，我们需要初始化的有两个指针。同单链表一样，我们需要一个头指针来标志链表的信息。因此我们可以写出该函数的定义：

pElem CreatList(){
	pElem head = (pElem)malloc( sizeof(eElem) );
	assert(head != NULL); // 包含于标准库<assert.h>
	head->next = head->front = NULL; // 初始化链表，指针置空
	return head;
}
1
2
3
4
5
6

双链表的插入节点

双链表的插入（头插法）

void inset_to_head(Data *head, Data *new)
{
	//先改变要插入的节点的指针域
	new->prev = head;
	new->next = head->next;
	//再改变要插入位置的前后节点的指针域
	if (head->next != NULL) //如果只有头节点，就不需要解引用头节点的下一个节点，不然就是解引用NULL
	{
		head->next->prev = new;
	}
	head->next = new;
}
1
2
3
4
5
6
7
8
9
10
11
12

双链表的插入（尾插法）

void inset_to_last(Data *head, Data *new)
{
	//找到尾节点
	Data *p = NULL;
	for (p = head; p->next != NULL; p = p->next) {}
	//将新节点插入到尾节点后面
	new->prev = p;
	p->next = new;
}
1
2
3
4
5
6
7
8
9

2.7 循环链表的介绍与算法

在单链表中我们是把结点遍历一遍后就结束了，为了使表处理更加方便灵活，我们希望通过任意一个结点出发都可以找到链表中的其它结点，因此我们引入了循环链表。

循环链表的定义

将单链表中终端结点的指针端由空指针改为头结点，就使整个单链表形成了一个环，这种头尾相接的单链表称为循环链表。

循环链表的结构体

typedef int ELEMTYPE;
typedef struct Clist
{
	ELEMTYPE data; //数据域存放数据
	struct Clist* next;
	// 指针域存放下一个节点的地址（尾结点的next保存头结点的地址）
}Clist, * PClist;
1
2
3
4
5
6
7

循环链表的操作

循环链表是单链表中扩展出来的结构，所以有很多的操作是和单链表相同的，如求长度，查找元素，获取一个元素，这里我们对循环链表进行初始化，创建，插入，删除，销毁的一系列操作。

循环链表尾插法（重点）

bool Insert_tail(PCNode plist, ELEM_TYPE val)
{
	struct CNode *pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if (pnewnode == NULL)
	{
		return false;
	}

	struct CNode *p;
	for (p = plist; p->next != plist; p = p->next) {}
	//用上面的for循环  让p停留在尾结点 此时 p指向尾结点

	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.8 链表的反转算法（3 种）

指针空值类型 nullptr 介绍

引入 nullptr 的原因，这个要从 NULL 说起。对于 C 和 C++ 程序员来说，不会对 NULL 感到陌生。但是 C 和 C++ 中的 NULL 却不等价。NULL 表示指针不指向任何对象，但是问题在于，NULL 不是关键字，而只是一个宏定义(macro)。

nullptr是C11新引入的关键字，是一个所谓“指针空值类型”的常量，在C++程序中直接使用。

方案一：调用栈：第一轮循环用栈保存各个节点上的值，第二轮循环重新赋值。

算法的时间复杂度：O（n），空间复杂度：O（n）

ListNode* ReverseList(ListNode* pHead) {
	stack<int> s;
	ListNode *pCur = pHead;
	while (pCur)
	{
		s.push(pCur->val);
		pCur = pCur->next;
	}

	// deassign val
	pCur = pHead;
	while (pCur)
	{
		pCur->val = s.top(); // get val of stack's top
		s.pop(); // exit stack
		pCur = pCur->next;
	}
	return pHead;
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方案二：前后指针：调整链表指针，反转链表

pre指针 指向已经反转好的链表的最后一个节点，初始化为 nullptr。

cur指针 指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向头指针。

nex指针 指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存。

图例展示：

算法复杂度分析：时间复杂度O(N)，空间复杂度O(1)

ListNode* ReverseList(ListNode* pHead) {
    ListNode *pre = NULL; 
    //pre指针指向已经反转好的链表的最后一个节点，初始化为null；
    ListNode *cur = pHead; 
    //cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向头指针；
    ListNode *next = NULL; 
    //next指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存
    while(cur){
        next = cur->next; 
        //next保存待反转指针的第一个节点
        cur->next = pre; 
        //cur的第一个节点保存已经反转好的链表的最后一个节点
        pre =cur; 
        //已经反转好的链表的最后一个节点保存待反转链表的第一个节点
        cur = next; 
        //待反转链表的第一个节点为反转指针的第一个节点
    }
    return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方案三：采取递归

思想：和迭代反转法的思想恰好相反，递归反转法的实现思想是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。

ListNode* ReverseList(ListNode* pHead) {
	if(pHead == nullptr || pHead->next == nullptr){
		//如果最后一个结点不操作
		return pHead;
	} 
	
	ListNode *node = ReverseList(pHead->next); 
	//先递归到最底层 然后返回 即一直循环到链尾
	pHead->next->next = pHead; 
	//翻转链表的指向
	pHead->next = nullptr; 
	//记得赋值nullptr 防止链表错乱
	return node; 
	//新链表头永远指向的是原链表的链尾
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第三章：数据结构 - 栈和队列

知识框架：栈、队列、数组

3.1 栈的基本概念

Stack 栈的定义

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。
1
2
3

注意：栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

栈的常见基本操作

InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。
1
2
3
4
5
6

3.2 栈的顺序存储结构

栈的顺序存储

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

若存储栈的长度为 StackSize，则栈顶位置 top 必须小于 StackSize。当栈存在一个元素时，top 等于 0，因此通常把空栈的判断条件定位 top 等于 -1。

栈的顺序存储结构可描述为：

#define MAXSIZE 50    //定义栈中元素的最大个数
typedef int ElemType; // ElemType的类型根据实际情况而定，这里假定为int
typedef struct
{
    ElemType data[MAXSIZE];
    int top; //用于栈顶指针
} SqStack;
1
2
3
4
5
6
7

若现在有一个栈，StackSize是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：

3.3 顺序栈的基本算法

（1）顺序栈 初始化：平均时间复杂度 O(1)

void InitStack(SqStack *S)
{
    S->top = -1; //初始化栈顶指针
}
1
2
3
4

（2）顺序栈 判栈空：平均时间复杂度 O(1)

bool StackEmpty(SqStack S)
{
    if (S.top == -1)
    {
        return true; //栈空
    }
    else
    {
        return false; //非空
    }
}
1
2
3
4
5
6
7
8
9
10
11

（3）顺序栈 进栈操作：平均时间复杂度 O(1)

Status Push(SqStack *S, ElemType e)
{
    // 插入元素e为新的栈顶元素
    if (S->top == MAXSIZE - 1) //满栈
    {
        return ERROR;
    }
    S->top++;            //栈顶指针增加一
    S->data[S->top] = e; //将新插入元素赋值给栈顶空间
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11

（4）顺序栈 出栈 出栈操作pop：平均时间复杂度 O(1)

Status Pop(SqStack *S, ElemType *e)
{
    if (S->top == -1) //栈空
    {
        return ERROR;
    }
    *e = S->data[S->top]; //将要删除的栈顶元素赋值给e
    S->top--;             //栈顶指针减一
    return OK;
}
1
2
3
4
5
6
7
8
9
10

（5）顺序栈 读栈顶元素：平均时间复杂度 O(1)

Status GetTop(SqStack S, ElemType *e)
{
    if (S->top == -1) //栈空
    { 
        return ERROR;
    }
    *e = S->data[S->top]; //记录栈顶元素
    return true;
}
1
2
3
4
5
6
7
8
9

3.4 有效括号序列（栈的实现）

给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。

数据范围：字符串长度 $0\le n\le 10000$
要求：空间复杂度 $O(n)$，时间复杂度 $O(n)$

方案一：有效括号序列 借助辅助栈 左括号入栈

核心思想：每次遇到’(‘,’{‘,’[‘这三种字符的时候，将字符入栈stk；而每次遇到’)‘,’}‘,’]'这三种字符的时候则让对应的匹配字符出栈。

具体规则如下：

1）引入辅助栈stk，遍历字符串，每次遇到'(','{','['字符的时候将字符入栈stk
2）当遇到')','}',']'字符的时候，则检查栈是否空，且顶元素是否为匹配元素（如{和}匹配等），如果栈空或者栈顶元素不为匹配元素则括号序列不合法
3）当栈非空，且栈顶元素为匹配元素，则栈顶元素出栈
4）循环匹配字符串，直到每次字符处理完
5）检查栈stk是否为空，栈为空则序列合法，否则不合法（当括号以正确顺序关闭时则最后的栈为空）
1
2
3
4
5

算法解析图解分析：

方案二：有效括号序列 借助辅助栈 右括号入栈

核心思想：借助辅助栈，当遇到’(‘,’[‘,’{‘这三种字符的时候则让对应的匹配字符入栈(分别对应’)‘,’]‘,’}‘)，当出现的字符不是’(‘,’[‘,’{'这三种字符时，则先判断栈是否为空或者当前字符是否与栈顶元素一样，当栈空或者当前字符与栈顶字符不一样时，则括号序列不合法，直接返回；否则栈顶元素出栈。遍历字符串直到所有元素遍历完成。最后判断栈是否为空，不为空则括号序列不合法；否则为合法序列。

bool isValid(string s) {
    stack<char> stk;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') 
            stk.push(')');
        else if (s[i] == '[')
            stk.push(']');
        else if (s[i] == '{')
            stk.push('}');
        else {               
            //当字符不是'(','[','{'这三种字符时，则判断当前字符是否与栈顶元素一样(栈非空时)
            if (stk.empty() || s[i] != stk.top())
                return false;
            stk.pop();
        }
    }
    return stk.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

算法的复杂度分析：

代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于引入额外的栈空间，因此空间复杂度为O(N)，最坏的情况是数组中的元素都为右括号。

时间复杂度O(n)、空间复杂度O(n)
‘

3.5 最大矩形面积（栈的实现）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

题目图示：

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
1
2
3

空间换时间，可以使用的数据结构是栈

要搞清楚这个过程，请大家一定要在纸上画图，搞清楚一些细节，这样在编码的时候就不容易出错了。

记录什么信息呢？记录高度是不是可以呢？其实是不够的，因为计算矩形还需要计算宽度，很容易知道宽度是由下标确定的，记录了下标其实对应的高度就可以直接从输入数组中得出，因此，应该记录的是下标。

我们就拿示例的数组 [2, 1, 5, 6, 2, 3] 为例：

1. 一开始看到的柱形高度为 2 ，这个时候以这个 2 为高度的最大面积的矩形还不能确定，我们需要继续向右遍历，如下图。
   

2. 然后看到到高度为 1 的柱形，这个时候以这个柱形为高度的矩形的最大面积还是不知道的。但是它之前的以 2 为高度的最大面积的矩形是可以确定的，这是因为这个 1 比 2 小 ，因为这个 1 卡在了这里 2 不能再向右边扩展了，如下图。
   

3. 我们计算一下以 2 为高度的最大矩形的面积是 2。其实这个时候，求解这个问题的思路其实已经慢慢打开了。如果已经确定了一个柱形的高度，我们可以无视它，将它以虚框表示，如下图。
   

4. 遍历到高度为 5 的柱形，同样的以当前看到柱形为高度的矩形的最大面积也是不知道的，因为我们还要看右边高度的情况。那么它的左右有没有可以确定的柱形呢？没有，这是因为 5 比 1 大，我们看后面马上就出现了 6，不管是 1 这个柱形还是 5 这个柱形，都还可以向右边扩展；
   

5. 接下来，遍历到高度为 6 的柱形，同样的，以柱形 1、5、6 为高度的最大矩形面积还是不能确定下来；
   

6. 再接下来，遍历到高度为 2 的柱形。
   

7. 发现了一件很神奇的事情，高度为 6 的柱形对应的最大矩形的面积的宽度可以确定下来，它就是夹在高度为 5 的柱形和高度为 2 的柱形之间的距离，它的高度是 6，宽度是 1。
   

8. 将可以确定的柱形设置为虚线。
   

9. 接下来柱形 5 对应的最大面积的矩形的宽度也可以确定下来，它是夹在高度为 1 和高度为 2 的两个柱形之间的距离；
   

10. 确定好以后，我们将它标成虚线。
    

11. 我们发现了，只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边。

    这个现象告诉我们，在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。

12. 这个时候，还需要考虑的一个细节是，在确定一个柱形的面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小。

    那如果是左边的高度和自己相等怎么办呢？我们想一想，我们之前是只要比当前严格小，我们才可以确定一些柱形的最大宽度。只要是大于或者等于之前看到的那一个柱形的高度的时候，我们其实都不能确定。

    因此我们确定当前柱形对应的宽度的左边界的时候，往回头看的时候，一定要找到第一个严格小于我们要确定的那个柱形的高度的下标。这个时候 中间那些相等的柱形其实就可以当做不存在一样。因为它对应的最大矩形和它对应的最大矩形其实是一样的。

    说到这里，其实我们的思路已经慢慢清晰了。

    我们在遍历的时候，需要记录的是下标，如果当前的高度比它之前的高度严格小于的时候，就可以直接确定之前的那个高的柱形的最大矩形的面积，为了确定这个最大矩形的左边界，我们还要找到第一个严格小于它的高度的矩形，向左回退的时候，其实就可以当中间这些柱形不存在一样。

    这是因为我们就是想确定 6 的宽度，6 的宽度确定完了，其实我们就不需要它了，这个 5 的高度和这个 5 的高度确定完了，我们也不需要它了。

    我们在缓存数据的时候，是从左向右缓存的，我们计算出一个结果的顺序是从右向左的，并且计算完成以后我们就不再需要了，符合后进先出的特点。因此，我们需要的这个作为缓存的数据结构就是栈。

    当确定了一个柱形的高度的时候，我们就将它从栈顶移出，所有的柱形在栈中进栈一次，出栈一次，一开始栈为空，最后也一定要让栈为空，表示这个高度数组里所有的元素都考虑完了。

13. 最后遍历到最后一个柱形，即高度为 3 的柱形。
    

14. 一次遍历完成以后。接下来考虑栈里的元素全部出栈。接下来我们就要依次考虑还在栈里的柱形的高度。和刚才的方法一样，只不过这个时候右边没有比它高度还小的柱形了，这个时候计算宽度应该假设最右边还有一个下标为 len （这里等于 6） 的高度为 0 （或者 0.5，只要比 1 小）的柱形。
    

15. 下标为 5 ，即高度为 3 的柱形，左边的下标是 4 ，右边的下标是 6 ，因此宽度是 6 - 4 - 1 = 1（两边都不算，只算中间的距离，所以减 1）；算完以后，将它标为虚线。
    

16. 下标为 4 ，高度为 2 的柱形，左边的下标是 1 ，右边的下标是 6 ，因此宽度是 6 - 1 - 1 = 4；算完以后，将它标为虚线。
    

17. 最后看下标为 1，高度为 1 的矩形，它的左边和右边其实都没有元素了，它就是整个柱形数组里高度最低的柱形，计算它的宽度，就是整个柱形数组的长度。
    

18. 到此为止，所有的柱形高度对应的最大矩形的面积就都计算出来了。
    

19. 这个算法经过一次遍历，在每一次计算最大宽度的时候，没有去遍历，而是使用了栈里存放的下标信息，以 O(1)O(1) 的时间复杂度计算最大宽度。

代码展示：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


class Solution {
public:
    int largestRectangleArea(vector<int> &heights) {
        unsigned long size = heights.size();
        if (size == 1) {
            return heights[0];
        }
        int res = 0;
        stack<int> stk;
        for (int i = 0; i < size; ++i) {
            while (!stk.empty() && heights[stk.top()] > heights[i]) {
                int length = heights[stk.top()];
                stk.pop();
                int weight = i;
                if (!stk.empty()) {
                    weight = i - stk.top() - 1;
                }
                res = max(res, length * weight);
            }
            stk.push(i);
        }
        while (!stk.empty()) {
            int length = heights[stk.top()];
            stk.pop();
            int weight = size;
            if (!stk.empty()) {
                weight = size - stk.top() - 1;
            }
            res = max(res, length * weight);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Leetcode 另一位大佬解释

全局分析展示如下：

代码模板：

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}
1
2
3
4
5
6
7
8
9

1. 对于一个高度，如果能得到向左和向右的边界
2. 那么就能对每个高度求一次面积
3. 遍历所有高度，即可得出最大面积
4. 使用单调栈，在出栈操作时得到前后边界并计算面积

int largestRectangleArea(vector<int>& heights)
{
    int ans = 0;
    vector<int> st;
    heights.insert(heights.begin(), 0);
    heights.push_back(0);
    for (int i = 0; i < heights.size(); i++)
    {
        while (!st.empty() && heights[st.back()] > heights[i])
        {
            int cur = st.back();
            st.pop_back();
            int left = st.back() + 1;
            int right = i - 1;
            ans = max(ans, (right - left + 1) * heights[cur]);
        }
        st.push_back(i);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

前后添加0，让所有元素强制弹出（但是如果输入是递增的话，这个代码最后都无法弹出计算面积。需要在Heights数组的后面再加上一个0）

3.6 队列的基本概念

队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。

队列是一个先进先出的线性表，相应的也有顺序存储和链式存储两种方式。

顺序存储就是用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)，性能自然不高。

为了提高出队的性能，就有了循环队列，什么是循环队列呢？就是有两个指针，front指向队头，rear指向对尾元素的下一个位置，元素出队时front往后移动，如果到了对尾则转到头部，同理入队时rear后移，如果到了对尾则转到头部，这样通过下标front出队时，就不需要移动元素了。

同时规定，当队列为空时，front和rear相等，那么队列什么时候判断为满呢？按照循环操作rear依次后移，然后再从头开始，也是出现rear和front相等时，队列满。这样跟队列空的情况就相同了，为了区分这种情况，规定数组还有一个空闲单元时，就表示队列已满，因为rear 可能在front后面，也可能循环到front前面，所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize。

队列主要应用在下面几种场景

• 队列用于异步数据传输(例如，数据不以两个进程之间的相同速率传输)。 管道，文件IO，套接字。

• 队列在大多数应用程序中用作缓冲区，如MP3媒体播放器，CD播放器等。

• 队列用于维护媒体播放器中的播放列表，以便添加和删除播放列表中的歌曲。

• 队列在操作系统中用于处理中断。

队列 Queue的分类

双端队列：双端队列（Deque）是 Queue 的子类也是 Queue 的补充类，头部和尾部都支持元素插入和删除。

阻塞队列：在元素操作时（添加或删除），如果没有成功，会阻塞等待执行。例如，当添加元素时，如果队列元素已满，队列会阻塞等待直到有空位时再插入。

非阻塞队列：非阻塞队列和阻塞队列相反，会直接返回操作的结果，而非阻塞等待。双端队列也属于非阻塞队列。

3.7 链式队列的基本算法

若采用顺序表的方式实现队列，随着出队入队的操作，队头指针和队尾指针的移动，队头前的空间就可能发生内存泄漏，或出现假溢出问题。对此有两种解决方法，一种是采用链表的方式实现队列，一种是采用循环队列，这里采用的是链表的方式实现队列，随后会发布循环队列的实现方法。

链式结构定义队列的结构体

定义结构体结构

typedef struct Queue_Node {
	QUEUE_TYPE data;
	struct Queue_Node *next;
}QueueNode;
1
2
3
4

创建一个结构体指针

QueueNode *head; // ①、创建头指针：QueueNode *head;
QueueNode *tail; // ②、创建尾指针：QueueNode *tail;
1
2

数据入队列

①、创建一个结构体指针 new_node
②、通过malloc动态分配地址块，将该地址块的首地址传给 new_node
③、通过判断 new_node == NULL 查看 malloc 是否分配内存空间成功，为空则表示分配失败，打印错误信息
④、将数据赋值给 new_node 指针指向的 data 域
⑤、通过判断 head == NULL 确定该队列是否为空
1
2
3
4
5

• 队列为空则将头指针 head 和尾指针 tail 都指向新节点【new_node 指向的内存空间】
• 队列不为空则将 “ 尾指针 tail 指向的内存空间中的 next 域 ” 指向 “ new_node 指向的内存空间 ”
• 将尾指针 tail 指向 “ new_node 指向的内存空间 ”【尾指针指向新节点】

void enqueue(QUEUE_TYPE value) {
	QueueNode *new_node;
	new_node = (QueueNode *)malloc(sizeof(QueueNode));
	if (new_node == NULL)
		perror("malloc fail\n");
	new_node->data = value;
	if (head == NULL) {
		head = new_node;
		tail = new_node;
	} else {
		tail->next = new_node;
		tail = new_node;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

数据出队列

①、判断该队列是否为空
②、创建一个结构体指针 front_node
③、将 “ 头指针指向的内存空间 ” 传给 “ front_node ”，使得 front_node 指向第一个节点
④、将 “ front_node 指向内存空间中的next的值 ”【第二个节点的首地址】传给 头指针 head，使得头指针 head 指向第二个节点
⑤、将 front_node 指向的内存空间通过 free() 释放掉【释放第一个节点的内存空间】
⑥、如果这时 头指针 head 指向为空，说明该队列已为空，将尾指针 tail 也设置为指向为空
1
2
3
4
5
6

void dequeue(void) {
	assert(!is_empty());
	QueueNode *front_node;
	front_node = head;
	head = front_node->next;
	free(front_node);
	if (head == NULL)
		tail = NULL;
}
1
2
3
4
5
6
7
8
9

判断队列是否为空

在队列中，头指针 head 指向为空，则说明该队列为空，所以只需要返回 head == NULL 的结果

返回值为1：表明队列为空，返回值为0：说明队列不为空

int is_empty(void) {
	return head == NULL;
}
1
2
3

获取队列第一个数据

①、判断队列是否为空
②、返回头指针 head 所指向 内存空间 中的 data 域数据

QUEUE_TYPE get_head(void) {
	assert(!is_empty());
	return head->data;
}
1
2
3
4

获取队列最后一个数据

①、判断队列是否为空
②、返回尾指针 tail 所指向 内存空间 中的 data域数据

QUEUE_TYPE get_tail(void) {
	assert(!is_empty());
	return tail->data;
}
1
2
3
4

用的数据结构是栈