2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)

2.2.1 順序表

順序表是線性表的順序存儲(chǔ)表示的簡(jiǎn)稱，它指的是用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，即以存儲(chǔ)位置的相鄰表示相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼（線性）的關(guān)系（邏輯關(guān)系），并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱為線性表的基地址，如圖2-1所示。其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素，其物理（存儲(chǔ)）位置也是相鄰的。

假設(shè)每個(gè)數(shù)據(jù)元素占用k個(gè)存儲(chǔ)單元，b為第一個(gè)元素的存儲(chǔ)地址，則線性表中任意相鄰的兩個(gè)數(shù)據(jù)元素ai-1與ai的存儲(chǔ)地址之間滿足下面的關(guān)系：

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

線性表中的任意一個(gè)元素ai的存儲(chǔ)地址與第一個(gè)元素的存儲(chǔ)地址之間滿足：

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

順序存儲(chǔ)結(jié)構(gòu)可以借助于高級(jí)程序設(shè)計(jì)語言中的數(shù)組來表示，一維數(shù)組的下標(biāo)（從0開始）與元素在線性表中的序號(hào)（從1開始）一一對(duì)應(yīng)。其類型描述如下：

#define MaxSize 線性表可能達(dá)到的最大長(zhǎng)度
typedef struct
{ ElementType elem[MaxSize];   /* 線性表占用的數(shù)組空間*/
  int listlength;              /* 線性表的實(shí)際長(zhǎng)度*/
}SeqList;

【注意】此處ElementType elem[MaxSize]的含義是數(shù)組elem可以是任何類型（如int、float、char等），包括用戶自定義的任何其他結(jié)構(gòu)類型。

若將線性表a定義為：

SeqList a；

則線性表a中序號(hào)為i的元素所對(duì)應(yīng)數(shù)組元素的下標(biāo)是i-1，即ai用a.elem[i-1]表示，a的長(zhǎng)度由a.listlength表示。

2.2.2 順序表上基本運(yùn)算的實(shí)現(xiàn)

在上一節(jié)中，列出了線性表的7種基本運(yùn)算，其中，初始化線性表l（InitList(l)），判斷線性表l是否為空表（EmptyList(l)），求線性表l的長(zhǎng)度（ListLength(l)），返回線性表l中第i個(gè)元素的值（GetData(l,i)），這些運(yùn)算都很簡(jiǎn)單，不再討論。在此僅對(duì)求線性表l中元素e的位置（Locate(l,e)），在l中第i個(gè)元素（或位置）之前插入元素e（InsList(l,i,e)），刪除l中的第i個(gè)數(shù)據(jù)元素（DelList(l,i)）這些運(yùn)算進(jìn)行討論。

1.查找運(yùn)算

求線性表l中元素e的位置（Locate(l,e)），即在線性表l中查找元素e?？紤]到算法的簡(jiǎn)潔性，本教材在討論這些運(yùn)算的實(shí)現(xiàn)時(shí)一律以數(shù)組的下標(biāo)值代替線性表中元素的位置（序號(hào)），即序號(hào)與下標(biāo)一致。若在表l中找到與e相等的元素，則返回該元素在表中的序號(hào)；若找不到，則返回一個(gè)“空序號(hào)”，如-1。查找過程從第一個(gè)元素開始，依次將表中元素與e相比較，若相等，則查找成功，返回該元素在數(shù)組中的下標(biāo)；若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 */

下面分析算法的時(shí)間復(fù)雜度（查找成功時(shí)）。算法中的基本操作是i++，它出現(xiàn)在 while循環(huán)中，該操作的執(zhí)行次數(shù)取決于要查找的元素在線性表中的位序，設(shè)Pi為查找第i個(gè)元素的概率，并假設(shè)對(duì)任何位置上元素的查找都是等概率的，即Pi=1/n，i=0,1,…,n-1。設(shè)Eloc為在長(zhǎng)度n的表中查找一元素時(shí)i++操作的平均執(zhí)行次數(shù)，則

所以算法的平均時(shí)間復(fù)雜度為O(n)。

2.插入運(yùn)算

在l中第i個(gè)元素（或位置）之前插入數(shù)據(jù)元素e（InsList(l,i,e)），使得線性表(a1,…,ai-1, ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)，即改變了表中元素之間的關(guān)系，使<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>，同時(shí)表長(zhǎng)增加1。

由于順序表是以“存儲(chǔ)位置相鄰”表示“元素之間的前驅(qū)和后繼關(guān)系”的，所以在插入e之前，必須將元素an,an-1,…,ai依次向后移動(dòng)一個(gè)單元，在原（移動(dòng)之前）ai的位置處插入e，以保證數(shù)據(jù)元素之間的邏輯關(guān)系。插入過程如圖2-2所示，相應(yīng)的算法描述如下。

void InsList(SeqList *l,int i,ElemType e)
/*在順序表l中第i（i應(yīng)視做數(shù)組的下標(biāo)）個(gè)數(shù)據(jù)元素之前插入元素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]依次向后移動(dòng)一個(gè)單元（位置）*/
        l->elem[k+1]=l->elem[k];
   l->elem[i]=e;
   l-> listlength++;
} /*InsList*/

插入算法的基本操作是l->elem[k+1]=l->elem[k]，即數(shù)據(jù)元素的后移，它出現(xiàn)在 for循環(huán)中。與查找算法類似，該操作的執(zhí)行次數(shù)取決于插入元素在線性表中的位序。同樣，設(shè)Pi為等概率插入時(shí)在第i（0≤i≤l-> listlength）個(gè)位置上插入元素的概率，即，i=0,1,…,n（長(zhǎng)度為n的線性表具有n+1個(gè)插入位置）。設(shè)Eins為在長(zhǎng)度為n的線性表中插入一元素時(shí)所需的元素的平均移動(dòng)次數(shù)，則

所以算法的平均時(shí)間復(fù)雜度為O(n)。

3.刪除運(yùn)算

刪除l中的第i個(gè)數(shù)據(jù)元素（DelList(l,i)），使得線性表(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1, ai＋1,…,an)，即改變了線性表中元素之間的關(guān)系，使<ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>，同時(shí)表長(zhǎng)減1。同樣地，為了反映數(shù)據(jù)元素之間邏輯關(guān)系的變化，需將數(shù)據(jù)元素ai,ai-1,…,an依次向前移動(dòng)一個(gè)單元，其實(shí)現(xiàn)過程如圖2-3所示。相應(yīng)的算法描述如下。

void DelList(SeqList *l,int i)
/*在順序表l中刪除第i（i應(yīng)視做數(shù)組的下標(biāo)）個(gè)數(shù)據(jù)元素*/
{
     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個(gè)數(shù)據(jù)元素后面的元素依次前移*/
     l->listlength--;
} /* DelList */

與插入算法類似，Edel為在長(zhǎng)度為n的表中刪除一元素時(shí)所需的元素的平均移動(dòng)次數(shù)，則

其中，Pi為等概率情況下刪除第i個(gè)元素的概率。所以算法的平均時(shí)間復(fù)雜度為O(n)。

【例2-1】已知la與lb是兩個(gè)遞增有序的順序表，要求寫一算法，構(gòu)造遞增有序表lc，表中的元素是由la與lb合并后得到的。

順序表lc中的元素是復(fù)制la與lb中的元素得到的。當(dāng)la與lb中都有元素時(shí)，從第一個(gè)元素起，逐對(duì)進(jìn)行比較，將小的復(fù)制到lc，直到將其中一個(gè)表的全部元素都復(fù)制到lc。再將另一表中剩余的元素也復(fù)制到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中的剩余元素復(fù)制到lc*/
   {  lc->elem[k]=la.elem[i];
         ++k;++i;
   }
   while (j<=lb.listlength) /*將lb中的剩余元素復(fù)制到lc*/
   {  lc->elem[k]=lb.elem[j];
         ++k;++j;
   }
   lc->listlength=la.listlength+lb.listlength;
｝