1

我似乎在让这个合并排序运行时遇到了一些麻烦。当我尝试使用 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;
}

非常感谢!

4

2 回答 2

2

您的实现中有三件事没有意义或完全错误:

首先这些:

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

这些声明都没有任何效果,我不知道你想做什么。

接下来,一个重要的错误:

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

这个 for 循环的条件子句是assignment 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)etc.. 来代替。

于 2013-11-06T01:22:52.100 回答
0

在您的情况下,当您尝试读取变量不存在的内存时,可能会导致分段错误,例如,假设您有一个名为 foo 的大小为 10 的数组(so foo[10]),并且您的此语句foo[11]会导致分段错误.

您需要做的是使用调试语句打印出您的索引变量(i、j、n、m、p 和 q)并查看其中是否有任何大于您的数组大小

编辑:另一个不相关的问题是你不应该使用using namespace std,如果你不小心,这行代码可能会导致范围问题,请记住一些事情:)

于 2013-11-06T01:03:44.143 回答