C++ рекурсивно сливане на низове

Това е въпрос за домашна работа, така че макар да искам използваем код, това, което наистина търся, е прозрение как да се справя с този проблем. Имам два сортирани масива във възходящ ред, които трябва да комбинирам в рекурсивна функция. Изглежда, че трябва да въведа частта за сортиране на алгоритъм за сортиране чрез сливане. Изискванията са рекурсивната функция да може да приема само двата сортирани низа като параметри и да не може да използва глобални или статични променливи.

Мисля, че псевдокодът е:

  • ако размерът на двата низа == 0, тогава се връща резултатният низ.
  • сравнете substr(0,1) на всеки низ, за ​​да видите кой е по-малък, и го добавете към резултантния низ
  • рекурсивно извикване на функцията, като новите параметри са подниз на низа, който е добавен

Въпросите ми са: как да запазя резултатен низ, ако не мога да използвам статични променливи? Виждал съм код, където низ е дефиниран като = към израза за връщане на рекурсивното извикване. Това би ли проработило в този случай?

Вторият въпрос е как да увеличим функцията. Трябва да извикам substr(1,size-1) след първата итерация и след това да го увелича, без да използвам статични променливи.

Ето опита ми да реша уравнението СЪС статични променливи (които не са разрешени):

static string result="";
static int vv=0;
static int ww=0;

if(v.size()==0 && w.size()==0)
    return result;
if(w.size()==0 || v.substr(0,1) <= w.substr(0,1)){ 
    result+=v.substr(0,1);
    vv++;
    return spliceSortedStrings( v.substr(vv,v.size()-vv) , w); 
    }
else if(v.size()==0 || w.substr(0,1) > v.substr(0,1)){
    result+=w.substr(0,1);
    ww++;
    return spliceSortedStrings( v , w.substr(ww,w.size()-ww));
    }

Ще бъда благодарен за всякакви насоки.


c++ string recursion mergesort
person banana muffin    schedule 04.02.2014    source източник
comment
Съжалявам, но пропуснах нещо. смисълът на това упражнение ли е да вземе два низа от сортирани знаци и рекурсивно да ги обедини в един низ, където резултатите също са сортирани? И независимо дали това е целта или не, повтарящите се substr() извиквания са луди, когато всичко, което ви интересува, е front() (ако приемем, че !empty() е валидирано). substr() е скъпо, тъй като всеки генерира новоразпределен независим низ.   -  person WhozCraig    schedule 04.02.2014
comment
Да, това бяха изискванията на упражнението.   -  person banana muffin    schedule 04.02.2014
comment
Добре. Ще публикувам нещо, ако смятате, че ще помогне, въпреки че изглежда, че вече имате отговор, който харесвате.   -  person WhozCraig    schedule 04.02.2014
comment
Отговорът на user1734710 беше много полезен.   -  person banana muffin    schedule 04.02.2014
comment
Съгласен съм, това беше причината да гласувам за него.   -  person WhozCraig    schedule 04.02.2014

Отговори (1)


arrow_upward
1
arrow_downward

Какво ще кажете за това:

std::string merge(std::string a, std::string b) {
    if (a.size() == 0) return b;
    if (b.size() == 0) return a;

    if (a.back() < b.back()) {
        std::string m = merge(a, b.substr(0, b.size()-1));
        return m + b.back();
    }
    else {
        std::string m = merge(a.substr(0, a.size()-1), b);
        return m + a.back();
    }
}

Коректността и прекратяването трябва да са очевидни и мисля, че трябва да отговарят на ограниченията, които са ви дадени. Но се чудя кой учител би поставил такава задача в C++, тъй като горният код е толкова неефективен, колкото е възможно.

person gTcV    schedule 04.02.2014