C语言实现带头双向环形链表 C语言实现带头双向环形链表

双向循环链表上一次我们讲了单向无头非循环链表的实现，单向无头非循环链表的特点是：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。而带头双向循环链表则恰恰与无头单向非循环链表相反，它的结构最复杂，一般用来单独存储数据。这个结构虽然复杂，但是使用单吗实现后会发现，这个结构用起来很简单。
结构示意图

文章图片

带头双向循环链表在逻辑上大概就是这样的一个样子，链表的最后一个节点的后继指向的是头结点。而头结点的前驱则是指向链表的最后一个结点。所以，一个空的带头双向循环链表的逻辑结构应该是这样的：

文章图片

它的前驱和后继都是指向的头结点。
实现带头双向循环链表

#pragma once#include#include#includetypedef int LTDataType; // 定义链表的节点typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode; // 创建返回链表的头结点.LTNode* ListCreate(); // 双向链表销毁void ListDestory(LTNode* pHead); // 双向链表打印void ListPrint(LTNode* pHead); // 双向链表尾插void ListPushBack(LTNode* pHead, LTDataType x); // 双向链表尾删void ListPopBack(LTNode* pHead); // 双向链表头插void ListPushFront(LTNode* pHead, LTDataType x); // 双向链表头删void ListPopFront(LTNode* pHead); // 双向链表查找LTNode* ListFind(LTNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入void ListInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点void ListErase(LTNode* pos);

首先我们得定义一个结点的结构，它由前驱指针、后继指针和数据这三部分组成。

// 定义链表的节点typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode;

定义好之后，我们要创建一个头结点。我们把创建头结点的过程也封装成一个函数，这个函数的返回值就是头结点的指针。我们在使用的时候就创建一个变量来接收这个指针。
**注意：**头结点创建的时候，它的data部分是不存数据的，它的前驱和后继都是指向它自己

LTNode* ListCreate() { LTNode* head = (LTNode*)malloc(sizeof(LTNode)); head->next = head; head->prev = head; return head; }// 在main函数中是这样使用的int main(){LTNode* head = ListCreate(); return 0; }

创建好头结点之后就可以向链表中插入数据了，首先实现尾插，就是在链表的最后一个结点后面再插入一个结点。然后就是头插法，头插法就是在头结点的后面插入一个新节点。

// 双向链表尾插void ListPushBack(LTNode* pHead, LTDataType x) { assert(pHead); LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); // 创建的新节点 newnode->data = https://www.it610.com/article/x; // 将新节点插入到链表中 LTNode* prev = pHead->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pHead; pHead->prev = newnode; }

// 双向链表头插void ListPushFront(LTNode* pHead, LTDataType x) { assert(pHead); // 创建新节点 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = https://www.it610.com/article/x; //将新节点插入链表 LTNode* next = pHead->next; pHead->next = newnode; newnode->prev = pHead; newnode->next = next; next->prev = newnode; }

有插入数据就有删除数据，同样的删除数据也有两种，一个是头删一个是尾删。头删就是将头结点的next指向的那个结点删除。尾删，就是将最后一个节点删掉。带头双向循环链表，在我们尾删的时候就很方便。因为头结点的前驱指向的节点就是链表的最后一个节点，就不需要我们再遍历链表去找最后一个节点的地址。

// 双向链表头删void ListPopFront(LTNode* pHead) { assert(pHead); assert(pHead->next != pHead); // 定义一个临时变量来保存我们要删掉的节点的位置 LTNode* popnode = pHead->next; // 将要删除节点的链都断掉 LTNode* next = popnode->next; pHead->next = popnode->next; next->prev = pHead; // free掉那个节点 free(popnode); popnode = NULL; }

// 双向链表尾删void ListPopBack(LTNode* pHead) { assert(pHead); assert(pHead->prev != pHead); LTNode* popnode = pHead->prev; LTNode* prev = popnode->prev; prev->next = pHead; pHead->prev = prev; free(popnode); popnode = NULL; }

在实现了增加和删除节点之后，我们就实现查找结点。方法也是遍历整个链表，如果有一个节点的data的值和x相同就返回这个节点的地址。如果没找到就返回空。

// 双向链表查找LTNode* ListFind(LTNode* pHead, LTDataType x) { if (pHead->next == pHead) {return NULL; } LTNode* find = pHead->next; while (find != pHead) {if (find->data =https://www.it610.com/article/= x) {return find; }find = find->next; } return NULL; }

实现随机插入数据，这里的随机插入的意思是，我们把新节点插入到我们指定的节点的后面一个或前面一个。这个节点可以是在链表的任何一个地方。我们这个函数会传入一个节点的地址，通过那个地址可以找到要出入的那个节点，把新节点连接到那个节点后面就可以了

// 双向链表删除pos位置的节点void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }

打印双向循环链表，也是通过遍历链表来打印

// 双向链表打印void ListPrint(LTNode* pHead) { assert(pHead); LTNode* tail = pHead->next; while (tail != pHead) {printf("%d->", tail->data); tail = tail->next; }}

在我们使用完链表后，要记得销毁链表，防止内存泄漏

// 双向链表销毁void ListDestory(LTNode* pHead) { assert(pHead); LTNode* tail = pHead->next; while (tail != pHead) {LTNode* tmp = tail->next; free(tail); tail = tmp; } free(pHead); pHead = NULL; }

【C语言实现带头双向环形链表】以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。