删除链表中的函数

Question

我有一个名为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:

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。有什么建议吗？

print（）：

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

Answer 1

假设您在一个双链接列表中有三个节点，并且您想要删除中间节点，由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是列表中唯一的节点的问题。

表面工作代码。。。未经CCD_ 7验证。然而，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;
}