0

我有一个名为 StringList.h 的头文件，其中包括以下内容：

#include <string>
using namespace std;

class StringList;


class StringListNode
{
    friend class StringList;
private:
    StringListNode * pPrev;
    string data;
    StringListNode * pNext;
};

class StringList
{
public:
    StringList();
    ~StringList();
    void addToBottom(string s);
    void addToTop(string s);
    void remove(string s);
    string print();
    void clear();
    bool isEmpty() {return (pTop==NULL);}
private:
    StringListNode * pTop;
    StringListNode * pBottom;
};

我的 StringList.cpp 文件将包含我所有函数的定义。到目前为止，我想出了如何 addtotop 和 addtoBottom 工作

添加到顶部：

if(isEmpty())
    {
        StringListNode * pNewNode;
        pNewNode = new StringListNode;
        (*pNewNode).data = s;
        pTop=pNewNode;
        pBottom=pNewNode;
        (*pNewNode).pPrev = NULL;
        (*pNewNode).pNext = NULL;
    }
    else //it's not empty
    {
        StringListNode * pNewNode;
        pNewNode = new StringListNode;
        (*pNewNode).data = s;
        (*pNewNode).pNext = pTop;
        (*pTop).pPrev = pNewNode;
        (*pNewNode).pPrev =NULL;
        pTop=pNewNode;
    }

addToBottom 基本相同，只是在 else 语句中将 pTop 替换为 pBottom。现在，我被卡住的地方是移除。我想遍历每个点头，直到它在 *data 中找到字符串并将其删除。但是我真的不知道如何使指向我要删除的节点的前一个指针指向下一个节点的 pNext。有什么建议么？

打印（）：

string StringList::print()
{
    string result;
    StringListNode * pCurrent;
    pCurrent=pTop;
    while(pCurrent!=NULL)
    {
        result+=(*pCurrent).data+"\n";
        pCurrent=(*pCurrent).pNext;
    }
    return result;
}
4

1 回答 1

0

假设您在双向链表中有三个节点，并且您要删除中间节点，由 标识curr：

 curr ----------------------+
                            |
                            v
       +--------+       +--------+       +--------+
...----| pPrev  |<------| pPrev  |<------| pPrev  |<---...
       | Node 1 |       | Node 2 |       | Node 3 |
...--->| pNext  |------>| pNext  |------>| pNext  |----...
       +--------+       +--------+       +--------+

两个重新链接操作是：

curr->pPrev->pNext = curr->pNext;  // Previous node's next points to curr's next
curr->pNext->pPrev = curr->pPrev;  // Next node's previous points to curr's previous

您现在可以curr以任何合适的方式进行处理。唯一的技巧是处理最终情况；当您删除列表开头或结尾的节点或列表中的唯一节点时会发生什么。什么是合适的取决于您创建列表的方式。你有空指针，或者循环列表，或者......

鉴于您使用空指针来标记列表的结尾，因此您必须在删除时检查空指针。

if (curr->pPrev != 0)
    curr->pPrev->pNext = curr->pNext;
if (curr->pNext != 0)
    curr->pNext->pPrev = curr->pPrev;

您还必须处理curr成为列表的头部，调整头部（pTop）或作为列表的尾部，调整尾部（pBottom）。您还必须处理curr成为列表中唯一的节点。

表面上工作的代码...未使用valgrind. 但是，重复使用toString()成员函数 (née print()) 表明列表结构是可以的。没有关于不泄漏的承诺。

#include <string>
using namespace std;

class StringList
{
private:
    struct StringListNode
    {
        StringListNode *pPrev;
        string          data;
        StringListNode *pNext;
    };
public:
    StringList() : pTop(0), pBottom(0) {}
    ~StringList();
    void addToTop(const string &s);
    void remove(const string &s);
    string toString();
    bool isEmpty() { return (pTop == NULL); }
private:
    StringListNode *pTop;
    StringListNode *pBottom;
    StringListNode *find(const string &s);
};

string StringList::toString()
{
    string result;
    StringListNode *pCurrent = pTop;
    while (pCurrent != NULL)
    {
        result += pCurrent->data + "\n";
        pCurrent = pCurrent->pNext;
    }
    return result;
}

StringList::StringListNode *StringList::find(const string &s)
{
    StringListNode *sp = pTop;
    while (sp != 0 && sp->data != s)
        sp = sp->pNext;
    return sp;
}

void StringList::addToTop(const string &s)
{
    if (isEmpty())
    {
        StringListNode * pNewNode = new StringListNode;
        pNewNode->data = s;
        pNewNode->pPrev = NULL;
        pNewNode->pNext = NULL;
        pTop = pNewNode;
        pBottom = pNewNode;
    }
    else
    {
        StringListNode * pNewNode;
        pNewNode = new StringListNode;
        pNewNode->data = s;
        pNewNode->pNext = pTop;
        pNewNode->pPrev = NULL;
        pTop->pPrev = pNewNode;
        pTop = pNewNode;
    }
}

void StringList::remove(const string &s)
{
    StringListNode *curr = this->find(s);
    if (curr == 0)
        return;
    if (curr->pPrev != 0)
        curr->pPrev->pNext = curr->pNext;
    if (curr->pNext != 0)
        curr->pNext->pPrev = curr->pPrev;
    if (pTop == curr)
        pTop = curr->pNext;
    if (pBottom == curr)
        pBottom = curr->pPrev;
}

StringList::~StringList()
{
    StringListNode *next;
    for (StringListNode *sp = pTop; sp != 0; sp = next)
    {
        next = sp->pNext;
        delete sp;
    }
}

#include <iostream>

int main()
{
    StringList s;
    s.addToTop("abc");
    std::cout << "After add abc: " << s.toString();
    s.addToTop("def");
    std::cout << "After add def: " << s.toString();
    s.addToTop("ghi");
    std::cout << "After add ghi: " << s.toString();
    s.addToTop("jkl");
    std::cout << "After add jkl: " << s.toString();
    s.remove("def");
    std::cout << "After del def: " << s.toString();
    s.remove("ghi");
    std::cout << "After del ghi: " << s.toString();
    s.remove("abc");
    std::cout << "After del abc: " << s.toString();
    s.remove("jkl");
    std::cout << "After del jkl: " << s.toString();
    return 0;
}
于 2013-07-14T00:51:26.303 回答