数据结构--线性表的顺序存储结构

一 线性表的本质和操作

线性表的表现形式主要有以下几个方面
1 零个或多个数据元素组成的集合
2 数据元素在位置上是有序排列的
3 数据元素的个数是有限的
4 数据元素的类型必须相同
线性表的抽象定义是具有相同的n(n>=0)个数据元素的优先序列(a0,a1......an)

二 线性表的性质

a0为线性表的i的一个元素，只有一个后继
an-1为线性表的最后一个元素，只有一个前驱
除去这两个元素外的其他元素ai既有前前驱，又有后继
直接支持逐项访问和顺序存取

三线性表的一些常用操作

1将元素插入线性表
2将元素从线性表中删除
3获取目标位置处元素的值
4设置目标位置处元素的值
5获取线性表的长度
6清空线性表

template <typename T> class List :public Object {//Object为顶层父类 protected: List(const List&); List& operator=(const List&);//避免赋值操作 public: List(){}; virtual bool insert(int i,const T&e)=0;//插入 virtual bool remove(int i)=0;//删除 virtual bool set(int i,const T&e)=0//设置值; virtual bool get(int i,const T&e)=0;//获取值 virtual int length()const=0;//获取长度 virtual void clear()=0;//清空操作 }

四 线性表的顺序存储结构的实现
思路：可以用一维数组来实现顺序存储结构
存储空间 *T array
当前的长度 int length**

a.顺序存储结构的元素插入操作
1.判断目位置是否合法
2.将目标位置之后的所有元素后移一个位置
3.将新元素插入目标位置
4.线性表的长度+1
简单的图示

代码的实现部分

inset (int i,const T&e) { bool ret=((0<=i)&&(i<length)); ret=ret&&((length+1)<=capacity());//对位置进行判断是否合法 if(ret) { for(int p=length-1;p>i;p--) { array[p+1]=arrray[p];//将目标位置后的元素后移一位 } array[i]=e;//将元素插入 length++;//线性表长度加1 } return ret; }

b.顺序存储结构的元素删除操作
1.对位置进行判断是否合法
2.将目标位置后的所有元素前移一个位置
3.线性表的长度减1
实现代码如下
简单的图示

remove(int i,const T&e) { bool ret=((o<=i)&&(i<=length)); ret=ret&&((length+1)<=capacity());//对位置进行判断是否合法 if(ret) { for(int p=i;p<length-1;p++)//在删除处进行遍历 { array[p]=array[p+1];//将元素前移一个位置 } length--;//线性表的长度减1 } return ret; }

c.元素的设置以及获取
1判断目标位置是否合法
2.将目标位置作为数组下标对元素进行操作
实现代码如下

set(int i,const T&e) { bool ret=((0<=i)&&(i<=length)) if(ret) { array[i]=e; } return ret; } get(int i,T&e)const { bool ret=((0<=i)&&(i<=length)) if(ret) { e=array[i]; } return ret; }

d.其他的操作(清除及获取长度)
实现代码如下

 int length()const { return length; } void clear() { length=0; }

完整的代码如下

include "List" include "Object" namespace MyLib { template<typename T> class SeqList :public List<T> { protected: T* array; int length; public: bool insert(int i,const T&e) { bool ret=((0<=i)&&(i<=m_length)); ret=ret&&(m_length<capacity()); if(ret) { for(int p=m_length-1;p>=i;p--) { m_array[p+1]=m_array[p]; } m_array[i]=e; m_length++; } return ret; } bool insert(const T&e)//在尾部插入数据 { return insert(m_length,e); } /*删除操作 1.判断目标是否合法 2.将目标位置后的所有元素前移一个位置 3.线性表长度减1 */ bool remove(int i) { bool ret=((0<=i)&&(i<=m_length)); if(ret) { for(int p=i;p<m_length;p++) { m_array[p]=m_array[p+1]; } m_length--; } return ret; } bool set(int i,const T&e) { bool ret=((0<=i)&&(i<=m_length)); if(ret) { m_array[i]=e; } return ret; } bool get(int i,T&e) const { bool ret=((0<=i)&&(i<=m_length)); if(ret) { e=m_array[i]; } return ret; } int find(const T&e)const { int ret=-1; for(int i=0;i<m_length;i++) { if(m_array[i]=e) { ret=i; break; } } return ret; } int length()const { return m_length; } void clear() { m_length=0; } //数组的访问 T& operator[](int i)//数组操作符的重载 { if((0<=i)&&(i<=m_length)) { return m_array[i]; } else { THROW_EXCEPTION(indexOutOfBoundsException,"Parameter i is invaild...");//i不合法，越界操作异常 } } T operator [](int i)const { //去除当前对象的const属性 return (const_cast<SeqList<T>&>(*this))[i]; } virtual int capacity()const=0;//纯虚h函数，由子类重写 }; }