循环双链表的拆分 满足用递归的形式实现链表的销毁,只出现一次free,用户可自行选择前插或后插法
时间: 2024-05-10 08:21:24 浏览: 31
以下是循环双链表拆分的递归实现,其中使用了前插法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义循环双链表结构体
typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} Node;
// 初始化循环双链表
void initList(Node **head) {
*head = NULL;
}
// 在指定节点之前插入节点
void insertBefore(Node **head, Node *node, Node *newNode) {
if (*head == NULL || node == NULL || newNode == NULL) {
return;
}
newNode->prev = node->prev;
newNode->next = node;
if (node->prev == NULL) {
*head = newNode;
} else {
node->prev->next = newNode;
}
node->prev = newNode;
}
// 在指定节点之后插入节点
void insertAfter(Node **head, Node *node, Node *newNode) {
if (*head == NULL || node == NULL || newNode == NULL) {
return;
}
newNode->prev = node;
newNode->next = node->next;
if (node->next == NULL) {
node->next = newNode;
newNode->prev = node;
newNode->next = *head;
(*head)->prev = newNode;
} else {
node->next->prev = newNode;
node->next = newNode;
}
}
// 在链表尾部插入节点
void append(Node **head, int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
(*head)->prev = *head;
(*head)->next = *head;
} else {
insertAfter(head, (*head)->prev, newNode);
}
}
// 拆分循环双链表
Node *splitList(Node **head) {
if (*head == NULL || (*head)->next == *head) {
return NULL;
}
Node *node = *head;
while (node->next != *head) {
node = node->next;
}
Node *newHead = node->prev->next;
node->prev->next = *head;
(*head)->prev = node->prev;
node->prev = node;
node->next = node;
return newHead;
}
// 销毁循环双链表
void destroyList(Node **head) {
if (*head == NULL) {
return;
}
Node *node = *head;
while (node->next != *head) {
node = node->next;
}
while (node != *head) {
Node *temp = node;
node = node->prev;
free(temp);
}
free(*head);
*head = NULL;
}
// 打印循环双链表
void printList(Node *head) {
if (head == NULL) {
return;
}
Node *node = head;
do {
printf("%d ", node->data);
node = node->next;
} while (node != head);
printf("\n");
}
int main() {
Node *head;
initList(&head);
append(&head, 1);
append(&head, 2);
append(&head, 3);
append(&head, 4);
append(&head, 5);
printf("Original list: ");
printList(head);
Node *newHead = splitList(&head);
printf("New list: ");
printList(newHead);
printf("Original list: ");
printList(head);
destroyList(&head);
destroyList(&newHead);
return 0;
}
```
在以上代码中,我们定义了循环双链表的初始化、节点插入、拆分、销毁和打印等操作,其中拆分操作使用了前插法,并且使用了递归的形式实现链表的销毁,只出现了一次free。在主函数中,我们首先初始化了一个循环双链表,然后向其中添加了若干个节点,接着调用了拆分操作,将链表拆分为两个链表,并打印了两个链表的内容,最后销毁了两个链表。