C语言双向循环链表排序案例

在C语言中实现双向循环链表的排序，通常可以通过插入排序算法来进行。以下是一个简单的双向循环链表排序的案例，包括节点的定义、链表的创建、排序函数以及主函数的实现。

首先定义双向循环链表的节点结构体：

typedef struct DNode {
    int data;                // 数据域
    struct DNode *prior, *next; // 指向前驱和后继的指针
} DNode, *DLinkedList;

然后创建链表：

void createDLinkedList(DLinkedList *L, int n) {
    DNode *tail, *p;
    int i, x;
    *L = (DNode*)malloc(sizeof(DNode));
    (*L)->next = *L;
    (*L)->prior = *L;
    tail = *L;
    for (i = 0; i < n; i++) {
        p = (DNode*)malloc(sizeof(DNode));
        scanf("%d", &x);
        p->data = x;
        p->next = *L;
        p->prior = tail;
        tail->next = p;
        tail = p;
        (*L)->prior = tail;
    }
}

接下来是排序函数：

void sortDLinkedList(DLinkedList L) {
    DNode *p, *q, *r;
    int flag;
    if (L == NULL || L->next == L)
        return;
    do {
        flag = 0;
        p = L->next;
        q = p->next;
        while (q != L) {
            if (p->data > q->data) {
                // 交换数据域的值
                r = p->prior;
                r->next = q;
                q->prior = r;
                p->prior = q;
                p->next = q->next;
                q->next->prior = p;
                q->next = p;
                flag = 1;
            }
            p = q;
            q = p->next;
        }
    } while (flag);
}

最后是主函数的示例：

int main() {
    DLinkedList L;
    int n, x;
    printf("请输入链表长度：");
    scanf("%d", &n);
    createDLinkedList(&L, n);
    printf("请输入链表元素：");
    // 为了简化问题，这里假设输入已经正确排序
    for (DNode *p = L->next; p != L; p = p->next) {
        scanf("%d", &x);
        p->data = x;
    }
    sortDLinkedList(L);
    printf("排序后的链表为：");
    for (DNode *p = L->next; p != L; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
    return 0;
}

在上述代码中，我们首先定义了双向循环链表的节点结构体，然后通过`createDLinkedList`函数创建链表，并通过`sortDLinkedList`函数实现了链表的排序。在主函数中，我们读取用户输入的链表长度和元素值，然后调用排序函数，并输出排序后的链表。