【数据结构】双链表和循环链表的相关操作--创建-插入-删除-查找
程序员文章站
2022-03-22 19:52:39
...
双链表与循环链表
双链表
单链表 VS 双链表
- 单链表:无法逆向检索,有时候不太方便
- 双链表:可进可退,存储密度更低一点
- 总结:单链表结点中,只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。为了克服单链表此缺点,引入了双链表,双链表结点两个指针分别指向其前驱结点和后继结点。
双链表的初始化(带头结点)
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;
}
}
双链表的插入
- 因为双链表在单链表的基础上,为结点增加了前驱结点指针,故在进行插入操作时,也要根据链的变化对前驱结点指针进行修改,关键是保证在修改的过程中不断链。
//双链表的插入操作
//在p结点之后插入s结点
bool InsertNextDNode (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;
}
- 前插操作:由于双链表的结点有两个指针,分别指向该结点的前驱结点和后继结点,故要进行前插操作时,只需找到其前驱结点,并对其前驱结点实施后插操作,即可达到对结点的前插操作。
双链表的删除
//双链表的删除
//删除p结点的后继结点
bool DeleteNextDNode (DNode *p) {
if (p == NULL) {
return false;
}
DNode *q = p -> next; //找到p的后继结点q
if (q == NULL) {
return false; //p没有后继结点
}
p -> next = q -> next;
if (q -> next != NULL) { //q结点不是最后一个结点
q -> next -> prior = p;
}
free(q); //释放结点空间
return true;
}
//销毁一个双链表
void Destory (DLinklist &L) {
//循环释放各个数据结点
while (L -> next != NULL) {
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;
}
循环链表
循环单链表
- 循环单链表:将单链表尾结点的next指针指向NULL改为指向单链表的头结点
- 从一个结点出发可以找到其他任何一个结点
typedef struct LNode { //定义单链表结点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
}LNode,*LinkList; //强调为结点和强调为单链表
//初始化一个空的循环单链表
bool InitLink(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;
}
}
循环双链表
- 将双链表表尾结点的next指向头结点,将头结点的prior指向表尾结点,形成了循环
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;
}
}
静态链表
静态链表的创建
- 静态链表借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,与之前的链表指针不同的是,今天链表的指针是结点的相对地址(数组下标),又称作游标。和顺序表一样,静态链表也要预先分配一块连续的内存空间。
#define MaxSize 50 //静态链表的最大长度
typedef struct { //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList [MaxSize];
#define MaxSize 50 //静态链表的最大长度
struct Node { //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
};
typedef struct Node SLinkList [MaxSize];
推荐阅读
-
[PHP] 数据结构-链表创建-插入-删除-查找的PHP实现
-
[PHP] 数据结构-链表创建-插入-删除-查找的PHP实现
-
数据结构c(单链表的创建以及插入删除等操作)
-
数据结构(C语言):双向链表的创建、插入、修改、删除、查找、修改等操作
-
数据结构——链表单向链表的创建插入删除遍历操作(C++实现)
-
【数据结构】双链表和循环链表的相关操作--创建-插入-删除-查找
-
数据结构(c语言版)---- 双向循环链表的创建、插入、删除、遍历等基本操作
-
(C语言、数据结构)双向链表---双向链表的初始化、尾插法的建立、插入、删除、遍历等相关操作的实现
-
数据结构基础--单链表的基本操作(创建,插入,删除和查找)C++
-
数据结构(C语言):单链表的创建、插入、修改、删除、查找、修改等操作