合并排序函数中的分段错误-核心转储

Question

有人能解释一下为什么以下代码段会导致分段错误(core dumped)吗？我确定我有一个游离指针或者其他问题，但是我找不到它。任何帮助都将不胜感激。我正在尝试创建一个归并排序函数。

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)++;
    }
}

- udubb2012

---

是时候学习如何使用调试器了。确定崩溃发生的位置，然后向后工作，了解您的程序如何进入无效状态。 - Jonathon Reinhart

代码审查并不能帮助你找到崩溃错误。在调试器中运行代码，调试器会准确地告诉你哪一行代码导致了崩溃。 - Carey Gregory

这里有一个好的技巧：在释放内存的同时，将内存分配在同一位置。您的代码释放了辅助数组“left”和“right”，但从未为它们分配内存。 - chqrlie

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数组不是问题，但如果将算法推广到更复杂的元素，则很有用）。

- chqrlie

---

问题已经解决了。非常感谢您详细的解释，而不仅仅是发布更正后的代码。 - udubb2012