C语言双向循环链表排序案例,不要只是交换数据域的值
时间: 2024-09-13 17:07:28 浏览: 49
在C语言中,双向循环链表是一种数据结构,每个节点都包含数据域以及两个指针域,一个指向前一个节点,一个指向后一个节点。与单向链表不同,双向循环链表的头尾相接,形成一个环。对双向循环链表进行排序时,我们通常需要比较节点中的数据,并根据排序算法调整节点的指针域,而不仅仅是数据域的值。
下面是一个简化的C语言双向循环链表排序的案例,使用插入排序算法进行演示。请注意,实际代码需要进行错误检查和异常处理,此处仅提供基本的排序逻辑。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义双向循环链表的节点结构体
typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} Node;
// 创建一个新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = data;
newNode->prev = newNode;
newNode->next = newNode;
return newNode;
}
// 向双向循环链表中插入一个节点
void insertNode(Node** head, int data) {
Node* newNode = createNode(data);
if (!newNode) return;
if (*head == NULL) {
*head = newNode;
} else {
Node* temp = *head;
// 找到链表的最后一个节点
while (temp->next != *head) {
temp = temp->next;
}
// 插入新节点
temp->next = newNode;
newNode->prev = temp;
newNode->next = *head;
(*head)->prev = newNode;
}
}
// 双向循环链表的插入排序
void insertionSort(Node** head) {
if (*head == NULL || (*head)->next == *head) {
return; // 链表为空或只有一个节点时不需要排序
}
Node *sorted = NULL; // 已排序部分的最后一个节点
// 遍历链表中的所有节点
for (Node* current = *head; current != NULL; ) {
Node* next = current->next; // 保存下一个节点的指针
// 寻找current的正确位置,插入到sorted链表中
if (sorted == NULL || sorted->data >= current->data) {
// 插入到sorted的开头
if (sorted != NULL) {
current->next = sorted;
sorted->prev = current;
}
current->prev = NULL;
current->next = *head;
(*head)->prev = current;
*head = current;
} else {
// 寻找current在sorted中的位置并插入
Node* sortedCurrent = sorted;
while (sortedCurrent->next != sorted && sortedCurrent->data < current->data) {
sortedCurrent = sortedCurrent->next;
}
// 插入current到sortedCurrent之后
current->next = sortedCurrent->next;
current->prev = sortedCurrent;
sortedCurrent->next->prev = current;
sortedCurrent->next = current;
}
// 更新current为下一个要处理的节点
current = next;
if (current != NULL && current == *head) {
// 如果已经回到链表头部,则结束排序
break;
}
}
}
// 打印双向循环链表
void printList(Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
Node* temp = head;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
Node* head = NULL;
insertNode(&head, 4);
insertNode(&head, 3);
insertNode(&head, 2);
insertNode(&head, 1);
printf("Original list:\n");
printList(head);
insertionSort(&head);
printf("Sorted list:\n");
printList(head);
// 释放链表内存的代码应该在这里,但为了简洁性,省略了
return 0;
}
```
请注意,上述代码是一个简单的示例,仅用于演示插入排序算法在双向循环链表中的应用。在实际应用中,可能需要处理更复杂的情况,如内存释放、错误处理等。
阅读全文