gpt4 book ai didi

c++ - 链表上的合并排序

转载 作者:行者123 更新时间:2023-12-01 14:52:30 25 4
gpt4 key购买 nike

我正在尝试对链表进行合并排序。

我将头部变量保持在全局范围内,并应用了基本算法,即分而治之。

我不明白为什么会出现段错误。

我知道我可以通过传递 head 作为引用来做到这一点,但我仍然需要知道为什么会这样。

#include <bits/stdc++.h>

using namespace std;

class Node {
public:
int data;
Node *next;
};
Node *head;

void push(Node **head_ref, int x) {
Node *temp = new Node();
temp->next = *head_ref;
temp->data = x;
*head_ref = temp;
}

void split(Node *temp, Node **a, Node **b) {
Node *slow;
Node *fast;
slow = temp;
fast = temp->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*a = temp;
*b = slow->next;
slow->next = NULL;
}

Node *mergesort(Node *a, Node *b) {
if (a == NULL) {
return b;
} else
if (b == NULL) {
return a;
}
if (a->data < b->data) {
a->next = mergesort(a->next, b);
return a;
} else {
b->next = mergesort(a, b->next);
return b;
}
}

void merge(Node **head_ref) {
Node *head = *(head_ref);
Node *a;
Node *b;
if (head == NULL || head->next == NULL) {
return;
}
split(head, &a, &b);
merge(&a);
merge(&b);
head = mergesort(a, b);
}

void print(Node *n) {
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}

我的主要方法如下:
int main() {
Node *head;
push(&head, 1);
push(&head, 3);
push(&head, 6);
push(&head, 4);
push(&head, 2);
print(head);
merge(&head);
cout << endl;
print(head);
}

最佳答案

您的代码中有一些简单的错误:

  • head被定义为全局变量,但在 main 中也定义为局部变量, 所以这个局部变量在 main 内部使用而不是全局的。确实不需要全局变量。
  • 局部变量 Node *head;main()未初始化。所有push调用将成功,构造 head 指向的列表但是对于 next 有一个未定义的指针1 之后的节点, print试图取消引用这个指针会崩溃。行为未定义,您可能会在 head 中偶然出现空指针但是您可能反而有一个无效的指针,从而导致未定义的行为。初始化 headNULL :
        Node *head = NULL;
  • merge 结尾,您不会通过 head_ref 更新头指针,所以调用者中的变量不会更新。写这个:
        *head_ref = mergesort(a, b);

  • 请注意, merge 会更简单。接收 Node *head指针并返回更新后的 Node *头指针。

    另请注意,您的函数名称令人困惑: merge应命名为 mergesort反之亦然。

    这是修改后的版本:

    #include <bits/stdc++.h>

    using namespace std;

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

    void push(Node **head_ref, int x) {
    Node *temp = new Node();
    if (temp) {
    temp->next = *head_ref;
    temp->data = x;
    *head_ref = temp;
    }
    }

    void split(Node *temp, Node **a, Node **b) {
    Node *slow = temp;
    Node *fast = temp->next;
    while (fast != NULL) {
    fast = fast->next;
    if (fast != NULL) {
    slow = slow->next;
    fast = fast->next;
    }
    }
    *a = temp;
    *b = slow->next;
    slow->next = NULL;
    }

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

    Node *mergesort(Node *head) {
    Node *a;
    Node *b;
    if (head == NULL || head->next == NULL) {
    return head;
    }
    split(head, &a, &b);
    a = mergesort(a);
    b = mergesort(b);
    return merge(a, b);
    }

    void print(const Node *n) {
    while (n != NULL) {
    cout << n->data << " ";
    n = n->next;
    }
    count << endl;
    }

    int main() {
    Node *head = NULL;
    push(&head, 1);
    push(&head, 3);
    push(&head, 6);
    push(&head, 4);
    push(&head, 2);
    print(head);
    head = mergesort(head);
    print(head);
    return 0;
    }

    关于c++ - 链表上的合并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62229704/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com