c - 我的合并排序有什么问题？

Question

我想使用指针编写合并排序，但是当我尝试用 C 编写时，出现了段错误。我预计会出现段错误，但不是我实际得到它的地方。这是我的代码:

#include <stdio.h>
#include <stdlib.h>


int *merge(int [], int *, int *, int *); 
int *mergesort(int [], int *, int *); 

int main(){
    int n[] = {4, 2, 9, 5, 10, 11, 1, 0}; 
    int *m = mergesort(n, n, n + 7); 

    int i;
    for(i = 0; i < 7; i++)
        printf("[%d]\n", n[i]); 

    return 0;

}

int *mergesort(int *a, int *p, int *r){
    if(p >= r)
        return a; 

    int *q = p + (q - p)/2;
    mergesort(a, p, q); 
    mergesort(a, q+1, r); 

    return merge(a, p, q, r);   
}
/*0, 1, 2, 3, 4, 5, 6, 7*/
int *merge(int *a, int *p, int *q, int *r){
    /*int *arrone = new int[q - p + 1]; 
    int *arrtwo = new int[r - q]; */

    int *arrone = malloc(sizeof(int) * (q - p + 1));
    int *arrtwo = malloc(sizeof(int) * (r - q)); 

    int i;
    for(i = 0; p + i <= q; i++)
        arrone[i] = p[i]; 

    for(i = 0; q + i + 1 <= r; i++)
        arrtwo[i] = *(q + 1 + i); 

    int j;
    for(j = 0; arrone <= q && arrtwo <= r; j++){
        if(*arrone < *arrtwo)
            a[j] = *arrone, arrone++; 
        else
            a[j] = *arrtwo, arrtwo++; 
    }

    if(arrone <= q)
        for(; p + j <= r; j++)
            a[j] = *arrone++; 
    else
        for(; p + j <= r; j++)
            a[j] = *arrtwo++;

    free(arrone);
    free(arrtwo);

    return a; 
}

现在奇怪的是，我在第一次调用 mergesort 时就得到了这个段错误。在 DDD 中，它一接触到这个函数就会出错。 DDD 给了我这个

Program received signal SIGSEGV, Segmentation fault. (Very long address) in mergesort (a<= error reading variable: Cannot access memory at address 0x7fffff7feff8, p=< error reading variable: Cannot access memory at 0x7fffff7feff0, r=< error reading variable: cannot access memory at address 0x7fffff7fefe8) at (line where mergesort begins its definition)

然而，当我回溯它时，它在合并中调用第二个合并排序的行提供了无限数量的调用，尽管我不明白为什么这与调用第一个合并排序的位置有任何不同(实际上那个也在我的 gdb 回溯的第 0 帧中突出显示)

这次我做错了什么？

Answer 1

这里的q是什么？您正在声明 *q 并在表达式中使用 q 进行初始化..

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

此外，

a[j] = *arrtwo++;   <-- Here increment of pointer is happening instead of value

应该用作

a[j] = (*arrtwo)++;

因此随后在 free(..) 中失败。检查所有此类实例。

我认为你的指针递增逻辑是正确的，但你不能释放更新的指针，它可能指向其他东西。