帮我写一个C语言代码,动态链表排序用快速排序法排序
时间: 2023-05-26 11:02:50 浏览: 66
很抱歉,我是一个语言模型,无法编写代码。以下是一份使用快速排序法对动态链表进行排序的C语言代码,希望能够帮到你:
```c
#include <stdio.h>
#include <stdlib.h>
/* 定义链表结构体 */
typedef struct Node {
int data;
struct Node *next;
} Node;
/* 创建新节点 */
Node *createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
/* 遍历链表 */
void traverseList(Node *head) {
Node *p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
/* 快速排序核心函数,对链表进行排序 */
Node *quickSort(Node *head, Node *tail) {
if (!head || head == tail) {
return head;
}
Node *pivot = head;
Node *prev = head;
Node *cur = head->next;
while (cur != tail) {
if (cur->data < pivot->data) {
prev = prev->next;
int temp = prev->data;
prev->data = cur->data;
cur->data = temp;
}
cur = cur->next;
}
int temp = pivot->data;
pivot->data = prev->data;
prev->data = temp;
Node *left = quickSort(head, prev);
Node *right = quickSort(prev->next, tail);
pivot->next = right ? right : NULL;
if (left) {
Node *p = left;
while (p->next) {
p = p->next;
}
p->next = pivot;
return left;
} else {
return pivot;
}
}
/* 主函数 */
int main() {
Node *head = createNode(-1); // 头节点不存储数据
Node *tail = head;
/* 添加测试数据 */
tail->next = createNode(5);
tail = tail->next;
tail->next = createNode(2);
tail = tail->next;
tail->next = createNode(7);
tail = tail->next;
tail->next = createNode(3);
tail = tail->next;
printf("排序前:");
traverseList(head);
head->next = quickSort(head->next, NULL);
printf("排序后:");
traverseList(head);
return 0;
}
```