c++ - 在 C++ 中使用递归反转数组

Question

赋值相对简单，使用 ReverseStringRecursive 函数反转 main 中的数组。然而，限制是我只能使用一个 int 和一个 char 没有其他声明变量的东西(这包括禁止 for 循环和很快)。此外，不能使用额外的库我仅限于 iostream 和 conio.h。我遇到的问题是 string 将向前打印，然后在我只需要向后打印时向后打印。 reverseMe 变量指向 main 中的一个 string，其中包含 "abcdefghijklmnopqrstuvwxyz"。此函数不应该打印 string 只是相反，然后 main 将打印字符串。

// INCLUES AND NAMESPACES
#include <iostream>
#include<conio.h>
using namespace std;

// CONSTANTS
const int STRING_SIZE = 100;

// PROTOTYPES
int ReverseStringRecursive(char*);

// MAIN
int main() {
    // create a string
    char someString[STRING_SIZE] = "abcdefghijklmnopqrstuvwxyz";

    // display the string before being reversed
    cout << "The string contains: " << endl;
    cout << someString << endl << endl;

    // make the call to the recursive function
    cout << "CALL THE REVERSING FUNCTION" << endl << endl;
    ReverseStringRecursive(someString);

    // display the string after being reversed
    cout << "The string contains: " << endl;
    cout << someString << endl;

    // exit program
    _getch();
    return 0;
}
    int ReverseStringRecursive(char* reverseMe) {
// YOUR IMPLEMENTATION GOES HERE...
int position = 0;
char holder = ' ';

if (reverseMe[0] == '\0') {
    return 1;
}
else {
    holder = reverseMe[position];
}

ReverseStringRecursive(reverseMe + 1);

while (reverseMe[position] != '\0') {
    position++;
}
reverseMe[position] = holder;

return position;
}

我得到的示例输出:

"abcdefghijklmnopqrstuvwxyz zyxwvutsrqponmlkjihgfedcba"

我应该得到什么:

"zyxwvutsrqponmlkjihgfedcba"

Answer 1

棘手的问题。在调用递归函数之前，您必须通过在最后一个字符上放置一个 '\0' 来缩短每次递归的内部字符串，然后在递归调用之后执行交换。

算法:

0. save the index of the last character in the string
1. Save the last character of the current string
2. Set the last character of the current string to null (use the saved index)
3. Call the recursive function starting one character in which will recurse the algorithm for the next inner string (we have already shortened the end of the recursed string)
4. Once the recursion has finished, set the last character to the first char of the current string; then
5. set the first character of the current string to the saved character (which was at the end)

这也适用于奇数长度的字符串。

以下代码应该可以在 Windows 系统上运行。要使其在 Linux 上运行，只需注释掉 conio.h 包含行，注释掉 __getch() 行并取消注释 cin.getch() 行。

// INCLUES AND NAMESPACES
#include <iostream>
#include <conio.h>

using namespace std;

// CONSTANTS
const int STRING_SIZE = 100;

// PROTOTYPES
int ReverseStringRecursive(char *);

char *orig;

// MAIN
int main()
{
  // create a string
  char someString[STRING_SIZE] = "abcdefghijklmnopqrstuvwxyz";

  orig = someString;

  // display the string before being reversed
  cout << "The string contains: " << endl;
  cout << someString << endl << endl;

  // make the call to the recursive function
  cout << "CALL THE REVERSING FUNCTION" << endl << endl;
  ReverseStringRecursive(someString);

  // display the string after being reversed
  cout << "The string contains: " << endl;
  cout << someString << endl;

  // exit program
  _getch();        // uncoment conio.h on a windows system
  //  std::cin.get();  // use this if on a linux system

  return 0;
}

int ReverseStringRecursive(char *reverseMe)
{
  int last_index = 0;
  while (reverseMe[last_index + 1] != '\0')
    last_index++;

  char save_char = reverseMe[last_index];

  if (*reverseMe != '\0') {
    reverseMe[last_index] = '\0';  // shorten the inner string by one

    // recurse on the shorter string
    ReverseStringRecursive(reverseMe + 1);

    // save the outer two characters
    reverseMe[last_index] = *reverseMe;
    *reverseMe = save_char;
  }
}