0

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

测试者：

#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是正确的，但在开头有一个添加的节点，其中包含该节点的地址位置。我尝试了很多方法，但无论如何它们似乎都没有删除最后一个节点。

4

1 回答 1

4

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

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块中添加一条return语句if。

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

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

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

于 2012-09-17T10:05:40.943 回答