线性表之顺序存储详解

1、顺序存储的定义

是指用一段地址相连的存储单元依次存储线性表中的数据元素

2、设计思路

可以用一维数组实现顺序存储结构

包括：

存储空间：T* m_array
当前长度：int m_length

1 class SeqList: public List<T>
2 {
3 protected:
4     T* m_array;//指向一个数组
5     int m_length;//记录线性表的长度
6 }

3、元素的获取

判断目标位置是否合法
将目标位置作为数组下标获取元素

 1 bool SeqList<T>::get(int i,T& e) const
 2 {
 3     bool ret=((0<=i)&&(i<m_length));
 4     
 5     if(ret)
 6     {
 7         e=m_array[i]
 8     }
 9     return  ret; 
10 }

4、数据的insert

判断目标位置是否合法
将目标位置之后的所有元素后移一个位置
将新元素加入目标位置
线性表长度加1

 1 bool SeqList<T>::insert(int i,const T& e)
 2 {
 3     bool ret =((0<=i)&&(i <m_length));
 4     ret= ret&&((m_length+1)<=capacity));
 5     
 6     if(ret)
 7     {
 8         for(int p=m_length-1;p>=i;p--)
 9         {
10             m_array[p+1]=m_array[p];
11         }
12         
13         m_ayyay[i]=e;
14         m_length++;
15     }
16     return ret ;  
17 }

5、数据的delete

判断目标位置是否合法
将目标位置后的所有的元素前移一个位置
线性表长度减1

 1 bool SeqList<T>::remove(int i)
 2 {
 3     bool ret=((0<=i)&&(i<m_length));
 4     
 5     if(ret)
 6     {
 7         
 8         for(int p=i;p<m_length-1;p++)
 9         {
10             m_array[p]=m_array[p+1];
11         }
12         m_length--;
13     }
14     
15     return ret;     
16 }

完整代码为：

  1 #ifndef SEQLIST_H
  2 #define SEQLIST_H
  3 #include "list.h"
  4 #include "Exception.h"
  5 
  6 namespace DataStructureLib
  7 {
  8 
  9     template <typename T>;
 10     class Seqlist:public List <T>
 11     {
 12     private:
 13         T* m_array;//顺序存储空间
 14         int m_length;//当前链表长度
 15     public:
 16         bool insert(int i, const T& e)
 17         {
 18             bool ret=(0<=i)&&(i  <=m_length);
 19             ret=ret&&(m_length<capcity());
 20 
 21             if(ret)
 22             {
 23                 for(int p=m_length-1;p>=i;p--)
 24                 {
 25                     m_array[p+1]=m_array[p];
 26                 }
 27                 m_array[i]=e;
 28                 m_length++;
 29             }
 30 
 31             return ret;
 32         }
 33 
 34         bool remove(int i)
 35         {
 36             bool ret=(0<=i)&&(i  <=m_length);
 37 
 38             if(ret)
 39             {
 40                 for(int p=i;p<m_length-1;p--)
 41                 {
 42                     m_array[p]=m_array[p+1];
 43                 }
 44                 m_length--;
 45             }
 46 
 47             return ret;
 48         }
 49 
 50         bool set(int i,const T& e)
 51         {
 52             bool ret=(0<=i)&&(i  <=m_length);
 53 
 54             if(ret)
 55             {
 56                 m_array[i]=e;
 57             }
 58 
 59             return ret;
 60         }
 61 
 62         bool get(int i,T& e) const
 63         {
 64             bool ret=(0<=i)&&(i  <=m_length);
 65 
 66             if(ret)
 67             {
 68                 e=m_array[i];
 69             }
 70 
 71             return ret;
 72         }
 73 
 74         int length() const
 75         {
 76             return  m_length;
 77         }
 78 
 79         void clear()
 80         {
 81             m_length=0;
 82         }
 83 
 84         //顺序存储线性表数组访问方式
 85         T& operator[](int i)   //
 86         {
 87             bool ret=(0<=i)&&(i  <=m_length);
 88 
 89             if(ret)
 90             {
 91                 return m_array[i];
 92             }
 93             else
 94             {
 95                 THROW_EXCEPTION(IndexOutOfBoundsException,"Paramara i is invalid... ");
 96             }
 97 
 98         }
 99 
100         T operator [](int i) const// 重载   即如果调用了这个函数就说明了当前的对象是一个const对象
101         {
102             return  const_cast<Seqlist<T>&>(*this)[i];//将当前对象的const属性剔除（const_cast<Seqlist<T>&>(*this)） (即当前对象的类型变成了Seqlist<T>&，非const类型)，进而使用上面一个[]重载的函数
103         }
104 
105         //顺序存储空间的容量
106         virtual int capacity()=0;//子类来完成
107     };
108 
109 }
110 #endif // SEQLIST_H

View Code

小结：

Seqlist也是一个抽象类，其结构：静态线性表和动态线性表