一、定义

线性表是由n个类型相同的数据元素组成的有限序列，记为（a₁,a₂,...,a_i-1,a_i,a_i+1,...,a_n）。

 

二、特点

逻辑上相邻的元素，在物理上也相邻。只要确定了第一个元素的起始位置，线性表的任一元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。

 

三、存储结构

#define ListSize 100typedef struct{    DataType list[ListSize];  //DataType表示数据类型,list用于存储线性表中的数据元素     int length; //length用来表示线性表中数据元素的个数 }SeqList;  //结构体类型名

 

 

如果要定义一个顺序表，代码如下：

SeqList L;

 

如果要定义一个指向顺序表的指针，代码如下：

SeqList *L;

 

 

四、基本运算

（1）初始化线性表

void InitList(SeqList *L)  //初始化线性表{    L->length=0;  //把线性表的长度置为0 }

 

 

（2）判断线性表是否为空

int InitEmpty(SeqList L)  //判断线性表是否为空，线性表为空返回1，否则返回0{    if(L.length==0)  //线性表的长度若为0        return 1;  //返回1    else        return 0;  //返回0 }

 

 

（3）按照序号查找

int GetElem(SeqList L,int i,DataType *e)//查找线性表中第i个元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败{    if(i<1 || i>L.length)  //在查找第i个元素之前先判断该序号是否合法         return -1;    *e=L.list[i-1];  //将第i个元素的值赋值给e*     return 1;}

 

 

（4）按内容查找

int LocateElem(SeqList L,DataType e)  //查找线性表中元素值为e的元素{    int i;    for(i=0;i

 

 

（5）插入操作

要在顺序表中的第i个位置上插入元素e，首先将第i个位置以后的元素依次向后移动1个位置，其次把元素e插入第i个位置。

int InsertList(SeqList *L,int i,DataType e)//在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满了就返回0{    int j;    if(i<1 || i>L->length+1)  //在插入元素前，判断插入位置是否合法    {        printf("插入位置i不合法!\n");        return -1;    }     else if(L->length>=ListSize)  //在插入元素前，判断顺序表是否已经满，不能插入元素    {        printf("顺序表已满，不能插入元素。\n");        return 0;    }     else    {        for(j=L->length;j>=i;j--)  //将第i个位置以后的元素依次后移            L->list[j]=L->list[j-1];        L->list[i-1]=e;  //插入元素到第i个位置        L->length=L->length+1;  //将顺序表长增1        return 1;     }}

 

注：插入元素的位置i的合法范围应该是1<=i<=L->length+1。当i=1时，插入位置是在第一个元素之前；当i=L->length+1时，插入位置是最后一个元素之后。当插入位置是i=L->length+1时，不需要移动元素；当插入位置是i=0时，则需要移动所有元素。

 

（6）删除第i个元素

在进行删除操作时，先判断顺序表是否为空，如果不空，接着判断序号是否合法，如果不空且合法，则要将删除的元素赋给e，并把该元素删除，将表长减1。

int DeleteList(SeqList *L,int i,DataType *e){    int j;    if(L->length<=0)  //判断顺序表是否为空     {        printf("顺序表已空不能进行删除\n");        return 0;    }    else if(i<1 || i>L->length)  //判断序号是否合法     {        printf("删除位置不合适!\n");        return -1;    }    else    {        *e=L->list[i-1];        for(j=i;j<=L->length-1;j++)            L->list[j-1]=L->list[j];        L->length=L->length-1;  //表长-1         return 1;    }}

 

注：删除元素的位置i的合法范围应该是1<=i<=L->length。当i=1时，表示要删除第一个元素，对应数据中的第0个元素；当i=L->length时，要删除的是最后一个元素。

 

（7）求线性表的长度

int ListLength(SeqList L){    return L.length;}

 

 

（8）清空顺序表

void ClearList(SeqList *L){    L->length=0;}

 

注：可将上述顺序表存储结构的定义及基本运算保存在一个头文件中，在使用时通过#include "  .h"引用这些基本运算即可。

 

五、示例

（1）分拆顺序表：左边的元素小于等于0，右边的元素大于等于0.

编写一个算法，把一个顺序表分拆成两个部分，使顺序表中不大于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如顺序表（88，-9，-28，19，-31，22，-50，62，-76）经过分拆调整后变为（-76，-9，-28，-50，-31，22，19，62，88）。

 

算法思想：设置两个指示器 i 和 j，分别扫描顺序表中的元素，i 和 j 分别从顺序表的左端和右端开始扫描。如果 i 遇到小于等于0的元素，则略过不处理，继续向前扫描；如果遇到大于0的元素，则暂停扫描。如果 j 遇到大于0的元素，则略过不处理，继续向前扫描；如果遇到小于等于0的元素，则暂停扫描。如果 i 和 j 都停下来，则交换 i 和 j 指向的元素。重复执行直到 i >= j 为止。

 

#include 
     
      #include 
      
       #define ListSize 200typedef int DataType;#include "SeqList.h"void SplitSepList(SeqList *L);void main(){    int i,flag,n;    DataType e;    SeqList L;    int a[]={
   88,-9,-28,19,-31,22,-50,62,-76};    InitList(&L);                //初始化顺序表l    n=sizeof(a)/sizeof(a[0]);    for(i=1;i<=n;i++)   //将数组a的元素插入顺序表L中    {        if(InsertList(&L,i,a[i-1])==0)        {            printf("位置不合法");            return;        }    }    printf("顺序表L中的元素:\n");    for(i=1;i<=L.length;i++)  //输出顺序表L中的每个元素    {        flag=GetElem(L,i,&e);  //返回顺序表L中的每个元素到e中        if(flag==1)            printf("%4d",e);    }    printf("\n");    printf("顺序表L调整后（左边元素小于等于0，右边元素大于等于0）:\n");    SplitSepList(&L);   //调整顺序表    for(i=1;i<=L.length;i++)  //输出调整后顺序表L中所有元素    {        flag==GetElem(L,i,&e);        if(flag==1)            printf("%4d",e);    }    printf("\n");}void SplitSepList(SeqList *L){    int i,j;  //定义两个指示器 i 和 j    DataType e;    i=0;j=(*L).length-1;  //指示器 i 和 j 分别指示顺序表的左端和右端元素    while(i
       
        list[i]<=0)  //i 遇到小于等于0的元素            i++;  //略过        while(L->list[j]>0)  //j 遇到大于0的元素            j--;   //略过        if(i
        
         list[i];            L->list[i]=L->list[j];            L->list[j]=e;        }    }}