c++ - 实现链表：头部插入和析构函数

Question

我已经这样做了：

class Node {
  //
  int key;
  Node* next;

public:

  //
  Node() : key( -1 ), next( NULL ) {}
  Node( int i, Node* j ) : key( i ), next( j ) {}
  //
  ~Node() { delete next; }

  //
  static void head_insertion( Node* & head, int i );
  void print_list();
};


void Node::head_insertion( Node* & head, int i ) {


  cout << "insert() 1 head = " << head << endl; 
  // append the current list to n
  Node n(i, head);
  cout << "address of n = " << &n << endl;
  // make n the new head
  head = &n;
  //

  cout << "insert() 2 head = " << head << endl; 
}

头部插入不起作用：

insert() 1 head = 0x7fff56821518
address of n = 0x7fff56821518
insert() 2 head = 0x7fff56821518
Segmentation fault: 11

我有两个问题：

• nin中新创建的 Nodehead_insertion与 指向的地址具有相同的地址head。这是怎么回事？
• 我写了析构函数，认为会递归调用列表中下一个元素的析构函数。这个对吗？

Answer 1

You did not use dynamic memory to allocate n. On the first pass through, it gets added to the list, the function then ends and n goes out of scope. On the second pass, it happens to come up in the same position on the stack, yielding the same pointer

Answer 2

In the function void Node::head_insertion( Node* & head, int i ) you are creating a automatic variable Node n() whose lifetime is within the function scope, So outside the head_insertion function if you want to access that node you will get segmentation fault because that memory area you no longer own. To prevent that you may dynamically create object :

Node* n = new Node(i,head)

About your last question: Even if you don't write destructor of your own the compiler will provide you a default version. I guess the destructor is not calling destractor so why should be recursion.

Answer 3

中的代码void Node::head_insertion( Node* & head, int i )：

Node n(i, head);
cout << "address of n = " << &n << endl;
// make n the new head
head = &n;

应该：

Node *pn = new Node(i, head);
cout << "address of n = " << pn << endl;
// make n the new head
head = pn;

而析构函数~Node() { delete next; }导致断链，应该避免。

还有更多……整个设计都引起了问题。

你的类是为了实现一个节点，所以做一个节点应该做的。

class Node {
  int key;
  Node* next;

public:

  Node() : key( -1 ), next( NULL ) {}
  Node( int i, Node* j ) : key( i ), next( j ) {}
  //
  ~Node() { }   // don't delete the next node here! Not the job of this object.


  void print_node();
};

class Linklist {
    Node *head;
public:
    Linklist(): head(0) {}
    static void head_insertion( Linklist & list, int i );
    void print_list();
    〜Linklist();       // traverse your list node and do the deletion here
}

把应该由列表级别完成的事情交给类Linklist来处理。