c - 递归-段错误(核心已转储)

所以我写了一个代码作为递归的练习。它的目的是通过递归地将数组的最后一个元素替换为最大的元素，按升序对整数数组进行排序。我一直有分割错误，找不到问题所在。这是密码。

#include <stdio.h>

#define N 10

void selection_sort(int array[], int length);

int main (void)
{
    int array[N];
    int i;

    printf("Enter a series of integrs: ");
    for(i = 0; i < N; i ++)
    {
        scanf("%d", &array[i]);
    }

    selection_sort(array, N);

    printf("In sorted order: ");
    for(i = 0; i < N; i ++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

void selection_sort(int array[], int length)
{
    int max = array[0];
    int temp;
    int i;
    int maxPlace;

    if (length < 2)
    {
        return;
    }

    for (i = 1; i < length; i ++)
    {
        if (array[i] > max)
        {
            max = array[i];
            maxPlace = i;
        }
    }
    temp = array[length - 1];
    array[length - 1] = max;
    array[maxPlace] = temp;

    selection_sort(array, length - 1);
}

最佳答案

因为maxPlace可能未初始化。而且因为您错误地读取了输入，所以即使用户只输入了1，也总是会得到N元素。
这说明了我是如何追踪到这件事的。通常我会用Valgrind来追踪一个segfault，它会告诉我违规的行，但是在OS X上它现在坏了，所以这里有一种老式的打印和演绎方法。
首先，如果离开已分配内存的末尾（例如使用未初始化的变量），编译器标志将导致运行时失败。这通常可以捕捉到记忆错误一旦发生而不是遥远的道路。它也会告诉你发生在哪个函数中。

$ make
cc -fsanitize=address -Wall -Wshadow -Wwrite-strings -Wextra -Wconversion -std=c99 -pedantic -g `pkg-config --cflags glib-2.0`   -c -o test.o test.c
cc `pkg-config --libs glib-2.0` -lssl -lcrypto -fsanitize=address  test.o   -o test

$ ./test
Enter a series of integrs: 5
ASAN:DEADLYSIGNAL
=================================================================
==80879==ERROR: AddressSanitizer: SEGV on unknown address 0x7ffee6679358 (pc 0x0001095a7cac bp 0x7ffee6659330 sp 0x7ffee66592b0 T0)
    #0 0x1095a7cab in selection_sort (/Users/schwern/tmp/./test+0x100001cab)
    #1 0x1095a78db in main (/Users/schwern/tmp/./test+0x1000018db)
    #2 0x7fff73819114 in start (/usr/lib/system/libdyld.dylib+0x1114)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV (/Users/schwern/tmp/./test+0x100001cab) in selection_sort
==80879==ABORTING
Abort trap: 6

现在我知道它在-fsanitize=address中。我可以开始添加调试打印语句来缩小范围。这个循环是可疑的，也许你是从数组中走出来的，所以我从这个开始。我还想知道你是不是复发了，所以我已经打印了一份。

puts("Entering loop");
for (i = 1; i < length; i ++)
{
    printf("i: %d\n", i);
    if (array[i] > max)
    {
        max = array[i];
        maxPlace = i;
    }
    puts("Loop next");
}
puts("Leaving loop");

temp = array[length - 1];
array[length - 1] = max;
array[maxPlace] = temp;

puts("Recursing");
selection_sort(array, length - 1);

试试看。。。

$ ./test
Enter a series of integrs: 5
Entering loop
i: 1
Loop next
i: 2
Loop next
i: 3
Loop next
i: 4
Loop next
i: 5
Loop next
i: 6
Loop next
i: 7
Loop next
i: 8
Loop next
i: 9
Loop next
Leaving loop
ASAN:DEADLYSIGNAL

不，你不能离开阵列。但你也不是在递归。所以它必须在循环之后的几行代码中。好的，把它们标出来。没什么奇怪的，当范围这么小的时候，数字就可以了。

puts("1");
temp = array[length - 1];
puts("2");
array[length - 1] = max;
puts("3");
array[maxPlace] = temp;

运行。。。

$ ./test
Enter a series of integrs: 5
Entering loop
i: 1
Loop next
i: 2
Loop next
i: 3
Loop next
i: 4
Loop next
i: 5
Loop next
i: 6
Loop next
i: 7
Loop next
i: 8
Loop next
i: 9
Loop next
Leaving loop
1
2
3
ASAN:DEADLYSIGNAL

现在我知道是在selection_sort()之后和for之前。这意味着它是3。好的，recursing里有什么？

puts("1");
temp = array[length - 1];
puts("2");
array[length - 1] = max;
printf("maxPlace: %d\n", maxPlace);
array[maxPlace] = temp;

运行。。。

$ ./test
Enter a series of integrs: 5
Entering loop
i: 1
Loop next
i: 2
Loop next
i: 3
Loop next
i: 4
Loop next
i: 5
Loop next
i: 6
Loop next
i: 7
Loop next
i: 8
Loop next
i: 9
Loop next
Leaving loop
1
2
maxPlace: 32766
ASAN:DEADLYSIGNAL

array[maxPlace] = temp;为32766意味着它可能包含垃圾。现在我知道了什么变量是问题所在，我可以看看它是如何声明、初始化和设置的，以发现有一种情况下它永远不会被初始化：如果列表是按降序排序的。
但我只输入了一个数字，5！难道maxPlace不应该抓住它吗？不，因为不管你读了多少输入，你总是在maxPlace元素上迭代。

printf("Enter a series of integrs: ");
for(i = 0; i < N; i ++)
{
    scanf("%d", &array[i]);
}

如果我输入if (length < 2)然后点击N结束输入，5将只设置ctrl-d。但循环将继续运行1到9。scanf将失败，因为array[0] = 5已关闭。数组的其余部分将被取消初始化。
你在对元素进行排序，而不是读取的数字。所以不管10个元素是否初始化，都要对它们进行排序。
你很幸运他们正好是0。

$ ./test
Enter a series of integrs: 5
In sorted order: 0 0 0 0 0 0 0 0 0 5

相反，您应该一直阅读到scanf或stdin失败，以先到者为准。这也将保护您免受垃圾输入的影响。并且只对读取的整数排序和打印，而不是数组的最大容量。

int main (void)
{
    int array[N];
    int num_ints;

    printf("Enter a series of integrs: ");
    for(num_ints = 0; num_ints < N; num_ints++)
    {
        if( scanf("%d", &array[num_ints]) < 1 ) {
            break;
        }
    }

    selection_sort(array, num_ints);

    printf("In sorted order: ");
    for(int i = 0; i < num_ints; i ++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}