单链表c++构造函数、析构函数和打印输出

Question

我是一个学习c++的初学者，目前正在制作一个单链表。我遇到了一些问题，我想了很长时间，搜索了很多，但仍然没有这个代码的答案，所以我请求一些帮助。。

所以这是我链接的.h

template <class T>
class Node {
public:
T data;
Node<T>* next;
};
template <class T>
class List {
private:
Node<T> *head;
public:
List() : head(NULL) {};
~List() {
Node<T>* ptr, tmp;
for(ptr = head->next; ptr == NULL; ptr = head->next) {
delete ptr;
}     
}
List(T* arr, int n_nodes) {
head = NULL; 
Node<T> *tmp = head;
for(int i = 0; i < n_nodes; i++) {
Node<T>* node = new Node<T>;
node->data = arr[i];
if(head == NULL) {
head->next = node;
tmp = node;
}
else {
tmp->next = node;
node->next = NULL;
tmp = node;
}
}
}
friend std::ostream& operator<<(std::ostream& out, List<T>& rhs) {                                                                                                                                 
Node<T>* cur = rhs.head;
out << cur;
while(cur != NULL) {       
if(cur->next != NULL) { 
out << cur->data << ", ";
cur = cur->next;
}
else
out << cur->data << " ";
}
return out;
}
}; 

这是我的main.cc文件。

#include <iostream>
#include "linked.h"
int main() {
int array[5] = {12, 7, 9, 21, 13};
List<int> li(array, 5);
std::cout << li;
return 0;
}

我在运行构造函数时不断出现分段错误，我不知道为什么。我在哪里犯错误？任何帮助都将不胜感激！

Answer 1

您可以用一个指向指针的指针来解决这个问题：

List(T* arr, int n_nodes)
{
Node<T>** tmp = &head; // tmp *pointing* to uninitialized(!) head pointer
for(int i = 0; i < n_nodes; i++)
{
Node<T>* node = new Node<T>();
node->data = arr[i];
// now the trick:
*tmp = node; // !!!
// you now have assigned the new node to whatever pointer
// the tmp pointer points to - which initially is - guess - head...
// but we now need to advance!
tmp = &node->next;
}
// tmp now points to latestly created node's next pointer
// (or still head, if no nodes where created because of n_nodes == 0)
// be aware that this one still is not initialized! so:
*tmp = nullptr;
}

你的析构函数也必然会失败：

Node<T>* ptr, tmp;
for(ptr = head->next; ptr == NULL; ptr = head->next)
{
delete ptr; // you delete ptr, but advancing (ptr = head->next)
// is done AFTERWARDS, so you'd access already deleted memory
// undefined behaviour
}

此外，您不会删除头节点！如果head是nullptr，那么您将再次有未定义的行为。

试试这个方法：

while(head)
{
Node<T>* tmp = head; // need a copy of pointer
head = head->next;   // need to advance BEFORE deleting
delete tmp;          // now can delete safely
}