在数据结构中，链表是一种非常基础且重要的线性结构。链表有多种形式，如单向链表、双向链表、循环链表等。本文将详细介绍如何在C语言中实现一个带头节点的双向循环链表。带头节点的双向循环链表结合了双向链表和循环链表的优点，具有较高的灵活性和效率。
双向循环链表是一种特殊的链表结构，它具备以下特点：
在C语言中，我们可以通过结构体来定义双向循环链表的节点结构。每个节点包含三个部分：
计算
安全
数据库
网络和加速
企业服务
typedef struct Node {
int data; // 数据域
struct Node* prev; // 前驱指针
struct Node* next; // 后继指针
} Node;
初始化链表时，我们需要创建一个头节点，并将其前驱和后继指针都指向自身，形成一个空的循环链表。
Node* createList() {
Node* head = (Node*)malloc(sizeof(Node));
if (head == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
head->prev = head;
head->next = head;
return head;
}
在带头双向循环链表中插入节点时，通常有以下几种情况：
以下是插入节点的代码示例：
void insertAfter(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = data;
newNode->next = head->next;
newNode->prev = head;
head->next->prev = newNode;
head->next = newNode;
}
void insertBefore(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = data;
newNode->prev = head->prev;
newNode->next = head;
head->prev->next = newNode;
head->prev = newNode;
}
void insertAt(Node* head, int position, int data) {
Node* current = head->next;
int count = 0;
while (current != head && count < position) {
current = current->next;
count++;
}
if (count == position) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = data;
newNode->next = current;
newNode->prev = current->prev;
current->prev->next = newNode;
current->prev = newNode;
} else {
printf("Position out of range!\n");
}
}
删除节点时，我们需要找到要删除的节点，并调整其前驱和后继节点的指针，使其跳过该节点。以下是删除节点的代码示例：
void deleteNode(Node* head, int data) {
Node* current = head->next;
while (current != head) {
if (current->data == data) {
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
return;
}
current = current->next;
}
printf("Node with data %d not found!\n", data);
}
查找节点时，我们可以从头节点开始遍历链表，直到找到目标节点或回到头节点为止。以下是查找节点的代码示例：
Node* findNode(Node* head, int data) {
Node* current = head->next;
while (current != head) {
if (current->data == data) {
return current;
}
current = current->next;
}
return NULL;
}
遍历链表时，我们可以从头节点开始，依次访问每个节点的数据域，直到回到头节点为止。以下是遍历链表的代码示例：
void traverseList(Node* head) {
Node* current = head->next;
while (current != head) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
Node* createList() {
Node* head = (Node*)malloc(sizeof(Node));
if (head == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
head->prev = head;
head->next = head;
return head;
}
void insertAfter(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = data;
newNode->next = head->next;
newNode->prev = head;
head->next->prev = newNode;
head->next = newNode;
}
void insertBefore(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = data;
newNode->prev = head->prev;
newNode->next = head;
head->prev->next = newNode;
head->prev = newNode;
}
void insertAt(Node* head, int position, int data) {
Node* current = head->next;
int count = 0;
while (current != head && count < position) {
current = current->next;
count++;
}
if (count == position) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = data;
newNode->next = current;
newNode->prev = current->prev;
current->prev->next = newNode;
current->prev = newNode;
} else {
printf("Position out of range!\n");
}
}
void deleteNode(Node* head, int data) {
Node* current = head->next;
while (current != head) {
if (current->data == data) {
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
return;
}
current = current->next;
}
printf("Node with data %d not found!\n", data);
}
Node* findNode(Node* head, int data) {
Node* current = head->next;
while (current != head) {
if (current->data == data) {
return current;
}
current = current->next;
}
return NULL;
}
void traverseList(Node* head) {
Node* current = head->next;
while (current != head) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
Node* head = createList();
insertAfter(head, 10);
insertAfter(head, 20);
insertBefore(head, 5);
insertAt(head, 1, 15);
printf("List after insertions: ");
traverseList(head);
deleteNode(head, 15);
printf("List after deletion: ");
traverseList(head);
Node* found = findNode(head, 20);
if (found != NULL) {
printf("Node with data 20 found!\n");
} else {
printf("Node with data 20 not found!\n");
}
return 0;
}
本文详细介绍了如何在C语言中实现一个带头节点的双向循环链表。通过定义节点结构体，并实现链表的初始化、插入、删除、查找和遍历等基本操作，我们可以灵活地管理链表中的数据。带头双向循环链表在实际应用中具有较高的效率和灵活性，适用于需要频繁插入和删除操作的场景。希望本文能帮助读者更好地理解和掌握双向循环链表的实现方法。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
