2.2 线性表的顺序表示和实现

 

2.2  线性表的顺序表示和实现

实现线性表最简单也是最常见的方法是采用顺序存储结构。线性表的顺序存储是把线性表中的所有元素，按照其逻辑顺序依次存储到存储器某个指定位置开始的一段连续存储空间中。

在计算机内部，系统用一段连续的存储单元存储高级语言程序中定义的数组。例如，在C语言中，定义一个数组就是定义了可供用户使用的一段连续的存储空间，该存储空间的起始地址就是由数组名表示的地址常量。按照线性表中数据元素的逻辑顺序，用每一个数组元素空间来依次存储线性表的每一个数据元素。每个数组元素所占用的存储空间长度（字节数）为sizeof(ElemType)，整个线性表所占用的存储空间长度为n×sizeof(ElemType)（n为线性表的长度，ElemType为数据元素类型）。以这种存储结构实现线性表被称为线性表的顺序存储结构，并称此时的线性表为顺序表。

2.2.1  顺序表的定义

顺序表是线性表的顺序存储结构，即按顺序存储方式构造的线性表。按照顺序存储方式，顺序表的一个存储单元存储线性表的一个节点内容，即数据元素（此外不含其他信息），所有存储单元按相应数据元素间的逻辑关系（即一对一的邻接关系）来决定排列顺序。这就是顺序表表示法的基本思想，由此决定了顺序表的特点：逻辑结构中相邻的节点在存储结构中仍相邻。

假定线性表的数据元素类型为ElemType（在实际应用中，此类型应根据实际问题中出现的数据元素的特性具体定义，如为int、char类型等），在C/C++语言中，可用下述类型定义来描述顺序表：

#DEFINE MAXSIZE                         /*顺序表的容量*/

typedef struct

{  

    ElemType data[MAXSIZE];             /*存放顺序表的元素*/

    int length;                          /*顺序表的实际长度*/

} SqList;

顺序表示意图如图2-1所示。

图2-1  顺序表示意图

其中，数据域data是一个一维数组，线性表的第1，2，……，n个元素分别存放在此数组的第0，1，……，length-1个分量中，如图2-1所示。数据域length表示线性表当前的长度，而length-1是线性表的终端元素在顺序表中的位置（因为C/C++语言的数组下标从0开始）。常数MAXSIZE称为顺序表的容量，其值通常根据具体问题的需要取为线性表实际可能达到的最大长度。从length到MAXSIZE-1为顺序表当前的空闲区（或称备用区）。

顺序表是由数组data和变量length两部分组成的。为了反映data与length之间的这种内在联系，避免误用，上述类型定义中将它们说明为结构体类型SqList的两个域。这样，SqList类型完整地描述了顺序表的组织。它使得对顺序表L的引用仅涉及结构体变量L，符合现代的结构化程序设计思想。

假定每个ElemType类型的变量占用R（R≥1）个内存单元，b是顺序表的第一个存储元素的内存地址，那么，第i个元素a_i的存储地址为b+(i-1)×R。

综上所述，顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的相对地址。它的特点是逻辑上相邻的元素，存储在物理位置也相邻的单元中。

2.2.2  顺序表的基本运算

在本书的约定下，实现运算就是设计出完成该运算功能的算法，也就是用C/C++语言给出求解方法和求解步骤的完整规定。因此，运算实现必须以存储结构的类型定义为前提。上面已经给出了顺序表的类型定义，在此基础上可以进一步讨论线性表的基本运算在顺序表上的实现。

在顺序表上实现线性表基本运算的算法如下。

1．初始化线性表运算

将顺序表L的length域置为0。

void InitList(SqList &L)

{

   L.length=0;

}

2．求线性表长度运算

返回顺序表L的length域值。

int GetLength(SqList L)

{

   return L.length;

}

3．求线性表中第i个元素运算

在i无效时返回特殊值0，有效时返回1，并用e存储第i个元素的值。

int GetElem(SqList L,int i,ElemType &e)

{

   if(i<1 || i>L.length)    /*无效的i值*/

     return 0;

   else

   {

     e=L.data[i-1];

     return 1;

   }

}

4．按值查找运算

在顺序表L中查找第一个值为x的元素，并返回其位置，若未找到，则返回0。

int Locate(SqList L,ElemType x)         /*按值查找*/

{

   int i=0;

   while(L.data[i]!=x)                  /*查找值为x的第一个节点*/

       i++;

   if(i>L.length)

       return(0);                       /*未找到*/

   else

       return(i+1);

}

5．插入元素运算

在i无效时返回0，有效时将L.data[i-1]～L.data[L.length-1]后移一个位置，在L.data[i-1]处插入x，顺序表长度加1，并返回1。

int InsElem(SqList &L,ElemType x,int i)

{

   int j;

   if(i<1 || i>L.length+1)           /*无效的参数i*/

       return 0;

   for(j=L.length;j>i;j--)          /*将位置为i的节点及之后的节点后移*/

       L.data[j]=L.data[j-1];

       L.data[i-1]=x;                  /*在位置i处放入x*/

       L.length++;                      /*线性表长度加1*/

   return 1;

}

6．删除元素运算

在i无效时返回0，有效时将L.data[i]～L.data[L.length-1]前移一个位置，顺序表长度减1，并返回1。

int DelElem(SqList &L,int i)

{

   int j;

   if (i<1 || i>L.length)            /*无效的参数i*/

      return 0;

   for (j=i;j<L.length;j++)         /*将位置为i的节点之后的节点前移*/

        L.data[j-1]=L.data[j];

        L.length--;                     /*线性表长度减1*/

   return 1;

}

7．输出线性表运算

扫描顺序表L，输出各元素值。

void DispList(SqList L)

{

   int i;

   for(i=1;i<=L.length;i++)

        printf("%c",L.data[i-1]);

   printf("\n");

}

当顺序表的基本运算设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序表各种操作的实现过程。

void main()

{

  int i;

  ElemType e;

  SqList L;

  InitList(L);                         /*初始化顺序表L*/

  InsElem(L,'a',1);                     /*插入元素a*/

  InsElem(L,'c',2);                   /*插入元素c*/

  InsElem(L,'a',3);                   /*插入元素a*/

  InsElem(L,'e',4);                   /*插入元素e*/

  InsElem(L,'d',5);                   /*插入元素d*/

  InsElem(L,'b',6);                   /*插入元素b*/

  printf("线性表:");DispList(L);       /*输出各元素值*/

  printf("长度:%d\n",GetLength(L));  /*返回顺序表的长度*/

  i=3;

GetElem(L,i,e);                         /*求线性表中第i个元素，并用e存储*/

   printf("第%d个元素:%c\n",i,e);

   e='a';

   /*在顺序表L中查找第一个值为e的元素*/

   printf("元素%c是第%d个元素\n",e,Locate(L,e)); 

   i=4;printf("删除第%d个元素\n",i);

   DelElem(L,i);                        /*删除一个元素*/

   printf("线性表:");DispList(L);    /*输出各元素值*/

}

以上程序的执行结果如下：

线性表:a c a e d b

长度:6

第3个元素:a

元素a是第1个元素

删除第4个元素

线性表:a c a d b

【例2-1】用顺序表表示两个集合（每个集合中没有重复的元素），设计一个算法求这两个集合A和B的公共元素，并将求出的公共元素存放在顺序表C中。

解：算法设计思路是用i扫描顺序表A，判断当前元素是否在顺序表B中，若在，表示它是公共元素，将其添加到顺序表C中。对应的算法如下：

void common(SqList A,SqList B,SqList &C)  /*C为引用型参数*/

{

   int i,j;

   C.length=0;                            /*顺序表C的长度初始化*/

   for(i=0;i<A.length;i++)                /*顺序表A未扫描完则循环*/

   {

      j=0;

      while(j<B.length && B.data[j]!=A.data[i])

       j++;

      if (j<B.length)                      /*元素A.data[i]在B中，是公共元素*/

      { 

         C.data[C.length]=A.data[i];       /*将A.data[i]添加到C中*/

         C.length++;                       /*顺序表C的长度加1*/

      }

   }

}

【例2-2】已知有两个按元素值递增有序的顺序表A和B，设计一个算法将A表和B表的全部元素归并成一个按元素递增有序的线性表C。实现上述算法并分析时间复杂度。

解：算法设计思路是用i扫描顺序表A，用j扫描顺序表B。当A和B都未扫描完时，比较两者的当前元素，则将较小者复制到C中，若两者的当前元素相等，则这两个元素都复制到C中。最后将尚未扫描完的顺序表的余下元素均复制到顺序表C中。对应的算法如下：

void merge(SqList A,SqList B,SqList &C)     /*C为引用型参数*/

{

   int i=0,j=0,k=0;

   while(i<A.length && j<B.length)           /*顺序表A和B都没扫描完时循环*/

   { 

      if(A.data[i]<B.data[j])                /*顺序表A中元素小，复制到表C中*/

      {

         C.data[k]=A.data[i];

         i++;k++;                            /*顺序表A和C的i和k后移*/

      }

      else if(A.data[i]>B.data[j])           /*顺序表B中元素小，复制到表C中*/

      { 

         C.data[k]=B.data[j];

         j++;k++;                            /*顺序表B和C的j和k后移*/

      }

      else                                   /*A.data[i]=B.data[j]*/

      { 

         C.data[k]=A.data[i];                /*顺序表A中元素复制到表C中*/

         i++;k++;                            /*顺序表A和C的i和k后移*/

         C.data[k]=B.data[j];                /*顺序表B中元素复制到表C中*/

         j++;k++;                            /*顺序表B和C的j和k后移*/

      }

   }

while(i<A.length)                              /*将A中剩余的元素复制到C中*/

{

   C.data[k]=A.data[i];

   i++;k++;

}

while(j<B.length)                              /*将B中剩余的元素复制到C中*/

{

   C.data[k]=B.data[j];

   j++;k++;

}

   C.length=k;                                 /*指定顺序表C的实际长度*/

}

本算法的时间复杂度为O(m+n)，其中m和n分别为顺序表A和B的长度。

2.2.3  顺序表实现算法的分析

对于顺序表上的插入、删除算法的时间复杂度分析来说，通常以节点移动为标准操作。其合理性依据是：在这类问题中，移动一个节点所花费的时间往往比其他基本操作（如条件判断、算术表达式的计算等）要多得多，因为在现实问题中一个节点往往包含了大量的信息。

对于插入算法InsElem()来说，节点移动的次数不仅与表长L.length=n有关，而且与插入位置i有关：当i=n+1时，移动次数为0；当i=1时，移动次数为n，达到最大值。在线性表L中共有n+1个可以插入节点的地方。假设p_i（p_i=）是在第i个位置上增加一个节点的概率，则在长度为n的线性表中插入一个节点时所需移动节点的平均次数为：

因此，插入算法的平均时间复杂度为O(n)。

对于删除算法DelElem()来说，节点移动的次数也与表长n和删除节点的位置i有关：当i=n时，移动次数为0；当i=1时，移动次数为n-1。在线性表L中共有n个节点可以被删除。假设p_i（p_i=）是删除第i个位置上节点的概率，则在长度为n的线性表中删除一个节点时所需移动节点的平均次数为：

因此，删除算法的平均时间复杂度为O(n)。

以上分析中，线性表的顺序实现在插入、删除算法的时间性能方面是不理想的。后面将考虑线性表的链式实现方法，并对两种实现做全面比较。