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)。