2.3.3 双链表
单链表：单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历,无法逆向检索，有时候不太方便
双链表的定义：双链表结点中有两个指针prior和next，分别指向其直接前驱和直接后继
表头结点的prior域和尾结点的next域都是NULL。
双链表结点类型描述如下：
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior, *next; //前驱和后继指针
} DNode, *DLinklist;双链表在单链表结点中增加了一个指向其前驱的指针 prior
双链表的初始化 (带头结点)：
typedef struct DNode{ //D表示double
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;
}
void testDLinkList(){
DLinklist L; //L是一个链表 初始化双链表
InitDLinkList(L);
...
}
// 判断双链表是否为空
bool Empty(DLinklist L){
if(L->next == NULL)
return true;
else
return false;
}
双链表的插入操作：
typedef struct DNode{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinklist;
bool InsertNextDNode(DNode *p, DNode *s){
if(p==NULL || s==NULL)
return false;
s->next = p->next; // 将结点s插入到结点p之后
if (p->next != NULL) // 判断结点p之后是否有后继结点
p->next->prior = s; //p结点的后置结点的前向指针指向新插入的s
s->prior = p; //把s的前向指针指向p结点
p->next = s; //把p结点的后向指针指向s结点
return true;
}
双链表的删除操作：
// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){
if(p==NULL)
return false;
DNode *q =p->next; // 找到p的后继结点q
if(q==NULL) //p没有后继就返回false
return false;
p->next = q->next; //q结点不是最后一个结点
if(q->next != NULL)
q->next->prior=p;
free(q); //释放结点空间
return true;
}
// 销毁一个双链表
bool DestoryList(DLinklist &L){
// 循环释放各个数据结点
while(L->next != NULL){
DeletNextDNode(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 循环链表
循环单链表
循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环
在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针L。
循环单链表的实现：
typedef struct LNode{ //定义单链表结点类型
ElemType data;
struct LNode *next; //指针指向下一个元素
}DNode, *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) //看p结点的下一个结点是否是头结点
return true;
else
return false;
}
单链表:从一个结点出发只能找到后续的各个结点
循环单链表:从一个结点出发可以找到其他任何一个结点
循环双链表
循环双链表的初始化
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指针指向头结点
}
void testDLinkList(){
//初始化循环双链表
DLinkList L;
InitDLinkList(L);
//...
}
// 判断循环双链表是否为空
bool Empty(DLinklist L){
if(L->next == L)
return true;
else
return false;
}
// 判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){
if(p->next == L) //结点的next指针指向头结点
return true;
else
return false;
}
循环双链表的插入
// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){
s->next = p->next;
//循环双链表不用担心p结点的下一个结点为空
p->next->prior = s;
s->prior = p;
p->next = s;
}循环双链表的删除
// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){
// 找到p的后继结点q
DNode *q =p->next;
//循环双链表不用担心q结点的下一个结点为空
p->next = q->next;
q->next->prior=p;
free(q);
return true;
}
2.3.5 静态链表
静态链表：用数组的方式实现的链表
优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不可变
适用场景：
①不支持指针的低级语言；
②数据元素数量固定不变的场景(如操作系统的文件分配表FAT）
静态链表是用数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点在数组中的相对地址(数组下标)，又称游标。
静态链表的定义
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标 即游标
};
// 用数组定义多个连续存放的结点
void testSLinkList(){
struct Node a[MaxSize]; //数组a作为静态链表, 每一个数组元素的类型都是struct Node
...
}
王道书上是这么定义的，侧重于强调 a 是一个静态链表而非数组。
#define MaxSize 10 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ELemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
void testSLinkList(){
SLinkList a;
}
静态链表基本操作实现
初始化静态链表:
把a[0]的next 设为-1
把其他结点的next 设为一个特殊值用来表示结点空闲，如-2
查找结点：
从头结点出发挨个往后遍历结点
插入位序为 i 的结点：
①找到一个空的结点，存入数据元素
②从头结点出发找到位序为 i-1 的结点
③修改新结点的 next
④修改 i-1 号结点的 next
删除某个结点：
①从头结点出发找到前驱结点
②修改前驱结点的游标
③被删除结点 next 设为 -2