当前位置：首页 > news >正文

【数据结构】_C语言实现带头双向循环链表

news 来源：原创 2025/5/21 10:36:32

1. 单链表与双链表

1.1 单链表的结构及结点属性

1.2 双链表的结构及结点属性

2. 单链表与双链表的区别

3. 双链表的实现

3.1 List.h

3.2 List.c

3.3 Test_List.c

注：部分方法的实现细节注释

1. 双链表结点前驱、后继指针域的初始化

2. 各种增、删结点的方法的一级、二级指针传参

3. 增结点与删结点的判空操作

4. 关于初始化方法Init的不同实现形式

5. 关于删除pos结点Erase操作的接口一致性问题

关于链表的C语言相关实现，已经介绍了不带头单向不循环链表（简称单链表），原文如下：

【数据结构】_C语言实现不带头非循环单向链表-CSDN博客

本文介绍带头双向循环链表（简称双链表）。

1. 单链表与双链表

1.1 单链表的结构及结点属性

对于单链表，每一个结构体结点有数据域data及后继指针域next：

typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;

1.2 双链表的结构及结点属性

对于双链表，每一个结构体结点有数据域data、前驱指针prev、后继指针next；

typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;

2. 单链表与双链表的区别

1、区别 “ 头结点 ” 与 “ 第一个结点 ” ：

① 头结点是不存储有效数据的哨兵位，哨兵位结点不能被删除，结点的地址也不能改变；

② 第一个结点是不计入头结点的、存储有效数据的第一个结点。

单链表中对于第一个结点称为头结点，实际上是不严谨的。

2、区别单双链表的 “ 空链表 ” ：

① 单链表为空：链表无结点，若定义链表的第一个结点为phead，则phead=NULL；

② 双链表为空：链表仅剩一个头结点，若定义链表的头结点为phead，则phead->next=NULL；

对于双链表，任何插入删除的方法的实现都基于该链表已经被初始化生成一个头结点，若某一双向链表的头结点phead=NULL，则这不是一个有效的双链表。

3. 双链表的实现

3.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 定义结点
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;
// 方法
// 初始化
void LTInit(LTNode** pphead);
LTNode* CreateLTNode(LTDataType x);
void LTPrint(LTNode* phead);
// 头尾插、头尾删
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
// 在pos结点后插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos结点
void LTErase(LTNode* pos);
// 查找数据域为x的结点的指针
LTNode* LTFind(LTNode* phead,LTDataType x);

3.2 List.c

#include "List.h"
LTNode* CreateLTNode(LTDataType x) {LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL) {perror("malloc failed");exit(1);}newNode->data = x;newNode->next = newNode->prev = newNode;return newNode;
}
void LTInit(LTNode** pphead) {// 双链表的初始化即创建头结点*pphead = CreateLTNode(-1);
}
//LTNode* LTInit() {
//	LTNode* phead = CreateLTNode(-1);
//	return phead;
//}
void LTPrint(LTNode* phead) {assert(phead);LTNode* curNode = phead->next;while (curNode!= phead) {printf("%d -> ",curNode->data);curNode = curNode->next;}printf("\n");
}
// 头尾插、头尾删
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newNode = CreateLTNode(x);LTNode* tailNode=phead->prev;tailNode->next = newNode;newNode->prev = tailNode;newNode->next = phead;phead->prev = newNode;
}
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newNode = CreateLTNode(x);LTNode* firstNode = phead->next;phead->next = newNode;newNode->prev = phead;newNode->next = firstNode;firstNode->prev = newNode;
}
void LTPopBack(LTNode* phead) {assert(phead && phead->next!=phead);LTNode* tailNode = phead->prev;LTNode* prevTailNode = tailNode->prev;prevTailNode->next = phead;phead->prev = prevTailNode;free(tailNode);tailNode = NULL;
}
void LTPopFront(LTNode* phead) {assert(phead && phead->next!=phead);LTNode* firstNode = phead->next;LTNode* secNode = firstNode->next;phead->next = secNode;secNode->prev = phead;free(firstNode);firstNode= NULL;
}
// 在pos结点后插入
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newNode = CreateLTNode(x);LTNode* nextPosNode = pos->next;pos->next = newNode;newNode->prev = pos;newNode->next = nextPosNode;nextPosNode->prev = newNode;
}
// 删除pos结点
void LTErase(LTNode* pos) {assert(pos);LTNode* prePosNode = pos->prev;LTNode* nextPosNode = pos->next;prePosNode->next = nextPosNode;nextPosNode->prev = prePosNode;free(pos);pos = NULL;
}
// 查找数据域为x的结点的指针
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead && phead->next != phead);LTNode* curNode = phead->next;while (curNode != phead) {if (curNode->data == x) {return curNode;}curNode = curNode->next;}return NULL;
}
// 销毁
void LTDestory(LTNode* phead) {assert(phead);LTNode* curNode = phead->next;LTNode* nextCurNode = curNode->next;while (curNode != phead) {free(curNode);curNode = nextCurNode;nextCurNode = nextCurNode->next;}// 释放头结点free(phead);phead = NULL;
}

3.3 Test_List.c

#include"List.h"
void Test06() {LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTNode* aimNode= LTFind(plist, 3);LTInsert(aimNode, 85);LTPrint(plist);LTNode* delNode = LTFind(plist, 4);LTErase(delNode);// Erase方法将形参pos置为NULL，而并未改变实参delNode，// 故需在调用Erase后再将delNode置空，防止delNode为野指针delNode = NULL;LTPrint(plist);// 同Erase方法的理解，需手动将plist置为NULL；LTDestory(plist);plist = NULL;
}
void Test05() {LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* result1 = LTFind(plist, 3);LTNode* result2 = LTFind(plist,6);if (result2 == NULL) {printf("find nothing\n");}else {printf("find successfully\n");}
}
void Test04() {LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);
}
void Test03() {LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);
}
void Test02() {LTNode* plist = NULL;LTInit(&plist);LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);
}
void Test01() {LTNode* plist = NULL;LTInit(&plist);//LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);
}
int main() {//Test01();//Test02();//Test03();//Test04();//Test05();Test06();return 0;
}

注：部分方法的实现细节注释

1. 双链表结点前驱、后继指针域的初始化

对于初始化方法，不可将next与prev初始置为NULL，双链表初始化即创建头结点，当链表仅有头结点一个结点时，令其next和prev都指向自身：

2. 各种增、删结点的方法的一级、二级指针传参

关于一二级指针传参，在单链表部分已经进行详细介绍，详见下文：

【数据结构】_以SLTPushBack(尾插)为例理解单链表的二级指针传参-CSDN博客文章浏览阅读691次，点赞24次，收藏9次。但对于部分方法如尾插、头插、任意位置前插入、任意位置前删除的相关实现，其形参均采用了二级结构体指针类型。本文以尾插为例，分析单链表的二级指针传参方法的实现逻辑。https://blog.csdn.net/m0_63299495/article/details/145343619https://blog.csdn.net/m0_63299495/article/details/145343619https://blog.csdn.net/m0_63299495/article/details/145343619https://blog.csdn.net/m0_63299495/article/details/145343619对于双链表，由于设有头结点，头结点不能被删除，结点的地址也不能改变，故而：

（1）对于初始化方法，双链表的初始化就是创建头结点，必然会改变当前链表的头结点，故而需要传二级指针；

（2）对于其他增、删结点的方法，如尾插、尾删、头插、头删、任意位置后插入与删除，任意位置前插入与删除，都不会造成链表头结点的改变，故而只需传一级指针即可。

3. 增结点与删结点的判空操作

1、对于增结点的操作如尾插、尾删等，只需保证双向链表必须是一个有效的双向链表，即该双向链表至少存在一个头结点即可，即只需保证phead != NULL，断言如下：

assert(phead);

2、对于删结点的操作如尾删、头删等，除保证双线链表有效(存在一个头结点)外，还需要保证链表中存在可删除的非头结点的其他结点(头结点不可删除)，即需满足phead != NULL和phead->next != phead两个条件，断言如下：

assert(phead && phead->next!=phead);

3、对于删除pos结点的Erase方法，由2可知需保证phead不为空，但其参数并无pphead，故无需校验pphead；

4. 关于初始化方法Init的不同实现形式

（1）实现方式1：返回值为空，参数为二级指针：

在3.2部分已经实现的初始化方法如下：

void LTInit(LTNode** pphead) {// 双链表的初始化即创建头结点*pphead = CreateLTNode(-1);
}

调用时，需将二级结构体指针作为参数调用LTInit函数，且无需接收返回值：

void Test01() {LTNode* plist = NULL;LTInit(&plist);
}
int main() {Test01();return 0;
}

（2）实现方式2：返回值为结构体指针，参数为空：

LTNode* LTInit() {LTNode* phead = CreateLTNode(-1);return phead;
}

调用时，使用结构体指针接收返回值：

void Test01() {LTNode* plist = LTInit();
}
int main() {Test01();return 0;
}

5. 关于删除pos结点Erase操作的接口一致性问题

对于Erase方法，其参数仅有待删除结点pos的结构体指针：

void LTErase(LTNode* pos);

试分析，按照一二级指针传参规则，由于该操作会删除pos结点，实参传递的是待删除结点的指针，即需要将实参置空。

为了实现实参的改变，此处使用二级指针似乎才正确。

但试观察List.h中对于各方法的声明：除初始化可通过无参实现外，其他方法均传参一级指针。为保持接口一致性，试传参一级指针实现方法功能：

对于双向链表删除某一结点的操作，实际上最关键的需要是改变该结点前一个结点和后一个结点的指针域指向问题，至于pos指向结点的置空完全可以在调用时实现。

根据此思路实现参数为一级结构体指针的删除操作：

void LTErase(LTNode* pos) {assert(pos);LTNode* prePosNode = pos->prev;LTNode* nextPosNode = pos->next;prePosNode->next = nextPosNode;nextPosNode->prev = prePosNode;free(pos);pos = NULL;
}

对应调用时：

	LTNode* delNode = LTFind(plist, 4);LTErase(delNode);delNode = NULL;

Erase方法将形参pos置为NULL，而并未改变实参delNode；

故需在调用Erase后再将delNode置空，防止delNode为野指针；

注：同理理解双链表销毁LTDestory操作，为保持接口一致性，令其参数为一级指针，但又由于该方法需改变plist，故需在调用时将plist手动置为NULL。

1. 单链表与双链表

1.1 单链表的结构及结点属性

1.2 双链表的结构及结点属性

2. 单链表与双链表的区别

3. 双链表的实现

3.1 List.h

3.2 List.c

3.3 Test_List.c

注：部分方法的实现细节注释

1. 双链表结点前驱、后继指针域的初始化

2. 各种增、删结点的方法的一级、二级指针传参

3. 增结点与删结点的判空操作

4. 关于初始化方法Init的不同实现形式

5. 关于删除pos结点Erase操作的接口一致性问题

相关文章：