使用c语言 建立双向链表，data域为正整数，输入0为默认链表终止，打印该双向链表。对该双向链表进行快速排序，打印排序后的结果

可以使用双向链表的快速排序算法来实现，该算法可以在O(nlog n)的时间复杂度内完成排序，并且打印排序后的结果。代码如下：#include <stdio.h>
#include <stdlib.h>/* 双向链表节点定义 */
typedef struct node {
int data;
struct node *prev;
struct node *next;
} NODE;/* 读取输入，构造双向链表 */
NODE *construct_list(int n) {
NODE *head = NULL, *p, *q;
int x;
scanf("%d", &x);
if (x != 0) {
head = (NODE*)malloc(sizeof(NODE));
head->data = x;
head->prev = NULL;
head->next = NULL;
p = head;
n--;
}
while (n--) {
scanf("%d", &x);
if (x == 0) break;
q = (NODE*)malloc(sizeof(NODE));
q->data = x;
q->next = NULL;
q->prev = p;
p->next = q;
p = q;
}
return head;
}/* 快速排序双向链表 */
void quick_sort(NODE *head, NODE *tail) {
if (head == NULL || head == tail) {
return;
}
//使用头尾元素作为分界点
int pivot = head->data;
NODE *p = head;
NODE *q = tail;
while (p != q) {
while (p != q && q->data >= pivot) {
q = q->prev;
}
if (p != q) {
p->data = q->data;
p = p->next;
}
while (p != q && p->data < pivot) {
p = p->next;
}
if (p != q) {
q->data = p->data;
q = q->prev;
}
}
p->data = pivot;
quick_sort(head, p->prev);
quick_sort(p->next, tail);
}int main() {
int n;
scanf("%d", &n);
NODE *head = construct_list(n);
NODE *tail = head;
while (tail->next != NULL) {
tail = tail->next;
}
quick_sort(head, tail);
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
return 0;
}