使用递归或迭代来分离C++链表中的偶数和奇数长度字符串更好吗？

Question

早上好.使用递归或迭代来分离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());
    }
}

Answer 1

尽管由于尾部调用优化最终可能无关紧要,但链接列表处理的迭代方法更为惯用,至少就C++而言.与递归方法不同,即使您的编译器不应用尾调用优化,迭代也不会导致堆栈溢出.