天天看点
返回

顺序表

        代码所示为模板类，无法直接编译。我感觉学习数据结构主要还是学习各种数据结构的原理，至于只用是比较简单的。

        顺序表AList是由线性表List抽象类继承来的。从代码数量上就能够看出AList类中insert和remove方法是比较重要的。将顺序表看成由两部分构成，在AList类中定义了fence属性，是为了定义当前元素的概念，同时也助于修改线性表的表示形式。

     
  1.  //List abstract class         
    2.       
  2.  template <class Elem> class List        
    3.       
  3.  {        
    4.       
  4.      public:        
    5.       
  5.          //virtual void clear() = 0;        
    6.       
  6.          virtual bool insert(const Elem&) = 0;        
    7.       
  7.          virtual bool append(const Elem&) = 0;        
    8.       
  8.          virtual bool remove(Elem&) = 0;        
    9.       
  9.          virtual void setStart() = 0;        
    10.       
  10.          virtual void setEnd() = 0;        
    11.       
  11.          virtual void prev() = 0;        
    12.       
  12.          virtual void next() = 0;        
    13.       
  13.          virtual int leftLength() = 0;        
    14.       
  14.          virtual int rightLength() = 0;        
    15.       
  15.          virtual bool setPos(int pos) = 0;        
    16.       
  16.          virtual bool getValues(Elem&) = 0;        
    17.       
  17.          virtual void print() const = 0;         
    18.       
  18.  };        
    19.           
  19.  template <class Elem>        
    20.       
  20.  class AList : public List<Elem>        
    21.       
  21.  {        
    22.       
  22.      private:        
    23.       
  23.          int maxSize;        
    24.       
  24.          int listSize;        
    25.       
  25.          int fence;        
    26.       
  26.          Elem *listArray;        
    27.       
  27.      public:        
    28.       
  28.          AList(int size=DefaultListSize)        
    29.       
  29.          {        
    30.       
  30.              maxSize = size;        
    31.       
  31.              listSize = fence = 0;        
    32.       
  32.              listArray = new Elem[maxSize];        
    33.       
  33.          }        
    34.       
  34.          ~AList()        
    35.       
  35.          {        
    36.       
  36.              delete [] listArray;        
    37.       
  37.          }        
    38.       
  38.          bool insert(const Elem&);        
    39.       
  39.          bool append(const Elem&);        
    40.       
  40.          bool remove(Elem&);        
    41.       
  41.          void setStart();        
    42.       
  42.          void setEnd();        
    43.       
  43.          void prev();        
    44.       
  44.          void next();        
    45.       
  45.          int leftLength();        
    46.       
  46.          int rightLength();        
    47.       
  47.          bool setPos(int pos);        
    48.       
  48.          bool getValues(Elem&);        
    49.       
  49.          void print() const;         
    50.       
  50.  };        
    51.               
  51.  template <class Elem>        
    52.       
  52.  bool  AList<Elem>::insert(const Elem& item)        
    53.       
  53.  {        
    54.       
  54.      if(listSize==maxSize)        
    55.       
  55.          return false;        
    56.       
  56.      for(int i=listSize;i>fence;i--)        
    57.       
  57.          listArray[i] = listArray[i-1];        
    58.       
  58.      listArray[fence]=item;        
    59.       
  59.      listSize++;        
    60.       
  60.      return true;        
    61.       
  61.  }        
    62.           
  62.  template <class Elem>        
    63.       
  63.  bool  AList<Elem>::append(const Elem& item)        
    64.       
  64.  {        
    65.       
  65.      if(listSize == maxSize)        
    66.       
  66.          return false;        
    67.       
  67.      listArray[listSize++]=item;        
    68.       
  68.          return true;        
    69.       
  69.  }        
    70.           
  70.  template <class Elem>        
    71.       
  71.  bool AList<Elem>::remove(Elem& it)        
    72.       
  72.  {         
    73.       
  73.      if(rightLength() == 0)        
    74.       
  74.          return false;        
    75.       
  75.      it=listArray[fence];        
    76.       
  76.      for(int i=fence;i<maxSize;i++)        
    77.       
  77.          listArray[i]=listArray[i+1];        
    78.       
  78.      listSize--;        
    79.       
  79.      return true;            
    80.       
  80.  }        
    81.           
  81.  template <class Elem>        
    82.       
  82.  void AList<Elem>::setStart()        
    83.       
  83.  {        
    84.       
  84.      fence=0;        
    85.       
  85.  }        
    86.           
  86.  template <class Elem>        
    87.       
  87.  void AList<Elem>::setEnd()        
    88.       
  88.  {        
    89.       
  89.      fence=listSize;        
    90.       
  90.  }        
    91.           
  91.  template <class Elem>        
    92.       
  92.  void AList<Elem>::prev()        
    93.       
  93.  {        
    94.       
  94.      if(fence!=0)        
    95.       
  95.          fence--;        
    96.       
  96.  }        
    97.           
  97.  template <class Elem>        
    98.       
  98.  void AList<Elem>::next()        
    99.       
  99.  {        
    100.       
  100.      if(fence<=listSize)        
    101.       
  101.          fence++;        
    102.       
  102.  }        
    103.           
  103.  template <class Elem>        
    104.       
  104.  int AList<Elem>::leftLength()        
    105.       
  105.  {        
    106.       
  106.      return fence;        
    107.       
  107.  }        
    108.           
  108.  template <class Elem>        
    109.       
  109.  int AList<Elem>::rightLength()        
    110.       
  110.  {        
    111.       
  111.      return (listSize-fence);        
    112.       
  112.  }        
    113.           
  113.  template <class Elem>        
    114.       
  114.  bool AList<Elem>::setPos(int pos)        
    115.       
  115.  {        
    116.       
  116.      if((pos >= 0)&&(pos <=listSize))        
    117.       
  117.          fence=pos;        
    118.       
  118.      return ((pos >=0)&&(pos <=listSize));        
    119.       
  119.  }        
    120.           
  120.  template <class Elem>        
    121.       
  121.  bool AList<Elem>::getValues(Elem& it)        
    122.       
  122.  {        
    123.       
  123.      if(listSize==0)        
    124.       
  124.          return false;        
    125.       
  125.      it=listArray[fence];        
    126.       
  126.      return true;        
    127.       
  127.  }        
    128.           
  128.  template <class Elem>        
    129.       
  129.  void AList<Elem>::print() const        
    130.       
  130.  {        
    131.       
  131.      int temp=0;        
    132.       
  132.      cout<<"In AList:<";        
    133.       
  133.      while(temp < fence)        
    134.       
  134.          cout<<listArray[temp++]<<" ";        
    135.       
  135.      cout<<"|";        
    136.       
  136.      while(temp < listSize)        
    137.       
  137.          cout<<listArray[temp++]<<" ";        
    138.       
  138.      cout<<">\n";        
    139.       
  139.  }        
    140.
职场 休闲 线性表 顺序表 AList
上一篇: 顺序表
下一篇: 顺序表

继续阅读