无法在 C++ 中的双向链表上实现合并排序

Question

（仅供参考，有史以来第一个 post 到 Whosebug）

我正在尝试在 C++ 中为双重 linked 列表实现合并排序。虽然排序确实有效，但它没有正确重建列表。它似乎是一个没有 "previous" 指针的单 linked 列表；该列表可以向前读取，但是当我尝试向后显示它时，只显示最后一个节点。我认为 "merge" 例程一定有问题，但我找不到它在哪里。

首先，这里是创建列表的双重 linked 节点的代码：

#include <iostream>
using namespace std;

class DLNode
{
public:
    int data;
    DLNode* prev;
    DLNode* next;

    DLNode();
    DLNode(int entry);
};

DLNode::DLNode()
{
    data = -99999;
    prev = NULL;
    next = NULL;
}

DLNode::DLNode(int entry)
{
    data = entry;
    prev = NULL;
    next = NULL;
}

这是双重 linked 列表 class，简化为仅构建列表并对其进行排序所需的那些函数：（仅供参考，这遵循 "C++ Programming: Program Design Including Data Structures"，第 6 版 D.S.Malik)

#include "DLNode.h"  //the doubly-linked node class above
using namespace std;

class DblLinkList
{
private:
    DLNode* head;  //pointer to head of list
    DLNode* last;  //pointer to end of list
    int count;  //keeps count of number of items in list
    //these 3 methods are used only to implement a mergeSort, called within sort() function
    void splitList(DLNode* first1, DLNode*& first2);
    DLNode* mergeList(DLNode* first1, DLNode* first2);
    void recMergeSort(DLNode* &head);

public:
    DblLinkList();

    void displayForwards();
    void displayBackwards();
    int getCount();

    void addToFront(int entry);
    void addToBack(int entry);
    int popFront();
    int popBack();
    void sort();        
};

DblLinkList::DblLinkList()
{
    head = NULL;
    last = NULL;
    count = 0;
}

void DblLinkList::addToFront(int entry)
{
    DLNode* tmpDLNode = new DLNode();

    tmpDLNode->data = entry;  
    head->prev = tmpDLNode;
    tmpDLNode->next = head;  
    head = tmpDLNode;  
    head->prev = NULL;
    count++;

    if (last==NULL)
        last=tmpDLNode;
    //cout << head->data << endl;
    //cout << last->data << endl;
}

void DblLinkList::addToBack(int entry)
{
    DLNode* tmpDLNode = new DLNode();
    tmpDLNode->data = entry;  
    tmpDLNode->next = NULL;  
    tmpDLNode->prev = NULL;  

    if (head==NULL)  //if list is empty
    {
        head=tmpDLNode;
        last=tmpDLNode;
    }
    else  //if list is not empty
    {
        tmpDLNode->prev = last;
        last->next = tmpDLNode;
        last = tmpDLNode;
        last->next = NULL;

        //cout << head->data << endl;
        //cout << last->data << endl;
    }
    count++;
}

int DblLinkList::popFront()
{
    DLNode* trash;
    int popval;

   if (head==NULL)
       cout << "List empty, nothing to pop." << endl;
   else
   {
       trash = head;
       popval = head->data;
       head = head->next;
       head->prev = NULL;
       count--;
       delete trash;
   }
   return popval;
}

int DblLinkList::popBack()
{
    DLNode* trash;
    int popval;

   if (head==NULL)
       cout << "List empty, nothing to pop." << endl;
   else if (head==last) 
       popFront();
   else
   {
       trash = last;
       popval = last->data;
       last = last->prev;
       last->next = NULL;
       count--;
       delete trash;
   }
   return popval;
}


void DblLinkList::displayForwards()
{
    DLNode* yad;

    yad = head;

    while (yad != NULL)
    {
        cout << yad->data << " ";
        yad = yad->next;
    }
    cout << endl;
}

void DblLinkList::displayBackwards()
{
    DLNode* yad;

    yad = last;

    while (yad != NULL)
    {
        cout << yad->data << " ";
        yad = yad->prev;
    }
    cout << endl;
}

int DblLinkList::getCount()
{
    return count;
}

//private function used only to implement sort()
void DblLinkList::splitList(DLNode* first1, DLNode* &first2)  
{
    DLNode* middle;
    DLNode* current;

    if(first1==NULL)
        first2 = NULL;
    else if (first1->next == NULL)
        first2 = NULL;
    else
    {
        middle = first1;
        current = first1->next;

        if (current != NULL)
            current = current->next;
        while (current != NULL)
        {
            middle = middle->next;
            current = current->next;
            if (current != NULL)
                current = current->next;
        }
        first2 = middle->next;
        middle->next = NULL;
        first2->prev = NULL;
    }
}

DLNode* DblLinkList::mergeList(DLNode* first1, DLNode* first2)
{
    DLNode* lastSmall;
    DLNode* newHead;

    if (first1==NULL)
        return first2;
    else if (first2==NULL)
        return first1;
    else
    {   //first figure out which list's head should be the head of the merged list
        if (first1->data < first2->data)
        {
            newHead = first1;
            first1 = first1->next;
            lastSmall = newHead;
        }
        else
        {
            newHead = first2;
            first2 = first2->next;
            lastSmall = newHead;
        }

        while ((first1 != NULL) && (first2 != NULL))
        {
            if (first1->data < first2->data)
            {
                lastSmall->next = first1;
                lastSmall = lastSmall->next;
                first1 = first1->next;
            }
            else
            {
                first2->prev = lastSmall;
                lastSmall->next = first2;
                lastSmall = lastSmall->next;
                first2 = first2->next;
            }
        }
        if (first1 == NULL)
            lastSmall->next = first2;
        else
            lastSmall->next = first1;

        return newHead;
    }
}

void DblLinkList::recMergeSort(DLNode* &head)
{
    DLNode* otherHead;

    if (head != NULL)
        if (head->next != NULL)
        {
            splitList(head, otherHead);
            recMergeSort(head);
            recMergeSort(otherHead);
            head = mergeList(head,otherHead);
        }
}

//public sort function
void DblLinkList::sort()
{
    recMergeSort(head);
    if (head == NULL)
        last = NULL;
    else
    {
        last = head;
        while (last->next != NULL)
            last = last->next;
    }
}

这里有一个驱动程序来测试它：

#include <iostream>
#include "DblLinkList.h" //the doubly-linked list class above
using namespace std;

int main()
{
    DblLinkList myDLList;

    myDLList.addToBack(10);
    myDLList.addToBack(40);
    myDLList.addToBack(30);
    myDLList.addToBack(20);
    myDLList.addToBack(50);
    myDLList.addToBack(70);
    myDLList.addToBack(80);
    myDLList.addToBack(60);
    myDLList.addToBack(90);
    myDLList.addToBack(100);

    myDLList.displayForwards();
    myDLList.displayBackwards();

    myDLList.sort();
    myDLList.displayForwards();
    myDLList.displayBackwards();
    cout << myDLList.getCount() << endl;

    system("pause");
    return 0;
}

如果你能运行这个，你会看到排序的列表被 displayForwards 正确显示，但没有被 displayBackwards 反向显示。

希望我提供了足够的信息来帮助您！我猜合并步骤中向后 link 的部分一定有问题，我只是没看到！

干杯，提前致谢！

Answer 1

合并步骤的主要问题发生在一个子列表先用完的情况下。其他列表的其余部分附加到合并列表的末尾，但保留了 none 的 prev 指针。在 mergeList() 的底部，它应该是这样的：

    if (first1 == NULL) {
        lastSmall->next = first2;
        first2->prev = lastSmall; <------
    }
    else {
        lastSmall->next = first1;
        first1->prev = lastSmall; <------
    }
    return newHead;

此外，主 while 循环中的不对称性似乎是个错误

    while ((first1 != NULL) && (first2 != NULL))
    {
        if (first1->data < first2->data)
        {
            first1->prev = lastSmall; <------ missing?
            lastSmall->next = first1;
            lastSmall = lastSmall->next;
            first1 = first1->next;
        }
        else

最后，有几个地方没有正确处理单个元素列表，例如addToFront().

希望对您有所帮助！

无法在 C++ 中的双向链表上实现合并排序

Trouble implementing merge sort on doubly-linked list in C++

c++

sorting

mergesort

doubly-linked-list