以下代码对数组中的反转计数有分段错误。

#include <iostream>
#include <limits.h>
using namespace std;

int merge(int *a, int p, int q, int r);

int mergesort(int *a, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        //Dividing the array in two.
        int l = mergesort(a, p, q);
        int r = mergesort(a, q + 1, r);
        int cross = merge(a, p, q, r);
        return (l + r + cross);
    } else
        return 0;
}

这是应该分割数组的mergesort函数。这里似乎没有错误。
int merge(int *a, int p, int q, int r) {
    int inv_count =0;
    int n1 = q - p + 1, n2 = r - q;

    int L[n1 + 1], R[n2 + 1];
    //Two subarrays with last elements as inf.
    L[n1] = INT_MAX; R[n2] = INT_MAX;

    for (int i = p, j = 0; j < n1; i++, j++) L[j] = a[i];//copy left
    for (int i = q + 1, j = 0; j < n2; i++, j++) R[j] = a[i];//copy right

    int i = 0, j = 0, k = p;//merge and count
    while (k <= r) {
        if (L[i] <= R[j]) {
            a[k++] = L[i];
            i++;
        } else {
            a[k++] = R[j];
            inv_count += n2 - j + 1;
            j++;
        }
    }
    return inv_count;
}

问题似乎在上面的函数中,我已经声明了LR数组。
int main() {
    //code
    int n; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << mergesort(a, 0, n - 1);
    return 0;
}

输入示例:5 5 4 3 2 1显示Seg Fault

最佳答案

mergesort中,您有一个阴影问题:

int r = mergesort(a,q+1,r);
                        ^

传递的r参数不是函数中声明的r,而是您刚刚声明的r。那是未定义的行为。

通过“打印调试” merge与代码:

int merge(int *a, int p, int q, int r) {
  int inv_count = 0;
  int n1 = q - p + 1, n2 = r - q;
  std::cout << "merge(a, " << p << ", " << q << ", " << r << ')'<< std::endl;
  std::cout << "\tsize of L: " << (n1 + 1) << std::endl;
  std::cout << "\tsize of R: " << (n2 + 1) << std::endl;
  (...)

我得到了输出:
merge(a, 0, 0, 0)
    size of L: 2
    size of R: 1
merge(a, 0, 1, 0)
    size of L: 3
    size of R: 0
merge(a, 0, 2, 0)
    size of L: 4
    size of R: -1

当您尝试创建大小为负的数组时,会发生段错误。注意传递给合并的r参数,是因为第一个问题。

关于c++ - 我正在访问哪个错误的内存,这会导致段错误?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/57461606/

10-11 23:05
查看更多