線性表（二）——順序存儲結構

線性表的順序存儲結構

構造原理

用一組位址連續的存儲單元依次存儲線性表的資料元素，資料元素之間的邏輯關系通過資料元素的存儲位置直接反映。

記做 ( a1，a2，a3，… … , an )

所謂一個元素的位址是指該元素占用的若幹(連續的)存儲單元的第一個單元的位址。記做LOC(ai)

若假設每個資料元素占用k個存儲單元，并且已知第一個元素的存儲位置LOC(a1)，則有LOC(ai) = LOC(a1)+(i−1)×k

在C語言中，順序存儲結構的定義如下：

#define MaxSize 100
ElemType A[MaxSize];
int n;      

其中，MaxSize表示預先配置設定給線性表的空間大小，n表示表的長度。

基本操作

1、确定元素item在長度為n的線性表A中的位置（位置比下标大1）

int LOCATE( ElemType A[], int n, ElemType item ){ 
   inti;
   for(i=0;i<n;i++){
       if (A[i]==item) 
           return i+1;           /* 查找成功,傳回在表中位置*/
   }
   return -1;                    /*查找失敗,傳回資訊-1 */
 }      

時間複雜度O(n)

2、在長度為n的線性表A的第i個位置上插入一個新的資料元素item

正常情況下需要做的工作：

(1)将第i個元素至第n個元素依次後移一個位置；

(2)将被插入元素插入表的第i個位置；

(3)修改表的長度(表長增1)；

異常情況：

(1)是否表滿？n=MaxSize;

(2)插入位置是否合适？正常位置：1≤i≤n+1)

int INSERTLIST(ElemType A[], int &n, int i, ElemType item ){
     int j;
     if (n == MaxSize ||  i<1 || i>n+1)   //判斷空間滿否、插入位置合适否
         return -1;                                  //插入失敗
     for( j=n-1; j>=i-1; j--)
         A[j+1]=A[j];            /* 元素依次後移一個位置*/
     A[i-1]=item;              /*将item插入表的第i個位置*/
     n++;                         //線性表長度加1   
     return 1;                   /* 插入成功*/
 }      

該算法的時間複雜度是O(n)，如下：

3、删除長度為n的線性表A的第i個資料元素

正常情況下需要做的工作：

(1)将第i+1個元素至第n個元素依次前移一個位置；

(2)修改表的長度(表長減1)。

需要考慮的異常情況：

(1)是否表空？（n=0？）

(2)删除位置是否合适？(正常位置：1≤i≤n)

int DELETELIST( ElemType A[], int &n, int i ){
    int  j;
    if( i<1 || i>n )       //判斷表空和位置是否合适
        retutn -1;
    for( j=i; j<n; j++ )
        A[j−1]=A[j];          /* 元素依次前移一個位置*/
    n--;                   //線性表長度減1
    return 1;                 /* 删除成功*/
}      

該算法的時間複雜度為O(n)

線性表的順序存儲結構的特點