単一チェーンテーブル(c++実装)

単一チェーンテーブルとシーケンステーブルで処理できる問題は多くないが、チェーンテーブルの利点は空間を節約でき、空間の利用率が高く、プログラム実行の効率が速く、チェーンテーブルの基本操作も面接官が考察するのが好きな問題の一つであり、チェーンテーブルは基本的なデータ構造であり、以下は主にc++を利用してチェーンテーブルの基本的な機能を実現することである.

//    
#include <assert.h>

typedef int DataType;
class SListNode
{
     friend class SList;      //    ， SList     SListNode   
public:
     SListNode(DataType x)   //    
        :Data(x)
        , Next(NULL)
     { }
     
private:
     DataType Data;     //   
     SListNode * Next;     //   
};

class SList
{
public:
     void pushBack(DataType x)     //    
     {
         if (_head == NULL)    //         
         {
             _head = new SListNode(x);    //new         
             _tail = _head;
          }
         else
         {
             _tail->Next = new SListNode(x);
             _tail = _tail->Next;
          }
     }
      
     void popBack()   //    
     {
         if (_head == _tail)
         {
             if (_head)
             {
                 delete _head;
                 _head = _tail = NULL;
              }
         }
        else
       {
            SListNode * tmp = _tail;
            SListNode * cur = _head;
            while (cur)
            {
                 if (cur->Next->Next == NULL)
                {
                     delete tmp;
                     _tail = cur;
                     _tail->Next = NULL;
                 }
                 cur = cur->Next;
            }
         }
     }
     
     void pushFront(DataType x)    //    
     {
          SListNode * tmp = new SListNode(x);
          tmp->Next = _head;
          _head = tmp;
      }
      
     void popFront()    //    
    {
         SListNode * tmp = _head;
         if (tmp != NULL)    //        
         {
             _head = _head->Next;
             delete tmp;
          }
     }
     
     void Insert(SListNode * pos, DataType x)    //        
     {
          assert(pos);
          if (pos == _tail)
          {
              pushBack(x);
          }
          else
         {
              SListNode * tmp = new SListNode(x);
              tmp->Next = pos->Next;
              pos->Next = tmp;
          }
     }
     
     SListNode * Find(DataType x)   //  
     {
         SListNode * cur = _head;
         while (cur != NULL)
        {
            if (cur->Data == x)
            {
                return cur;
            }
            else
           {
                cur++;
            }
        }
        if (cur == NULL)
        {
             cout << "    ！" << endl;
         }
     }
     
      void Erase(SListNode * pos)    //  pos      
      {
          assert(pos);
          SListNode * cur = _head;
          while (cur->Next != pos)
          {
              cur = cur->Next;
          }
          cur->Next = pos->Next;
          delete pos;
      }
      
      void PrintSList()    //    
     {
         SListNode *cur = _head;
         while (cur)
         {
             cout << cur->Data << " " ;
             cur = cur->Next;
          }
             cout << endl;
      }
      
      void Clear()     //      
      {
          SListNode * cur = _head;
          while (cur)
          {
              SListNode *tmp = cur;
              cur = cur->Next;
              delete tmp;
          }
      }
public:
      SList()   //      
         :_head(NULL)
         , _tail(NULL)
      {}
      
 //   
      SList(const SList & S)     //      
         :_head(NULL)
         , _tail(NULL)
     {
         SListNode * cur = S._head;
         while (cur)
         {
             this->pushBack(cur->Data);
             cur = cur->Next;
         }
     }
     
     ~SList()    //    
    {
        Clear();
     }
     
 //    
     SList& operator=(const SList & s)      //       
     {
         if (this != &s)    //            
         {
             this->Clear();    //         ，delete        
             SListNode * cur = s._head;
             while (cur)
             {
                 this->pushBack(cur->Data);
                 cur = cur->Next;
              }
         }
      }
      
 ////    
 //SList & operator=(const SList & s)
 //{
 // swap(_head, s._head);
 // swap(_tail, s._tail);
 // return *this;
 //}
 
private:
     SListNode * _head;      //        
     SListNode * _tail;      //        
};

本文は“無心な執着”のブログから出て、転載をお断りします!