c++ - 双向链表的实现

Question

我正在尝试实现一个链表，但我完全迷失了。我到处都是断点，特别是使用删除方法。每当我改变删除方法时，不可避免地会出现一些错误。我遇到了指针错误、只有在调用删除方法时才会出现的析构函数问题等等。

这是我目前所拥有的:

头文件:

#pragma once

class IntList {
private:

    class IntNode {
    public:
        IntNode(int v, IntNode *pr, IntNode *nx);
        ~IntNode();
        IntNode* previous;
        IntNode* next;

        class iterator {

        public:
            iterator(IntNode* t);
            int& operator*();
            iterator& operator++();
            iterator& operator--();
            bool operator!=(iterator other)const;
        private:
            IntNode* target;
        };

    private:
        int value;
    };

    IntNode* head;
    IntNode* tail;
    int count;

public:

    IntList();
    ~IntList();
    void push_back(int v);
    void pop_back();
    int size() const { return count; }
    typedef IntNode::iterator iterator;
    iterator begin();
    iterator end();
    //unsigned int size() const;
    void push_front(int value);
    bool empty() const;
    int& front();
    int& back();
    void clear();
    iterator erase(iterator position);
};

实现:

#include "IntList.h"
#include <stdexcept>

IntList::IntList() : head{ nullptr }, tail{ nullptr }, count{ 0 }
{}

IntList::~IntList() {
    while (head) {
        head = head->next;
        delete head;
    }
}

void IntList::push_back(int v) {
    tail = new IntNode{ v, tail, nullptr };
    if (!head) { head = tail; }
    count += 1;
}

void IntList::pop_back() {
    tail = tail->previous;
    delete tail->next;
    count -= 1;
}

IntList::iterator IntList::begin()
{
    return iterator{ head };
}

IntList::iterator IntList::end() {
    return iterator{ nullptr };
}

void IntList::push_front(int value) {
    head = new IntNode{ value, nullptr, head };
    if (!tail) { tail = head; }
    count += 1;
}

bool IntList::empty() const{
    return (count==0);
}

int& IntList::front() {
    return *begin();
}

int& IntList::back() {
    return *begin();
}

void IntList::clear() {
    head = nullptr;
    tail = nullptr;
    count = 0;
}

IntList::iterator IntList::erase(iterator position) {

    int midpointL = 0;

    for (iterator index = begin(); index != position; ++index) {
        midpointL++;
    }

    if (midpointL == 0) {
        head = head->next;
    }
    else if (midpointL == count) {
        tail = tail->previous;
    }
    else {

        // Move head to get a reference to the component that needs to be deleted
        for (int i = 0; i < midpointL; i++) {
            head = head->next;
        }

        // Change the previous and next pointers to point to each other
        (head->previous)->next = (head->next);
        (head->next)->previous = (head->previous);

        for (int i = midpointL-1; i > 0; i++) {
            head = head->previous;
        }

    }

    count-=1;

    return position;
}


IntList::IntNode::IntNode(int v, IntNode * pr, IntNode * nx)
    : previous{ pr }, next{ nx }, value{ v }
{
    if (previous) { previous->next = this; }
    if (next) { next->previous = this; }
}

IntList::IntNode::~IntNode() {
    if (previous) previous->next = next;
    if (next) next->previous = previous;
}

IntList::IntNode::iterator::iterator(IntNode* t)
    : target{ t }
{}

int& IntList::IntNode::iterator::operator*() {
    if (!target) { throw std::runtime_error{ "Deferenced sentinel iterator." }; }
    return target->value;
}

IntList::IntNode::iterator& IntList::IntNode::iterator::operator++()
{
    if (target) { target = target->next; }
    return *this;
}

IntList::IntNode::iterator& IntList::IntNode::iterator::operator--()
{
    if (target) { target = target->previous; }
    return *this;
}

bool IntList::IntNode::iterator::operator!=(iterator other)const
{
    return (!(target == other.target));
}

谁能帮我指明正确的方向？

谢谢!

Answer 1

让我们在这里做一个快速回顾:

IntList::~IntList() {
    while (head) {
        head = head->next;
        delete head;
    }
}

你应该这样做:

IntList::~IntList() {
    while (head) {
        IntNode* newHead = head->next;
        delete head;
        head = newHead;
    }
}

因为您正在删除“下一个”对象，然后您试图在下一次迭代中访问它。

void IntList::pop_back() {
    tail = tail->previous;
    delete tail->next;
    count -= 1;
}

这里您没有检查 tail 是否为 null 或者它是否指向 head..(什么是空条件？)，也许 count!=0？如果您可以删除不存在的下一个节点

IntList::iterator IntList::end() {
    return iterator{ nullptr };
}

..end 为空？ ebd 应该是你的尾部......

int& IntList::back() {
    return *begin();
}

那是开始..不是回来。

void IntList::clear() {
    head = nullptr;
    tail = nullptr;
    count = 0;
}

清除应该释放列表中的所有对象。你在这里产生垃圾(泄漏)。

我在这里停了下来，很抱歉，这只是一个咖啡休息时间。但是你应该仔细看看:* 空指针的使用* 在不需要时删除您的节点列表项* 注意不要使用无效指针(比如我在某处看到的head->previous->next)

您必须自下而上地检查您的代码。希望这些最初的提示能帮助您完成学习过程。

玩得开心，