c - C 中的数组大小有限制吗？

Question

首先，here is my code只是为了让您能够跟上。

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

#define MAX 10000000

long long min(long long a, long long b, long long c) {

    long long temp_min = a;
    if (b < temp_min) temp_min = b;
    if (c < temp_min) temp_min = c;

    return temp_min;

}

long long numOp (long long n, long long memo[]) {

    memo[1] = 0;

    for (int i = 2; i <= n; i++) {

        long long guess_1 = MAX, guess_2 = MAX, guess_3 = MAX;

        guess_1 = memo[i - 1] + 1;

        if (i % 2 == 0) guess_2 = memo[i / 2] + 1;

        if (i % 3 == 0) guess_3 = memo[i / 3] + 1;

        memo[i] = min(guess_1, guess_2, guess_3);

    }

    return memo[n];

}

int main (void) {
    // Read the input from the user
    long long n, v = 0, N;
    scanf ("%lld", &n);
    N = n;

    long long num_operations[n + 1];
    long long sequence[n];

    for (long long i = 1; i <= n; i++) {
        num_operations[i] = -1;
    }

    for (long long l = 0; l < n; l++) {
        sequence[l] = -1;
    }

    // Compute the minimum number of operations required to get to n starting form 1
    long long op = numOp (n, num_operations);

    // Print the result
    printf ("%lld\n", op);

    sequence[v++] = n;
    while (n > 1) {

        if (num_operations[n - 1] < num_operations[n]) {

            //printf("%lld ", n - 1);
            sequence[v++] = n - 1;
            n = n - 1;

        } else {

            long long temp1 = -1, 
                      temp2 = -1;

            if (n % 2 == 0) {
                temp1 = num_operations[n / 2];
            } 

            if (n % 3 == 0) {
                temp2 = num_operations[n / 3];
            }

            if (temp2 < temp1) {

                //printf("%lld ", n / 2);
                sequence[v++] = n / 2;
                n = n / 2;

            } else {

                //printf("%lld ", n / 3);
                sequence[v++] = n / 3;
                n = n / 3;

            }
        }
    }

    // Print the intermediate numbers from 1 up through n
    for (long long k = N - 1; k >= 0; k--) {
        if (sequence[k] != -1)
            printf("%lld ", sequence[k]);
    }
    printf("\n");

    return 0;
}

所以我正在解决这个问题，输入 n 使得 n 在 1 到 1,000,000 之间。该程序在输入高达 100,000 个时运行良好，但一旦达到(甚至小于)1,000,000，我就会出现段错误。

我调试了程序，试图缩小可能性，发现段错误发生在第 52 行，我尝试在该行访问数组元素。

我唯一的猜测是，C 中的数组的大小存在某种限制，如果是这样，你们知道有什么办法吗？

Answer 1

您正在使用VLA s 作为自动变量分配在 call stack 上。因此，您受到调用堆栈最大大小的限制(通常只有几兆字节，详细信息取决于操作系统和计算机)。

您应该在堆上分配它们。了解 C dynamic memory allocation 。所以用代码代替

long long *num_operations = calloc (n + 1, sizeof(long long));
long long *sequence = calloc(n, sizeof(long long));

不要忘记测试 calloc 是否失败:

if (!num_operations) 
    { perror("num_operations calloc"); exit(EXIT_FAILURE); }

同样对于sequence的calloc

不要忘记释放(例如在main末尾)

free (num_operations);
free (sequence);

避免memory leaks (使用valgrind来调试它们)。在您的特定情况下，您可能无法免费，因为 virtual address space程序(在 Linux 或 Windows 等上)的 process 被删除时已结束。

仅供引用，malloc、calloc 和 free 正在使用 system calls ，如mmap(2) ，更改虚拟地址空间。但 C 标准库通常不会向操作系统释放(使用 munmap)free-d 内存，而是将其标记为可由将来的 malloc 重用-s 或 calloc-s。

实际上，一旦不需要内存，您最好立即释放内存(因此您通常可以在同一个内存中calloc和free常规)。阅读关于garbage collection技术、概念和术语是有值(value)的。

当然，堆分配的内存也是有限的(因为您的计算机的资源有限)，但该限制可能取决于计算机，并且通常要大得多(笔记本电脑上至少为 GB，在 super 计算机上可能为 TB)；有时，即使资源耗尽(这是我通常禁用的操作系统功能)，calloc 似乎也能工作(请阅读 memory overcommitment )。在 POSIX 和 Linux 系统上 setrlimit(2)可以用来降低(或稍微改变)该限制。