双链表冒泡排序

Question

我的项目是一个双向链表的冒泡排序系统。我正在尝试按日期对双向链表（对象）的元素进行排序。我使用基于指针的排序，因为我不想更改指针的数据。问题是我的代码可以（我认为有效地）对链表进行排序。但是最后，当我尝试打印链表的对象时，我的头不在应该在的地方。你能帮帮我吗？

struct DoubleNode *DoubleDynamic::swap( DoubleNode *pointer1,  DoubleNode *pointer2) {
    DoubleNode* temp=pointer2->next;
    pointer2->next=pointer1;
    pointer2->prev=pointer1->prev;
    pointer1->next=temp;
    pointer1->prev=pointer2;
    return pointer2;
}

void DoubleDynamic::sort(int size)
{
    DoubleNode* temp;
    DoubleNode* current;
    bool sorting;
    if (head==NULL)
    {
        return;
    }else
    {
        for (int i = 0; i <= size; ++i)
        {
            sorting= false;
            temp=head;
            for (int j = 0; j < size-1-i; ++j)
            {
                DoubleNode *employee1=temp;
                DoubleNode *employee2=employee1->next;
                if (employee2!=NULL)
                {
                    if (employee1->data->getAppointment().operator>(employee2->data->getAppointment()))
                    {
                        temp = swap(employee1,employee2);
                        sorting= true;
                    }
                    temp= temp->next;
                }
            }
            if (!sorting)
            {
                break;
            }
        }
    }
    current=head;
    while (current->prev!=NULL)
    {
        current=current->prev;
    }
    head=current;
}

void DoubleDynamic::display()
{

    struct DoubleNode *trav;
    trav=head;
    if (trav==NULL)
    {
        cout<<"Liste boş yaa"<<endl;
    }
    while (trav != NULL)
    {
        cout<<*(trav->data)<<endl;
        trav=trav->next;
    }
    cout<<endl;
}

Answer 1

问题是当你交换头指针时，你没有更新head来引用新的头节点。

解决此问题的一种方法是在进行交换后，您应该检查是否应更新头指针。

temp = swap(employee1,employee2);
if (employee1 == head)
    head = temp;

或者，在swap中，如果在pointer2->prev=pointer1->prev;中分配的新prev指针为NULL，则更新头部（因为头部节点没有前一个节点）。

if ((pointer2->prev=pointer1->prev) == nullptr)
    head = pointer2;

双链表冒泡排序

Doubly Linked List Bubble Sort

c++

sorting

linked-list

bubble-sort

doubly-linked-list