2.3.3 双链表
第二章单链表中学到：
单链表：无法逆向检索，有时候不太方便；
双链表：双向链表，可进可退，存储密度更低；
存储密度 = （结点数据本身所占的存储量）/（结点结构所占的存储总量）
计算结构体大小时需要考虑其内存布局，结构体在内存中存放是按单元存放的，每个单元多大取决于结构体中最大基本类型的大小。
一、双链表的定义
// 双向链表定义
typedef struct DNode{ // 定义双链表结点类型
ElemType data; // 数据域
struct DNode *prior, *next; // 前驱和后继指针
}DNode, *DLinklist; 二、双链表的初始化（带头结点）
#include <iostream>
using namespace std;
typedef int ElemType; // 数据域元素为int型
// 双向链表定义
typedef struct DNode{ // 定义双链表结点类型
ElemType data; // 数据域
struct DNode *prior, *next; // 前驱和后继指针
}DNode, *DLinklist;
// 初始化双链表
bool InitDLinkList(DLinklist &L){
L = (DNode *)malloc(sizeof(DNode)); // 分配一个头结点
if(L == NULL){ // 内存不足，分配失败
return false;
}
L->prior = NULL; // 头结点的prior永远指向NULL
L->next = NULL; // 头结点之后暂时还没有结点
return true;
}
// 判断双链表是否为空（带头结点）
bool Empty(DLinklist L){
if(L->next == NULL){
return true;
}else{
return false;
}
}
int main(){
// 定义并初始化一个双向链表
DLinklist L;
InitDLinkList(L);
return 0;
}
初始化双向链表传参时使用的是 DLinklist &L 想强调的是，这里引用了一个双向链表；分配头结点时使用 DNode * 想强调的是 malloc 出了一个结点；
DLinklist 与 DNode * 是等价的。
三、双链表的插入
// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
s->next = p->next; // 为新结点s的后继指针赋值
p->next->prior = s; // 为p后的旧结点的前驱赋指针值
s->prior = p; // 为新结点s的前驱指针赋值
p->next = s; // 为p后继指针赋值
}
如果p恰好是最后一个结点，就不用再做第二步 p->next->prior = s;? // 为p后的旧结点的前驱赋指针值 了，所以为了更加严谨，单独做一个判断，判断p结点是否为最后一个结点。
// 在p结点之后插入s结点(增加对p结点为最后一个结点的判断)
bool InsertNextDNode(DNode *p, DNode *s){
if(P == NULL || s == NULL){ // 非法参数
return false;
}
s->next = p->next; // 为新结点s的后继指针赋值
if(p->next != NULL){ // 如果p结点有后续结点
p->next->prior = s; // 为p后的旧结点的前驱指针赋值
}
s->prior = p; // 为新结点s的前驱指针赋值
p->next = s; // 为p后继指针赋值
return true;
}
在p结点之后插入s结点新结点称为后插操作；想要完成按位序插入前插操作，则需找到p的前驱结点，做p前驱结点的后插操作。
四、双链表的删除与销毁
// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
if(p == NULL){ // 非法参数
return false;
}
DNode *q = p->next; // 找到p的后继结点q
if(q == NULL){ // q没有后继结点
return false;
}
if(q->next != NULL){ // q结点不是最后一个结点
q->next->prior = p; // 将p赋值给q的后继结点的前驱指针域
}
free(q); // 释放结点空间
return true;
}
// 销毁双链表
void DestoryList(DLinklist &L){
// 循环释放各个数据结点
while(L->next != NULL){ // 从L第二个结点开始删除，然后第三个、第四个......一直到最后一个结点
DeleteNextDNode(L);
}
free(L); // 释放头结点
L = NULL; // 头指针指向NULL
}
五、双向链表的后向、前向遍历
// 后向遍历
while(p != NULL){
// 对每个p结点做处理
p = p->next;
}
// 前向遍历
while(p != NULL){
// 对每个p结点做处理
p = p->prior;
}
// 前向遍历（跳过头结点）
while(p->prior != NULL){
// 对每个p结点做处理
p = p->prior;
}
双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方法实现。时间复杂度为O(n)。
2.3.4 循环链表
一、循环单链表的定义、初始化、判空、判表尾结点
循环单链表：最后一个结点的指针域指向头结点；
单链表从一个结点出发只能找到后续的各个结点；循环单链表从一个结点出发，可以找到其它任何一个结点。
typedef int ElemType; // 结构体中的数据域为Int型变量
// 循环单链表定义
typedef struct LNode{ // 定义单链表结点类型
ElemType data; // 每个结点存放一个数据元素
struct LNode *next; // 指针指向下一个结点
}LNode, *LinkList;
// 初始化一个循环单链表
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode)); // 分配一个头结点
if(L == NULL){ // 内存不足，分配失败
return false;
}
L->next = L; // 头结点next指向头结点
return true;
}
// 判断循环单链表是否为空
bool Empty(LinkList L){
if(L->next == L){
return true;
}else{
return false;
}
}
// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){
if(p->next == L){
return true;
}else{
return false;
}
}
二、循环双链表定义、初始化、判空
typedef int ElemType; // 结构体中数据类型为int型
// 循环双链表定义
typedef struct DNode{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinklist;
// 初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
L = (DNode *)malloc(sizeof(DNode)); // 分配一个头结点
if(L == NULL){ // 内存不足，分配失败
return false;
}
L->prior = L; // 头结点的前驱指针域prior指向头结点
L->next = L; // 头结点的next指向头结点
return true;
}
// 判断循环双链表是否为空
bool Empty(DLinklist L){
if(L->next == L){
return true;
}else{
return false;
}
}
三、循环双链表的插入
// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
}
四、循环双链表删除
// 删除p结点的后继结点q
bool DeleteNextDNode(DNode *p, DNode *q){
p->next = q->next;
q->next->prior = p;
free(p);
}
2.3.5 静态链表
一、什么是静态链表
单链表：各个结点在内存中分散；
静态链表：用数组的方式实现的链表，分配一整片连续的内存空间，各个结点集中安置；0 号结点充当头结点，游标（数组下标）充当指针，游标 -1 表示已经到达表尾。
设每个数据元素4B，每个游标4B，则每个结点共8B；设起始地址（头结点之前的地址）为addr，结点e1的存放地址则为 addr+8*2。
优点：增、删操作不需要大量移动元素；
缺点：不能随机存取，只能从头结点开始依次向后查找；容量固定不可变；
适用场景：
① 不支持指针的低级语言；
② 数据元素数量固定不变的场景（如操作系统的文件分配表FAT）；
二、静态链表的定义
#define MaxSize 10 // 静态链表的最大长度
struct Node{ // 静态链表结构类型的定义
ElemType data; // 存储数据元素
int next; // 下一个元素的下标
};
void testSLinkList(){
// 定义一个静态链表
struct Node a[MaxSize]; // 数组a作为静态链表
}
上述代码加上一句定义语句：
// 用LinkList定义“一个长度为MaxSize的Node型数组”,加上这一句就等于书中代码
typedef struct Node SLinkList[MaxSize]; 就等价于书中的代码：
#define MaxSize 10 // 静态链表的最大长度
// 书中定义静态链表的方法
typedef struct{
ElemType data; // 静态链表结构类型的定义
int next; // 存储数据元素
}SLinkList[MaxSize]; // 下一个元素的数组下标
// --------------------------------------------------------
void testSLinkList(){
// 定义一个链表，书中写法
SLinkList a;
}
第一种方法struct Node a[MaxSize]; 的定义方法从代码角度看起来像一个Node型数组，而书上写的SLinkList a; 这种写法更像是一个静态链表；
这两种方法生成的结构体数组的大小是一样的。
三、静态链表的基本操作
初始化静态链表：把a[0]的next设为-1；
查找：从头结点出发挨个往后遍历结点；时间复杂度O(n)
插入位序为i的结点：
① 扫描链表，找到一个空的结点，存入数据元素；
② 从头结点出发找到位序为i-1的结点；
③ 将位序为i-1的结点的游标值赋给新结点；
④ 修改i-1号结点的next；
那么在第一步中如何判断结点为空呢？
解决方法是可让next为某个特殊值，如-2，这一步可以在初始化的时候设置。
2.3.6 顺序表和链表比较
一、逻辑结构方面的比较
都属于线性表，都是线性结构。
二、存储结构方面的比较
顺序表：
优点：支持随机存取，存储密度高；
缺点：大片连续空间分配不方便，改变容量不方便；
链表：
优点：离散的小空间分配方便，改变容量方便；
缺点：不可随机存取，存储密度低；
三、基本操作
复习回忆思路：创销、增删改查；
创建：
顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便扩展容量；若分配空间过大，则浪费内存资源；
顺序表的实现方式有两种：
静态分配：静态数组；（容量不可改变）
动态分配：动态数组（malloc、free）；容量可改变，但需要移动大量元素，时间代价高；
链表：只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展；
销毁：
顺序表：修改lenth=0；
静态分配：静态数组，系统自动回收空间；
动态分配：动态数组（malloc、free），需要手动free；
链表：依次删除各个结点（free）;
插入、删除：
顺序表：插入、删除元素要将后续元素都后移、前移，时间复杂度O(n)，时间开销主要来自移动元素；
链表：插入、删除元素只需修改指针即可，时间复杂度O(n)，时间开销主要来自查找目标元素；
虽然他们的时间复杂度一样，但是他们的操作并不一样，若数据元素很大，则顺序表中移动的时间代价很高，而链表中查找元素的时间代价更低。
查找：
顺序表：随机存储，按位查找时间复杂度O(1)；按值查找时间复杂度O(n)，若表内元素有序，可在O(log2n)时间内找到（比如折半查找算法）；
链表：按位查找时间复杂度O(n)；按值查找时间复杂度O(n)；
四、什么时候用顺序表或者链表？
表长难以预估，经常要增加、删除元素——链表；
表长可预估，查询（搜索）操作较多——顺序表；
开放式问题的答题思路：
?