一、何为线性表？

线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

1. 两种线性存储结构

线性表存储数据可细分为以下 2 种：

将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；
数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）；

2. 线性表常用术语

数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。例如，图 1 显示的这组数据，其中 1、2、3、4 和 5 都是这组数据中的一个元素。

某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”；

某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”；

二、顺序存储结构（顺序表）

顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。

由此我们可以得出，将“具有一对一逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。

可以发现，顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组。

1. 顺序表的初始化

初始化操作就是构造一个空的顺序表。

（1）参数用引用

Status InitList_Sq(SqList &L){     //构造一个空的顺序表L
    L.elem=new ElemType[MAXSIZE];  //为顺序表分配数组空间
    if(!L.elem) exit(OVERFLOW);    //存储分配失败退出
    L.length=0;                    //空表长度为0
    return OK;
}

（2）参数用指针

Status InitList_Sq(SqList *L){        //构造一个空的顺序表L
    L-> elem=new ElemType[MAXSIZE];   //为顺序表分配数组空间
    if(! L-> elem) exit(OVERFLOW);    //存储分配失败退出
    L-> length=0;                     //空表长度为0
    return OK;
}

2. 顺序表的取值

获取线性表L中的某个数据元素的内容

int GetElem(SqList L,int i,ElemType &e)
{
  if (i<1||i>L.length) return ERROR;   //判断i值是否合理，若不合理，返回ERROR
  e=L.elem[i-1];                       //第i-1的单元存储着第i个数据
  return OK;
}

3. 顺序表的查找

根据指定数据获取数据所在的位置，在线性表L中查找值为e的数据元素

int LocateELem(SqList L,ElemType e)
{
  for (i=0;i< L.length;i++)
      if (L.elem[i]==e) return i+1;                
  return 0;
}

4. 顺序表的插入

【算法步骤】：

判断插入位置i 是否合法。
判断顺序表的存储空间是否已满。
将第n至第i 位的元素依次向后移动一个位置，空出第i个位置。
将要插入的新元素e放入第i个位置。
表长加1，插入成功返回OK。

在线性表L中第i个数据元素之前插入数据元素e：

Status ListInsert_Sq(SqList &L,int i ,ElemType e){
   if(i<1 || i>L.length+1) return ERROR;           //i值不合法
   if(L.length==MAXSIZE) return ERROR;             //当前存储空间已满     
   for(j=L.length-1;j>=i-1;j--) 
       L.elem[j+1]=L.elem[j];                      //插入位置及之后的元素后移
   L.elem[i-1]=e;                                  //将新元素e放入第i个位置
   ++L.length;                                     //表长增1
   return OK;
}

5. 顺序表的删除

【算法步骤】：

判断删除位置i 是否合法（合法值为1≤i≤n）。
将第i+1至第n 位的元素依次向前移动一个位置。
表长减1，删除成功返回OK。

将线性表L中第i个数据元素删除：

Status ListDelete_Sq(SqList  &L, int i){
   if((i<1)||(i>L.length)) return ERROR;   //i值不合法
   for (j=i;j<=L.length-1;j++)                   
     L.elem[j-1]=L.elem[j];                //被删除元素之后的元素前移  
   --L.length;                             //表长减1
   return OK;
}