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如果混淆，则用于 2 个不同的目的。实际上，您需要复制两半以传递给 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 的数组来说不是问题，但如果将算法推广到更复杂的元素，则很有用)。