大家好，我是讯享网，很高兴认识大家。



文章目录

• 0 笔记说明
• 1 线性表

• 1.1 线性表的定义
• 1.2 线性表的基本操作

• 2 顺序存储的线性表：顺序表

• 2.1 静态分配的顺序表
• 2.2 动态分配的顺序表
• 2.3 顺序表的特点
• 2.4 顺序表的基本操作

• 2.4.1 插入元素操作
• 2.4.2 删除元素操作
• 2.4.3 查找元素操作

• 2.4.3.1 按位置查找元素
• 2.4.3.2 按数值查找元素

• 3 链式存储的线性表：链表

• 3.0 链表的特点
• 3.1 单链表

• 3.1.1 不带头结点的单链表
• 3.1.2 带头结点的单链表
• 3.1.3 单链表的基本操作

• 3.1.3.1 插入

• 3.1.3.1.1 按位序插入（带头结点）
• 3.1.3.1.2 按位序插入（不带头结点）
• 3.1.3.1.3 指定结点的后插（有无头结点均适用）
• 3.1.3.1.4 指定结点的前插（有无头结点均适用）

• 3.1.3.2 删除

• 3.1.3.2.1 按位序删除（带头结点）
• 3.1.3.2.2 按位序删除（不带头结点）
• 3.1.3.2.3 指定结点的删除（带头结点）
• 3.1.3.2.4 指定结点的删除（不带头结点）

• 3.1.3.3 查找

• 3.1.3.3.1 按位查找（带头结点）
• 3.1.3.3.2 按位查找（不带头结点）
• 3.1.3.3.3 按值查找（带头结点）
• 3.1.3.3.4 按值查找（不带头结点）

• 3.1.3.4 求表长

• 3.1.3.4.1 求表长（带头结点）
• 3.1.3.4.2 求表长（不带头结点）

• 3.1.3.5 建立单链表

• 3.1.3.5.1 尾插法

• 3.1.3.5.1.1 尾插法（带头结点）
• 3.1.3.5.1.2 尾插法（不带头结点）

• 3.1.3.5.2 头插法

• 3.1.3.5.2.1 头插法（带头结点）
• 3.1.3.5.2.2 头插法（不带头结点）

• 3.1.3.6 单链表逆置

• 3.1.3.6.1 通过新建一个单链表

• 3.1.3.6.1.1 通过新建一个单链表（带头结点）
• 3.1.3.6.1.2 通过新建一个单链表（不带头结点）

• 3.1.3.6.2 我的方法

• 3.1.3.6.2.1 我的方法（带头结点）
• 3.1.3.6.2.2 我的方法（不带头结点）

• 3.1.3.6.3 就地逆置

• 3.1.3.6.3.1 就地逆置（带头结点）
• 3.1.3.6.3.2 就地逆置（不带头结点）

• 3.2 双链表

• 3.2.1 双链表的初始化
• 3.2.2 双链表的判空
• 3.2.3 双链表的插入操作
• 3.2.4 双链表的删除操作

• 3.3 循环链表

• 3.3.1 循环单链表
• 3.3.2 循环双链表

• 3.4 静态链表

• 3.4.1 删除操作

• 3.4.1.1 删除序号为i的结点
• 3.4.1.2 删除值为e的结点
• 3.4.1.3 删除第i个结点

• 4 顺序表vs链表

• 4.1 在各个方面进行比较
• 4.2 实际中选那个更合适
• 4.3 总结

• 5 存储与存取

• 5.1 存取方式

• 5.1.1 随机存取
• 5.1.2 顺序存取

• 5.2 存储结构

• 5.2.1 顺序存储
• 5.2.2 随机存储

---

，博客内容是对自己笔记的书面整理，根据自身学习需要，我可能会增加必要内容。

---

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为L=(a₁,a₂,…,a_i,a_i+1,…,a_n)。

注意以下几点：

（1）线性表中每个数据元素所占空间大小相同；

（2）线性表中的元素是有限的，并且有前后次序；

（3）a_i是线性表中的“第i个”元素，但是线性表中的元素下标从0开始；

（4）a₁是表头元素，a_n是表尾元素;

（5）除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

介绍9种基本操作（创建、销毁、增删改查等），注意若参数前有取地址符号&，则代表的是需要对该参数做出修改：

（1）lnitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

（2）DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

（3）Listlnsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

（4）ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

（5）LocateElem(L,e)：按值查找元素操作。在表L中查找元素e。

（6）GetElem(L,i)：按位置查找元素操作。获取表L中第i个位置的元素的值。

（7）Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

（8）PrintList(L)：输出线性表元素操作。按前后顺序输出线性表L的所有元素值。

（9）Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

---

顺序表：用顺序存储的方式实现线性表。顺序存储指的是把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的逻辑顺序关系由存储单元的邻接关系来体现。

设线性表第一个元素的存放位置是Loc(L)，每个元素大小为k，则有：

讯享网

即第i个元素a_i的存放位置为Loc(L)+(i-1)·k。

下面是C++代码实现顺序表的静态分配：

注意，静态数组一旦分配，大小长度不可变，且会给各个数据元素分配连续的存储空间，静态数组总大小为MaxSize*sizeof(ElemType)。

下面是C++代码实现初始化一个顺序表：

注意，初始化时，必须使L.length=0。

下面是C++代码实现顺序表的动态分配：

在动态分配的顺序表中，可以申请额外的内存空间，也可以释放内存空间，使用的C++函数分别是malloc、free函数。malloc函数返回一个指针，并且必须强制转换为原顺序表中定义的数据元素类型的指针，如下C++代码：

在动态分配的顺序表中，当顺序表存满时，可使用malloc扩展顺序表的容量。在这个过程中，为了使所有数据元素存储位置连续，需要将数据元素复制到新的一整片存储区域，然后使用free释放原区域的内存空间。示例C++代码如下：

上述C++代码输出如下：

顺序表的特点：

（1）随机，一般为读操作。只要知道该单元所在的行和列的地址即可直接访问任一个存储单元。即可以在O(1)时间内找到第i个元素（data[i-1]）；

（2）存储密度高，每个结点只存储数据元素（后面讲到的链式存储还会存储额外的指针）；

（3）拓展容量不方便，即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高；

（4）插入、删除操作不方便，需要移动大量元素；

2.4.1 插入元素操作

本节代码建立在静态分配的顺序表上，而动态分配的顺序表的代码也基本与其一致，C++代码如下：：

好的算法，应该具有“健壮性”。能处理异常情况，并给使用者反馈。在插入元素之前，需要判断输入数据是否合法并给予反馈。

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第9行代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：新元素插入到表尾，则不需要移动元素——即当i=n+1时，语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动——即i=1时，语句循环n次。最坏时间复杂度=O(n)；

（3）平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,2,3,…,n+1的概率都是p=1/(n+1)——当i=1时，循环n次；i=2时，循环n-1次：i=3时，循环n-2次…i=n+1时，循环0次。平均循环次数=np+(n-1)p+(n-2)p+…+p= n/2。平均时间复杂度=O(n/2)=O(n)。

2.4.2 删除元素操作

本节代码也是建立在静态分配的顺序表上，而动态分配的顺序表的代码也基本与其一致。C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：删除表尾元素，不需要移动其他元素——即i=n时，循环0次。最好时间复杂度=O(1)；

（2）最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动——即i=1时，循环n-1次。最坏时间复杂度=O(n)；

（3）平均情况：假设删除任何一个元素的概率相同，即i=1,2,3,…,n的概率都是p=1/n。i=1时，循环n-1次；i=2时，循环n-2次；i=3，循环n-3次….i=n时，循环0次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

2.4.3 查找元素操作

2.4.3.1 按位置查找元素

静态分配和动态分配的顺序表的代码完全一致，如下：

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，这就是顺序表的“随机存取”特性。所以上述代码的时间复杂度为O(1)。

2.4.3.2 按数值查找元素

静态分配和动态分配的顺序表的代码完全一致，如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第3行的if判断代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：目标元素在表头，则需要比较元素1次，该语句循环1次。最好时间复杂度=O(1)；

（2）最坏情况：目标元素在表尾，需要和n个元素进行比较，该语句循环n次。最坏时间复杂度=O(n)；

（3）平均情况：假设目标元素在任何一个位置的概率都相同，即是第1,2,3,…,n个元素的概率都是p=1/n——当是第1个时，循环1次；当是第2个时，循环2次…当是第n个时，循环n次。平均循环次数=np+(n-1)p+(n-2)p+…+p= (n+1)/2。平均时间复杂度=O((n+1)/2)=O(n)。

---

在链表中，每个结点除了存放数据元素外，还要存储指向其他结点（如下一个，或者还包括上一个）的指针。链表包括单链表、双链表、循环链表、静态链表。

1、相比于顺序表，链表存储密度小 ，每个结点由数据域和指针域组成。在相同内存空间中，假设全存满的话，顺序表比链表存储的元素个数更多；

2、逻辑上相邻的结点物理上不必相邻；

3、插入、删除灵活，不必移动结点，只需要改变结点中的指针；

4、查找结点时比顺序表慢。

单链表的局限性——无法逆向检索，对于某些基本操作来说写代码不是很方便。

定义单链表的C++代码如下：

上面代码等价于如下代码：

要声明一个单链表时，只需声明一个头指针L，指向单链表的第一个结点，有两种方式如下：

当强调是一个单链表时，使用LinkList；强调是一个结点时，使用LNode *；

3.1.1 不带头结点的单链表

初始化不带头结点的单链表的C++代码如下：

判断不带头结点的单链表是否为空的C++代码如下：

不带头结点，写代码更麻烦——对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑，而且对空表和非空表的处理需要用不同的代码逻辑。

3.1.2 带头结点的单链表

初始化带头结点的单链表的C++代码如下：

判断带头结点的单链表是否为空的C++代码如下：

带头结点的话，写基本操作的代码时更为方便，继续往下阅读便可以看到这种差别。

3.1.3 单链表的基本操作

3.1.3.1 插入

3.1.3.1.1 按位序插入（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第8行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：插在表头，即i=1时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：插在表尾，即i=n+1时，该语句循环n次。最坏时间复杂度=O(n)；

（3）平均情况：假设插在任何一个位置的概率都相同，即插在第1,2,3,…,n,n+1个位置的概率都是p=1/(n+1)——当是第1个时，循环0次；当是第2个时，循环1次…当是第n个时，循环n-1次，当是第n+1个时，循环n次。平均循环次数=np+(n-1)p+(n-2)p+…+p=n/2。平均时间复杂度=O(n/2)=O(n)。

3.1.3.1.2 按位序插入（不带头结点）

因为不存在“第0个”结点，因此i=1时需要特殊处理。C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第15行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：插在表头，即i=1时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：插在表尾，即i=n+1时，该语句循环n次。最坏时间复杂度=O(n)；

（3）平均情况：假设插在任何一个位置的概率都相同，即插在第1,2,3,…,n,n+1个位置的概率都是p=1/(n+1)——当是第1个时，循环0次；当是第2个时，循环1次…当是第n个时，循环n-1次，当是第n+1个时，循环n次。平均循环次数=np+(n-1)p+(n-2)p+…+p=n/2。平均时间复杂度=O(n/2)=O(n)。

3.1.3.1.3 指定结点的后插（有无头结点均适用）

C++代码如下：

上述代码对有无头结点的单链表均适用，时间复杂度=O(1)。

有了向指定结点的后插的函数，则可以简化【3.1.3.1.1 按位序插入（带头结点）】一节的代码，C++代码如下：

同样地，【3.1.3.1.2 按位序插入（不带头结点）】一节的代码也可以简化，C++代码如下：

将某一特定功能写为一个函数，需要时候调用即可，可以减少主程序的代码量，还可以使阅读代码的同学更多关注于程序逻辑而非代码的具体实现。

3.1.3.1.4 指定结点的前插（有无头结点均适用）

在结点p之前插入元素e，C++代码如下：

上述代码对有无头结点的单链表均适用。但是：① 如果传入的参数p为头指针L时，对于有头结点的单链表会使头结点的数据域变为e，而头结点之后的第一个结点（这个结点是刚刚生成的结点s）的数据域可能变成被某脏数据；② 对于无头结点的单链表则不会发生任何意外情况。时间复杂度=O(1)。

在结点p之前插入结点s，C++代码如下：

上述代码对有无头结点的单链表均适用。但是：① 如果传入的参数p为头指针L时，对于有头结点的单链表会使头结点的数据域变为结点s中的数据，而头结点之后的第一个结点（即结点s）的数据域可能变成被某脏数据；② 对于无头结点的单链表则不会发生任何意外情况。时间复杂度=O(1)。

3.1.3.2 删除

3.1.3.2.1 按位序删除（带头结点）

头结点可以看作第0个结点，找到第i-1个结点，将其指针指向第i+1个结点，井释放第i个结点。C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：即i=1时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：即i=n时，该语句循环n-1次。最坏时间复杂度=O(n-1)=O(n)；

（3）平均情况：假设任何一个位置的概率都相同，即i=1,2,3,…,n的概率都是p=1/n——当是第1个时，循环0次；当是第2个时，循环1次…当是第n个时，循环n-1次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

3.1.3.2.2 按位序删除（不带头结点）

i=1，即删除第一个结点时需要特殊对待，C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第13行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：即i=1时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：即i=n时，该语句循环n-1次。最坏时间复杂度=O(n-1)=O(n)；

（3）平均情况：假设任何一个位置的概率都相同，即i=1,2,3,…,n的概率都是p=1/n——当是第1个时，循环0次；当是第2个时，循环1次…当是第n个时，循环n-1次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

3.1.3.2.3 指定结点的删除（带头结点）

删除头结点（即传入的参数p为头指针L时）和最后一个结点（即p->next=NULL时）需要特殊对待，C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：即p指向除最后一个结点外的任意其他结点时，该语句均循环0次。最好时间复杂度=O(1)；

（2）最坏情况：即p为最后一个结点，即p->next=NULL时，该语句循环n-1次。最坏时间复杂度=O(n-1)=O(n)；

（3）平均情况：假设p指向任意一个结点的概率都相同，即指向头结点、第1,2,3,…,n个结点的概率都是p=1/(n+1)——当是头结点时，循环0次；第1个结点时，循环0次；第2个结点时，循环0次…当是第n-2个结点时，循环0次；当是第n-1个时，循环0次；当是第n个，即最后一个结点时，循环n-1次。平均循环次数=(n-1)p=(n-1)/(n+1)。平均时间复杂度=O((n-1)/(n+1))=O(1)。

3.1.3.2.4 指定结点的删除（不带头结点）

删除第一个结点（即传入的参数p为头指针L时）不需要特殊对待，删除最后一个结点（即p->next=NULL时）需要特殊对待，C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：即p指向除最后一个结点外的任意其他结点时，该语句均循环0次。最好时间复杂度=O(1)；

（2）最坏情况：即p为最后一个结点，即p->next=NULL时，该语句循环n-1次。最坏时间复杂度=O(n-1)=O(n)；

（3）平均情况：假设p指向任意一个结点的概率都相同，即指向第1,2,3,…,n个结点的概率都是p=1/n——当是第1个结点时，循环0次；第2个结点时，循环0次…当是第n-1个时，循环0次；当是第n个，即最后一个结点时，循环n-1次。平均循环次数=(n-1)p=(n-1)/n。平均时间复杂度=O((n-1)/n)=O(1)。

3.1.3.3 查找

3.1.3.3.1 按位查找（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第8行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：即i=0，即查找头结点时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：即i=n时，该语句循环n次。最坏时间复杂度=O(n)；

（3）平均情况：假设任何一个位置的概率都相同，即i=0,1,2,3,…,n的概率都是p=1/(n+1)——当i=0时，循环0次；当i=1时，循环1次…当i=n时，循环n次。平均循环次数=np+(n-1)p+(n-2)p+…+p=n/2。平均时间复杂度=O(n/2)=O(n)。

3.1.3.3.2 按位查找（不带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第8行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：即i=1时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：即i=n时，该语句循环n-1次。最坏时间复杂度=O(n-1)=O(n)；

（3）平均情况：假设任何一个位置的概率都相同，即i=1,2,3,…,n的概率都是p=1/n——当i=1时，循环0次…当i=n时，循环n-1次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

3.1.3.3.3 按值查找（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第4行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：在第一个结点时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：在最后一个结点时，该语句循环n-1次。最坏时间复杂度=O(n-1)=O(n)；

（3）平均情况：假设在任意一个结点的概率都相同，即在第1,2,3,…,n个结点的概率都是p=1/n——当是第1个结点时，循环0次；第2个结点时，循环1次…当是第n-1个时，循环n-2次；当是第n个，即最后一个结点时，循环n-1次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

3.1.3.3.4 按值查找（不带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第4行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系：

（1）最好情况：在第一个结点时，该语句循环0次。最好时间复杂度=O(1)；

（2）最坏情况：在最后一个结点时，该语句循环n-1次。最坏时间复杂度=O(n-1)=O(n)；

（3）平均情况：假设在任意一个结点的概率都相同，即在第1,2,3,…,n个结点的概率都是p=1/n——当是第1个结点时，循环0次；第2个结点时，循环1次…当是第n-1个时，循环n-2次；当是第n个，即最后一个结点时，循环n-1次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

3.1.3.4 求表长

3.1.3.4.1 求表长（带头结点）

C++代码如下：

时间复杂度为O(n)。

3.1.3.4.2 求表长（不带头结点）

C++代码如下：

时间复杂度为O(n)。

3.1.3.5 建立单链表

3.1.3.5.1 尾插法

3.1.3.5.1.1 尾插法（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行的代码）的执行次数与问题规模n的关系，如果建立n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

3.1.3.5.1.2 尾插法（不带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第8行的代码）的执行次数与问题规模n的关系，如果建立n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

3.1.3.5.2 头插法

3.1.3.5.2.1 头插法（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第8行的代码）的执行次数与问题规模n的关系，如果建立n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

3.1.3.5.2.2 头插法（不带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行的代码）的执行次数与问题规模n的关系，如果建立n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

3.1.3.6 单链表逆置

3.1.3.6.1 通过新建一个单链表

3.1.3.6.1.1 通过新建一个单链表（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行的代码）的执行次数与问题规模n的关系，如果原链表是有n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

3.1.3.6.1.2 通过新建一个单链表（不带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第6行的代码）的执行次数与问题规模n的关系，如果原链表是有n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

3.1.3.6.2 我的方法

3.1.3.6.2.1 我的方法（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第6行的代码）的执行次数与问题规模n的关系，如果原链表是有n个结点的单链表，则该语句循环n-1次，即时间复杂度为O(n-1)=O(n)。

3.1.3.6.2.2 我的方法（不带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第6行的代码）的执行次数与问题规模n的关系，如果原链表是有n个结点的单链表，则该语句循环n-1次，即时间复杂度为O(n-1)=O(n)。

3.1.3.6.3 就地逆置

3.1.3.6.3.1 就地逆置（带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第5行的代码）的执行次数与问题规模n的关系，如果原链表是有n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

3.1.3.6.3.2 就地逆置（不带头结点）

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第5行的代码）的执行次数与问题规模n的关系，如果原链表是有n个结点的单链表，则该语句循环n次，即时间复杂度为O(n)。

本博文提到的双链表均带头结点。

双链表的每个结点有两个指针域，分别指向前一个结点和后一个结点。对于单链表，无法逆向检索，有时候不太方便，但是对于双链表，可进可退，与此同时导致双链表的存储密度更低。

定义双链表结点的C++代码如下：

3.2.1 双链表的初始化

初始化双链表的C++代码如下：

3.2.2 双链表的判空

判断双链表是否为空的C++代码如下：

3.2.3 双链表的插入操作

C++代码如下：

时间复杂度为O(1)。

3.2.4 双链表的删除操作

C++代码如下：

时间复杂度为O(1)。

销毁双链表的C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第3行的代码）的执行次数与问题规模n的关系，如果原链表是有n个结点的双链表，则该语句循环n次，即时间复杂度为O(n)。

3.3.1 循环单链表

本博文提到的循环单链表均带头结点。

在单链表中，表尾结点的next指针指向 NULL；而在循环单链表中，表尾结点的next指针指向头结点。

下面是定义单链表结点类型的C++代码：

初始化循环单链表的C++代码如下：

循环单链表判空的C++代码如下：

判断节点p是否为循环单链表的表尾结点的C++代码如下：

对于普通的单链表，从一个结点出发只能找到后续的各个结点；而对于循环单链表，从任意一个结点出发都可以找到其他的所有结点。

3.3.2 循环双链表

本博文提到的循环双链表均带头结点。

在双链表中，表头结点的prior指向NULL，表尾结点的next指向NULL；而在循环双链表中，表头结点的prior指向表尾结点，表尾结点的next指向头结点。

下面是定义双链表结点类型的C++代码：

初始化循环双链表的C++代码如下：

循环双链表判空的C++代码如下：

判断节点p是否为循环双链表的表尾结点的C++代码如下：

在结点p之后插入结点s的C++代码如下：

删除p的后继结点的C++代码如下：

静态链表是用数组的方式实现的链表。在静态链表中，指针变成了游标，即下个结点的数组下标；下标为-1表示为表尾元素；0号结点充当头结点。优点：增、删操作不需要大量移动元素。缺点：不能随机访问，只能从头结点开始依次往后查找。

在静态链表中，计算机会分配一整片连续的内存空间，各个结点集中安置。下图为静态链表的一个示例：

定义静态链表结点的C++代码如下：

上述定义静态链表结点的代码与下面的C++代码等价：

初始化静态链表的C++代码如下：

判断静态链表是否为空的C++代码如下：

3.4.1 删除操作

3.4.1.1 删除序号为i的结点

删除序号为i的结点，即静态数组的第i个结点，与表示的线性表中结点的先后顺序无关。

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第8行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系。直接看平均情况：假设【序号为i的结点的前驱】在任意一个结点的概率都相同，即在头结点、第1,2,3,…,n个结点的概率都是p=1/(n+1)——当是头结点时，循环1次；当是第1个结点时，循环2次；第2个结点时，循环3次…当是第n-1个时，循环n次；当是第n个，即最后一个结点时，循环n+1次。平均循环次数=(n+1)p+np+(n-1)p+(n-2)p+…+p=(n+2)/2。平均时间复杂度=O((n+2)/2)=O(n)。

3.4.1.2 删除值为e的结点

C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第6行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系。直接看平均情况：假设在任意一个结点的概率都相同，即第1,2,3,…,n个结点的数据域为e概率都是p=1/n——当第1个结点的数据域为e时，循环0次；第2个结点的数据域为e时，循环1次…当第n-1个结点的数据域为e时，循环n-2次；当第n个结点的数据域为e，即最后一个结点时，循环n-1次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

3.4.1.3 删除第i个结点

与【3.4.1.1 删除序号为i的结点】一节不同，本节删除的是线性表的第i个结点，这个i值与表示的线性表中结点的先后顺序有关。C++代码如下：

下面分析上述代码的时间复杂度，还是只需要关注最深层循环语句（第7行的代码）的执行次数与问题规模n（这里n=L.length，即表长）的关系。直接看平均情况：假设删除任意一个结点的概率都相同，即在第1,2,3,…,n个结点的概率都是p=1/n——当是第1个结点时，循环0次；第2个结点时，循环1次…当是第n-1个时，循环n-2次；当是第n个，即最后一个结点时，循环n-1次。平均循环次数=(n-1)p+(n-2)p+…+p=(n-1)/2。平均时间复杂度=O((n-1)/2)=O(n)。

下面是我思考的第二个版本，实现的功能还是删除第i个结点：

自己编程能力还是很弱，在测试函数时没有发现主程序数据有问题，还是一味地看着函数，看了很长很长时间，确实没什么问题，但是运行结果就是不正确，后来写了第二个版本也就是本节第一个版本时回来再看，才发现是数据的问题，自己写的函数是正确的，该死！

---

1、存取方式：顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问i次。

2、逻辑结构与物理结构：采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置则不一定相邻，对应的逻辑关系是通过指针链接来表示的。

3、查找、插入和删除操作：对于按值查找，顺序表无序时，两者的时间复杂度均为O(a)；对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

4、空间分配：顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。但是预先分配过大，可能会导致顺序表后部大量闲置，而预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

1、基于存储的考虑：难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的。

2、基于运算的考虑：在顺序表中按序号访问第i个元素的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)，因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。在顺序表中进行插入、删除操作时，平均会移动表中一半的元素，当数据元素较大且表较长时，这一点是不应忽视的；在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。

3、基于环境的考虑：顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素。

两种存储结构各有长短，选择哪一种由实际问题的主要因素决定：

1、表长难以预估，经常要增加、删除元素一一链表；

2、表长可预估，查询、搜索操作较多——顺序表。

---

存取方式分为随机存取和非随机存取（也称顺序存取）。

随机存取指存取时间与存储单元的物理位置无关，存取分别指写入与读出操作，可以在相同时间访问一组序列中的任一个元素。即存取第N个数据时，不需要访问前N-1个数据，直接就可以对第N个数据操作。数组就是随机存取。

非随机存取就是顺序存取，只能按照存储顺序存取，与存储位置有关，例如链表。顺序存取就是存取第N个数据时，必须先访问前N-1个数据。

存储结构分为顺序存储结构和随机存储结构。

用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助数组来描述的。顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用于存放结点的数据。可实现任意元素的随机访问，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。

用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。不要求逻辑上相邻的元素在物理位置上也相邻，因此失去了可随机存取的优点。随机存储代表为链式存储。

---

END