带节点的双向链表类C++

fzsnzjdm  于 2022-12-15  发布在  其他
关注(0)|答案(1)|浏览(192)

我尝试在C++中创建一个调用Node类的双向链表类
Node类的代码工作得很好,我的类的代码只在尝试从最小到最大打印值时工作,但如果我尝试从最大到最小打印,它只打印一些值。
我还需要指导如何使一个删除功能,类似于插入
节点类编码:

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;

};

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(Node *currentPrt) {}

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());
            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->setNextPtr(newPtr);
                newPtr->setBeforePtr(currentPrt);
            }
            else{
                currentPrt->setBeforePtr(newPtr);
                newPtr->setNextPtr(currentPrt);
            }
        }
    }



}

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(2);
    test.insert(1);
    test.insert(2);

    test.insert(7);
    test.insert(8);
    test.insert(6);
    test.print();

输出:8 7 5 3 2 1
当打印函数为:

void MyList::print() const {
    Node *ptr;
    ptr = currentPrt;
    while(ptr->getBeforePtr() != nullptr){
        ptr = ptr->getBeforePtr();
    }
    for (ptr; ptr != nullptr; ptr = ptr->getNextPtr()){
        cout << ptr->getData() << endl;
    }

}

输出为:1 2 2 3 5 6 7 8,符合预期
谢谢你的帮助

8yparm6h

8yparm6h1#

首先,由于这个构造函数,您的代码具有未定义的行为:

MyList::MyList(Node *currentPrt) {}

这使得currentPrt成员未初始化。它应该是:

MyList::MyList(Node *currentPrt) : currentPrt(currentPrt) {}

列表顺序的问题是由insert方法引起的。有两个代码块设置了两个next指针,但只有一个before指针,所以总共设置了三个指针。但一般情况下应该有四个。
此问题发生在第二个if块中:

Node *newPtr = new Node(value);
        newPtr->setNextPtr(currentPrt->getNextPtr());
        currentPrt->setNextPtr(newPtr);
        newPtr->setBeforePtr(currentPrt);

其中,newPtr->setNextPtr(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);

在不需要if保护的更深的if块中也会出现同样的问题:

if (currentPrt->getBeforePtr() != nullptr){
            currentPrt = currentPrt->getBeforePtr();
            newPtr->setNextPtr(currentPrt->getNextPtr());
            currentPrt->setNextPtr(newPtr);
            newPtr->setBeforePtr(currentPrt);
        }

缺少相同的语句,可以更正为:

if (currentPrt->getBeforePtr() != nullptr){
            currentPrt = currentPrt->getBeforePtr();
            newPtr->setNextPtr(currentPrt->getNextPtr());
            currentPrt->getNextPtr()->setBeforePtr(newPtr); // <---
            currentPrt->setNextPtr(newPtr);
            newPtr->setBeforePtr(currentPrt);
        }

相关问题