以下代码对数组中的反转计数有分段错误。
#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;
}
问题似乎在上面的函数中,我已经声明了
L
和R
数组。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/