删除链接列表中的函数 [英] Remove function in a Linked List
问题描述
我有一个名为StringList.h的头文件，其中包含以下内容：
I have a header file called StringList.h that includes the following:
#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的工作
My StringList.cpp file will have the definitions to all my functions. So far I figured out how to addtotop and addtoBottom works
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语句中用pBottom替换pTop。
现在，im stuck在删除。我想通过每个节点，直到它找到*数据中的字符串，并删除它。但我真的不知道如何使以前的指针，我想删除的节点指向下一个节点的pNext。任何建议？
addToBottom is basically the same but replacing pTop with pBottom in the else statement. Now, where im stuck is at remove. I want to go through each nod until it finds the string within *data and delete it. However i dont really know how to make the previous pointer to the node i want deleted point to the pNext of the next node. Any suggestions?
print（）：
string StringList::print()
{
string result;
StringListNode * pCurrent;
pCurrent=pTop;
while(pCurrent!=NULL)
{
result+=(*pCurrent).data+"\n";
pCurrent=(*pCurrent).pNext;
}
return result;
}
推荐答案
一个双向链表，你要删除 curr ：
Assuming you have three nodes in a doubly-linked list and you want to delete the middle node, identified by curr:
curr ----------------------+
|
v
+--------+ +--------+ +--------+
...----| pPrev |<------| pPrev |<------| pPrev |<---...
| Node 1 | | Node 2 | | Node 3 |
...--->| pNext |------>| pNext |------>| pNext |----...
+--------+ +--------+ +--------+
这两个重新链接操作是：
The two relinking operations are:
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 。唯一的诀窍是处理终端情况;当删除列表开始或结束处的节点或列表中唯一的节点时会发生什么。什么是适当的取决于你如何创建你的列表。你有空指针或循环列表，或...
You can now dispose of curr in any suitable way. The only trick is dealing with end-cases; what happens when you delete the node at the start or end of the list, or the only node in the list. What's appropriate depends on how you've created your list. Do you have null pointers, or a circular list, or ...
由于使用空指针来标记列表的末尾，你必须检查null
Given that you use null pointers to mark the ends of the list, you have to check for null pointers when deleting.
if (curr->pPrev != 0)
curr->pPrev->pNext = curr->pNext;
if (curr->pNext != 0)
curr->pNext->pPrev = curr->pPrev;
您还必须处理 curr 调整头部（ pTop ）或者它是列表的尾部，调整尾部（ pBottom ）。您还必须处理 curr 是列表中唯一的节点。
You also have to deal with curr being the head of the list, adjusting the head (pTop) or with it being the tail of the list, adjusting the tail (pBottom). You also have to deal with curr being the only node in the list.
表面工作代码... not使用 valgrind 验证。然而，重复使用 toString（）成员函数（née print（））表明列表结构好。没有关于没有泄漏的承诺。
Superficially working code...not validated with valgrind. However, the repeated use of the toString() member function (née print()) suggests that the list structure is OK. No promises about no leaks.
#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;
}
这篇关于删除链接列表中的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
