双链表、循环链表和静态链表
双链表
（对比单链表）
单链表：无法逆向检索，有时不太方便
双链表：可进可退，但存储密度低一些
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; //头结点的前驱结点永远为空
L->next = NULL; //头结点的后继结点暂时为空
return true;
}
bool Empty(DLinklist L){
return L->next == NULL; //判断是否为空只需要判断头结点是否有后继结点
}
void testDLinkList(){
//初始化双链表
DLinklist L;
InitDLinkList(L);
//后续代码……
}
双链表的插入
后插操作：
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
s->next = p->next;
s->prior = p;
p->next->prior = s;
p->next = s;
}
存在问题：如果p结点为表尾结点 由于 p->next = NULL 在执行代码 p->next->prior = p时会出现错误
代码优化
bool InsertDNode(DNode *p,DNode *s){
if(p == NULL||s == NULL) return false;
s->next = p->next;
if(p->next != NULL){ //保证在p结点有后继结点的情况下
p->next->prior = s;
}
s->prior = p;
p->next = s;
return true;
}
[!NOTE]
一定要注意指针修改顺序 防止错误修改导致后续结点的丢失
前插操作：
找到给定结点的前驱节点 然后再该结点之后进行插入操作
双链表的删除
//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);
同样存在问题：如果q为最后一个结点
代码优化：
bool DeleteNextDNode(DNode *p){
if(p == NULL) return false;
DNode *q = p->next;
if(q == NULL) return false;
p->next = q->next;
if(q->next != NULL){ //q结点不是最后一个结点
q->next->prior = p;
}
free(q); //释放结点空间
return true;
}
销毁双链表
void DestoryList(DLinklist &L){
//循环释放各个数据结点
while(L->next != NULL){
DeleteNextDNode(L);
}
free(L); //释放头结点
L = NULL; //头指针指向NULL
}
双链表的遍历
//后向遍历
while(p != NULL){
p = p->next;
}
//前向遍历
while(p != NULL){
p = p->prior;
}
//前向遍历（跳过头结点）
while(p->prior != NULL){
p = p->prior;
}
双链表不可随机存取，按位查找、按值查找操作都只能能用遍历的方式实现 时间复杂度O（n）
循环链表
循环单链表
与普通单链表的区别：表尾结点的next指针指向表头结点
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//初始化
bool InitList(LinkList &L){
L = (LNode*)malloc(sizeof(LNode)); //分配一个头节点
if(L==NULL) retutn false; //内存不足 分配失败
L->next = L; //头结点next指针指向头节点
return true;
}
//判断链表是否为空
bool Empty(LinkList L){
return L->next == L;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
return p->next==L;
}
void test(){
LinkList L: //声明一个指向单链表的空指针
//初始化一个空表
InitList(L);
//后续代码……
}
对链表的操作大多都是在表头结点或表尾结点
普通单链表找到尾部的时间复杂度为O（n）
而循环单链表如果让链表指针L直接指向表尾结点 则找到表尾结点的时间复杂度为O（1） 同时因为表尾结点的next指针指向头结点 所以找到表头结点的时间复杂度也为O（1）
所以在经常在表头和表尾进行操作时 可以使用循环单链表并让L指向表尾结点
循环双链表
与普通双链表的区别：表头结点的prior指针指向表尾结点 表尾结点的next指针指向表头结点
//初始化双链表
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){
return L->next == L; //判断是否为空只需要判断头结点的后继指针是否指向自己
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(LinkList L,LNode *p){
return p->next==L;
}
void testDLinkList(){
//初始化双链表
DLinklist L;
InitDLinkList(L);
//后续代码……
}
在插入、删除时，因为循环双链表的表尾指针不为空，所以不需要对表尾结点进行单独处理，即不需要考虑先前普通双链表实现后插操作时存在的问题（下图）
静态链表
静态链表–定义
分配一整片连续的内存空间，各个节点集中安置
数据元素+游标 其中游标充当指针使用 数据元素与游标一一映射
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
};
void testSLinkList(){
struct Node a[MaxSize]; //数组a作为静态链表
//……后续代码
}
另一种定义方式：
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize]; //这段代码与下面注释行代码等价 声明后 可使用SLinkList定义“一个长度为MaxSize的Node型数组”
//typedef struct Node SLinkList[MaxSize];
void testSLinkList(){
SLinkList a;
//……后续代码
}
[!CAUTION]
为什么要使用第二种方式进行定义？
为了凸显出a是一个静态链表 防止a被误认为是一个Node型的数组
静态链表的基本操作
初始化：
把a[0]的next设为-1 （-1等价于NULL）
查找：
从头结点出发依次遍历 找到第i个结点 （时间复杂度O（n））
插入位序为i的结点：
①找到一个空结点 存入数据元素 （问题：如何能找到空结点–在初始化时 将结点的next都初始化为-2）
②从头结点出发找到位序为i-1的结点
③修改新结点的next
④修改第i-1个结点的next
删除某个结点：
①从头结点出发找到该结点的前驱结点
②修改前驱结点的next
③被删除节点的next设为-2
静态链表的优缺点
优点：
增、删操作不需要大量移动元素
缺点：
不能随机存取，只能能从头结点开始依次向后查找；容量固定不可变
适用场景：
①不支持指针的低级语言②数据元素固定不变的场景（如操作系统的文件分配表FAT）
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
