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

根据我的经验，我可以说对于任何算法，迭代版本总是比递归版本快。递归版本也可能导致溢出，因为递归的长度是有限的。但是，递归实现的一个优点是它们非常简单。

于 2012-12-31T16:12:02.893 回答