1

おはようございます。C++ リンク リストで偶数長と奇数長の文字列を分離するには、再帰または反復を使用する方がよいでしょうか?

より良いとは、1) 堅牢性 2) クロス プラットフォームの Windows/Linux/Unix 移植性 3) 最悪の場合のランタイム パフォーマンスを意味します。

cSinglyLinkedList* SeparateOddandEvenlLengthStrings(cSinglyLinkedList* list){
    cSinglyLinkedList* Retval(NULL);
    char* Temp(NULL);
    if (list == NULL || list->Head == NULL){
        return NULL;
    }
    if (list && list->Current && list->Current->Next == NULL){
        return list;
    }
    if (list->Iterate()){
        Temp = list->Current->String;

        Retval = SeparateOddAndEvenLengthStrings(list);

        if ((strlen(Temp) % 2) == 0){
            Retval->Remove(Temp);       
            Retval->Add(Temp);
        }
        return Retval;
    }
    return NULL;
}

class cSinglyLinkedList {
private:
    struct SinglyLinkedInfo{
        SinglyLinkedInfo* Next;
        char* String;
        SinglyLinkedInfo(void){
            Next =  0;
            String= 0;
        }
    } Item;
    SinglyLinkedInfo *Head, *Current; 
    int Count;
    void ClearStrings(void);

public:
    cSinglyLinkedList(void);
    ~cSinglyLinkedList(void);
    bool Add(const char *string1);
    void Remove(const char *string1);
    bool RestartIterator(void);
    bool Iterate(void);
    int GetCount(void);
    SinglyLinkedInfo* GetHead(void);
    SinglyLinkedInfo* GetCurrent(void);
    void Trace(const char *title_);
};

inline bool cSinglyLinkedList::RestartIterator(void) {
    Current=Head;
    return (Current!=0);
}

inline bool cSinglyLinkedList::Iterate(void) {
    if (Current==0){
        Current=Head;
    } else if (Current){ 
        Current = Current->Next;
    }
    return (Current!=0);
}
inline SinglyLinkedInfo *cSinglyLinkedList::GetHead(void) {
    return Head;
}
inline SinglyLinkedInfo *cSinglyLinkedList::GetCurrent(void) {
    return Current;
}
cSinglyLinkedList::cSinglyLinkedList(void) {
    Head=Current=0;
    Count=0;
}
cSinglyLinkedList::~cSinglyLinkedList(void) {
    ClearStrings();
}
void cSinglyLinkedList::ClearStrings(void) {
    SinglyLinkedInfo* nextCurrent;
    Current=Head;
    while (Current!=0) {
        nextCurrent = Current->Next;
        delete[] Current;
        Current=nextCurrent;
    }
    Head=Current=0;
    Count=0;
}
void cSinglyLinkedList::Remove(const char* string1_) {
    SinglyLinkedInfo* Prev(NULL);
    RestartIterator();
    Current = Head;
    while (Current!=0) {
        if (strcmp(Current->String,string1_)==0){       
            if (Prev){
                Prev->Next = Current->Next;
            } else{
                Head = Current->Next;
            }
            delete [] Current;
            break;
        }
        Prev=Current;
        Current=Current->Next;
    }
    RestartIterator();
    Count -= 1;
}

bool cSinglyLinkedList::Add(const char *string1_){ 
    SinglyLinkedInfo* newElement = (SinglyLinkedInfo*)new char[sizeof(SinglyLinkedInfo)];
    memset(newElement, '\x0', sizeof(SinglyLinkedInfo)); 
    newElement->String = new char[sizeof(char*)];
    memcpy(newElement->String, &string1_, sizeof(char*));
    newElement->String = (char*)string1_; 
    newElement->SinglyLinked = new cPCRE();
    newElement->SinglyLinked->SetOptions(PCRE_CASELESS);
    if (newElement->SinglyLinked->Compile(string1_) == 0){
        return false;
    }
    if (Head==0) {
        Head = newElement;

    } else {
        SinglyLinkedInfo* Temp(NULL);

        Temp = Head;

        while (Temp != 0 && Temp->Next != 0){
            Temp = Temp->Next;
        }

        Temp->Next = newElement;
    }

    Count++;
    return true;
}
void cSinglyLinkedList::Trace(const char *title_) {
    int i=0;

    if (title_!=0)
        printf("%s:\n",title_);

    if (RestartIterator()) {
        do {
            printf(" %d: %s\n",i++,GetString());
        } while (Iterate());
    }
}
4

3 に答える 3

5

末尾呼び出しの最適化により、最終的には問題にならないかもしれませんが、少なくとも C++ に関する限り、連結リスト処理への反復アプローチはより慣用的です。再帰的アプローチとは異なり、コンパイラーが末尾呼び出しの最適化を適用しなくても、反復的アプローチではスタック オーバーフローが発生しません。

于 2012-12-31T15:54:32.593 に答える
2

「制限」されていない再帰[1]は、間違いなく悪いことです。誰かがあなたの関数にシェイクスピア全集を入力として与えたらどうなるでしょう（そして私は、約32文字の長さの「シェイクスピア全集」ではなく、すべての本を意味します）。

無制限の再帰の問題は、スタックが完全に使い果たされると、プロセスを強制終了する以外に誰もできないため、回復できない方法で爆発することです。スタックスペースを使用しているため、「申し訳ありませんが、スタックが不足しました」という関数を呼び出すことはできません。

[1]または、指定された回数の再帰呼び出しで問題ないと合理的に言えるようになります。たとえば、適度にバランスの取れたバイナリツリーは、32の再帰レベルで40億のエントリを検索できるため、データベースが機能しない場合数百万を超えるエントリになる[そして、すべてのノードがツリーの左側または右側のリンクリストに含まれるという病理学的なケースに対するガードがあります]、それなら大丈夫だと言えます。

于 2012-12-31T16:08:43.590 に答える
1

私の経験から言えば、どのアルゴリズムでも、反復バージョンは常に再帰バージョンよりも高速です。再帰の長さが制限されているため、再帰バージョンでもオーバーフローが発生する可能性があります。しかし、再帰的な実装の利点の 1 つは、それらが非常に単純であることです。

于 2012-12-31T16:12:02.893 に答える