合并排序不拆分列表的右侧

Question

如标题所述，我的合并排序仅拆分左侧。其他一切正常，包括我的合并功能。我不知道为什么。我真的很感激你的帮助。在包含以下内容的列表中： 7, 4, 10, 2, 6, 1, 3, 7, 11, 5 它输出 1, 2, 3, 4, 6, 7, 7, 10, 11, 5

编辑：添加了我 class 的其余部分。

#include <iostream>
#include <string>
using namespace std;

class linkedList
{
private:
    class node
    {
    public:
        int data;
        node * next;
        node * prev;


    node(int x)
    {
        data = x;
        next = NULL;
        prev = NULL;
    }
};

node * head;
node * tail;

node * split()
{
    node * finger = head;
    node * fast = head->next;
    while (fast != NULL)
    {
        fast = fast->next;
        if (fast != NULL)
        {
            fast = fast->next;
            finger = finger->next;
        }
    }
    tail = finger->next;
    node * splitB = tail;
    splitB->prev = NULL;
    finger->next = NULL;
    return splitB;
}

node * merge(node * a, node * b)
{
    linkedList m;

    while(a != NULL || b != NULL)
    {
        if(b == NULL)
        {
            if(m.head != NULL)
            {
                a->prev = m.tail;
                m.tail->next = a;
                m.tail = a;

            }
            else
            {
                m.head = a;
                m.tail = m.head;
            }
            a = a->next;
        }
        else if(a == NULL)
        {
            if(m.head != NULL)
            {               
                b->prev = m.tail;
                m.tail->next = b;
                m.tail = b;
            }
            else
            {
                m.head = b;
                m.tail = m.head;
            }
            b = b->next;
        }
        else if (a->data < b->data)
        {
            if(m.head == NULL)
            {
                m.head = a;
                m.tail = m.head;
            }
            else
            {
                a->prev = m.tail;
                m.tail->next = a;
                m.tail = a;
            }
            a = a->next;
        }
        else
        {
            if(m.head == NULL)
            {
                m.head = b;
                m.tail = m.head;
            }
            else
            {
                b->prev = m.tail;
                m.tail->next = b;
                m.tail = b;
            }
            b = b->next;
        }
    }
    return m.head;
}

node* mergeSort(node * a)
{
    if (head == NULL || head->next == NULL)
    {
        return a;
    }
    else
    {
        node * b = split();

        node* right = mergeSort(a);
        node* left = mergeSort(b);

        return merge(right, left);
    }
}



public:
    linkedList()
    {
        head = NULL;
        tail = NULL;
    }


void push_back(int x)
{
    node * baby = new node(x);

    if( head == NULL )
    {
        head=baby;
        tail=baby;
    }
    else
    {
        baby->prev = tail;
        tail->next = baby;
        tail = baby;
    }
}

void mergeSort()
{
    head = mergeSort(head);
}

bool empty()
{
    if (head == NULL)
        return true;
    else
        return false;
}

int pop()
{
    int popMe = head->data;
    node * deleteMe = head;
    if (head->next == NULL)
    {
        head = NULL;
        tail = NULL;
        delete deleteMe;
        return popMe;
    }
    else
    {
        head = head->next;
        head->prev = NULL;
        delete deleteMe;
        return popMe;
    }
}
//test
void display()
{
    node * finger = head;
    while(finger!=NULL)
    {
        cout << finger->data << endl;
        finger = finger->next;
    }
}

};

Answer 1

停止使用全局变量！
删除出现在函数之前的所有变量声明。
仅依赖作为参数传递给函数的数据。

编辑

这是对原始代码的（可能是最小的）修改，它不使用外部变量（无参数 mergeSort() 除外，它应该是唯一的 public 方法，如果您实现sortableList class).
中的代码该代码也不使用 last 指针或 prev 链接，因为它们在 mergeSort 中不需要，并且可以在排序后轻松重建（这里很容易意味着 'in O(n) time' 使用单个传递排序后的列表）。

// split the list and return a pointer to a second half
node * split(node * fast)
{
    // assert(fast != NULL)

    node * finger = fast;
    fast = fast->next;

    while (fast != NULL)
    {
        fast = fast->next;
        if (fast != NULL)
        {
            fast = fast->next;
            finger = finger->next;
        }
    }

    node * splitB = finger->next;
    finger->next = NULL;
    return splitB;
}

// sort the (sub)list and return its new head
node* mergeSort(node * a)
{
    // assert(a != NULL)    // list not empty

    node * b = split(a);    // take second half

    if (b != NULL)
    {
        a = mergeSort(a);
        b = mergeSort(b);

        a = merge(a, b);
    }
    return a;
}

void mergeSort()
{
    if (head != NULL)       // make sure list isn't empty
        head = mergeSort(head);
}

编辑 2

您的 merge 例程似乎太长且过于复杂。请参阅下面的较短版本。是不是更红了？

node * merge(node * a, node * b)
{
    // assert(a != NULL)
    // assert(b != NULL)

    node * head, * tail;

    if (a->data <= b->data)
        head = a, a = a->next;
    else
        head = b, b = b->next;
    tail = head;

    while (a != NULL && b != NULL)
    {
        if (a->data <= b->data)
            tail->next = a, a = a->next;
        else
            tail->next = b, b = b->next;
        tail = tail->next;
    }

    if (a != NULL)
        tail->next = a;
    else
        tail->next = b;

    return head;
}

如果您创建临时 node 变量，您也可以删除第一个 if（但有时不允许这样做，例如 node class太复杂或者它的构造会导致一些不需要的副作用):

node * merge(node * a, node * b)
{
    // assert(a != NULL)
    // assert(b != NULL)

    node head, * tail = &head;

    while (a != NULL && b != NULL)
    {
        if (a->data <= b->data)
            tail = tail->next = a, a = a->next;
        else
            tail = tail->next = b, b = b->next;
    }

    tail->next = a ? a : b;

    return head->next;
}

这就是如何在前向链表排序后恢复 prev 链接：

void restoreBacklinks()
{
    node * prev = NULL;

    for (node * p = head; p != NULL; p = p->next)
    {
        p->prev = prev;
        prev = p;
    }

    tail = prev;
}

void mergeSort()
{
    if (head != NULL)       // make sure list isn't empty
    {
        head = mergeSort(head);
        restoreBacklinks();
    }
}

Answer 2

要进行合并排序，您将不得不拆分列表。例如，总是在头部和尾部分裂是没有意义的。它总是在整个列表上拆分，而不是列表中越来越小的部分。所以你的拆分必须看起来像这样：

void split(node *& a, node *& b)
{
    node * finger = a;
    node * fast = a->next;
    while (fast != NULL)
    {
        fast = fast->next;
        if (fast != NULL)
        {
            fast = fast->next;
            finger = finger->next;
        }
    }
    b = finger->next;
    b->prev->next = NULL;
    b->prev = NULL; 
}

我建议将变量名称 fast 和 finger 更改为更具描述性的名称。

Merge 和 mergeSort 将需要类似的修改。

编辑了 post 以按照 C++ 方式执行操作。抱歉。

合并排序不拆分列表的右侧

Merge sort does not split the right side of the list

c++

sorting

mergesort