0

マージソート用の簡単なコードを書きましたが、次のエラーが発生しました。

*** glibc detected *** ./merge: free(): invalid next size (fast): 0x09306058****Segmentation fault (core dumped)

これはコードです：

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

void mergesort(int[], int, int);
void merge(int[], int, int, int);
void printarray(int[]);

int gs;
int main()
{
    int* a,i,s;
    printf("Enter size of the array\n");
    scanf("%d",&s);
    a = (int*)calloc(s,sizeof(int));
    gs = s;
    printf("Enter the array\n");
    for(i=0;i<s;i++)
    {
        scanf("%d",&a[i]);
    }

    printf("Showing the array\n");

    printarray(a);
    printf("\n");

    mergesort(a,0,s-1);

    printf("The sorted array is:\n");
    printarray(a);

    free(a);
    return 0;
}

void mergesort(int a[], int f, int l)
{
    int m;
    if(f<l)
    {
        m = (f+l)/2;
        mergesort(a,f,m);
        mergesort(a,m+1,l);
        merge(a,f,m,l);
    }
}

void merge(int a[], int f, int m, int l)
{
    int* t,i,j,h1,h2;
    t = (int*)calloc(l-f+1,sizeof(int));
    i = h1 = f;
    h2 = m+1;
    while(h1 <= m && h2 <= l)
    {
        if(a[h1] < a[h2])
        {
            t[i] = a[h1];
            h1++;
        }
        else
        {
            t[i] = a[h2];
            h2++;
        }
        i++;
    }

    if(h1>m)
    {
        for(j=h2; j<=l; j++)
        {
            t[i] = a[j];
            i++;
        }
    }
    else
    {
        for(j=h1; j<=m; j++)
        {
            t[i] = a[j];
            i++;
        }
    }

    for(j=f;j<=l;j++)
    a[j] = t[j];

    free(t);
    printarray(a);
}

void printarray(int a[])
{
    int i;
    for(i=0;i<gs;i++)
    printf("%d ",a[i]);
    printf("\n");
}

free(t)エラーは関数の行にあると思いますmerge。何らかの理由で、そのブロックは本来あるべき方法で解放されていません。どうすればこれを修正できますか？

4

2 に答える 2

3

tの範囲外を割り当てています。

int maxIdx = f+l-1;
int * const t = (int*)calloc(maxIdx,sizeof(int));

while(h1 <= m && h2 <= l) {
    assert(h1 < gs);
    assert(h2 < gs);
    assert(i < maxIdx);
    if(a[h1] < a[h2]) {
        t[i] = a[h1];
        h1++;
    } else {
        t[i] = a[h2];
        h2++;
    }
    i++;
}

これを実行すると：

Assertion failed: (i < maxIdx), function merge, file crash.c, line 59.

これはb/cl == 1で発生しているため、iは最大許容インデックスより1大きくなります。

于 2012-09-12T06:20:44.697 に答える
1

マージでは、iをfではなく0に等しくし、配列をコピーしてシフトに戻す場合は、それに応じてインデックスをシフトします。

編集：これはideoneの例で修正されたコードです

于 2012-09-12T06:18:50.657 に答える