我想在此页面上尝试链接列表的示例：如何使用 C++ 创建链接列表。
到目前为止，这是我的代码：
#include <iostream>
using namespace s-td;
class node {
public:
int value;
node *next;
};
int main() {
node *head = nullptr;
node *temp1;
temp1 = new node();
temp1->value = 1;
temp1 = head;
while(temp1->next!=nullptr) {
temp1 = temp1->next;
}
return 0;
}
但不幸的是，我得到了一个Segmentation fault. 我认为这部分是错误的：
while(temp1->next!=nullptr) {
temp1 = temp1->next;
}
您的代码有两个问题：
a）您正在分配，这在您的情况下temp1 = head是同义词temp1 = nullptr
b）您没有初始化->next为 be nullptr，因此您的 while 条件可能会或可能不会满足（未定义的行为）
node *head = nullptr;
head是NULL
temp1 = head;
temp1变成NULL
while(temp1->next!=nullptr) {
temp1是NULL，因此temp1->next是取消引用一个NULL指针。
head您的程序使用空指针开始遍历列表。如果您在调试器中查看它，head 将仍然为 NULL，因为您从未设置它。
node *temp1, *temp2, *temp3;
temp1 = new node();
temp1->value = 1;
temp1->next = nullptr;
head= temp; // link to head
temp2 = new node();
temp2->value = 2;
temp2->next = nullptr;
temp1->next= temp2; // link 1 -> 2
temp3 = new node();
temp3->value = 3;
temp3->next = nullptr;
temp2->next= temp3; // link 2 -> 3
// now we have head -> temp1 -> temp2 -> temp3
// now use temp1 as iterator starting with head
temp1 = head;
while(temp1->next!=nullptr) {
printf("%d\n", temp1->value);
temp1 = temp1->next;
}
您正在分配：
node *head = 0;
// ...
temp1 = head;
while(temp1->next!=nullptr) { // temp1 is null here
temp1 = temp1->next;
}
另外temp1->next也不会为空。你应该初始化它：
#define NULL 0
class node {
public:
node(int value, node *next) {
this.value = value;
this.next = next;
}
int value;
node *next;
};
// ..
node *n3 = new node(1, NULL);
node *n2 = new node(1, n3);
node *n1 = new node(1, n2);
那篇文章对如何在 C 中创建链表给出了合理的解释，并且使用了 C++ 注释，但对如何在 C++ 中创建链表却是一个糟糕的解释。
让我带你远离那里的 C 思维模式，让你走上封装的道路。
通常，链表中的每个元素都称为“节点”，每个节点都有一个指向链表中一个或多个其他节点的指针。在“单链表”中，它指向下一个节点，在“双向链表”中，有一个指向之前节点和之后节点的指针，以允许我们向后和向前移动。
一个重要的早期决定是您希望如何封装此指向。您可以选择拥有一个简单的“Node”类，它是 List 类的私有，它具有 prev/next 指针和指向实际数据本身的离散“void*”指针。这是一种非常类似于 C 的方法，因为它丢弃了类型信息。啊-但是您可以将类型存储为枚举之类的吗？你可以，这是一个很棒的 C 解决方案。
但是 C++ 完全是关于封装的。作为列表的节点是一个定义明确且相当离散的角色，具有一组简单的属性和属性。它非常适合封装为简单的基类。
class ListNode
{
ListNode* m_next;
ListNode() : m_next(NULL) {}
ListNode* next() { return m_next; }
// return the last node in my current chain.
ListNode* tail() {
ListNode* node = this;
while (node->next() != nullptr)
node = node->next();
return node;
}
// insert a new node at this point in the chain,
// think about what happens if newNode->next() is not null tho.
bool linkTo(ListNode* newNode);
};
但是，一个同样重要的封装问题是，您是否希望任何人都能够来调用 ListNode 成员，或者您是否希望限制他们对 List 本身的访问者的可见性。确实有一些模式可以帮助处理抽象的“ListNode*”，而无需知道它们属于哪个列表。但是单链表有局限性——例如，在不知道列表本身的情况下，您永远无法删除条目（您怎么知道谁指向您？）
但是，这允许我们做
class Product : public ListNode {
string m_name;
std::vector<float> m_priceHistory;
public:
Product(const std::string& name_)
: ListNode()
, m_name(name_)
, m_priceHistory()
{}
void save();
};
class Book : public Product { ... };
class DVD : public Product { ... };
List productList;
productList.add(new Book("hello world"));
productList.add(new DVD("lose wait: lose a limb"));
productList.add(new Insurance("dietary related gangrene"));
...
for(ListNode* node = productList.head(); node != nullptr; node = node->next()) {
node->save();
}
另一种方法将带我们回到第一个 ListNode 想法，越像 C；问题不在于它使用了指针，而在于它丢弃了类型信息。“void”主要用于当您想说“此指针的类型不重要”时。缺点是，“这个指针的类型消失了”。我们可以用模板解决这个问题。
template<typename T> // T will be an alias for whatever type we have to deal with.
class List
{
struct Node* m_list;
public:
struct Node
{
Node* m_next;
T* m_data;
Node() : m_next(nullptr), m_data(nullptr) {}
Node* next() const { return m_next; }
bool linkTo(Node* newPredecessor);
bool link(Node* newFollower);
};
public:
List() : m_list(nullptr) {}
Node* head() { return m_next; }
Node* tail() {
if (m_list == nullptr)
return nullptr;
for (Node* node = m_list; node->m_next != nullptr; node = node->m_next)
{}
return node;
}
void insert(T* data) { // add to head of the list
Node* node = new Node(data);
node->m_next = m_head;
m_head = node;
}
Node* append(T* data) {
if (head() == nullptr)
insert(data);
else {
Node* node = new Node(data);
Node* tail = this->tail(); // could get expensive.
tail->link(node);
}
return node;
}
};
List<Product> productList;
productList.append(new Book("Gone with the money"));
productList.append(new DVD("that's no moon"));
productList.append(new Pet("llama"));
这种方法的一个优点是我们不必在数据定义中添加额外的成员/混乱。缺点是我们使用更多内存 - 每个节点需要两个指针，并且节点没有简单的方法来告诉您它们是否/在列表中的位置（您必须搜索所有节点并找到指向您的物品）。
在内存分配方面，还有一个由使用决定的成本/收益。
在这个最新的迭代中还有一个主要的 C 风格组件，Node 类太明显了。理想情况下，它应该对最终用户完全私有。但是由于数据元素无法知道它们在列表中的位置，因此不可能遍历列表。
您想要的是隐藏节点定义，以便只有列表可以看到它（不，没关系，您真的不需要更改“m_next”的能力）并创建一个提供我们需要的功能的辅助类不让我们做任何我们不应该做的事情。
public:
class Iterator
{
Node* m_node;
public:
Iterator(Node* node_=nullptr) : m_node(node_) {}
bool advance() {
if (isValid())
m_node = m_node->m_next;
return isValid();
}
T* data() {
return isValid() ? m_node->m_data : nullptr;
}
bool isValid() const { return (m_node != nullptr); }
bool isTail() const { return isValid() && (m_node->m_next != nullptr); }
// if you feel the need to get seriously advanced,
// overload operator "++" to allow ++it;
// overload operator "*" to allow (*it) to get m_data
// overload operator "=" to allow Iterator* it = list->head();
};
// in class list:
Iterator head() { return Iterator(m_head); }
Iterator tail() {
Iterator it(m_head);
while (!it.isTail()) {
it.advance();
}
return it;
}
Iterator find(const T& data_) { return find(&data_); }
Iterator find(const T* data_) {
for (Iterator it = head(); it.isValid(); it.advance()) {
if(it.data() == data_)
return it;
}
}
希望这足以给你很多想法:)