C++ 合并排序分段错误？

Question

我似乎在运行这个合并排序时遇到了一些麻烦。当我尝试使用 g++ 运行它时，终端显示“分段错误（核心已转储）”，并且我不知道是什么导致了这种情况发生（您也许可以看出我仍然是初学者）。有人可以帮忙吗？

#include <iostream>
using namespace std;


void merge (int*, int, int, int);

void mergesort (int* A, int p, int r){

 if (p < r){

  int q = (p+r)/2;
  mergesort (A, p, q);
  mergesort (A, q+1, r);
  merge ( A, p , q, r);
  }
}

void merge (int* A, int p, int q, int r){
 

  int n = q-p+1;
  int m = r-q ;
   int L [n+1];
  int R [m+1];

  for (int i=1;i <n+1;i++)
       L[i] = A[p+i-1];

  for (int j=1; j< m+1; j++)
      R[j] = A[q+j];

L[n+1];
R[m+1];

 int i= 1;
 int j=1;

for (int k = p; k= r + 1; k++){
   if (L[i] <= R[j]){
      A[k] = L[i];
       i+=1;
   }
   else{
     j += 1;
    }
}
}


int main() {

int A [15] = {1, 5, 6, 7,3, 4,8,2,3,6};

mergesort (A, 0, 9);

for (int i=0; i <9; i++){
cout << A[i] << endl;
}

return 0;
}

Answer 1

您的实现中存在三件事要么没有意义，要么完全错误：

首先是这些：

L[n+1];
R[m+1];

这些陈述都没有任何效果，我不知道你想做什么。

接下来，一个重大错误：

for (int k = p; k= r + 1; k++){

这个for循环的条件子句是赋值

k = r + 1

。由于

r

不会在循环中的任何位置发生变化，因此表达式为

false

的唯一方式是 if

r == -1

，但事实并非如此。您刚刚在计数器

k

上创建了一个无限循环，它将永远运行到平流层，并在进程索引中写入，并写入在进程中不再有效的内存。因此，这是“未定义的行为”。我相当确定你想要这个： for (int k = p; k< (r + 1); k++){

尽管我无法评论这是否是有效的限制，因为我没有进一步剖析你的算法。我没有花时间进一步调试这个。我留给你了。

编辑

。在你的主要合并排序中，这不是“错误”，而是很容易溢出 int q = (p+r)/2;

考虑这个：

int q = p + (r-p)/2;

尤其是这个：

int L [n+1];
int R [m+1];

使用 C++ 标准不支持的可变长度数组扩展。您可能想使用 

std::vector<int> L(n+1)

等代替。

Answer 2

foo[10]

）并且您执行此语句

 foo[11]

会导致分段错误。您需要做的是使用调试语句打印出您的索引变量（i、j、n、m、p 和 q）并查看其中是否有任何大于您的数组大小

编辑：另一个不相关的问题是你不应该使用

using namespace std

，如果你不小心，这行代码可能会导致范围问题，只是要记住一点:)