反转字符串中子字符串的递归函数

Question

我正在做一个实验作业，用户输入一个字符串以及字符串中要反转的子字符串的起点和终点。例如，如果用户输入字符串 "go bobcats"，以及数字 3（起始索引）和 7（结束索引），则输出应为 "go acbobts"。我能够编写一个递归函数来反转整个字符串（"go bobcats" 变为 "stacbob og"），但我在子字符串方面遇到了问题。

完整字符串反转代码：

void reversing(string s, int start, int end){
    if(s.size() == 0){return;}
    else{
        reversing(s.substr(1), start + 1, end);
        cout << s[0];
    }
}

对于这个的开始和结束索引，我只输入了 0 和 9，因为那将是字符串的全长。

如何调整该函数，使其仅反转用户输入的索引处开始和结束的字符串？此外，对于我当前的函数，我必须在 main 中使用 endl 在字符串输出的末尾创建一个新行。有没有办法在函数内部执行此操作？如果我在 cout << s[0]; 之后放置一个 endl，它会在每次迭代后换行，使输出垂直：

s

t

一个

c

b

o

b

o

克

主要实现：

string s;
    int start, end;
    cout << "Enter a string: ";
    while(cin.peek() == '\n' || cin.peek() == '\r'){
        cin.ignore();
    }
    getline(cin,s);
    cout << "Now enter two numbers that are within the bounds of the string. ";
    cin >> start >> end;
    cout << "This is how your words look now:\n";
    reversing(s,start,end);
    cout << endl;

Answer 1

一个反转字符串的函数可以交换范围两端的元素，并将范围两边都减一。

void reversing(string& s, int start, int end) {
    if (start >= end)
        return;
    swap(s[start], s[end]);
    reversing(s, start + 1, end - 1);
}

然后在里面 main():

// ...
cout << "This is how your words look now:\n";
reversing(s, start, end);
cout << s << endl;

Answer 2

在你的函数声明中，第一个参数的类型不是引用类型。因此该函数处理作为参数传递给该函数的原始字符串的副本。

但是无论如何你的递归函数定义都是无效的。至少不需要提取子串。

注意函数的第二个和第三个参数的类型应该是std::string::size_type。否则，当参数的类型为 int 时，用户可以为参数提供负值，函数将具有未定义的行为。

另外，当函数 returns 引用反向字符串本身时更好。

事实上，在函数中你只需要使用一个检查开始位置小于结束位置。

这是一个演示程序，展示了如何定义函数。

#include <iostream>
#include <string>

std::string & reversing( std::string &s, std::string::size_type start, std::string::size_type end )
{
    if ( not s.empty() )
    {
        if ( not ( end < s.size() ) ) end = s.size() - 1;

        if ( start < end )
        {
            std::swap( s[start], s[end] );
            reversing( s, start + 1, end - 1 );
        }
    }       

    return s;
}

int main() 
{
    std::string s( "Hello bobaloogie" );

    std::cout << s << '\n';
    std::cout << reversing( s, 0, 4 ) << '\n';
    std::cout << reversing( s, 6, s.size() ) << '\n';

    return 0;
}

程序输出为

Hello bobaloogie
olleH bobaloogie
olleH eigoolabob

Answer 3

好吧，我也有一个解决方案，但没有实现库函数，只是为了给你实现的感觉，而且它非常简单。

调整你的函数 - 递归交换开始和最后位置而不是做详尽无遗。
1. endl in the main - 如果你只想在输入字符串中保存答案，那么是的，你必须在 main 中这样做。否则就在函数返回之前把'endl'.

我的代码是这样的。

#include<bits/stdc++.h>
using namespace std;


void rev(string &str,int s,int l){ // s = start l = last
     if(l<s) return ;            // base condition when l precedes s
     else {
         char temp = str[s];
         str[s] = str[l];
         str[l] = temp;
         rev(str,++s,--l);
     }
     return ;           
}

int main(){
   string str;
   int s,l;
   getline(cin,str);
   cin>>s>>l;
   assert(s<str.size() && l<str.size());
   rev(str,s,l);
   cout<<str;
}

Answer 4

有时看到 C++ 什么都教，却不教 C++，这让人很难过。下面是一个实验，看看我们是否可以通过实际忽略作业的要求并执行小的可消化步骤来以某种方式接近 std::reverse（你应该实际使用的算法）。

让我们从 . Instead of passing the string together with indices we can use iterators. In a nutshell, iterators are the glue between algorithms and data structures, more specifically container 中提供的解决方案的一个小变化开始。它们可以引用容器中的元素，就像索引或指针一样。

void reversing2(std::string::iterator first, std::string::iterator last) {
    if (first >= last) return;
    std::swap(*first,*last);
    reversing2(++first,--last);
}

迭代器可以像指针一样取消引用以获取对元素的引用（*first 和 *last）。 RandomAccessIterators 可以递增 (++first)、递减 (--last) 和进行比较 (first >= last)，就像使用索引一样。

下一步是困难的，因为它需要更多的手艺。请注意，除了函数签名之外，上述函数中没有任何内容实际上依赖于 first 和 last 作为 std::string 中元素的迭代器。例如，要反转 int[] 的子数组，只需更改签名即可：

void reversing2(int* first, int* last) {
    if (first >= last) return;
    std::swap(*first,*last);
    reversing2(++first,--last);
}

这是一个接触模板的好机会。我知道我在这里犯了一个小罪，因为我不能给你一个彻底的介绍，而只会给你一个非常狭窄的案例。为了使相同的代码可用于不同的容器，我们只需要稍微修改一下即可

template <typename IT>
void reversing(IT first,IT last) {
    if (first >= last) return;
    std::swap(*first,*last);
    reversing(++first,--last);
}

现在可以使用任何 RandomAccessIterator 调用它。所以这个：

#include <string>
#include <iostream>
int main() {        
   std::string s{"Hello world"};       
   std::cout << s << '\n';
   reversing2(s.begin()+3,s.begin()+7);    // pass iterators to 4th and 8th character
   std::cout << s << '\n';
   reversing(s.begin()+3,s.begin()+7);
   std::cout << s << '\n';   
   int x[]= {1,2,3,4,5,6};
   reversing(&x[2],&x[5]);                 // pointers are iterators too
   for (const auto e : x) std::cout << e;
}

将产生此输出：

Hello world
Helow olrld
Hello world
126543

最终，这就是前面的全部动机，我们可以看到 reversing 与 std::reverse 非常相似。当然 std::reverse 不是递归的，有一个小警告：标准算法通常在半开区间上工作，即由两个迭代器 first 和 last 组成的范围，其中 first 包含在区间中，但 last 是区间中最后一个元素之后的一个。因此，要获得相同的结果，您必须使用第二个迭代器调用它比使用上述函数更远一个位置：

std::reverse(s.begin()+3,s.begin()+8);  // pass iterators to 4th and one past the 8th character

Complete online example

Answer 5

解决这个问题有不同的方法，贪心的方法是使用子字符串将确切的字符串传递给反向函数：

void reversing(string s){
    if(s.size() == 0){return;}
    else{
        reversing(s.substr(1));
        cout << s[0];
    }
}

void main(string s, int start, int end) {
    string substring = reversing(s.substr(start, end - start + 1));
    cout << s.substr(0, start) + substring + s.substr(end + 1);
}

否则您需要编辑您的函数，仅当在该范围内时才反向编辑字符串

void reversing(string s, int start, int end, int index = 0, string output = ""){
    if(s.length() == index){return output;}
    else{
        if (index >= start && index <= end) {
            output = output + s[end - (index - start)];
        } else {
            output += s[index];
        }
        reversing(s, start, end, index+1, output);
        cout << output[output.length()-1];
    }
}

反转字符串中子字符串的递归函数

Recursive function that reverses substring within a string

c++

string

recursion

reverse

function-definition