检查数组的排序

Question

我正在尝试编写一个代码来检查动态数组是否已排序，但出现错误。代码必须是递归的。

当我输入一个未排序的数组时似乎没有问题，但是当我输入一个排序的数组时程序突然停止：

Process return -1073741571

这是我的代码：

#include <stdio.h>
#include <stdlib.h>
int ordenado(int*);

int main() {
    int i = 0, res = 0;
    int*arr = NULL;
    arr = (int*) malloc(sizeof (int));
    while (arr[i] != 0) {
        i++;
        arr = (int*) realloc(arr, (i + 1) * sizeof (int));
        scanf("%d", &arr[i]);
    }
    res = ordenado(arr);
    printf("\n%d ", res);
    return 0;
}

int ordenado(int* arr) {
    if (arr[0] == 0) {
        return 1;
    }
    if (arr[0] <= arr[1]) {
        return ordenado(arr++);
    }
        else return 0;
    }

Answer 1

抱歉，我的第一个答案不正确。我在下面更正了。

说明

我在循环前加了scanf("%d", &arr[i]);来填充arr[0]
我更改了ordenado函数
1. 当你点击 0 然后 return 1
2. 当你点击 x 但下一个元素是 0 然后 return 1 （注意 || 是短路。如果你不点击 0 然后是下一个元素。所以你也可以在这里检查 0。）
3. 一旦两个数字顺序不对return 0（我认为这样更快）
4. 否则有一个下一个元素是not 0并调用ordenado(++arr)（前缀，不是后缀）

前缀和后缀注意事项：

许多编程语言中前缀和后缀的区别在于执行顺序。假设 i 和 j 在两个语句中执行前都是 0。

i += ++j;

以上代码等价于此

j = j + 1;
i = i + j;

而下面的代码

i += j++;

相当于这个

i = i + j;
j = j + 1;

即在 prefix 中，递增发生在表达式求值之前，而在 postfix 中，递增发生在表达式求值之后。这通常适用于数据类型（即包括指针）。

你的代码行

return ordenado(arr++);

等同于

return ordenado(arr);
a++;

正如@BLUEPIXY 指出的那样，这会导致无限次的函数调用。

更正代码

#include <stdio.h>
#include <stdlib.h>
int ordenado(int*);

int main() {
        int i = 0, res = 0;
        int* arr = NULL;
        arr = (int*) malloc(sizeof (int));
        scanf("%d", &arr[i]);
        while (arr[i] != 0) {
                i++;
                arr = (int*) realloc(arr, (i + 1) * sizeof (int));
                scanf("%d", &arr[i]);
        }
        res = ordenado(arr);
        printf("\n%d ", res);
        return 0;
}

int ordenado(int* arr) {
        if (arr[0] == 0 || arr[1] == 0)
                return 1;
        if (arr[0] > arr[1])
                return 0;
        else
                return ordenado(++arr);
}

示例输入和输出：

Input:  0
Output: 1

Input:  1 newline 0
Output: 1

Input:  1 newline 2 newline 3 newline 0
Output: 1

Input:  2 newline 1 newline 0
Output: 0

Input:  1 newline 2 newline 3 newline 2 newline 3 newline 0
Output: 0

Answer 2

在这些行中：

arr = malloc(sizeof (int));
while (arr[i] != 0)

您不能指望 malloc 的内存有任何特定的价值。 未初始化。

您似乎在使用输入零作为标记。正确的做法是：

int i = 0;
int *arr = malloc(sizeof (int));
do {
    i++;
    arr = realloc (arr, (i + 1) * sizeof (int));
    scanf ("%d", &arr[i-1]);
} while (arr[i-1] != 0);

我还修复了元素零没有被赋值的问题。

我怀疑您遇到的错误是由失控的递归引起的。

Answer 3

您的代码有多个问题：

你在存储它之前读取了数组的第一个元素：它是未初始化的，即使只是读取它也会调用未定义的行为。
您永远不会将第一个元素存储在数组中（在偏移量 0 处）
如果数组至少有一个非零元素，当你比较最后两个元素时，你会得到一个潜在的不匹配，因为最后一个元素是 0;
当你递归时，你在增加它之前传递 arr，因此导致无限递归。你得到错误的事实证明编译器没有处理尾递归，你的代码最终失败并出现 stack overflow.

如果您可以为 ordenado 函数更改 API，您应该将数组中实际元素的数量传递给它。此函数应该是递归的，如果编译器未检测到尾递归，请选择一种限制递归的算法以避免堆栈溢出。

这是我的建议：

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

int ordenado(int *array, int count);

int main() {
    int i = 0, n, res;
    int *arr = NULL;
    while (scanf("%d", &n) == 1 && n != 0) {
        arr = realloc(arr, (i + 1) * sizeof(int));
        if (!arr) {
            printf("out of memory\n");
            return 1;
        }
        arr[i++] = n;
    }
    res = ordenado(arr, i);
    printf("%d\n", res);
    return 0;
}

int ordenado(int *arr, int n) {
    int m = n >> 1;
    return (m == 0) ||
           (ordenado(arr, m) && arr[m - 1] <= arr[m] && ordenado(arr + m, n - m));
}

注意：一次重新分配一个 int 数组效率极低，但这不是本次讨论的主题。

检查数组的排序

Check sorting of an array

c

arrays

sorting

recursion

dynamic

说明

更正代码

示例输入和输出：