c++ - 任何人都可以帮助我自定义链接列表吗？我无法找到或修复段错误

Question

我正在尝试为班级制作自定义链接列表。我相信段错误在插入函数中，但不确定。我已经按照需要的方式设置了它，但是在某个地方我遇到了段错误。我不知道它在哪里，当我更改插入函数代码的片段时，它不会运行。main 函数与标准库链表的 main 相同。当我运行打印语句时，它第二次通过添加项目的 for 循环失败，这就是我认为它在插入函数中的原因。

链表.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include "LinkedList.h"

// Step 1. create a Grocery class that holds an isle and a name
class Grocery {
public:
    int aisle;
    std::string food;

    Grocery(int aisle = 0, std::string food = "") {
        this->aisle = aisle;
        this->food = food;
    }

    void print() {
        std::cout << food << std::endl;
    }
};

int main() {
    // Step 2. Construct a std::list<Grocery>
    LinkedList<Grocery> list;
    int listLength;
    std::string name;
    int aisle;

    auto it = list.begin();

    std::cin >> listLength;

    // Step 3: Read N groceries and insert them one-at-a-time
    // into the list, making sure you insert them in sorted order.
    // I recommend using iterators and `insert()`.
    for(int i = 0; i < listLength; i++) {
        std::cin >> aisle;
        std::cin >> name;
        Grocery tempGrocery(aisle, name);

        for(it = list.begin(); !it.end(); it++) {
            if(it->aisle > aisle)
                break;
        }

        // After the loop you can do the insert.
        list.insert(it, tempGrocery);
    }

    int numRemove;
    std::cin >> numRemove;
    std::string remove;

    for(int i = 0; i < numRemove; i++) {
        std::cin >> remove;

        for(it = list.begin(); !it.end(); it++) {
            if(it->food == remove) {
                list.erase(it);
                break;
            }
        }
    }

    // Step 5: Print out all groceries in the list.

    for(it = list.begin(); !it.end(); it++)
        it->print();
}

链表.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

template <class T>  // ************Node**************
class Node {
public:
    T data;
    Node* next;

    Node() {
        T data;
        next = nullptr;
    }
};

template <class T>  //***************Iterator***********
class Iterator {
public:
    Node<T>* prev;
    Node<T>* node;

    Iterator(Node<T>* node, Node<T>* prev) {}
    bool end() {
        if(node == nullptr)
            return true;
        else
            return false;
    }

    T* operator->() { return &node->data; }

    void operator++(int) {
        node = node->next;
        // return *this;
    }
};

template <class T>  //****************List******************
class LinkedList {
public:
    Node<T>* head;

    LinkedList() { head = nullptr; }

    void insert(Iterator<T> it, T data) {
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        if(head == nullptr) {
            head = newNode;
            return;
        } else {
            // not calling node pointer??
            // trying to call node data??
            // if (!it.end()) {
            it.prev->next = newNode;
            it.prev = newNode;
            newNode->next = it.node;
            //}
        }
    }
    // should return head
    // will not convert to iterator from node??
    Iterator<T> begin() {
        Iterator<T> it = Iterator<T>(head, nullptr);
        // it.end() = true;
        return it;
    }

    void erase(Iterator<T> it) {
        it.node = it.prev;
        it.node = it.node->next;
        it.node->data = 0;
        it.node->next = nullptr;
    }
};

#endif  // LINKED_LIST_H

Answer 1

您可能首先要解决编译器警告：

请始终在启用所有警告的情况下进行编译。

---

然后，在您的迭代器函数中，取消引用 nullptr。

在编写类似的内容之前，it.prev->next您应该检查是否为 nullptr。it.prevnext

此外。很抱歉，您的迭代器实现是相当错误的。基本上这里解释的太多了。

但是给你一个想法，如何实现一个列表。我会给你一个单链表和双链表的例子。

特别有用的是双链表中的哨兵方法。

请参见：

单链表：

#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>

// Very simple implementation of a forward list
template <class T>
class SinglyLinkedList {

    // The node
    struct Node {
        T data{};     // Data. Would normally be a templated argument
        Node* next{};   // And the pointer to the next node

        Node(const T& i, Node* n = nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
    };

    Node* head{};       // This is the start of the list
    // It would be advisable to have a tail pointer. We use the more inefficient approach here
    Node* getLast() const { Node* n{ head }; while (n and n->next) n = n->next; return n; }

public:
    // Constructor / Destructor --------------------------------------------------------------------------------------------------------
    ~SinglyLinkedList() { clear(); }

    // Default constuctor
    SinglyLinkedList() {}   // Default

    // From an initialization list
    SinglyLinkedList(const std::initializer_list<T>& il) { clear();  for (const T& i : il) push_back(i); } // From initializer list

    // Copy constructor
    SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const T& i : other) push_back(i); }

    // Move constructor. Will steal the elements from the other 
    SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr;}

    // Assignment operator
    SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const T& i : other) push_back(i); }

    // Move assignment operator 
    SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }

    // Housekeeping --------------------------------------------------------------------------------------------------------------
    void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
    int empty() const { return head == nullptr; }
    int size() const { int k{}; Node* n{ head }; while (n) { ++k; n = n->next; } return k; }

    // Modify content --------------------------------------------------------------------------------------------------------------
    void push_front(const T& i) { Node* n = new Node(i); n->next = head; head = n; };
    void push_back(const T& i) { Node* n = new Node(i); Node* l = getLast(); if (l) l->next = n; else head = n; }
    void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
    void pop_back() { // This is a little bit more difficult in a singly linked list
        if (head) {
            Node* n{ head }, * previous{};
            while (n and n->next) {
                previous = n;
                n = n->next;
            }
            delete n;
            if (previous)
                previous->next = nullptr;
            else
                head->next = nullptr;
        }
    }

    // Access elements --------------------------------------------------------------------------------
    T& front() const { return head ? head->data : 0; };
    T back() const { Node* n = getLast(); return n ? n->data : 0; }

    // Add iterator properties to class ---------------------------------------------------------------
    struct iterator {                           // Local class for iterator
        Node* iter{};                           // Iterator is basically a pointer to the node
        Node* head{};

        // Define alias names necessary for the iterator functionality
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Constructor
        iterator() {}
        iterator(Node* n, Node* h) : iter(n), head(h) {}

        // Dereferencing
        reference operator *() const { return iter->data; }
        pointer operator ->() const { return &iter->data; }

        // Aithmetic operations
        iterator& operator ++() { if (iter) iter = iter->next; return *this; }
        iterator operator ++(int) { iterator temp{ *this }; ++* this; return temp; }

        // Clumsy subtratcion
        iterator& operator --() { Node* tmp = head; while (tmp and tmp->next != this->iter) tmp = tmp->next; iter = tmp;  return *this; }
        iterator operator --(int) { iterator temp{ *this }; --* this; return temp; }

        iterator operator +(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)++temp; else while (k++)--temp; return temp;
        }
        iterator operator +=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)++* this; else while (k++)--* this; return *this;
        };
        iterator operator -(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k++)++temp; return temp;
        }
        iterator operator -=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k++)++* this; return *this;
        };

        // Comparison
        bool operator != (const iterator& other) const { return iter != other.iter; }
        bool operator == (const iterator& other) const { return iter == other.iter; }
        bool operator < (const iterator& other) const { return other.iter - iter < 0; };
        bool operator <= (const iterator& other) const { return other.iter - iter <= 0; };
        bool operator > (const iterator& other) const { return other.iter - iter > 0; };
        bool operator >= (const iterator& other) const { return other.iter - iter >= 0; };

        // Difference. Also complicated, because no random access
        difference_type operator-(const iterator& other) const {
            difference_type result{};
            Node* nptr = head;
            int indexThis{ -1 }, indexOther{ -1 }, index{};

            while (nptr != nullptr) {
                if (nptr == iter)
                    indexThis = index;
                if (nptr == other.iter)
                    indexOther = index;
                nptr = nptr->next;
                ++index;
            }
            if (nptr == iter)
                indexThis = index;
            if (nptr == other.iter)
                indexOther = index;

            if (indexThis >= 0 and indexOther >= 0)
                result = indexThis - indexOther;
            return result;
        }
    };

    // Begin and end function to initialize an iterator
    iterator begin() const { return iterator(head, head); }
    iterator end() const { return iterator(nullptr, head); }

    // Functions typcical for forward lists ----------------------------------------------------------------------
    // Easy, becuase we can operate form the current iterator and do not need the "previous" element
    iterator insertAfter(iterator& pos, const T& i) {
        iterator result(nullptr, head);
        if (pos.iter and pos.iter->next) {
            Node* n = new Node(i, pos.iter->next);
            pos.iter->next = n;
            result.iter = n;
        }
        return result;
    }
    iterator eraseAfter(iterator& pos) {
        iterator result(nullptr, head);
        if (pos.iter and pos.iter->next) {
            Node* tmp = pos.iter->next->next;
            delete pos.iter->next;
            pos.iter->next = tmp;
            result.iter = pos.iter->next;
        }
        return result;
    }
};
// Test/Driver Code
int main() {

    // Example for initilizer list
    SinglyLinkedList<int> sllbase{ 5,6,7,8,9,10,11,12,13,14,15 };
    // Show move constructor
    SinglyLinkedList<int> sll(std::move(sllbase));

    // Add some values in the front
    sll.push_front(4);
    sll.push_front(3);
    sll.push_front(2);
    sll.push_front(1);

    // Delete 1st element (Number 1)
    sll.pop_front();
    // Delete last element
    sll.pop_back();

    // Use a std::algorithm on our custom linked list. Works because we have an interator
    SinglyLinkedList<int>::iterator iter = std::find(sll.begin(), sll.end(), 8);
    ++iter;
    --iter;

    // Now add an element after 8
    iter = sll.insertAfter(iter, 88);
    // And delete the 9
    iter = sll.eraseAfter(iter);

    std::cout << "\n\nDelta between end and begin: " << (sll.end() - sll.begin()) << "\n\n";

    // Use range based for loop. Works because, we have iterators
    for (int i : sll)
        std::cout << i << ' ';


    // Reverse Output
    std::cout << "\n\n";
    std::reverse_iterator<SinglyLinkedList<int>::iterator> riter = std::make_reverse_iterator(sll.end());
    std::reverse_iterator<SinglyLinkedList<int>::iterator> riterEnd = std::make_reverse_iterator(sll.begin());

    for (; riter != riterEnd; ++riter)
        std::cout << *riter << ' ';
    std::cout << "\n\n";

    return 0;
}

---

双链表。如同std::list

#include <iostream>
#include <iterator>
#include <vector>
#include <type_traits>
#include <initializer_list>
#include <algorithm>
#include <list>

// ------------------------------------------------------------------------------------------------
// This would be in a header file -----------------------------------------------------------------

// Type trait helper to identify iterators --------------------------------------------------------
template<typename T, typename = void>
struct is_iterator { static constexpr bool value = false; };
template<typename T>
struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::value_type, void>::value>::type> {
    static constexpr bool value = true;
};

// The List class ---------------------------------------------------------------------------------
template <typename T>
class List {
    // Sub class for a Node -----------
    struct Node {
        Node* next{};
        Node* previous{};
        T data{};
        Node(Node* const n, Node* const p, const T& d) : next(n), previous(p), data(d) {}
        Node(Node* const n, Node* const p) : next(n), previous(p) {}
        Node() {}
    };

    // Private list data and functions --------
    size_t numberOfElements{};
    Node* head{};
    void init() { head = new Node(); head->next = head; head->previous = head; numberOfElements = 0; }

public:
    struct iterator;    // Forward declaration

    // Constructor --------------------
    List() { init(); }
    explicit List(const size_t count, const T& value) { init(); insert(begin(), count, value); };
    explicit List(const size_t count) { init(); insert(begin(), count); }
    template <typename Iter>
    List(const Iter& first, const Iter& last) { init(); insert(begin(), first, last); }
    List(const List& other) { init(), insert(begin(), other.begin(), other.end()); };
    List(List&& other) : head(other.head), numberOfElements(other.numberOfElements) { other.init(); }
    List(const std::initializer_list<T>& il) { init(); insert(begin(), il.begin(), il.end()); }
    template <int N> List(const T(&other)[N]) { init(); insert(begin(), std::begin(other), std::end(other)); }
    template <int N> List(T(&other)[N]) { init(); insert(begin(), std::begin(other), std::end(other)); }


    // Assignment ---------------------
    List& operator =(const List& other) { clear(); insert(begin(), other.begin(), other.end()); return *this; }
    List& operator =(List&& other) { clear(); head = other.head; numberOfElements = other.numberOfElements; other.init(); return *this; }
    List& operator =(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); return *this; }
    template <int N> List& operator =(const T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }
    template <int N> List& operator =(T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }

    void assign(const size_t count, const T& value) { clear(); insert(begin(), count, value); }
    void assign(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); }
    template <typename Iter> void assign(const Iter& first, const Iter& last) { clear(); insert(begin(), first, last); }
    template <int N> void assign(const T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }
    template <int N> void assign(T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }

    // Destructor ---------------------
    ~List() { clear(); }

    // Element Access -----------------
    T& front() { return *begin(); }
    T& back() { return *(--end()); }

    // Iterators ----------------------
    iterator begin() const { return iterator(head->next, head); }
    iterator end() const { return iterator(head, head); }

    // Capacity -----------------------
    size_t size() const { return numberOfElements; }
    bool empty() { return size() == 0; }

    // Modifiers ----------------------
    void clear();

    iterator insert(const iterator& insertBeforePosition, const T& value);
    iterator insert(const iterator& insertBeforePosition);
    template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool> = true>
    iterator insert(const iterator& insertBeforePosition, const Iter& first, const Iter& last);
    iterator insert(const iterator& insertBeforePosition, const size_t& count, const T& value);
    iterator insert(const iterator& insertBeforePosition, const std::initializer_list<T>& il);

    iterator erase(const iterator& posToDelete);
    iterator erase(const iterator& first, const iterator& last);


    void push_back(const T& d) { insert(end(), d); }
    void pop_back() { erase(--end()); };

    void push_front(const T& d) { insert(begin(), d); }
    void pop_front() { erase(begin()); };

    void resize(size_t count);
    void resize(size_t count, const T& value);

    void swap(List& other) { std::swap(head, other.head); std::swap(numberOfElements, other.numberOfElements); }

    // Operations --------------------
    void reverse();

    // Non standard inefficient functions --------------------------
    T& operator[](const size_t index) const { return begin()[index]; }

    // ------------------------------------------------------------------------
    // Define iterator capability ---------------------------------------------
    struct iterator {

        // Definitions ----------------
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Data -----------------------
        Node* iter{};
        Node* head{};

        // Constructor ----------------
        iterator(Node* const node, Node* const h) : iter(node), head(h) {};
        iterator() {};

        // Dereferencing --------------
        reference operator*() const { return iter->data; }
        reference operator->() const { return &**this; }

        // Arithmetic operations ------
        iterator operator++() { iter = iter->next; return *this; }
        iterator operator++(int) { iterator tmp = *this; ++* this; return tmp; }
        iterator operator--() { iter = iter->previous; return *this; }
        iterator operator--(int) { iterator tmp = *this; --* this; return tmp; }

        iterator operator +(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)++temp; else while (k++)--temp; return temp;
        }
        iterator operator +=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)++* this; else while (k++)--* this; return *this;
        };
        iterator operator -(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k++)++temp; return temp;
        }
        iterator operator -=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k++)++* this; return *this;
        };
        // Comparison ----------------- (typical space ship implementation)
        bool operator ==(const iterator& other) const { return iter == other.iter; };
        bool operator !=(const iterator& other) const { return iter != other.iter; };
        bool operator < (const iterator& other) const { return other.iter - iter < 0; };
        bool operator <= (const iterator& other) const { return other.iter - iter <= 0; };
        bool operator > (const iterator& other) const { return other.iter - iter > 0; };
        bool operator >= (const iterator& other) const { return other.iter - iter >= 0; };

        // Special non standard functions -----------------
        difference_type operator-(const iterator& other) const;
        reference operator[] (const size_t index);
    };
};


// ------------------------------------------------------------------------------------------------
// Implementation of list functions. This would normally go into a TCC file -----------------------

// List class functions ---------------
template <typename T>
void List<T>::clear() {

    for (Node* nextNode{}, * currentNode(head->next); currentNode != head; currentNode = nextNode) {
        nextNode = currentNode->next;
        delete currentNode;
    }
    init();
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const T& value)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous, value);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
    ++numberOfElements;
    return iterator(newNode, head);
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
    ++numberOfElements;
    return iterator(newNode, head);
}

template <typename T>
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool>>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const Iter& first, const Iter& last) {
    iterator result(insertBeforePosition.iter, head);
    if (first != last) {
        result = insert(insertBeforePosition, *first);
        Iter i(first);
        for (++i; i != last; ++i)
            insert(insertBeforePosition, *i);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const size_t& count, const T& value) {

    iterator result(insertBeforePosition.iter, head);
    if (count != 0u) {
        result = insert(insertBeforePosition, value);
        for (size_t i{ 1u }; i < count; ++i)
            insert(insertBeforePosition, value);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const std::initializer_list<T>& il) {
    return insert(insertBeforePosition, il.begin(), il.end());
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& posToDelete) {

    iterator result = posToDelete;
    ++result;

    Node* nodeToDelete = posToDelete.iter;

    if (nodeToDelete != head) {

        nodeToDelete->previous->next = nodeToDelete->next;
        nodeToDelete->next->previous = nodeToDelete->previous;

        delete nodeToDelete;
        --numberOfElements;
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& first, const List<T>::iterator& last) {
    iterator result{ end() };
    if (first == begin() && last == end())
        clear();
    else {
        while (first != last)
            first = erase(first);
        result = last;
    }
    return result;
}

template <typename T>
void List<T>::resize(size_t count) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count; ++i)
            insert(end());
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::resize(size_t count, const T& value) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count; ++i)
            insert(end(), value);
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::reverse() {
    const Node* oldHead = head;

    for (Node* nptr = head; ; nptr = nptr->previous) {
        std::swap(nptr->next, nptr->previous);
        if (nptr->previous == oldHead) // Previous was the original next
            break;
    }
}

// ------------------------------------
// Iterator functions -----------------
template <typename T>
typename List<T>::iterator::difference_type List<T>::iterator::operator-(const iterator& other) const {

    difference_type result{};
    Node* nptr = head;

    int indexThis{ -1 }, indexOther{ -1 }, index{};

    do {
        nptr = nptr->next;
        if (nptr == iter)
            indexThis = index;
        if (nptr == other.iter)
            indexOther = index;
        ++index;
    } while (nptr != head);

    if (indexThis >= 0 and indexOther >= 0)
        result = indexThis - indexOther;
    return result;
}
template <typename T>
typename List<T>::iterator::reference List<T>::iterator::operator[] (const size_t index) {
    Node* nptr = head->next;
    for (size_t i{}; i < index and nptr != head; ++i, nptr = nptr->next)
        ;
    return nptr->data;
}

// ------------------------------------------------------------------------------------------------
// This would be in a cpp file --------------------------------------------------------------------
int main() {


    List<int> list3{ 10,20 };
    List<int>::iterator l3 = list3.end();
    for (int k = 0; k < 10; ++k) {
        std::cout << *l3 << ' ';
        --l3;
    }
    std::cout << '\n';

    // Custom list
    List<int> list2{ 1, 2, 3, 4, 5 };

    for (int i : list2)
        std::cout << i << ' '; std::cout << '\n';

    // Delta works
    std::cout << list2.begin() - list2.end() << '\n';
    std::cout << list2.end() - list2.begin() << '\n';

    // Hopp Count works
    List<int>::iterator i = list2.end();
    while (i-- != list2.begin())
        std::cout << *i << ' '; std::cout << '\n';
}