C ++合并排序的链表不对前两个索引进行排序

Question

我在尝试弄清楚如何递归合并排序我的链表时有点迷茫。我尝试遵循一些指南，但我对所有指针和递归有点迷茫。一旦列表每个都有一个节点，感觉问题就出在合并函数上。

我有一个 Node class 和一个列表 class。我省略了其他成员函数以使其更具可读性。这是 classes。对不起，一些变量名不是函数中最好的。

class Node {
  public:
    int val;
    Node *next;
};

class Linked_list {
  private:
    unsigned int length;
    Node *head;
    Node *tail;
  public:
    void sort_ascending();
    void merge_sort(Node **);
    void halve(Node *&, Node *&, Node *&);
    Node* merge(Node *, Node *);
};

我从 sort_ascending() 开始，它创建一个 Node 指针并将其设置为列表中的第一个节点，然后使用该指针作为参数调用 merge_sort。

void Linked_list::sort_ascending() {
    Node *h = head->next;
    merge_sort(&h);
}

merge_sort 检查前两个索引是否为 NULL，如果为 returns。否则链表减半

void Linked_list::merge_sort(Node **h) {
    Node *t = *h;
    Node *a;
    Node *b;
    if ((t == NULL) || (t->next == NULL)) {
        return;
    }
    halve(t, a, b);
    merge_sort(&a);
    merge_sort(&b);
    *h = merge(a, b);
    return;
}

这是将列表分成两半的函数。

void Linked_list::halve(Node *&t, Node *&a, Node *&b) {
    Node *h1 = t;
    Node *h2 = t->next;
    while (h2 != NULL) {
        h2 = h2->next;
        if (h2 != NULL) {
            h1 = h1->next;
            h2 = h2->next;
        }
    }
    a = t;
    b = h1->next;
    h1->next = NULL;
}

最后是合并功能。

Node *Linked_list::merge(Node *a, Node *b) {
    Node *h = NULL;
    if (a == NULL) {
        return b;
    }
    if (b == NULL) {
        return a;
    }
    if (a->val <= b->val) {
        h = a;
        h->next = merge(a->next, b);
    } else {
        h = b;
        h->next = merge(a, b->next);
    }
    return h;
}

当我运行我的程序和 enter/print 一些值时，我得到：

9 4 32 2 6

然后当我对其进行排序时，输出变为：

9 4 2 6 32

Answer 1

在sortAscending函数中

void Linked_list::sort_ascending(){
   Node *h = head->next;
   merge_sort(&h);
}

见上文，您将 node*h 指向 head 的下一个。不是头本身。也许这就是为什么它在对链表进行排序时排除了第一项，即 head 本身。

Answer 2

@VeryBhatti 指出的其他原因，

while(h2 != NULL){
    h2 = h2->next;
    if(h2 != NULL){
        h1 = h1->next;
        h2 = h2->next;
    }
}

我不明白你的 halve 函数的逻辑。由于 h1 也在沿 h2 移动，当 while 语句中断时，h1 将始终指向倒数第二个元素而不是中心。

为什么不使用 length 变量将列表减半？简化代码将极大地帮助您自己调试代码。

此外，同时使用 reference 和 pointer 似乎会使您的代码复杂化。我建议首先尝试以 c 风格而不是 cpp 风格来实现它。因为您使用的是链表，所以您应该能够在不使用指向指针的指针的情况下实现这一点。

再次尝试尽可能简化您的代码并寻找其他合并排序示例。

C ++合并排序的链表不对前两个索引进行排序

C++ Merge sort of linked list is not sorting the first two indices

c++

mergesort

singly-linked-list