记录下初学bushiC++遇到的一道题目

题干

编写函数void reverseStr(std::string &s)，用递归算法使字符串s倒序。

出自清华大学郑莉老师编写的教材《C++语言程序设计》第五版，题号6-22。

思路

题干明确说明需要用递归方法，而递归的基本思路，是逐步缩小问题规模并求解。则本题的主要代码框架可以如下所示：

#include <string>

void reverseStr(std::string &s)
{
  static std::string t = ""; //静态字符串常量t，存放逆序后的字符串
  if ({终止条件})
  {
    {最小规模下的求解方法}
  }
  else
  {
    reverseStr({缩小一“单位”规模后的参数});
  }
}

对于字符串，缩小问题规模意味着缩减字符串长度，最短的字符串只有一个字符，其逆序为其本身。因此，可以确定终止递归的条件是字符串中仅有一个字符，则{终止条件}可以写为：s.length() == 1。而在此{最小规模下的求解方法}可以写为：t.append(s)。

随后考虑缩小参数规模的方法。不难想到，每次应将字符串减少一个字符，且是减去首字符，再行递归调用。故而，可以使用string的substr方法，每次截取出需要的子串，供递归使用，则{缩小一“单位”规模后的参数}可表达为：std::string u = s.substr(1,s.length()-1)^1，即递归调用u。

之后，递归调用完成，跳回主调函数后，应将当前s的首字符插入到t的末尾，可写为：t.append(s.substr(0,1))。

最后，需要将逆序后字符串赋给s，放在if else外即可。

完整代码

#include <iostream>
#include <string>

void reverseStr(std::string &s)
{
    static std::string t = ""; //声明为静态变量，防止重复初始化
    if (s.length() == 1)
    {
        t.append(s);
    }
    else
    {
        std::string u = s.substr(1,s.length()-1);
        reverseStr(u);
        t.append(s.substr(0,1)); //这步执行完成后，s没用了
    }
    s = t; //所以在if else外将t赋给s不影响求解
}

int main()
{
    std::string sentence;
    std::cout << "pls enter ur sentence: " << std::endl;
    // std::cin >> sentence;
    getline(std::cin, sentence); //使用getline()来接收有空格的string
    std::cout << std::endl;
    reverseStr(sentence);
    std::cout << "the reversed sentence is: " << sentence << std::endl;
    return 0;
}

全文完