双向循环链表的基本操作
时间: 2023-12-07 07:38:22 浏览: 38
双向循环链表是一种链表结构,它的每个节点都有两个指针,一个指向前一个节点,一个指向后一个节点。与单向链表不同的是,双向循环链表的头节点的前一个节点指向尾节点,尾节点的后一个节点指向头节点,形成一个循环。以下是双向循环链表的基本操作:
1. 头文件
```c
#include <stdio.h>
#include <stdlib.h>
```
2. 双向链表的基本结构
```c
typedef struct node {
int data;
struct node *prev; // 指向前一个节点
struct node *next; // 指向后一个节点
} Node, *DoubleLinkedList;
```
3. 初始化双链表
```c
DoubleLinkedList init() {
DoubleLinkedList head = (DoubleLinkedList)malloc(sizeof(Node));
head->prev = head;
head->next = head;
return head;
}
```
4. 双链表判空
```c
int isEmpty(DoubleLinkedList head) {
return head->next == head;
}
```
5. 双链表尾插
```c
void insertTail(DoubleLinkedList head, int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = head->prev;
newNode->next = head;
head->prev->next = newNode;
head->prev = newNode;
}
```
6. 双链表头插
```c
void insertHead(DoubleLinkedList head, int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = head;
newNode->next = head->next;
head->next->prev = newNode;
head->next = newNode;
}
```
7. 创建一个新节点
```c
Node *createNode(int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
```
8. 在某一节点前插入一个新节点
```c
void insertBefore(DoubleLinkedList head, Node *node, int data) {
Node *newNode = createNode(data);
newNode->prev = node->prev;
newNode->next = node;
node->prev->next = newNode;
node->prev = newNode;
}
```
9. 删除当前节点
```c
void deleteNode(DoubleLinkedList head, Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
}
```
10. 双链表头删
```c
void deleteHead(DoubleLinkedList head) {
if (isEmpty(head)) {
printf("List is empty.\n");
return;
}
deleteNode(head, head->next);
}
```
11. 双链表尾删
```c
void deleteTail(DoubleLinkedList head) {
if (isEmpty(head)) {
printf("List is empty.\n");
return;
}
deleteNode(head, head->prev);
}
```
12. 双链表打印
```c
void printList(DoubleLinkedList head) {
if (isEmpty(head)) {
printf("List is empty.\n");
return;
}
Node *p = head->next;
while (p != head) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
```
13. 查找
```c
Node *search(DoubleLinkedList head, int data) {
Node *p = head->next;
while (p != head) {
if (p->data == data) {
return p;
}
p = p->next;
}
return NULL;
}
```
14. 销毁双链表
```c
void destroy(DoubleLinkedList head) {
Node *p = head->next;
while (p != head) {
Node *temp = p;
p = p->next;
free(temp);
}
free(head);
}
```