如何在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) 重复此操作直到结束。

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

How to insertion sort a doubly linked list in c

c

doubly-linked-list

insertion-sort