Ошибка сегментации в рекурсивной функции C ++ - PullRequest
Новая
       10

Ошибка сегментации в рекурсивной функции C ++

0 голосов
/ 08 мая 2018

Проблема заключается в удалении соседней пары идентичных алфавитов, пока такой пары не будет. Я использовал рекурсию для этого. Но код дает ошибку сегментации. Что не так с этой рекурсией? 

#include<iostream>
#include<string>
using namespace std;
string super(string s)
{
        for(int i=0;i<s.length();i++)
        {
                if(s[i]==s[i+1])
                {
                        s.erase(s.begin()+i);
                        s.erase(s.begin()+i+1);
                        s=super(s);
                        cout<<s;
                        break;
                }
                if(i+1==s.length())
                        return s;
        }
        return s;
}
int main()
{
        string s;
        cin>>s;
        s=super(s);
        if(s.length()<0)
                cout<<s;
        else
                cout<<"Empty String";
}

Ответы [ 3 ]

0 голосов
/ 08 мая 2018

Вы индексируете вне диапазона. если я == s.length () - 1 (который является последним символом индекс), то ваш s [i + 1] будет вне диапазона.

Также в общем случае логика имеет недостатки, потому что вы будете перезапускать операцию с самого начала каждый раз, когда сталкиваетесь с совпадением. Если у вас есть «abccba», я предполагаю, что вы захотите «abcba», однако ваш код вернет abca. Временная сложность вашего решения не идеальна. Это можно сделать за линейное время.

В последней строке вы хотите s.length ()> 0 (или вы можете просто использовать s.empty ()).

0 голосов
/ 08 мая 2018

Из того, что я понял, люди ненавидят комментарии в коде, поэтому я повторю их здесь в верхней части ответа:

Ну, во-первых, в цикле for, чтобы не выходить за пределы индекса, нужно начинать с 1 и проверять, равны ли позиции i-1 и i строки.

Во-вторых, вы можете просто стереть из позиции i - 1 в позицию i + 1.

Наконец, если вы хотите напечатать жало в основном, вы должны проверить, если длина строки не пуста, длина не может быть <0 </p>

И, кроме того, простой вызов метода внутри себя не делает его «рекурсивным решением», код ниже является итеративным решением вашей проблемы 

#include<iostream>
#include<string>
using namespace std;
string super(string s){
        for(int i=1;i<s.length();i++)                                 // you start from 1 to doesn't go out of bound
                if (s[i-1]==s[i])
                        s.erase(s.begin() + (--i), s.begin() + i + 1);// you decrease i and erase from i decreased to i + 1
        return s;
}
int main(){
        string s;
        cin>>s;
        s = super(s);
        cout << ((s.length())? s : "Empty String");                    // the string is empty if the lenght is not 0, you have to change < with >
        return 0;
}

Вместо этого это рекурсивное решение, вы можете увидеть исчезновение цикла for (это не неправильное использование циклов, но их легко ошибиться) 

#include<iostream>
#include<string>
using namespace std;
string super(string s, int i){
    if (i < s.length()){
        if (s[i-1]==s[i]){
            s.erase(s.begin() + i - 1, s.begin() + i + 1);
            s = super(s, i);
        }
        else
            s = super(s, i + 1);
    }
    return s;
}
int main(){
    string s;
    cin>>s;
    s = super(s, 1);    //from input the size can't be 0 so give 1 is ok
    cout << ((s.length())? s : "Empty String");
    return 0;
}
0 голосов
/ 08 мая 2018

Ваши условные проверки вышли из строя, s[s.length()], по определению, вызовет ошибку сегментации, поэтому вам нужно убедиться, что i+1 меньше длины s ДО ТОГО, как вы пытаетесь получить к нему доступ.

Прямо сейчас вы получаете доступ к s[i+1], и ТОГДА проверяете, если i+1 < s.length().

...