我正在学习链表，我决定尝试自己在C++中实现链表。
我制作了一个属性为int val和Node* ptr的Node类。然后，我制作了一个属性为first_node的Linked_list类，构造函数就可以工作了。
append()函数将一个节点"附加"到列表中(类似于Python)。我首先想到的是将ptr作为对节点指针的引用，然后在其为null时对其进行更改，但一旦进行了引用，就不能更改为引用任何其他变量，所以我制作了另一个指向Node指针的变量prev_ptr(这使其成为Node**)。
每次循环，它都会检查ptr是否为NULL，如果不是，则ptr和prev_ptr将分别更新到下一个Node的指针值和下一个Node的指针值的地址。
这种情况一直发生，直到它找到一个空指针，然后将其更改为输入节点的地址。
但我得到一个错误说：
引发异常：写入访问冲突。prev_ptr为0x4。
我搞不清楚出了什么问题。
类别：
#include <iostream>
#include <string>
#include <cmath>
class Node {
public:
int val;
Node* ptr = nullptr;
Node(int Val = NULL) {
val = Val;
}
};
class Linked_list {
public:
Node first_node;
Linked_list(int F) {
Node f(F);
first_node = f;
}
void append(Node& element) {
Node* ptr = first_node.ptr;
Node** prev_ptr = &first_node.ptr;
while (true) {
if (ptr == nullptr) {
*prev_ptr = &element;
break;
}
ptr = (*ptr).ptr;
prev_ptr = &((*ptr).ptr);
}
}
};
main()
int main() {
Linked_list list(5);
Node three(3);
list.append(three);
Node four(4);
list.append(four);
return 0;
}
ptr = (*ptr).ptr;
prev_ptr = &((*ptr).ptr);
首先将ptr推进到下一个节点。然后，您再次使用ptr，忘记了它已经被高级了：(*ptr).ptr现在指向两个节点，我们不知道我们是否可以走那么远。
也许你需要交换作业。
prev_ptr = &((*ptr).ptr);
ptr = (*ptr).ptr;
(此外，为什么不ptr->ptr？)
好吧，您正在以一种奇怪的方式做一些事情。首先，您的Linked_List可能不应该为firstNode设置Node。它应该有一个节点*。毕竟，空列表是可能的。(通常)删除第一个节点也是如此。此外，还有一个非正式的命名约定，称之为head。还有一个标准约定，即在节点next而不是ptr中调用链接。
但是append()方法有两个更简单的方法。首先，您还可以在Linked_List中保留一个Node*尾部。这很常见。它指向列表中的最后一个节点。如果你这样做，那么附加看起来像：
void append(Node &nodeToAppend) {
if (head == nullptr) {
head = &nodeToAppend;
tail = &nodeToAppend;
}
else {
tail->next = nodeToAppend;
tail = &nodeToAppend;
}
}
然而，能够在任何地方插入或无尾附加也是值得的：
void append(Node &nodeToAppend) {
if (head == nullptr) {
head = &nodeToAppend;
}
else {
Node *ptr = head;
while (ptr->next != nullptr) {
ptr = ptr->next;
}
ptr->next = &nodeToAppend;
}
}
按照某种排序顺序插入的内容几乎相同，但略有不同。while循环看起来像：
while (ptr->next != nullptr && ptr->value < nodeToAppend.value) ...
但在其他方面是相同的。
这段代码并不能解决您眼前的问题，而是回答了评论中提出的一个问题。
链表通常是(我教的地方)300-400级的作业。要写一份像样的链表，有很多原则是必须具备的。首先，我将展示main.cpp及其输出。
main.cpp
#include "list.hpp"
#include <iostream>
template <typename Container>
void print(Container& container, std::ostream& sout = std::cout)
{
for (auto i : container) {
sout << i << ' ';
}
sout << 'n';
}
int main()
{
List<int> list;
for (int i = 1; i <= 10; ++i) {
list.push_back(i);
}
print(list);
list.erase(list.find(4));
print(list);
list.erase(list.find(1));
print(list);
list.erase(list.find(10));
print(list);
}
输出：
1 2 3 4 5 6 7 8 9 10
1 2 3 5 6 7 8 9 10
2 3 5 6 7 8 9 10
2 3 5 6 7 8 9
它并没有测试链表的每一个方面，但它用来展示用户应该使用什么。用户将希望在C++中直接与列表及其迭代器进行交互。创建一个Node，然后将该Node添加到您的列表中。这是一个没有用户愿意被打扰的DIY水平。在下面的代码中，您将看到Node仍然在使用，但它只存在于List类中。用户永远看不到Node。
您可以在push_back()(类似于您的附加)等函数中查找与您的问题相关的特定答案。
更详细地解释一下，指针是关键。是的，我声明了一个本地Node*，它将超出作用域，但创建的对象仍然存在于堆中。由于链表的工作方式，列表能够跟踪这些Node，即Node知道他们的邻居住在哪里(保存他们的地址)。
还有一个List<T>::iterator类。在声明中，如果要在基于范围的for循环中使用链表，则需要标记为// minimum的函数。其他功能确实可以满足LegacyBidirectionalIterator的要求；这是std::list在C++标准库中使用的迭代器级别。
下面的代码应该只是一个不错的例子(希望我不要太冒昧)。它缺少std::list中的一些功能，可能会以非最佳方式做一些事情。需要调整的一件大事是删除成员函数find()，并使该类与std::find()一起工作。
list.hpp
#ifndef MY_LIST_HPP
#define MY_LIST_HPP
#include <algorithm> // std::swap
#include <cstddef> // std::size_t
/*
* Pre-declare template class and friends
*/
template <typename T>
class List;
template <typename T>
void swap(List<T>& lhs, List<T>& rhs);
/*
* List Class Declaration
*/
template <typename T>
class List {
public:
List() = default;
List(T val);
List(const List& other);
List(List&& other);
~List();
void push_front(T val);
void push_back(T val);
class iterator;
iterator begin();
iterator end();
iterator find(T val);
std::size_t size() const;
iterator erase(iterator toErase); // Implement
void clear();
bool operator=(List other);
friend void swap<T>(List& lhs, List& rhs);
private:
struct Node {
T data;
Node* prev = nullptr;
Node* next = nullptr;
Node(T val) : data(val) {}
};
Node* m_head = nullptr;
Node* m_tail = nullptr;
std::size_t m_size = 0;
// Helper functions
void make_first_node(T val);
Node* find_node(T val);
};
/*
* List Iterator Declaration
*/
template <typename T>
class List<T>::iterator {
public:
iterator() = default;
iterator(List<T>::Node* node); // minimum
T& operator*(); // minimum
iterator& operator++(); // minimum
iterator operator++(int);
iterator& operator--();
iterator operator--(int);
bool operator==(const iterator& other); // minimum
bool operator!=(const iterator& other); // minimum
private:
Node* m_pos = nullptr;
};
/*
* List Implementation
*/
template <typename T>
List<T>::List(T val) : m_head(new Node(val)), m_tail(m_head), m_size(1) {}
template <typename T>
List<T>::List(const List<T>& other) {
m_head = new Node((other.m_head)->data);
m_tail = m_head;
m_size = 1;
Node* walker = (other.m_head)->next;
while (walker) {
push_back(walker->data);
++m_size;
walker = walker->next;
}
}
template <typename T>
List<T>::List(List&& other) : List() {
swap(*this, other);
}
template <typename T>
List<T>::~List() {
clear();
}
template <typename T>
void List<T>::push_front(T val)
{
if (!m_head) {
make_first_node(val);
return;
}
Node* tmp = new Node(val);
tmp->next = m_head;
m_head->prev = tmp;
m_head = tmp;
++m_size;
}
template <typename T>
void List<T>::push_back(T val) {
if (!m_head) {
make_first_node(val);
return;
}
Node* tmp = new Node(val);
tmp->prev = m_tail;
m_tail->next = tmp;
m_tail = tmp;
++m_size;
}
template <typename T>
typename List<T>::iterator List<T>::begin() {
return iterator(m_head);
}
template <typename T>
typename List<T>::iterator List<T>::end() {
return iterator(nullptr);
}
template <typename T>
typename List<T>::iterator List<T>::find(T val) {
return iterator(find_node(val));
}
template <typename T>
std::size_t List<T>::size() const {
return m_size;
}
template <typename T>
typename List<T>::iterator List<T>::erase(typename List<T>::iterator toErase)
{
Node* node = find_node(*toErase);
if (node->prev) {
node->prev->next = node->next;
} else {
m_head = node->next;
}
if (node->next) {
node->next->prev = node->prev;
} else {
m_tail = node->prev;
}
Node* toReturn = node->next;
delete node;
return toReturn;
}
template <typename T>
void List<T>::clear() {
Node* tmp = m_head;
while (m_head) {
m_head = m_head->next;
delete tmp;
tmp = m_head;
}
m_tail = nullptr;
m_size = 0;
}
template <typename T>
bool List<T>::operator=(List other) {
swap(*this, other);
return *this;
}
template <typename T>
void List<T>::make_first_node(T val) {
m_head = new Node(val);
m_tail = m_head;
m_size = 1;
}
template <typename T>
typename List<T>::Node* List<T>::find_node(T val) {
if (!m_head) {
return nullptr;
}
Node* walker = m_head;
while (walker != nullptr && walker->data != val) {
walker = walker->next;
}
return walker;
}
template <typename T>
void swap(List<T>& lhs, List<T>& rhs) {
using std::swap;
swap(lhs.m_head, rhs.m_head);
swap(lhs.m_tail, rhs.m_tail);
swap(lhs.m_size, rhs.m_size);
}
/*
* List Iterator Implementation
*/
template <typename T>
List<T>::iterator::iterator(Node* node) : m_pos(node) {}
template <typename T>
T& List<T>::iterator::operator*() {
return m_pos->data;
}
template <typename T>
typename List<T>::iterator& List<T>::iterator::operator++() {
m_pos = m_pos->next;
return *this;
}
template <typename T>
typename List<T>::iterator List<T>::iterator::operator++(int) {
iterator tmp(m_pos);
++(*this);
return tmp;
}
template <typename T>
typename List<T>::iterator& List<T>::iterator::operator--() {
m_pos = m_pos->prev;
return *this;
}
template <typename T>
typename List<T>::iterator List<T>::iterator::operator--(int) {
iterator tmp(m_pos);
--(*this);
return tmp;
}
template <typename T>
bool List<T>::iterator::operator==(const iterator& other) {
return m_pos == other.m_pos;
}
template <typename T>
bool List<T>::iterator::operator!=(const iterator& other) {
return !(*this == other);
}
#endif
代码和解释
我认为这段代码应该也能工作，所以没有必要有两个指针。这是基于Linus Torvalds在一次采访中给出的一个"好品味">的例子。
void append(Node &element)
{
Node** cursor = &first_node.ptr;
while ((*cursor) != nullptr)
cursor = &(*cursor)->ptr;
*cursor = &element;
}
它消除了对多个指针的需要，消除了边缘情况，并允许我们评估while循环的条件，而不必松开指向下一个元素的指针。这允许我们修改指向NULL的指针，并与ptr和prev_ptr相反地使用单个迭代器。
命名约定
此外，规范是调用链表中的第一个节点head，并调用指向下一个节点的指针next而不是ptr，因此我将在下面的代码中重命名它们。
void append(Node &new)
{
Node** cursor = &head.next;
while ((*cursor) != nullptr)
cursor = &(*cursor)->next;
*cursor = &new;
}