2.2 线性表的顺序存储结构

2.2.1 顺序表

顺序表是线性表的顺序存储表示的简称，它指的是用一组地址连续的存储单元依次存放线性表中的数据元素，即以存储位置的相邻表示相继的两个数据元素之间的前驱和后继（线性）的关系（逻辑关系），并以表中第一个元素的存储位置作为线性表的起始地址，称为线性表的基地址，如图2-1所示。其特点是逻辑上相邻的数据元素，其物理（存储）位置也是相邻的。

假设每个数据元素占用k个存储单元，b为第一个元素的存储地址，则线性表中任意相邻的两个数据元素ai-1与ai的存储地址之间满足下面的关系：

LOC(ai)=LOC(ai-1)+k

线性表中的任意一个元素ai的存储地址与第一个元素的存储地址之间满足：

LOC(ai)=b+(i-1)k

顺序存储结构可以借助于高级程序设计语言中的数组来表示，一维数组的下标（从0开始）与元素在线性表中的序号（从1开始）一一对应。其类型描述如下：

#define MaxSize 线性表可能达到的最大长度
typedef struct
{ ElementType elem[MaxSize];   /* 线性表占用的数组空间*/
  int listlength;              /* 线性表的实际长度*/
}SeqList;

【注意】此处ElementType elem[MaxSize]的含义是数组elem可以是任何类型（如int、float、char等），包括用户自定义的任何其他结构类型。

若将线性表a定义为：

SeqList a；

则线性表a中序号为i的元素所对应数组元素的下标是i-1，即ai用a.elem[i-1]表示，a的长度由a.listlength表示。

2.2.2 顺序表上基本运算的实现

在上一节中，列出了线性表的7种基本运算，其中，初始化线性表l（InitList(l)），判断线性表l是否为空表（EmptyList(l)），求线性表l的长度（ListLength(l)），返回线性表l中第i个元素的值（GetData(l,i)），这些运算都很简单，不再讨论。在此仅对求线性表l中元素e的位置（Locate(l,e)），在l中第i个元素（或位置）之前插入元素e（InsList(l,i,e)），删除l中的第i个数据元素（DelList(l,i)）这些运算进行讨论。

1.查找运算

求线性表l中元素e的位置（Locate(l,e)），即在线性表l中查找元素e。考虑到算法的简洁性，本教材在讨论这些运算的实现时一律以数组的下标值代替线性表中元素的位置（序号），即序号与下标一致。若在表l中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。查找过程从第一个元素开始，依次将表中元素与e相比较，若相等，则查找成功，返回该元素在数组中的下标；若e与表中的所有元素都不相等，则查找失败，返回“-1”。算法如下：

int Locate(SeqList l，ElemType e)
/*在顺序表l中查找元素e，若l.elem[i]=e，则找到该元素，并返回i，若找不到，则返回-1*/
{ i=0 ;
   while ((i<=l.listlength-1)&&(l.elem[i]!=e) )
   /*顺序扫描表，直到找到值为e的元素,或扫描到表尾而没找到*/
      i++;
   if (i<=l.listlength-1)
       return(i);
   else
       return(-1);
} /* Locate */

下面分析算法的时间复杂度（查找成功时）。算法中的基本操作是i++，它出现在 while循环中，该操作的执行次数取决于要查找的元素在线性表中的位序，设Pi为查找第i个元素的概率，并假设对任何位置上元素的查找都是等概率的，即Pi=1/n，i=0,1,…,n-1。设Eloc为在长度n的表中查找一元素时i++操作的平均执行次数，则

所以算法的平均时间复杂度为O(n)。

2.插入运算

在l中第i个元素（或位置）之前插入数据元素e（InsList(l,i,e)），使得线性表(a1,…,ai-1, ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)，即改变了表中元素之间的关系，使<ai-1,ai>改变为<ai-1,e>和<e,ai>，同时表长增加1。

由于顺序表是以“存储位置相邻”表示“元素之间的前驱和后继关系”的，所以在插入e之前，必须将元素an,an-1,…,ai依次向后移动一个单元，在原（移动之前）ai的位置处插入e，以保证数据元素之间的逻辑关系。插入过程如图2-2所示，相应的算法描述如下。

void InsList(SeqList *l,int i,ElemType e)
/*在顺序表l中第i（i应视做数组的下标）个数据元素之前插入元素e*/
{  if((i<0) || (i>l-> listlength)) /*判断插入位置是否合法*/
   {  printf(“Error”)；
      return;
   }
   if(l-> listlength >=MaxSize-1) /*判断表是否已满*/
   {  printf(“Overflow”)；
      return;
   }
   for(k=l-> listlength-1;k>=i;k--)
   /*将元素elem[listlength-1..i]依次向后移动一个单元（位置）*/
        l->elem[k+1]=l->elem[k];
   l->elem[i]=e;
   l-> listlength++;
} /*InsList*/

插入算法的基本操作是l->elem[k+1]=l->elem[k]，即数据元素的后移，它出现在 for循环中。与查找算法类似，该操作的执行次数取决于插入元素在线性表中的位序。同样，设Pi为等概率插入时在第i（0≤i≤l-> listlength）个位置上插入元素的概率，即，i=0,1,…,n（长度为n的线性表具有n+1个插入位置）。设Eins为在长度为n的线性表中插入一元素时所需的元素的平均移动次数，则

所以算法的平均时间复杂度为O(n)。

3.删除运算

删除l中的第i个数据元素（DelList(l,i)），使得线性表(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1, ai＋1,…,an)，即改变了线性表中元素之间的关系，使<ai-1,ai>和<ai,ai+1>改变为<ai-1,ai+1>，同时表长减1。同样地，为了反映数据元素之间逻辑关系的变化，需将数据元素ai,ai-1,…,an依次向前移动一个单元，其实现过程如图2-3所示。相应的算法描述如下。

void DelList(SeqList *l,int i)
/*在顺序表l中删除第i（i应视做数组的下标）个数据元素*/
{
     if((i<0) || (i>l->listlength-1)) /*判断删除位置是否合法*/
     {  printf("Error")；
        return;
     }
     for(k=i+1;i<=l->listlength-1;k++)
          l->elem[k-1]=l->elem[k];
          /*将第i个数据元素后面的元素依次前移*/
     l->listlength--;
} /* DelList */

与插入算法类似，Edel为在长度为n的表中删除一元素时所需的元素的平均移动次数，则

其中，Pi为等概率情况下删除第i个元素的概率。所以算法的平均时间复杂度为O(n)。

【例2-1】已知la与lb是两个递增有序的顺序表，要求写一算法，构造递增有序表lc，表中的元素是由la与lb合并后得到的。

顺序表lc中的元素是复制la与lb中的元素得到的。当la与lb中都有元素时，从第一个元素起，逐对进行比较，将小的复制到lc，直到将其中一个表的全部元素都复制到lc。再将另一表中剩余的元素也复制到lc。

void Merge(SeqList la,SeqList lb,SeqList *lc,)
/*合并递增有序表la与lb，合并后的递增序列存放在lc中*/
｛ i=j=k=0;
   while (i<=la.listlength-1 && j<=lb.listlength-1)
   /*la与lb中都有元素，合并两表中的元素*/
   {  if (la.elem[i]<=lb.elem[j])
      {  lc->elem[k]=la.elem[i];
         ++k;++i;
      }
      else
      {  lc->elem[k]=lb.elem[j];
         ++k;++j;
      }
   }
   while (i<=la.listlength-1) /*将la中的剩余元素复制到lc*/
   {  lc->elem[k]=la.elem[i];
         ++k;++i;
   }
   while (j<=lb.listlength) /*将lb中的剩余元素复制到lc*/
   {  lc->elem[k]=lb.elem[j];
         ++k;++j;
   }
   lc->listlength=la.listlength+lb.listlength;
｝