2.2 线性表顺序存储及其操作的实现

2.2.1 顺序表

线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表中的各数据元素，用这种存储形式存储的线性表称为顺序表。因为内存中的地址空间是线性的，所以用物理位置关系上的相邻性实现数据元素之间的逻辑相邻关系既简单又自然。线性表的顺序存储示意图如图2.1所示，设a1的存储地址为Loc(a1)，每个数据元素占d个存储单元，则第i个数据元素的地址为：

Loc(ai)=Loc(a1)+(i-1)*d 1≤i≤n

这就是说，只要知道顺序表首地址和每个数据元素所占单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。

在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的了。考虑到线性表有插入、删除等运算，即表长是可变的，因此，数组的容量要设计得足够大，设用data[MAXSIZE]来表示，其中MAXSIZE是一个根据实际问题定义的足够大的整数，线性表中的数据从data[0]开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MAXSIZE个，因此需用变量last记录当前线性表中最后一个元素在数组中的位置，即last起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。这种存储思想的具体描述可以是多样的，如可以是：

datatype data [MAXSIZE]；
int last；

这样表示的顺序表如图2.1所示，表长为last+1，数据元素分别存放在data[0]到data[last]中。这样使用简单方便，但有时不便于管理。

从结构性上考虑，通常将data和last封装成一个结构，作为顺序表的数据类型：

typedef struct
            { datatype data[MAXSIZE]；
            int last；
            } SeqList；

定义一个顺序表：

SeqList  L；

这样表示的线性表如图2.2（a）所示。表长=L.last+1，线性表中的数据元素a1至an分别存放在L.data[0]至L.data[L.last]中。

由于本书后面的算法用C语言描述，根据C语言中的一些规则，有时定义一个指向SeqList类型的指针更为方便：

SeqList  *L；

L是一个指针变量，线性表的存储空间通过L=malloc(sizeof(SeqList))操作来获得。L中存放的是顺序表的地址，这样表示的线性表如图2.2（b）所示。表长表示为(*L).last+1或 L->last+1，线性表的存储区域为L->data，线性表中数据元素的存储空间为：

L->data[0] ~ L->data[L->last]。

在以后的算法中多用这种方法表示，读者在读算法时应注意相关数据结构的类型说明。

2.2.2 顺序表基本操作的实现

根据以上线性表顺序存储结构定义，确定了其存储方式，然后就可以讨论其基本操作的实现方法（即实现算法）了，同时还要对算法进行初步的分析。

1.顺序表的初始化

顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后将表中last指针置为-1，表示表中没有数据元素。算法如下：

SeqList *init_SeqList( )
     { SeqList *L；
       L=malloc(sizeof(SeqList))；
       L->last=-1；
       return L；
}

设调用函数为主函数，主函数对初始化函数的调用如下：

main( )
    { SeqList *L；
      L=init_SeqList( )；
       …
}

2.插入操作

线性表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表（a1, a2, …, ai-1, ai, ai+1, …, an）成为表长为n+1的表：（a1, a2, …, ai-1, x, ai, ai+1, …, an）。i的取值范围为1≤i≤n+1。

顺序表上完成这一运算则通过以下步骤进行：

（1）将ai～an顺序向后移动，为新元素让出位置；

（2）将x置入空出的第i个位置；

（3）修改last指针（相当于修改表长），使之仍指向最后一个元素。

图2.3所示为顺序表中的插入操作示意图。

算法2.1 顺序表的元素插入算法。

int Insert_SeqList(SeqList *L，int i，datatype x)
{ int j；
  if ( L->last== MAXSIZE-1 )
     { printf("表满")； return(-1)； }     /*表空间已满，不能插入*/
  if (i<1 || i>L->last+2)                  /*检查插入位置的正确性*/
     { printf("位置错")； return(0)； }
  for (j=L->last；j>= i-1；j--)
      L->data[j+1]=L->data[j]；            /* 结点移动 */
  L->data[i-1]=x；                         /*新元素插入*/
  L->last++；                              /*last仍指向最后一个元素*/
  return (1)；                             /*插入成功，返回*/
}

在本算法中应注意以下问题。

（1）顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时应先检查表空间是否满了，在表满的情况下不能再做插入，否则会产生溢出错误。

（2）要检验插入位置的有效性，这里i的有效范围是：1≤i≤n+1，其中n为原表长。

（3）注意数据的移动方向。

插入算法的时间复杂度分析：顺序表的插入操作，时间主要消耗在数据的移动上，在第i个位置上插入x，从ai到an都要向后移动一个位置，共需要移动n - i+1个元素，而i的取值范围为1≤i≤n+1，即有n+1个位置可以插入。设在第i个位置上做插入的概率为pi，则平均移动数据元素的次数为：

假设插入第i个位置的可能性为等概率情况，即，则

这说明：在顺序表上做插入操作，平均需移动表中一半的数据元素。显然其时间复杂度为O(n)。

3.删除操作

线性表的删除运算是指将表中第i个元素从线性表中去掉，删除后使原表长为n的线性表（a1, a2, …, ai-1, ai, ai+1, …, an）成为表长为n-1的线性表（a1, a2, …, ai-1, ai+1, …, an），i的取值范围为1≤i≤n。

顺序表上完成这一操作的步骤如下：

（1）将ai+1～an顺序向前移动；

（2）修改last指针（相当于修改表长）使之仍指向最后一个元素。

图2.4为顺序表中的删除操作示意图。

算法2.2 顺序表的元素删除算法。

int Delete_SeqList (SeqList *L; int i)
  { int j；
    if ( i<1 || i>L->last+1)                         /*检查空表及删除位置的合法性*/
      { printf ("不存在第i个元素")； return(0)； }
    for ( j=i；j<=L->last；j++ )
          L->data[j-1]=L->data[j]；                  /*向上移动*/
    L->last- -；
    return(1)；                                      /*删除成功*/
}

本算法注意以下问题：

① 删除第i个元素，i的取值为1≤i≤n，否则第i个元素不存在，因此，要检查删除位置的有效性；

② 当表空时不能做删除操作，因表空时L->last的值为-1，条件（i<1 || i>L->last+1）也包括了对表空的检查。

③ 删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。

删除算法的时间复杂度分析：与插入操作相同，删除操作的时间主要消耗在移动表中元素上，删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，所以平均移动数据元素的次数为：

同样，在删除位置等概率情况下，，则

这说明：在顺序表上做删除操作时平均大约需要移动表中一半的元素，显然该算法的时间复杂度为O(n)。

4.按值查找

线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。在顺序表中完成该操作最简单的方法是：从第一个元素a1起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与x相等的元素，返回-1。

算法2.3 顺序表的元素查找算法。

int Location_SeqList (SeqList *L，datatype x)
   { int i=0；
     while ( i<=L.last && L->data[i]!= x)
          i++；
     if ( i>L->last) return -1；
      else  return i；              /*返回的是存储位置*/
}

本算法的主要运算是比较。显然比较的次数与 x 在表中的位置有关，也与表长有关。当a1=x时，比较一次成功。当an=x时比较n次成功。其平均比较次数为(n+1)/2，时间复杂度为O(n)。

2.2.3 顺序表的其他操作举例

【例2.1】 将顺序表（a1, a2, …, an）重新排列为以a1为界的两部分：a1前面的值均比a1小、a1后面的值均比a1大（这里假设数据元素的类型具有可比性，不妨设为整型），操作前后如图2.5所示。这一操作称为划分，a1称为基准。

划分的方法有多种，下面介绍的划分算法思路简单，但性能较差。

基本思路：从第二个元素开始到最后一个元素，逐一向后扫描。

（1）当前数据元素ai比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。

（2）若当前元素若比a1小，说明它应该在a1的前面，此时将它上面的元素依次向下移动一个位置，然后将它置于最上方。

算法2.4 顺序表的划分算法。

void partition (SeqList *L)
    { int i，j；
      datatype x，y；
      x=L->data[0]；                                /*将基准置入 x 中*/
      for (i=1；i<=L->last；i++)
          if (L->data[i]<x)                         /*当前元素小于基准*/
              { y=L->data[i]；
                for (j=i-1；j>=0；j- -)             /*移动*/
                     L－>data[j+1]=L->data[j]；
                     L->data[0]=y；
       }
}

【例2.2】 设有顺序表A和B，其元素均按从小到大的顺序升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也从小到大升序排列。

算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将值较小的元素赋给C，如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。C的容量要能够容纳A、B两个线性表长度的和。

算法2.5 有序表的合并算法。

void merge (SeqList A, SeqList B, SeqList *C)
  { int i，j，k；
    i=0；j=0；k=0；
    while ( i<=A.last && j<=B.last )
       if (A.data[i]<B.data[j])
           C->data[k++]=A.data[i++]；
       else
           C->data[k++]=B.data[j++]；
    while (i<=A.last )
           C->data[k++]= A.data[i++]；
    while (j<=B.last )
           C->data[k++]=B.data[j++]；
    C->last=k-1；
}

算法的时间复杂度是O(m+n)，其中m是A的表长，n是B的表长。

【例2.3】 两个线性表的比较操作。假定两个线性表的比较方法如下：设A、B是两个线性表，表长分别为m和n。A′和B′分别为A和B中除去最大共同前缀后的子表。

例如，A=(x, y, y, z, x, z)，B=(x, y, y, z, y, x, x, z)，两表最大共同前缀为（x, y, y, z）。则A′=(x, z)，B′=(y, x, x, z)。

若A′=B′=空表，则A=B。若A′=空表且B′ ≠空表，或两者均不为空表且A′的首元素小于B′的首元素，则A<B；否则，A>B。

算法思路：首先找出A、B的最大共同前缀；然后求出A′和B′，再按比较规则进行比较，A>B函数返回1；A=B返回0；A<B返回-1。

算法2.6 两个顺序表的比较算法。

int compare( A, B, m, n)
int A[ ]，B[ ]；
int m，n；
{ int i=0, j，AS[ ]，BS[ ]，ms=0，ns=0；      /*AS, BS作为A′, B′*/
     while (A[i]==B[i]) i++；                 /*找最大共同前缀*/
     for (j=i；j<m；j++)
          { AS[j-i]=A[j]； ms++； }           /*求A′, ms为A′的长度*/
     for (j=i；j<n；j++)
          { BS[j-i]=B[j]； ns++； }           /*求B′, ns为B′的长度*/
     if (ms==ns&&ms==0) return 0；
       else if (ms==0&&ns>0 || ms>0 && ns>0 && AS[0]<BS[0]) return -1；
             else return 1；
}

算法的时间复杂度是O(m+n)。