我正在尝试制作链表，但它已经处理了一个异常——将新节点添加到第一个位置。
我的节点：
struct MyNode
{
string s;
int i;
MyNode* pointer;
}
链表：
private:
MyNode first;
int count;
public:
//methods
我有两个想法如何将新节点添加到第一个位置，但都不起作用。第一个：
void Add(Node* node, int index)
{
if (index == 1)
{
node->pointer = &first;
first = *node;
}
}
节点指针指向自身，所有其他节点都将丢失。
第二个想法：
void Add(Node* node, int index)
{
if (index == 1)
{
Node n2 = first;
first = *node;
first.pointer = &n2;
}
}
它一开始工作得很好，但一旦程序离开if，本应是第二个的节点就会丢失其字符串数据(整数不是出于某种原因(。
是否可以编写将节点添加到第一个位置的方法，而不必重新制作列表的结构(这会破坏我编写的所有其他方法(？
编辑：最小可复制示例：
#include <string>
using namespace std;
struct Person
{
string forename{};
string surname{};
int age{};
Person* pointer{};
};
class linked_list
{
private:
Person first;
int count = 0;
Person* GetPointer(int index)
{
Person* current = &first;
Person* next = first.pointer;
if (index == 1) return &first;
for (int i = 1; (i < index) && (next->pointer != NULL); i++)
{
current = next;
next = next->pointer;
}
return current;
}
public:
linked_list()
{
first.forename = "dummy";
first.surname = "dummy";
first.age = 0;
}
void Add(Person* p, int index)
{
if ((index < 1) || (index > count + 1))
{
throw 0;
}
else if (index == 1)
{
Person p2 = first;
first = *p;
first.pointer = &p2;
/*p->pointer = &first;
first = *p;*/
}
else if (index == count + 1)
{
p->pointer = NULL;
Person* p2 = GetPointer(index);
p2->pointer->pointer = p;
}
else
{
p->pointer = GetPointer(index);
Person* p2 = GetPointer(index - 1);
p2->pointer = p;
}
count++;
}
};
int main()
{
linked_list l;
Person p;
p.age = 35;
p.forename = "John";
p.surname = "Smith";
l.Add(&p, 1);
}
有些事情需要做。
所有变量都必须初始化。这是最重要的。您也可以在类定义中直接执行此操作。示例：
struct MyNode {
string s{};
int i{};
MyNode* pointer{};
};
使用{}进行统一值初始化已有10年历史。它将把字符串初始化为一个空字符串；i〃；到0和"0"；指针"；至CCD_ 2。
在单链表的上下文中，变量名"；下一个"；使用而不是指针。
然后，根据您的正确操作，节点是链表的一部分。在面向对象的术语中，你会说一个链表"；具有"；节点。我们称之为"；具有"-关系
但在这里，你会使用一个不同的名字。
"MyNode优先"将变成"；MyNode*头"因为，有符号链接的列表只需要指向列表中第一个节点的指针。
如果要将值添加到链表，则需要动态创建一个新节点，将值分配给节点，然后将节点添加到链表。
我们需要区分添加第一个节点还是向已经包含其他节点的列表中添加节点。
空的链表很容易识别。"；头部；指针将是CCD_ 3，然后您可以简单地将新节点的指针分配给"0"；头"；。
在单链表中已经有元素的情况下，那么你必须找到节点链中的最后一个元素，从开头开始，然后跟随所有"；下一个"；指针，直到这是"；nullptr"；。然后将新节点添加到下一个指针中。
为了让你更好地理解，你可以学习所附的代码(也许有点高级，但无论如何(：
#include <iterator>
#include <algorithm>
#include <iostream>
#include <initializer_list>
// 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_back(const T& i) { Node* n = new Node(i); Node* l = getLast(); if (l) l->next = n; else head = n; }
void push_front(const T& i) { Node* n = new Node(i); n->next = head; head = n; };
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;
}
}
void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
// Access elements --------------------------------------------------------------------------------
T back() const { Node* n = getLast(); return n ? n->data : 0; }
T front() const { return head ? head->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 --() { 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 --(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 iter < other.iter; }
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 iter >= other.iter; }
// Difference. Also complicated, because no random access
difference_type operator-(const iterator& other) const {
difference_type result{};
Node* n{ iter };
while (n and n != other.iter) {
++result;
n = n->next;
}
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);
// Use range based for loop. Works because, we have iterators
for (int i : sll)
std::cout << i << ' ';
// Reverse Output
std::cout << "nn";
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 << "nn";
return 0;
}