为什么我的合并排序程序会触发分段错误？

Question

#include<stdio.h>
void merge(int a[],int left[],int l,int right[],int r){
int i=0,j=0,k=0;
while(i<l&&j<r){
    if(left[i]<=right[j]){
        a[k]=left[i];
        k++;
        i++;
    }
    else{
        a[k]=right[j];
        k++;
        j++;
    }
}
while(i<l){
    a[k]=left[i];
    k++;
    i++;
   }
while(j<r){
    a[k]=right[j];
    k++;
    j++;
  }
}
void mergesort(int a[],int s,int n){
int i;
int mid=(s+n)/2;
int left[mid],right[n-mid];

if(n<2) return;

else{

    for(i=s;i<mid;i++){
        left[i]=a[i];
    }
    for(i=mid;i<n;i++){
        right[i]=a[i];
    }
    mergesort(left,s,mid);
    mergesort(right,n-mid,n);
    merge(a,left,mid,right,n-mid);
   }
 }
int main(int argv,char*argc){
int a[]={9,8,7,5,1,2,4,3,6},i;
printf("sorting....");
mergesort(a,0,9);
for(i=0;i<10;i++){
    printf("\n");
    printf("%d",a[i]);
}
return 1;
}

程序在给出输出之前终止...请帮助... 逻辑取自 mycodeschool.org

Answer 1

正如评论中所写，for(i=mid+1;i<n;i++){ right[i]=a[i]; } 上升到 i=n-1，但是 right 被声明为 int mid=(s+n)/2; int left[mid],right[n-mid]; ：right 太小了，它可以触发未定义的行为，例如分段错误和提前终止。

为了克服这个问题，引入了另一个索引j：int j=0;for(i=mid+1;i<n;i++){ right[j]=a[i]; j++; }，数组left也是如此。必须相应地更改对 mergesort() 的调用：

        mergesort(left,mid);
        mergesort(right,n-mid);

第二个参数 s 已被删除。稍后可以重新引入它以避免不必要的复制并减少内存占用。

额外的小问题是 int a[]={9,8,7,5,1,2,4,3,6},i;...for(i=0;i<10;i++)：a 有 9 个项目，for 循环试图访问第十个项目 a[9]。

这是提供预期输出的更正代码。用 gcc main.c -o main

编译它

#include<stdio.h>
void merge(int a[],int left[],int l,int right[],int r){
    int i=0,j=0,k=0;
    while(i<l&&j<r){
        if(left[i]<=right[j]){
            a[k]=left[i];
            k++;
            i++;
        }
        else{
            a[k]=right[j];
            k++;
            j++;
        }
    }
    while(i<l){
        a[k]=left[i];
        k++;
        i++;
    }
    while(j<r){
        a[k]=right[j];
        k++;
        j++;
    }
}
void mergesort(int a[],int n){
    int i;
    int mid=(n)/2;
    int left[mid],right[n-mid];

    if(n<2) return;

    else{
        int j=0;
        for(i=0;i<mid;i++){
            left[j]=a[i];
            j++;
        }
        j=0;
        for(i=mid;i<n;i++){
            right[j]=a[i];
            j++;
        }
        mergesort(left,mid);
        mergesort(right,n-mid);
        merge(a,left,mid,right,n-mid);
    }
}
int main(int argv,char*argc){
    int a[]={9,8,7,5,1,2,4,3,6},i;
    printf("sorting....\n");
    mergesort(a,9);
    for(i=0;i<9;i++){

        printf("%d\n",a[i]);
    }
    return 0;
}

为什么我的合并排序程序会触发分段错误？

why does my program on mergesort trigger a segmentation fault?

c

sorting

algorithm

data-structures