c - 如何对现有的双向循环链表进行排序？

Question

如何在不改变其中数据的情况下改变之前创建的双向循环链表中节点的位置？

(首先，我很抱歉我的英语不好，英语不是我的母语。)

我们参加了我们大学的“数据结构”类(class)考试。最后一个问题是这样给出的。

Check out the code given below. Complete the missing function.

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node* next;
    struct Node* pre;
};

struct Node* node_create(int data)
{
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    new_node->pre = NULL;

    return new_node;
}

void node_add(struct Node** head, struct Node* new_node)
{
    struct Node* list = *head;

    if(*head == NULL)
    {
        new_node->next = new_node;
        new_node->pre = new_node;
        *head = new_node;
    }
    else
    {
        while(list->next != *head)
        {
            list = list->next;
        }

        list->next = new_node;
        (*head)->pre = new_node;

        new_node->next = *head;
        new_node->pre = list;
    }
}

void node_list(struct Node** head)
{
    struct Node* list = *head;

    if(*head == NULL)
    {
        printf("\nEmpty Linked List!\n");
        return;
    }

    do{

        //printf("(%p) %p - %d-> (%p)", list->pre,list,list->data,list->next);
        printf("%d-> ", list->data);
        list = list->next;
    }while(list != *head);
}

void node_delete(struct Node** head, int data)
{
    if(*head == NULL)
    {
        printf("\nEmpty Linked List!\n");
        return;
    }

    struct Node* list = *head;
    struct Node* end = *head;

    if( list->data == data )
    {
        if(list->next == list)
        {
            free(list);
            *head = NULL;
        }
        else
        {
            while(end->next != *head)
            {
                end = end->next;
            }

            *head = list->next;
            end->next = *head;
            (*head)->pre = end;
            free(list);
        }
    }
    else
    {
        while(list->data != data && list->next != *head)
        {
            list = list->next;
        }

        if(list->data != data && list->next == *head)
        {
            printf("No value for delete!\n");
            return;
        }

        (list->pre)->next = list->next;
        (list->next)->pre = list->pre;
        free(list);
    }

    printf("\nDelete of complited!\n");


}

void node_sorting(struct Node** head)
{
    
}




int main()
{
    struct Node* head = NULL;
    struct Node* new_node = NULL;
    int select = 0, data = 0, one = 1;

    while(one == 1)
    {
        printf("\n\nNode Add (1)\n");
        printf("Node List (2)\n");
        printf("Node Delete (3)\n");
        printf("Node Sorting (4)\n");

        printf("\nSelect: ");
        scanf("%d", &select);

        if(select == 1)
        {
            printf("\nData: ");
            scanf("%d", &data);

            new_node = node_create(data);
            node_add(&head, new_node);
        }
        else if(select == 2)
        {
            node_list(&head);
        }
        else if(select == 3)
        {
            printf("\nData to delete: ");
            scanf("%d", &data);

            node_delete(&head, data);
        }
        else if(select == 4)
        {
            node_sorting(&head);
        }

    }

    return 0;
}

认为问题很简单，可以用冒泡算法解决，所以写了下面的代码作为答案。

void node_sorting(struct Node** head)
{
    struct Node* list = *head;
    struct Node* tolist = *head;

    if(*head == NULL)
    {
        printf("\nEmpty Linked List!\n");
        return;
    }

    if((*head)->next == *head)
    {
        printf("A single-element linked list cannot be sorted.");
        return;
    }

    do{

        tolist = list->next;
        list = list->next;

        while(tolist != *head)
        {
            if(list->data > tolist->data)
            {
                int temp = 0;
                temp = tolist->data;
                tolist->data = list->data;
                list->data = temp;
            }
    
            tolist = tolist->next;
        }


    }while(list != *head);

}

然而，当成绩公布时，我得知我没有通过考试，上面的问题得了0分。

当我与教授该类(class)的教授交谈时，我得到了以下答案。 “你写的答案只是一个骗局。如果我在现实生活中使用它，可能会造成严重损害。永远不要更改数据。更改节点的位置。”

我不明白这是什么。我研究了 1 周并找到了以下资源。

Inserting data in a sorted Circular Linked List

Inserting a element in a singly circular linked list in sorted manner

Insert element into a sorted Circular Double Linked List

这些都不适合对现有的双向循环链表进行排序。您可以与我分享的任何适合我的要求的文件或文本都会对我非常有帮助。预先非常感谢您。

Answer 1

想法是更新 pre 和 next 成员，以便节点以不同的顺序放置。

这是使用该原理的合并排序的实现。它由以下步骤组成:

1. 检查给定列表是否只有零个节点或只有一个节点:在这种情况下，列表已排序，我们可以返回。如果没有:
2. 查找给定列表中的中间节点。
3. 将链表分割成两个循环链表，使该节点成为第二个链表的头节点。这意味着必须更新一些 pre、next 指针。
4. 对两个较小的列表中的每一个执行此算法
5. 现在这两个列表已排序:将它们合并为一个已排序的循环列表。

以下是添加到代码中以使其像这样工作的函数:

struct Node* extract_head(struct Node** head) {
    struct Node *node = *head;
    // Detach node from the list it is in
    node->pre->next = node->next;
    node->next->pre = node->pre;
    // Make next node the new head
    *head = node == node->next ? NULL : node->next;
    // Return the node we have extracted
    return node;
}

struct Node* get_middle_node(struct Node* head) {
    if (!head) return head;
    struct Node *last = head->pre;
    // Walk forward and backwards until the two pointers meet:
    while (head != last) {
        head = head->next; // Forward
        if (head == last) break;
        last = last->pre;  // Backward
    }
    return head;
}

struct Node* merge(struct Node* left, struct Node* right) {
    struct Node *newHead = NULL;
    while (left || right) { // While there are nodes to merge...
        // Move the node with the least value into a new circular list
        node_add(&newHead, extract_head(
            !right || left && left->data < right->data ? &left : &right
        ));
    }
    return newHead;
}

struct Node* split_at(struct Node *head, struct Node *at) {
    struct Node *tail = at->pre;
    at->pre = head->pre;
    head->pre->next = at;
    head->pre = tail;
    tail->next = head;
    // Return the pointer to the second half that was separated
    return at;
}

struct Node* merge_sort(struct Node* head) {
    return !head || head->next == head ? head // One node only? => is sorted
         // Split in two, sort each, and merge:
         : merge(merge_sort(split_at(head, get_middle_node(head))), 
                 merge_sort(head));
}

void node_sorting(struct Node** head)
{
    *head = merge_sort(*head);
}

不是你的问题，但你提供的代码有一些奇怪的特殊性。例如，在 node_add 和 node_delete 中有一些 while 循环，它们遍历整个列表，仅在列表中的最后一个节点处停止。但是最后一个节点是头节点的前身，因此您只需查看 (*head)->pre 即可找到它!