c - 如何在c中对双向链表进行插入排序

Question

我正在尝试按整数值对双向链表进行排序。

这是一个示例节点:

struct Node
{

    struct Node* previous;
    struct Node* next;
    int* a;

}Node;

我最初打算使用插入排序，但我正在努力想出正确的代码。

我的头和尾只是struct Node* listHead和struct Node* listTail。它们都是全局变量。

编辑:我查看了有关此主题的其他几篇文章，但无法使代码正常运行。我为我的无能道歉。

到目前为止的尝试:

    struct Node* key = listHead;
    struct Node* i;
    struct Node* temp;

    while(key!=NULL)
    {
        temp=key;
        iterator=key->previous;
        while(i != NULL && temp->a>i->a)
        {
            if(i->next->next!=NULL&& i->next!=NULL)
            {
                i=i->next->next;
                i=i->previous;
            }
        }
        if(i->next->next!=NULL && key->next!=NULL)
        {
        i->next->next = temp;
        key = key->next;
        }
    }

编辑:第二次代码尝试:

    struct Node* newHead = NULL;
    struct Node* newTail = NULL;

    struct Node* i;
    struct Node* move = listHead;
    struct Node* temp;
    while(move->next!=NULL && move!=NULL)
    {
        if(newHead==NULL)
        {
            temp=move;
            newHead=temp;
        }else if(newTail==NULL)
        {
            temp=move;
            newTail=temp;
        }else if(newHead->next->next==NULL)
        {
            temp=move;
            insert_node(newHead, newTail, temp);
        }
        else
        {
            i=newHead->next;
            while(inserter->previous!=NULL)
            {
                if(i->previous->a < i->a)
                {
                    temp=move;
                    insert_node(i->previous,i,temp);
                    break;
                }
                i=i->previous;
            }
        }
        move=move->next;
    }
    listHead=newHead;
    listTail=newTail;

第二个代码块似乎仅对最后一个元素进行排序。

我的插入功能:

void insert_node(struct Node* first, struct Node* last, struct Node* insert)
{
    first->next=insert;
    insert->previous=first;
    last->previous=insert;
    insert->next=last;
}

Answer 1

创建一个新的双向链表。一次从原始双向链表中删除一个元素，然后根据插入排序将其插入到新双向链表的正确位置(正如您所提到的，您正在使用插入排序)。

我猜这就是您遇到问题的地方(在实现此操作时)。尝试分解问题。学习创建双向链表，在开头插入一个元素，在结尾插入一个元素，从开头删除元素，从结尾删除元素，在某个特定位置插入元素，在某个特定位置删除元素，交换两个元素列表的元素。

一旦您了解了所有这些，您的代码将分解为如下所示:

1) 创建一个新的空双向链表

2)从原来的双向链表中删除最后一个元素，并将其插入到新的双向链表中

3)从原来的双向链表中删除最后一个元素，并将其插入到新链表中的正确位置(使得一侧的元素较小，另一侧的元素较大)

4)重复集合3，直到原始链表中有元素

您只需要在这里调用相应操作的方法即可。如果您仍然遇到问题，请尝试在此处粘贴您的代码。

编辑: 您任何时候都不会拥有不必要的节点。但是，如果您的老师坚持只使用一个列表:

1) 创建一个新指针 A 来标记双向链表排序前的节点(最初这将是原始双向链表的第一个元素)

2) 现在考虑指针 A 处元素的值，迭代排序列表(即指针 A 处元素之前的列表)，找到指针 A 处元素适合的位置(即之前的元素较小，元素之后更大)。现在将指针 A 指向的节点插入到该位置。并使A指向下一个节点元素。

3)重复此操作直到到达终点。