c++ - 冒泡排序双向链表

Question

我想使用冒泡排序对双向链表进行排序。它存在循环问题，而且交换也没有正确进行。问题是最大的数字应该在 i 的一次迭代之后出现在最后。但它并没有停在两者之间。我尝试了各种选择但无法解决。请帮我解决这个问题

#include <iostream>
using namespace std;
class node{
    public:
        node *next;
        node *prev;
        int data;
        node(int x, node *p, node *n)
        {
            next = n;
            prev = p;
            data = x;
        }
};
class list{
    private:
    node *head;
    node *tail;
    public:
    list()
    {
        head = NULL;
        tail = NULL;
    }
    void addtoend(int x)
    {
        if(head == NULL)
        {
            head = new node (x,NULL,NULL);
            tail = head;
        }
        else if(tail->prev == NULL)
        {
            tail = new node(x,head,NULL);
            head->next = tail;
        }
        else
        {
            node *temp = tail;
            tail = new node(x,tail,NULL);
            temp->next = tail;

        }
    }
    void bubblesort()
    {
        node *temp = head;
        node *temp2 = temp;
        for(int i=0;i<10;i++)
        {
            cout<<"I: "<<i<<endl;
            temp = head;
            while(1)
            {
                temp2 = temp;
                if(temp->next->data < temp->data)
                {
                    if(temp == head)
                    {
                        cout<<"HEAD"<<endl;
                        head = head->next;
                        node *after = head->next;
                        head->prev = NULL;
                        temp->prev = head;
                        head->next = temp;
                        temp->next = after;
                        after->prev = temp;
                    }
                    else if(temp->next == tail)
                    {
                        cout<<"TAIL"<<endl;
                        node *back = temp->prev;
                        temp->next = NULL;
                        tail->next = temp;
                        temp->prev = tail;
                        back->next = tail;
                        tail->prev = back;
                        tail = tail->next;
                        tail->next=NULL;

                    }
                    else
                    {
                        cout<<"ANY"<<endl;
                        node *back = temp->prev;
                        node *after = temp->next->next;

                        back->next=temp->next;
                        temp->prev = temp->next;
                        after->prev->next = temp;
                        after->prev->prev = back;
                        after->prev = temp;
                        temp->next = after;

                    }
                }
                display();
                display0();
                temp = temp2->next;
                cout<<"HEAD: "<<head->data<<endl;
                cout<<"Tail: "<<tail->data<<endl;
                cout<<endl;
                if(temp->next->next== NULL)
                {
                    break;
                }
            }

        }

    }
    void display()
    {
        node *temp = head;
        while(temp != NULL)
        {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
        cout<<endl;
    }
    void display0()
    {
        node *temp = tail;
        while(temp != NULL)
        {
            cout<<temp->data<<" ";
            temp = temp->prev;
        }
        cout<<endl;
    }
};
main()
{
    list l1;
    int x[10] = {17,15,8,12,10,5,4,1,7,2};
    for(int i=0;i<10;i++)
    {
        l1.addtoend(x[i]);
    }
    l1.display();
    l1.bubblesort();
    l1.display();
}

Answer 1

如何实现双链表的冒泡排序算法

至少有两种方法可以在 c++ 中为双链表 实现冒泡排序算法。如 I. 所示交换内容，即两个相邻节点的数据，并如 II. 所示重新连接指针:

II.的优点是不需要临时内存temp2。因此，正如 OP 所述，这是首选解决方案。

我。交换数据

只需用这个替换 OP bubblesort 函数:

    void bubblesort()
    {
        bool is_sorted = false;
        node *temp = head;
        while (!is_sorted)
        {
            is_sorted = true;
            temp = head;
            while (temp->next != NULL)
            {
                if(temp->next->data < temp->data)
                {
                    is_sorted = false;
                    int temp2 = temp->data;
                    temp->data = temp->next->data;
                    temp->next->data = temp2;
                }
                temp = temp->next;
            }
        }
        display();
        display0();
    }

该算法使用 bool 变量is_sorted 来检查双链表 的排序是否完成。否则泡沫仍在上升。它只交换双链表的数据值。

二。重新连接指针

这是 OP 所需的解决方案，也是首选解决方案:

    void bubblesort()
    {
        bool is_sorted = false;
        node *temp = head;
        while (!is_sorted)
        {
            is_sorted = true;
            temp = head;
            while (temp->next != NULL)
            {
                if(temp->next->data < temp->data)
                {
                    is_sorted = false;
                    if(temp == head)
                    {
                        //temp->prev->next = temp->next; // 1. (impossible)
                        temp->next->prev = NULL;         // 2.
                        head = temp->next;
                    }
                    else
                    {
                        temp->prev->next = temp->next;   // 1.
                        temp->next->prev = temp->prev;   // 2.
                    }
                    temp->prev = temp->next;             // 3.
                    if(temp->next == tail)
                    {
                        temp->next = NULL;               // 4.
                        tail = temp;
                        //temp->next->prev = temp2;      // 5. (impossible)
                    }
                    else
                    {
                        temp->next = temp->next->next;   // 4.
                        temp->next->prev = temp;         // 5.
                    }
                    temp->prev->next = temp;             // 6.
                    temp = temp->prev;
                }
                temp = temp->next;
            }
        }
        display();
        display0();
    }

输出

具有更新的 bubblesort 函数的程序的输出是:

17 15 8 12 10 5 4 1 7 2
1 2 4 5 7 8 10 12 15 17
17 15 12 10 8 7 5 4 2 1
1 2 4 5 7 8 10 12 15 17

第一行显示未排序的输入列表。第二个显示升序排列结果，第三个显示降序排列，这证明列表的正向和反向链接仍然有效。最后一行是 main 函数中输出的排序列表。

当然，列表的原始顺序丢失了。

完整的源代码也可以在 github 上找到。 .

希望对您有所帮助。