我正在用C++开发一个使用Node类的双向链表类。
我正在尝试创建一个删除函数，如果所需的节点存在，则删除该节点。
但是如果值大于currentPrt，它就退出，不做任何事情，如果小于currentPrt，它就删除节点，程序就会进入打印奇怪值的无限循环。
节点类编码：
// Node.h
class Node {
public:
explicit Node(int data = 0, Node *nextPtr = nullptr, Node *beforePtr = nullptr);
int getData() const;
void setData(int data);
Node *getNextPtr() const;
void setNextPtr(Node *nextPtr);
Node *getBeforePtr() const;
void setBeforePtr(Node *beforePtr);
void print() const;
private:
int data;
Node *nextPtr;
Node *beforePtr;
};x
// Node.cpp
Node::Node(int data, Node *nextPtr, Node *beforePtr) : data(data), nextPtr(nextPtr), beforePtr(beforePtr) {}
int Node::getData() const {
return data;
}
void Node::setData(int data) {
Node::data = data;
}
Node *Node::getNextPtr() const {
return nextPtr;
}
void Node::setNextPtr(Node *nextPtr) {
Node::nextPtr = nextPtr;
}
Node *Node::getBeforePtr() const {
return beforePtr;
}
void Node::setBeforePtr(Node *beforePtr) {
Node::beforePtr = beforePtr;
}
void Node::print() const {
cout << getData() << endl;
}// MyList.h
class MyList {
public:
MyList(Node *currentPrt = nullptr);
void insert(int value);
void print() const;
private:
Node *currentPrt;
};// MyList.cpp
MyList::MyList(){
currentPrt = nullptr;
}
void MyList::insert(int value) {
if(currentPrt == nullptr){
currentPrt = new Node;
currentPrt->setData(value);
currentPrt->setNextPtr(nullptr);
currentPrt->setBeforePtr(nullptr);
}
else{
if(value > currentPrt->getData()){
while (currentPrt->getNextPtr() != nullptr && currentPrt->getNextPtr()->getData() < value){
currentPrt = currentPrt->getNextPtr();
}
Node *newPtr = new Node(value);
newPtr->setNextPtr(currentPrt->getNextPtr());
if (currentPrt->getNextPtr() != nullptr) // <---
currentPrt->getNextPtr()->setBeforePtr(newPtr); // <---
currentPrt->setNextPtr(newPtr);
newPtr->setBeforePtr(currentPrt);
}
else{
while (currentPrt->getBeforePtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
currentPrt = currentPrt->getBeforePtr();
}
Node *newPtr = new Node(value);
if (currentPrt->getBeforePtr() != nullptr){
currentPrt = currentPrt->getBeforePtr();
newPtr->setNextPtr(currentPrt->getNextPtr());
currentPrt->getNextPtr()->setBeforePtr(newPtr); // <---
currentPrt->setNextPtr(newPtr);
newPtr->setBeforePtr(currentPrt);
}
else{
currentPrt->setBeforePtr(newPtr);
newPtr->setNextPtr(currentPrt);
}
}
}
}
void MyList::remove(int value) {
if (currentPrt != nullptr){
if(value > currentPrt->getData()){
while (currentPrt->getNextPtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
currentPrt = currentPrt->getNextPtr();
}
if (currentPrt->getNextPtr()->getData() == value){
delete currentPrt->getNextPtr();
}
}
else{
while (currentPrt->getBeforePtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
currentPrt = currentPrt->getBeforePtr();
}
if (currentPrt->getBeforePtr()->getData() == value){
delete currentPrt->getBeforePtr();
}
}
}
}
void MyList::print() const {
Node *ptr;
ptr = currentPrt;
while(ptr->getNextPtr() != nullptr){
ptr = ptr->getNextPtr();
}
for (ptr; ptr != nullptr; ptr = ptr->getBeforePtr()){
cout << ptr->getData() << endl;
}
}的数据
主要：
MyList test;
test.insert(5);
test.insert(3);
test.insert(7);
test.insert(6);
test.printAscending();
std::cout<<endl;
test.remove(7); // doesn't work but doesn't cause infinit print
test.remove(5); // doesn't work but doesn't cause infinit print
test.remove(6); // causes infinit prints
test.remove(3); // causes infinit prints
test.printAscending();仅拆卸（5）、拆卸（7）的输出：
3
5
6
7
3
5
6
7如果我输入remove(6)（或3），它就会得到无数个数字，如下所示：
2109940880
2109365888
2109348064
2109342032我的remove实现有什么问题？
2条答案
按热度按时间yc0p9oo01#
不应该在链表中的节点上执行
delete，首先需要将所有引用重新连接到它，也就是说，前面的节点应该将其nextPtr重定向到要删除的节点后面的节点，并且该节点也应该将其beforePtr重定向。此外，代码在找到匹配值时会删除 next 节点，而不是删除该节点本身。此外，如果该值出现在多个节点中，也没有删除更多节点的规定。
我还建议将该算法一分为二，因为删除 current 节点的部分本身作为一个方法是有用的。
所以我们得到这个：
q43xntqr2#
让我建议一件事：由于您Assert在插入和存储第一个Node时列表是有序的，因此您永远不必按降序搜索-只需按升序搜索。
在你的实现中，你可以修改你所指向的，指向最后一个插入的节点。我看不出这样做有什么好处。只要存储列表的头部，并将其他指针作为局部变量。这会让你的事情变得更容易。
remove中的bug可能是你没有从被删除节点的后继节点和前趋节点中重新分配next和previous指针，调用delete只是释放内存，这也是为什么当试图读取未分配内存时，它会表现得很奇怪。