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)；

四、什么时候用顺序表或者链表？

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

表长可预估，查询（搜索）操作较多——顺序表；

开放式问题的答题思路：