线性表的顺序存储——顺序存储结构的抽象实现

1，本文完成顺序存储结构线性表的抽象实现：

　　1，SeqList 还是一个抽象类，这里仅实现线性表的关键操作，但是还是不能生成具体对象；

2，关键操作虽然指定，但是顺序存储的指定没有在 SeqList 中完成，所以还是抽象类，不能生成具体对象；

2，SeqList 设计要点：

1，抽象类模板，存储空间的位置和大小由子类完成；

2，实现顺序存储结构线性表的关键操作（增删查等）；

3，提供数组操作符，方便快速获取元素（因为是顺序存储结构，可以重载数组操作符）；

3，SeqList 具体函数接口（增删设获长清操容）：

4，顺序存储线性表实现：

  1 #ifndef SEQLIST_H
  2 #define SEQLIST_H
  3 
  4 #include "Object.h"
  5 #include "List.h"
  6 #include "Exception.h"
  7 
  8 namespace DTLib
  9 {
 10 
 11 template <typename T>
 12 class SeqList : public List<T>
 13 {
 14 protected:
 15     T* m_array;       //顺序存储空间，子类实现，这里不赋值指针
 16 　　 int m_length;     //当前线性表长度
 17 
 18 public:
 19     bool insert(int i, const T& e)    // n + 5 => O(n)
 20     {
 21         bool ret = ((0 <= i) && (i <= m_length));
 22         ret = ret && (m_length <= capacity());  // 要插入元素，当插入后长度要加 1，此时小于号正好合适
 23 
 24         if( ret )
 25         {
 26             for(int p=m_length-1; p>=i; p--)  // 基于顺序表的插入要涉及数据向后挪动空出目标位置，向后移动则从后开始
 27             {
 28                 m_array[p + 1] = m_array[p];  // 这里数组操作符实质是指针运算
 29             }
 30 
 31             m_array[i] = e;
 32             m_length++;
 33         }
 34 
 35         return ret;
 36 　　 }
 37 
 38     bool insert(const T& e)   // 在线性表的尾部插入一个元素；
 39     {
 40         return insert(m_length, e);
 41 　　 }
 42 
 43     bool remove(int i)   // O(n)
 44     {
 45         bool ret = ((0 <= i) && (i < m_length));
 46 
 47         if( ret )
 48         {
 49             for(int p = i; p<m_length-1; p++)  // 基于顺序表的删除要涉及数据向前挪动，向前移动则从前开始
 50             {
 51                 m_array[p] = m_array[p + 1];
 52             }
 53 
 54             m_length--;
 55         }
 56 
 57         return ret;
 58 　　 }
 59 
 60     bool set(int i, const T& e)
 61     {
 62         bool ret = ((0 <= i) && (i < m_length));
 63 
 64         if( ret )
 65         {
 66             m_array[i] = e;
 67         }
 68 
 69         return ret;
 70 　　 }
 71 
 72 /* 通过参数 e 来返回目标位置，而没有通过返回值返回，是由于目标位置可能不合法，不合法就返回 false，也就是 get() 操作用来说明当前操作是否合法*/
 73     bool get(int i, T& e) const
 74     {
 75         bool ret = ((0 <= i) && (i < m_length));
 76 
 77         if( ret )
 78         {
 79             e = m_array[i];
 80         }
 81 
 82         return ret;
 83 　　 }
 84 
 85 /*
 86     int get(int i) const
 87     {
 88         int ret = -1;
 89 
 90         if(get(i, ret))
 91         {
 92             return ret;
 93         }
 94 
 95         return ret;
 96     }
 97 */
 98 
 99     int find(const T& e) const     //O(n)
100     {
101         int ret = -1;
102 
103         for(int i=0; i<m_length; i++)
104         {
105             if(m_array[i] == e)
106             {
107                 ret = i;
108 
109                 break;
110             }
111         }
112 
113         return ret;
114 　　 }
115 
116     int length() const
117     {
118         return m_length;
119 　　 }
120 
121     void clear()
122     {
123         m_length = 0;
124 　　 }
125 
126     // 顺序存储线性表的数组访问方式，也是一般的访问方式；
127     T& operator[] (int i)
128     {
129         bool ret = ((0 <= i) && (i < m_length)); // 必须先插入数据元素，然后才能访问
130 
131         if( ret )
132         {
133             return m_array[i];
134         }
135         else
136         {
137             THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ..." );
138         }
139 　　 }
140 
141     // 这里考虑了 const 和非 const 对象
142     T operator[] (int i) const
143     {
144         return (const_cast<SeqList<T>&>(*this))[i];
145 　　 }
146 
147     //顺序存储空间的最大容量，顺序存储空间的指定没有在这个类中指定，在//其子类中完成的，所以具体实现要放在子类中完成；
148     virtual int capacity() const = 0;
149 };
150 
151 }
152 #endif // SEQLIST_H

5，顺序链表测试代码：

 1 #include <iostream>
 2 #include "SeqList.h"
 3 
 4 using namespace std;
 5 using namespace DTLib;
 6 
 7 int main()
 8 {
 9 　　 SeqList<int>* l;
10     return 0;
11 }