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;
 }

したがって、最初のノードを追加するたびに、実際には 2 つ追加されます。if条件が真でなくなったため、残りの挿入は正常に機能します。これを修正するには、コードの 2 番目の部分をブロックでラップするか、ブロック内にステートメントをelse追加します。returnif

現在処理している方法では、insert_frontメソッド全体を次のように短縮できることに注意してください。

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

ただし、これの設計にはいくつかの問題があります。クラス自体は、コンテナーとノードとして同時に機能します。通常、リンクされたリストの実装はノードに別のクラスを使用し、実際のコンテナー クラスは最初のノードへのポインターを保持するだけです (おそらくメンバーはサイズとテールなどをキャッシュします)。別の問題は、デフォルトのコンストラクターと、最初のノードを挿入する方法です。現在、デフォルトで構築されたリストはm_data、最初のノードとして undefined を保持します。ノードの最初の挿入は、おそらくm_data必要な値に設定m_nextし、NULL に設定する必要があります。

于 2012-09-17T10:05:40.943 に答える