在 C 中使用递归反转 int 数组

Question

I have learnt C language at school but I'm not good at it... And when I was trying to implement this algorithm using C language:

ReverseArray(int A[], int i, int j) {
   Input: Array A, nonnegative integer indices i and j
   Output: The reversal of the elements in A starting at index i and ending at j
   if i < j then
      swap A[i] and A[j]
      ReverseArray(A, i+1, j-1)
}

我设法编写了这个代码：

int *reverseArray(int A[], int i, int j) {
   int *R = NULL;
   if(i < j) {
      int temp = A[j];
      A[j] = A[i];
      A[i] = temp;
      R = reverseArray(A, i+1, j-1);
      return R;
   } else {
      return R;
   }
}

But when I tried to print the original and reversed array in the main:

int main(void) {
   int A[] = {1, 3, 5, 6, 8, 3, 4, 2};

   int *r = reverseArray(A, 0, 7);

   //This prints out the reversed array, when I intended to print the original
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", A[i]);
   }
   printf("\n");

   /* This was intended to print the reversed array but doesn't work
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", r[i]);
   }
   */

   return 0;
}

Could anyone please explain why the commented out for loop doesn't work? And why the first for loop prints out the reversed array... Is there any other way to get the result of reverseArray() without using *r? I tried to malloc *r just in case that was the problem, but it still didn't work.

谢谢。

Answer 1

R总是赋值NULL，而A不是指针，那么你编辑的是数组的真实数据。

如果你想反转并创建一个新数组，你必须这样做：

int *reverseArray(int array[], int arraySize) {
    int *reversedArray = malloc(sizeof(int) * arraySize);

    for ( int i = 0 ; i < arraySize ; ++i ) {
        reversedArray[i] = array[arraySize - i - 1];
    }
    return reversedArray;
}

你也可以用递归的方式做:

int   *reverseArray(int inputArray[], int arrayLength ) {

    int   *_reverseArray (int inputArray[], int arrayLength, int *outputArray, int actual) {

            if (outputArray == NULL) {
                outputArray = malloc(sizeof(int) * arrayLength);
            }
            if (actual < arrayLength) {
                outputArray[actual] = inputArray[arrayLength - actual - 1];
                return _reverseArray(inputArray, arrayLength, outputArray, ++actual);
            }
            return outputArray;

    }
    return _reverseArray(inputArray, arrayLength, NULL, 0);
}

如果要编辑原始数组：

void    reverseArray(int array[], int arraySize)
{
    for ( int i = 0 ; i < arraySize / 2 ; ++i ) {
        array[i] ^= array[arraySize - i - 1];
        array[arraySize - i - 1] ^= array[i];
        array[i] ^= array[arraySize - i - 1];
  }
}

Answer 2

只是不要 return 任何事情。您就地进行了反转，因此生成的数组与要反转的数组相同，调用者已经知道了。

Answer 3

您需要在调用 reverseArray 之前打印 A 的内容，而不是之后。原因是您正在反转字节，因此通过调用 reverseArray 更改了数组 A 本身。

Answer 4

根据您的代码库和问题描述进行尝试

如果允许就地重写数组，那么它将起作用

#include<stdio.h>

void reverseArray(int A[], int i, int j) {
   //int *R = NULL;
   if(i < j) {
      int temp = A[j];
      A[j] = A[i];
      A[i] = temp;
      reverseArray(A, i+1, j-1);
   }
}

int main(void) {
   int A[] = {1, 3, 5, 6, 8, 3, 4, 2};

   //This prints out original array
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", A[i]);
   }
   printf("\n");

   reverseArray(A, 0, 7);

   // print the reversed array
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", A[i]);
   }

   return 0;
}

它将输出：

1 3 5 6 8 3 4 2
2 4 3 8 6 5 3 1

在 C 中使用递归反转 int 数组

Reversing int array using recursion in C

c

arrays

pointers

recursion

reversing