c++ - 链表输出 1 太多了？

Question

我正在制作一个单向链表，并且正在添加到起始节点。每当我运行我的测试器时，它都会工作，但它会在地址的开头添加(我假设)一个额外的节点。

测试人员:

#include <iostream>
#include "linkedlist.h"

using namespace std;

void test01() {

  LinkedList < int > A;

  cout << endl << endl; 
  cout << " ***************** " << endl;
  cout << " *  TEST SET #1  * " << endl;
  cout << " ***************** " << endl;


  cout << "Is the list empty? " << boolalpha << A.isEmpty() <<endl; 
  cout << A << endl;
  cout << "Size of A = " << A.size() << endl;

  //TEST : Inserting 10 numbers to a
  cout << endl << "TEST : Inserting 10 numbers to A" << endl;
  for (int k=0; k<10; k++)
  {
    A.insert_front(k+1);
  } 
  cout << A << endl;
  cout << "Size of a = " << A.size() << endl;

  //TEST : Clearing A
  cout << endl << "TEST : Clearing A" << endl;
  A.clear();
  cout << A << endl;
  cout << "Size of A = " << A.size() << endl << endl;


  cout << "Test 01 - Done!" << endl;
} // Destructor Called Here!!

int main () {

  cout << "Hello World!!, This is the LinkedList LARGE Tester" << endl; 

  test01();


  cout << "LARGE Done!" << endl;
  return 0;
}

LinkedList.hpp(允许修改的内容)

#include "linkedlist.h"

 // --------
 // ---- Basic Accessor Operations ---
 // --------
 // Purpose: accessor function for the current # data values in the list
 // Returns: current size of the list
 template <class T>
 int LinkedList<T>::size() const
 {
 }

  // Purpose: puts the data x in the front of the list 
  // Parameters: x is data value to inserted
  // Postconditions: x is the first element of the list
 template <class T>
 void LinkedList<T>::insert_front(const T& x)
 {
  if(m_next == NULL)
  {
   m_next = new LinkedList<T>;
   m_next->m_data = x;
   m_next->m_next = NULL;
  }

  LinkedList<T> *temp;
  temp = new LinkedList<T>;
  temp->m_data = x;
  temp->m_next = m_next;
  m_next = temp;

 }

LinkedList.h(不允许修改)

template <class T>
class LinkedList
{
public:
  T m_data;                // Data to be stored
  LinkedList<T>* m_next;      // Pointer to the next element in the list
  static T m_objerr;

    // Purpose: Default constructor
    // Postconditions: next pointer set to NULL
    // -INLINE-
  LinkedList() : m_next(NULL) {}

    // Purpose: Auxiliaty constructor, construct from parameters
    //     useful when inserting elements
    // Postconditions: data and next pointer set to parameters
    // -INLINE-
  LinkedList(const T& x, LinkedList<T>* p) 
             : m_data(x), m_next(p) {}

   void insert_front(const T& x);

   int size() const;

}

编译列表后 cout 是正确的，但在开头添加了一个节点，其中包含该节点的地址位置。我尝试了很多方法，但无论如何似乎都没有删除最后一个节点。

Answer 1

让我们看看将第一个节点添加到列表时会发生什么:

template <class T>
 void LinkedList<T>::insert_front(const T& x)
 {
     if(m_next == NULL) // m_next is NULL
     {
        // ok, let's add the first node

        m_next = new LinkedList<T>;
        m_next->m_data = x;
        m_next->m_next = NULL; // this line isn't neccesary, the default constructor
                               // called in the new expression above took care of that
        // you should utilize the other constructor and say
        // m_next = new LinkedList<T>(x, m_next);

        // ok, done, let's continue with the code below
     }

     // Wait a second! We already added a node, what are we doing here?

     LinkedList<T> *temp;
     temp = new LinkedList<T>;
     temp->m_data = x;
     temp->m_next = m_next;
     m_next = temp;
 }

所以每次添加第一个节点时，实际上是在添加两个节点。其余的插入工作正常，因为 if 条件不再为真。 要修复它，您可以将代码的第二部分包装在 else block 中，或者在 if block 中添加一个 return 语句。

请注意，根据您当前处理事情的方式，整个 insert_front 方法可以缩短为

m_next = new LinkedList<T>(x, m_next);

不过，我可以看出它的设计存在一些问题。类本身同时充当容器和节点。通常链表实现为节点使用一个单独的类，而实际的容器类只包含指向第一个节点的指针(可能还有用于缓存大小和尾部等的成员)。另一个问题是默认构造函数和插入第一个节点的方式。当前，默认构造的列表将未定义的 m_data 作为第一个节点。节点的第一次插入可能应该只是将 m_data 设置为所需的值并将 m_next 设置为 NULL。