c - 在 C 中声明可变大小的数组

Question

我一直在经历Introduction to Algorithms并尝试使用 C 编程语言实现为合并排序提供的伪代码。

这是MERGE过程的伪代码:

虽然我理解这个过程，但当我到达第 3 行时，我正在努力用 C 实现。我的编译器给出了一个错误(在 C99 之后是正确的)expression must have a constant value。

错误发生在伪代码的第 3 行或下面发布的代码中的 int L[n1];

如何创建一个数组，其中包含 n1 和 n2 值，这些值在一次迭代和下一次迭代中不断变化？如有任何建议，我们将不胜感激。

我也遇到了https://www.geeksforgeeks.org/merge-sort/看看它是如何完成的，该网站使用的语法与我相同，但没有任何编译器警告。这是因为编译器版本较旧(C99？)还是我遗漏了什么？

我的代码如下:

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

#define infinite 9999;      //Used for sentinels

void MERGE(A, p, q, r);
void printArray(Arr, size);
void MERGE_SORT(A, p, r);

int main(void)
{
   int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
   int arr_size = sizeof(A) / sizeof(A[0]);

   MERGE_SORT(A, 1, arr_size);

   printf("\nSorted array is \n");
   printArray(A, arr_size);

   return 0;
 }

 void MERGE(int A[], int p, int q, int r)
 {
   int i = 0;
   int j =0;
   int n1 = q - p + 1;      //Computing length of sub-array 1
   int n2 = r - q;          //Computing length of sub-array 2
   int L[n1];               //Creating Left array
   int R[n2];               //Creating Right array

   for (int i = 1; i < n1; i++) {
       L[i] = A[p + i - 1];
   }
   for (int j = 1; j < n2; j++) {
       L[j] = A[q + j];
   }

   L[n1] = 99;  //Placing Ssentinel at the end of array
   R[n2] = 99;

   i = 1;
   j = 1;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not 
   been copied back to A*/
   for (int k = p; k < r; k++) {
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else if (A[k] = L[i])
           j++;
   }

}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
   }
}

编辑

MERGE 的代码更新如下，感谢以下答案和评论的建议。即使下面的代码没有语法或运行时错误，输出仍然不正确。但是，这超出了问题的范围。这里问了另一个问题:Writing Merge Sort Pseudo-Code Procedure in C

 void MERGE(int A[], int p, int q, int r)
 {
   int i = 0;
   int j =0;
   int n1 = q - p + 1;                      
   int n2 = r - q;                          
   int *L = malloc((n1+1) * sizeof(*L));        //Creating Left array
   int *R = malloc((n2+1) * sizeof(*R));            //Creating Right array

   for (int i = 1; i < n1; i++) {
       L[i] = A[p + i - 1];
   }
   for (int j = 1; j < n2; j++) {
       L[j] = A[q + j];
   }

   L[n1] = 99;  //<-- Some modification must be carried out here to allocate 
   R[n2] = 99;  //`99` to the end of array

   i = 1;
   j = 1;

   for (int k = p; k < r; k++) {
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else if (A[k] == L[i])
           j++;
   }

   free(L);
   free(R);  //Freeing both pointers at the end of iteration
}

Answer 1

要创建一个在运行时计算大小的数组，请使用 malloc()

int *L = malloc(n1 * sizeof(*L));
if (L == NULL) {
    // handle error
}

您链接到的代码使用的是可变长度数组，某些 C 编译器支持该数组，但并非所有 C 编译器都支持。见:

Passing array to a function (and why it does not work in C++)

访问数组末尾

L[n1] = 99;  //<-- Some modification must be carried out here to allocate 
R[n2] = 99;  //`99` to the end of array

请记住，对于包含 n 元素的数组，有效索引为 0 - n-1