C++ LinkedListを2に分割して入力リストを破棄する

Question

C++の初心者から。私は入力リストを2つの他のリストに分割し、元のまま変わらずに残しておく方法（以下）を書いたので、入力チェーンを破壊する新しいメソッド "split"が必要です。 b。元のチェーンを削除しようとしましたが失敗しました。前もって感謝します。

// Split A into two chains B and C. 
// When done, A is unchanged. 
template <class T> 
void chain<T>split(chain<T>& A, chain<T>& B, chain<T>& C) 
{ 
    // first free all nodes in B and C 

    int j; 
    j=0 ; 
    listSize = B.listSize; 
    for (j=0 ; j < listSize; j++) 
     B.erase(0); 

    // C.Erase(); 
    j=0 ; 
    listSize = C.listSize; 
    for (j=0 ; j < listSize; j++) 
     C.erase(0); 


    // assign elements alternately to B and C 
    int n=0; 
    chain<T>::iterator a = A.begin(); // find first node of A 
    while (a != A.end()) { 
     // first give B an element 
     B.insert(n,*a); 
     a++; 

     if (a == A.end()) break; 
     // now give C an element 
     C.insert(n,*a); 
     a++; 
     n=n+1; 
    } 
} 

    #ifndef chain_ 
    #define chain_ 
    #include "linearList.h" 
    #include "chainNode.h" 

    using namespace std; 
    template<class T> 

    class linkedDigraph; 
    template <class T> class linkedWDigraph; 

    template<class T> 
    class chain : public linearList<T> 
    { 
     friend linkedDigraph; 
     friend linkedWDigraph<int>; 
     friend linkedWDigraph<float>; 
     friend linkedWDigraph<double>; 


     public: 
      // constructor, copy constructor and destructor 
      chain(int initialCapacity = 10); 
      chain(const chain<T>&); 
      ~chain(); 

      // ADT methods 
      bool empty() const {return listSize == 0;} 
      int size() const {return listSize;} 
      T& get(int theIndex) const; 
      int indexOf(const T& theElement) const; 
      void erase(int theIndex); 
     void Split(chain<T>& A, chain<T>& B, chain<T>& C); 

       //Operator [] 
      typedef int size_type; 



      // iterators to start and end of list 
      class iterator; 
      iterator begin() {return iterator(firstNode);} 
      iterator end() {return iterator(NULL);} 

      // iterator for chain 
      class iterator 
      { 
      public: 
       // typedefs required by C++ for a forward iterator 
       typedef forward_iterator_tag iterator_category; 
       typedef T value_type; 
       typedef ptrdiff_t difference_type; 
       typedef T* pointer; 
       typedef T& reference; 

       // constructor 
       iterator(chainNode<T>* theNode = NULL) 
        {node = theNode;} 

       // dereferencing operators 
       T& operator*() const {return node->element;} 
       T* operator->() const {return &node->element;} 

       // increment 
       iterator& operator++() // preincrement 
         {node = node->next; return *this;} 
       iterator operator++(int) // postincrement 
          {iterator old = *this; 
          node = node->next; 
          return old; 
          } 


       // equality testing 
       bool operator!=(const iterator right) const 
         {return node != right.node;} 
       bool operator==(const iterator right) const 
         {return node == right.node;} 
      protected: 
       chainNode<T>* node; 

      }; // end of iterator class 


     //Overload [] 
     T& operator[](size_type index) 
      { 

       return element[index]; 
      } 

     const T& operator[](size_type index) const 
      { 

       return element[index]; 
      } 


     protected: 
      void checkIndex(int theIndex) const; 
       // throw illegalIndex if theIndex invalid 
      chainNode<T>* firstNode; // pointer to first node in chain 
      int listSize;    // number of elements in list 
    }; 

    template<class T> 
    chain<T>::chain(int initialCapacity) 
    {// Constructor. 
     if (initialCapacity < 1) 
     {ostringstream s; 
     s << "Initial capacity = " << initialCapacity << " Must be > 0"; 
     throw illegalParameterValue(s.str()); 
     } 
     firstNode = NULL; 
     listSize = 0; 
    } 

    template<class T> 
    chain<T>::chain(const chain<T>& theList) 
    {// Copy constructor. 
     listSize = theList.listSize; 

     if (listSize == 0) 
     {// theList is empty 
      firstNode = NULL; 
      return; 
     } 

     // non-empty list 
     chainNode<T>* sourceNode = theList.firstNode; 
         // node in theList to copy from 
     firstNode = new chainNode<T>(sourceNode->element); 
         // copy first element of theList 
     sourceNode = sourceNode->next; 
     chainNode<T>* targetNode = firstNode; 
         // current last node in *this 
     while (sourceNode != NULL) 
     {// copy remaining elements 
      targetNode->next = new chainNode<T>(sourceNode->element); 
      targetNode = targetNode->next; 
      sourceNode = sourceNode->next; 
     } 
     targetNode->next = NULL; // end the chain 
    } 

    template<class T> 
    chain<T>::~chain() 
    {// Chain destructor. Delete all nodes in chain. 
     while (firstNode != NULL) 
     {// delete firstNode 
      chainNode<T>* nextNode = firstNode->next; 
      delete firstNode; 
      firstNode = nextNode; 
     } 
    } 

    template<class T> 
    void chain<T>::checkIndex(int theIndex) const 
    {// Verify that theIndex is between 0 and listSize - 1. 
     if (theIndex < 0 || theIndex >= listSize) 
     {ostringstream s; 
     s << "index = " << theIndex << " size = " << listSize; 
     throw illegalIndex(s.str()); 
     } 

    } 

    template<class T> 
    T& chain<T>::get(int theIndex) const 
    {// Return element whose index is theIndex. 
    // Throw illegalIndex exception if no such element. 
     checkIndex(theIndex); 

     // move to desired node 
     chainNode<T>* currentNode = firstNode; 
     for (int i = 0; i < theIndex; i++) 
      currentNode = currentNode->next; 

     return currentNode->element; 
    } 

    template<class T> 
    int chain<T>::indexOf(const T& theElement) const 
    {// Return index of first occurrence of theElement. 
    // Return -1 if theElement not in list. 

     // search the chain for theElement 
     chainNode<T>* currentNode = firstNode; 
     int index = 0; // index of currentNode 
     while (currentNode != NULL && 
       currentNode->element != theElement) 
     { 
      // move to next node 
      currentNode = currentNode->next; 
      index++; 
     } 

     // make sure we found matching element 
     if (currentNode == NULL) 
      return -1; 
     else 
      return index; 
    } 

    template<class T> 
    void chain<T>::erase(int theIndex) 
    {// Delete the element whose index is theIndex. 
    // Throw illegalIndex exception if no such element. 
     checkIndex(theIndex); 

     // valid index, locate node with element to delete 
     chainNode<T>* deleteNode; 
     if (theIndex == 0) 
     {// remove first node from chain 
      deleteNode = firstNode; 
      firstNode = firstNode->next; 
     } 
     else 
     { // use p to get to predecessor of desired node 
      chainNode<T>* p = firstNode; 
      for (int i = 0; i < theIndex - 1; i++) 
      p = p->next; 

      deleteNode = p->next; 
      p->next = p->next->next; // remove deleteNode from chain 
     } 
     listSize--; 
     delete deleteNode; 
    } 

    template<class T> 
    void chain<T>::insert(int theIndex, const T& theElement) 
    {// Insert theElement so that its index is theIndex. 
     if (theIndex < 0 || theIndex > listSize) 
     {// invalid index 
      ostringstream s; 
      s << "index = " << theIndex << " size = " << listSize; 
      throw illegalIndex(s.str()); 
     } 

     if (theIndex == 0) 
      // insert at front 
      firstNode = new chainNode<T>(theElement, firstNode); 
     else 
     { // find predecessor of new element 
      chainNode<T>* p = firstNode; 
      for (int i = 0; i < theIndex - 1; i++) 
      p = p->next; 

      // insert after p 
      p->next = new chainNode<T>(theElement, p->next); 
     } 
     listSize++; 
    } 



    template <class T> 
    void chain<T>::Split(chain<T>& A, chain<T>& B, chain<T>& C) 

    {// Split A into two chains B and C. 

    // When done, A is unchanged. 

     // first free all nodes in B and C 

     // find firt node of A 

    // B.erase(); 
     int j; 
     j=0 ; 
     listSize = B.listSize; 
     for (j=0 ; j < listSize; j++) 
      B.erase(0); 

     // C.Erase(); 
     j=0 ; 
     listSize = C.listSize; 
     for (j=0 ; j < listSize; j++) 
      C.erase(0); 

     for (chain<T>::iterator b = A.begin(); 
      b != A.end(); b++) 
      cout << "A from in " << *b << " "; 

     // assign elements alternately to B and C 
     int n=0; 
     chain<T>::iterator a = A.begin(); 
     chainNode<T> *current; 

     while (a != A.end()) { 
      B.insert(n,*a);// first give B an element 
      a++; 

      if (a == A.end()) break; 
       C.insert(n,*a); // now give C an element 

      a++; 
      n=n+1; 
      } 

    } 



    // chain node 

    #ifndef chainNode_ 
    #define chainNode_ 

    template <class T> 
    struct chainNode 
    { 
     // data members 
     T element;//data 
     chainNode<T> *next;//link 

     // methods 
     chainNode() {} 
     chainNode(const T& element) 
      {this->element = element;} 
     chainNode(const T& element, chainNode<T>* next) 
      {this->element = element; 
      this->next = next;} 
     }; 

    #endif 

Answer 1

ここから元のチェーンを削除することはできません。これは関数本体全体に存在することを意味する参照として渡されます。 （あなたはBとCのためのあなたのdidのようにそれを空にすることができます。

オブジェクトを破棄するには、まずこのオブジェクトが動的に割り当てられていることを確認する必要があります（つまり、new）。次に、参照ではなくそのオブジェクトへのポインタが必要です。

は、だから、このようなあなたの機能を変更する必要があります。

template <class T> 
void chain<T>split(chain<T>* A, chain<T>& B, chain<T>& C) 
{ 
    .... // same as before 
    delete A; 
} 

注1：私は嘘をついた、あなたは、参照（すなわちdelete &A）からポインタを取ることができるが、それは非常に悪い習慣でしょう。

注2：あなたが改善する可能性があり、いくつかのささいなこと：それを毎回計算避けるために

• 店end()どこか（chain<T>::iterator end = A.end()）。
• C.listsizeはおそらく関数でなければなりません。関数でなければ、その値を変数に格納しないでください。
• n = n+1++n;
• あなたのコンパイラは、あなたがにemptyメソッドを追加する必要があり、各ループ（for (T& t: A)）のためとauto
• 使用に十分な最近のであれば、同じループ変数（for (int j = 0; ...）
• を再使用しないでくださいする必要がありますchainコードを因数分解する。