0

私は一日中マージソートをコーディングしようとしましたが、なぜそれが機能しないのかわかりません:(私は何をするにしてもSIGSEGVを持っています!

スタック トレースは次のとおりです。

#0  0x00401435 in tabLen (tab=0x1) at CodeBlocks\mergeSort.c:7
#1  0x004014d8 in mergeTabs (tab1=0x1, tab2=0x1) at CodeBlocks\mergeSort.c:26
#2  0x004016b3 in mergeSort (tab=0x3f1000, size=2) at CodeBlocks\mergeSort.c:51
#3  0x0040168b in mergeSort (tab=0x3f0fd8, size=3) at CodeBlocks\mergeSort.c:51
#4  0x0040168b in mergeSort (tab=0x3f2fb0, size=5) at CodeBlocks\mergeSort.c:51
#5  0x004013ea in main () at CodeBlocks\main.c:9

#1 と #2 の間で、配列が消えたようで、理由がわかりません...

そして、これが私が試した実装です: 

int tabLen(int *tab)
{
    int i = 0;

    for (; tab && tab[i] && tab[i] != ENDTAB; ++i)
        ;
    return i;
}

int *copy(int *tab, int beg, int end)
{
    int size = end - beg + 1;
    int *res = malloc(size * sizeof(int));
    int i = beg;

    for (; i < end; ++i)
        res[i - beg] = tab[i];
    res[i - beg] = ENDTAB;
    return res;
}

int *mergeTabs(int *tab1, int *tab2)
{
    int len1 = tabLen(tab1);
    int len2 = tabLen(tab2);
    int *res = malloc((len1 > len2) ? (len1+1) * sizeof(int) : (len2+1) * sizeof(int));
    int i = 0;
    int t1 = 0;
    int t2 = 0;

    printf("len1:%d | len2:%d\n", tabLen(tab1), tabLen(tab2));
    for (; t1 < len1 && t2 < len2; ++i)
        res[i] = (tab1[t1] < tab2[t2]) ? tab1[t1++] : tab2[t2++];
    while (t1 < len1)
        res[i++] = tab1[t1++];
    while (t2 < len2)
        res[i++] = tab2[t2++];
    res[i] = ENDTAB;
    return res;
}

int *mergeSort(int *tab, int size)
{
    int *t1 = copy(tab, 0, size/2);
    int *t2 = copy(tab, size/2, size);

    if (tabLen(tab) <= 1)
        return;
    return mergeTabs(mergeSort(t1, tabLen(t1)), mergeSort(t2, tabLen(t2)));
}

何か案は ？

ありがとう、フロリアン

4

1 に答える 1

0

コードをざっと見てみると (ここでローカルに実行したので、ENDTAB が -1 であると仮定しました)、tabLen() 関数で無効なポインターが取得されていることに気付きました。出力を以下に示します。

% ./a.out 
0x7fffb7dec6e0
0x7b9030
0x7b9030
0x7b9070
0x7b9070
0x7b9050
0x7b9050
0x1
Segmentation fault

私がやっているのは printf("%p\n", tab); です。tabLen() 関数で。あなたのコードにはおそらく他の問題もあります。ENDTAB に関する私の仮定が間違っている場合は、訂正してください。

tabLen(tab) <= 1 の場合、mergeSort() で適切な値を返すようにして、それを使用してください。

編集

スタック トレースで無効なポインターに気付きました。私の悪い。

NULL を返してもコードはクラッシュしませんが、確かに問題があります。これは、tabLen() でタブが非 NULL であることをチェックしてクラッシュしないからです。

于 2012-09-11T20:09:18.377 に答える