最基本的顺序表（经典顺序表）

// 顺序表.cpp -- 最基本的顺序表（经典顺序表）
// 完整的class.

// List abstract class -- 线性表的C++抽象类声明
template<class Elem> class List()
{
 public:
  // Reinitialize the list. the client is responsible for
  // reclaiming the storange used by the list elements.
  virtual void clear() = 0;
  // Insert an element at the front of the right partition.
  // Return true if successful, false if the list is full.
  virtual bool insert(const Elem&) = 0;
  // Append an element at the end of the right partition.
  // Return true if successful, false if the list is full.
  virtual bool append(const Elem&) = 0;
  // Remove the first element of right partition. Return
  // true if successful, false if the list is empty.
  // The element removed is returned in the parameter.
  virtual bool remove(Elem&) = 0;
  // Place fence at list start, making left partition empty.
  virtual void setStart() = 0;
  // Place fence at list end, making right partition empty.
  virtual void setEnd() = 0;
  // Move fence one step left; no change if already at start.
  virtual void prev() = 0;
  // Move fence one step right; no change if already at end
  virtual void next() = 0;
  // Return length of left partition
  virtual int leftLength() const = 0;
  // Return length of right partition
  virtual int rightLength() const = 0;
  // If pos or more elements are in the list, set the size
  // of left partition to pos and return true. Otherwise,
  // do nothing and return false.
  virtual bool setPos(int pos) = 0;
  // Return in first parameter the first element of the
  // right partition. Return true if successful, false 
  // if the right partition is empty.
  virtual bool getValue(Elem&) const = 0;
  // print the contents of the list
  virtual void print() const = 0;
};

// Array-based list implementation -- 线性表的实现
template <class Elem>
class Alist: public List<Elem> //继承
{
 private:
  int maxSize;   // Maximum size of list
  int listSize;   // Actual number of elements in list
  int fence;    // Position of fence
  Elem* listArray;  // Array holding list elementss
 public:
  AList(int size = DefaultListSize) // constructor
  {
  maxSize = size;
  lastSize = fence = 0;
  listArray = new Elem[maxSize];
  }
  ~AList() { delete [] listArray;} // Destructor
  
  void clear()
  {
   delete [] listArray;
   listSize = fence = 0;
   listArray = new Elem[maxSize];
  }
  bool insert(const Elem&);
  bool append(const Elem&);
  bool remove(Elem&);
  void setStart() { fence = 0;}
  void setEnd() { fence = listSize;}
  void prev()  { if (fence != 0) fence--;}
  void next()  { if (fence <= listSize) fence++;}
  int leftLength()const {return fence;}
  int rightLength()const {return lastsize - fence;}
  bool setPos(int pos)
  {
   if ((pos >= 0) && (pos <= listSize)) fence = pos;
   return (pos >= 0) && (pos <= listSize);
  }
  bool getValue(Elem& it)const()
  {
   if (rightLength() == 0) return flase;
   else { it = listArray[fence]; reutrn true;}
  }
  void print()const 
  {
   int temp = 0;
   cout << " < ";
   while (temp < fence) cout << listArray[temp++] << " ";
   cout << " | ";
   while (temp < ListSize) cout << listarray[temp++] << " ";
   cout << " >\n";
  }
};

template <class Elem>   // Insert at front of right partition
bool Alist <Elem>::insert(const Elem& item)
{
 if (listsize == maxSize) return flase; // List is full
 for (int i = listsize; i > fence; i--) // Shift Elem up
  listArray[i] = listArray[i-1];  // to make room
 listArray[fence] = item;
 listSize++;        // Increment list size
 return true;
}

// Remove and return first Elem in right partition
template <class Elem> bool AList <Elem>::remove(Elem& it)
{
 if (rightLength() == 0) return false; // nothing in right
 it = listArray[fence];     // copy removed elem
 for (int i = fence; i < listSize -1; i++) // Shift them down
  listArray[i] = listArray[i + 1];
 listSize--;        // Decrement Size
 return true;
}

// 看完以后就觉得，原来掌握顺序表是很简单的事，只需要掌握几个点；
// 其中最重要的思想是确定位置。
// 知道现在的位置，开始的位置，结束的位置，数组的大小，该位置左右的大小。