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

Question

如何更改之前创建的双向循环链表中节点的位置而不更改其中的数据？

（首先，我很抱歉我的英语不好，英语不是我的母语。）

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

查看下面给出的代码。完成缺失的功能。

#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分。

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

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

在已排序的循环链表中插入数据

以排序方式向单循环链表插入元素

将元素插入已排序的循环双链表

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

Answer 1

如何更改之前创建的双向循环链表中节点的位置而不更改其中的数据？

从这个意义上讲，

“位置”是指当您沿着

next

指针链（如果您以另一个方向遍历列表，则为

pre

指针）时，节点将被遍历的顺序。因此，要更改节点的位置，您需要修改各个节点的

next

和

pre

指针。

例如，考虑这个初始顺序（仅显示

next

指针）...

    A  --->  B  --->  C  --->  D

...假设我们想要交换节点 B 和 C。这意味着我们想要修改列表，以便前向迭代从 A 到 C 到 B 到 D。好吧，这已经告诉你应该修改指针指向哪里:

    r----------------\
    |                 V 
    A        B  <---  C        D
             |                 ^
             L----------------/

当然，对于双向链表，您需要与

pre

指针一致地更新

next

指针。

您不仅需要考虑正在交换的两个节点之间的指针，还需要考虑这些节点之间的指针以及两侧的指针 - 示例中的 A 和 D。

总的来说，您可以将节点从一个位置移动到另一个位置概念化为从列表中删除该节点而不取消分配它，然后将其重新插入到所需位置。您也可以通过调用给定的

node_add

和

node_delete

函数来实现它，尽管在您的情况下不是这样。