c-分割故障-MergeSort函数中的核心转储

Question

有人能深入了解为什么下面的代码部分会导致分段错误(核心转储)吗？我确信我有一个走失的指针什么的；但是，我找不到。如果有任何帮助，我将不胜感激。我正在尝试创建MergeSort函数。

int* mergesort(int* num, int n)
{
int *left, *right;
int middle = n/2;
if (n <= 1)
return num;
//split array into two halves each with elements of 0...middle-1 and middle...n-1 correspondingly
split(num, n, &left, &right, middle);
left = mergesort(left, middle);
right = mergesort(right, n-middle);
merge(num, left, right, middle, n-middle);
free(left);
free(right);
return num;
}       
void split( int* num, int n, int** left, int** right, int middle)
{
left = &num;
right = &num + middle;
} 
int* merge (int* num, int* left, int* right, int sizeLeft, int sizeRight)
{
int i, j, k, n;
i = j = k = 0;
n = sizeLeft + sizeRight;
while (k < n) 
{
if  (i < sizeLeft) 
{
if (j < sizeRight) 
{
insert(num, left, right, &i, &j, &k);
}
else 
{
append(num, left, sizeLeft, &i, &k);
}
}
else 
{
append (num, right, sizeRight, &j, &k);
}
}
}
void insert(int* num, int* left, int* right, int* i, int* j, int*k)
{
if (left[*i] < right[*j]) 
{
num[*k] = left[*i];
(*i)++;
}
else 
{
num[*k] = right[*j];
(*j)++;
}
(*k)++;
}
void append(int* num, int* half, int sizeHalf, int* i, int* k)
{
while (*i < sizeHalf) 
{
num[*k] = half[*i];
(*i)++; (*k)++;
}
}

Answer 1

您不在split函数中分配内存：

void split( int* num, int n, int** left, int** right, int middle) {
left = #
right = &num + middle;
}

上面的代码实际上没有做任何有用的事情：它修改了参数句点。参数本身不能在函数调用后继续存在。

相反，您应该分配数组左半部分和右半部分的副本：

void split(int *num, int n, int **left, int **right, int middle) {
*left = malloc(middle * sizeof(**left));
memcpy(*left, num, middle * sizeof(**left));
*right = malloc((n - middle) * sizeof(**right));
memcpy(*right, num + middle, (n - middle) * sizeof(**right));
} 

这不是mergesort的最有效的实现，因为它使用N*log(N)空间，但它应该可以工作。

一个更有效的解决方案是在合并阶段之前复制数组内容：然后可以将split写入以修改其接收地址的指针：

void split(int *num, int n, int **left, int **right, int middle) {
*left = num;
*right = num + middle;
}

但实际上并不需要它，因为如果混淆的话，将left和right用于两个不同的目的。事实上，您需要复制半个部分以传递给merge函数，这样后者在合并到位时就不会阻塞数据：

mergesort(num, middle);
mergesort(num + middle, n-middle);
left = malloc(middle * sizeof(*left));
memcpy(left, num, middle * sizeof(*left));
right = malloc((n - middle) * sizeof(*right));
memcpy(right, num + middle, (n - middle) * sizeof(*right));
merge(num, left, right, middle, n-middle);
free(left);
free(right);

实际上，在合并阶段之前不需要保存两半：如果修改middle点的计算以确保左半部分与右半部分(middle = (n+1) >> 1;)一样长，则只需要保存左半部分，因为合并阶段不会覆盖尚未复制的元素。使用此方法，您甚至不需要附加右半部分，因为它已经位于正确的位置。

函数split、insert和append应该折叠成merge。通过引用传递所有这些变量会导致代码复杂、容易出错且效率低下。merge和mergesort都无实际目的地返回int*，使它们成为void。

一个不太重要的问题是：insert()中的比较应该是<=，以实现稳定排序(对于int的数组来说不是问题，但如果将算法推广到更复杂的元素，则会很有用)。