线性表的顺序存储

一、线性表简介

  线性表是一种线性结构，它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中，除了头尾元素，每个元素都有且只有一个直接前驱，有且只有一个直接后继，而序列头元素没有直接前驱，序列尾元素没有直接后继。
  数据结构中常见的线性结构有数组、单链表、双链表、循环链表等。线性表中的元素为某种相同的抽象数据类型。可以是C语言的内置类型或结构体，也可以是C++自定义类型。
线性表的数据元素具有抽象的数据类型，在设计具体的应用程序时，数据元素的抽象类型将被具体的数据类型所取代。

二，线性表的顺序储存结构及实现

使用顺序存储结构存储的数据，第一个元素所在的地址就是这块存储空间的首地址。通过首地址，可以轻松访问到存储的所有的数据，只要首地址不丢，数据永远都能找着（一根绳上的蚂蚱，要有就都有）。

使用线性表的顺序存储结构生成的表，称为顺序表。

顺序表的实现方法

顺序表中存放数据的特点和数组这种数据类型完全吻合，所以顺序表的实现使用的是数组。

数组实现顺序表的存储结构时，一定要注意预先申请足够大的内存空间，避免因存储空间不足，造成数据溢出，导致不必要的程序错误甚至崩溃。

顺序表的存储结构

在建立顺序表时，除了预先申请内存空间，还需要实时记录顺序表的长度和顺序表本身申请的内存大小，便于后期对顺序表中的数据元素进行调取。

顺序表的实现

const int MaxSize=100;
template<class DataType>
class SeqList
{
public:
  SeqList(){length=0;}                //无参构造函数，建立一个空的顺序表
  SeqList(DataType a[],int n);        //有参构造函数，建立一个长度为n的顺序表
  ~SeqList(){}          //析构函数为空
  int Length(){return length;}      //求线性表的长度
  DateType Get(int i);        //按位查找，在线性表中查找第i个元素
  int Locate(DataType x);       //按值查找，在线性表中查找值为x的元素序号
  void Insert(int i,DataType x);      //插入操作，在线性表中第i个位置插入值为x的元素
  DateType Delete(int i);       //删除操作，删除线性表的第i个元素
  void PrintList();       //遍历操作，按序号依次输出各元素
private:
  DateType data[MaxSize];       //存放数据元素的数组
  int length;         //线性表的长度
};

顺序表有参构造函数SeqList

template<class DateType>
SeqList<DataType>::SeqList(DataType a[],int n)
{
  if(n>MaxSize)
    throw"参数非法";
  for(i=0;i<n;i++)
    data[i]=a[i];
  length=n;
}

顺序表按位查找算法Get

template<class DataType>
DataType SeqList<DataType>::Get(int i)
{
  if(i<1&&i>length)
    throw"查找位置非法";
  else
    return data[i-1];
}

顺序表插入算法

template<class DataType>
void SeqList<DataType>::Insert(int i,DataType x)
{
  if(length>=MaxSize)
    throw"上溢";
  if(i<1||i>length+1)
    throw"位置";
  for(j=length;j>=i;j--)
    data[j]=data[j-1];                //注意第j个元素存在于数组下标为j-1处
  data[i-1]=x;
  length++;
}

顺序表删除算法Delete

template<class DataType>
void SeqList<DataType>::Delete(int i)
{
  if(length==0)
    throw"下溢";
  if(i<1||i>length)
    throw"位置";
  x=data[i-1];                            //取出位置i的元素
  for(j=i;j<length;j++)
    data[j-1]=data[j];              //注意此处j已经是元素所在的数组下标
  length--;
  return x;
}