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

问题描述 投票：0回答：4

我正在做一个实验室作业，用户在其中输入一个字符串以及该字符串中要反转的子字符串的起点和终点。例如，如果用户输入字符串“ 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，因为这是字符串的全长。

如何调整功能，使其仅反转用户输入的索引处的字符串开头和结尾？另外，使用当前函数，我必须在主字符串中使用endl在字符串输出的末尾添加新行。我可以在函数中执行此操作吗？如果在endl之后放置cout << s[0];，则在每次迭代后将其放置在换行中，使输出垂直：

s

t

a

c

b

o

b

o

g

主要实现：

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;
c++ string recursion reverse function-definition
4个回答
2
投票

反转字符串的功能可以交换范围两端的元素，并在两侧将范围减小一。

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;
0
投票

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

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

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

此外，函数返回对反向字符串本身的引用也更好。

实际上，在该功能内，您只需使用一次检查即可确定起始位置小于终止位置。

这里是一个演示程序，显示了如何定义功能。

#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
0
投票

嗯，我也有一个解决方案，但没有实现库功能只是为了给您一种实现的感觉，这很简单。

  1. -递归交换开始位置和最后位置，而不是详尽地。

    1. [endl in 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;
}
0
投票

有时它是可悲的C ++是如何用来教导的一切，但不是C ++。以下是一种实验，旨在看看我们是否可以通过执行一些小的可消化步骤来以某种方式接近std::reverse（您应实际使用的算法）。

让我们从std::reverse中介绍的解决方案的微小变化开始。不用传递this answer和索引，我们可以使用迭代器。简而言之，string是iterators与数据结构（更具体地说是algorithms）之间的粘合。它们可以引用容器中的元素，就像索引或指针一样。 

container

迭代器可以像指针一样被取消引用，以获取对该元素的引用（void reversing2(std::string::iterator first, std::string::iterator last) { if (first >= last) return; std::swap(*first,*last); reversing2(++first,--last); } 和*first）。可以将RandomAccessIterators递增（*last），递减（++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);
}

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

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

将产生此输出：

#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和std::reverse构成的范围，其中first包含在区间中，但是last是间隔中最后一个元素之后的一个。因此，要获得相同的结果，您将不得不使用第二个迭代器比使用上面的函数更远地调用它：

first

last

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.