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;
｝