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 回答