線性表

定義

????????線性表是具有相同數(shù)據(jù)類型的N（N>=0）個元素的有限序列，其中N為表長，當N=0時線性表是一張空表。

????????線性表的邏輯特征：每個非空的線性表都有一個表頭元素和表尾元素，中間的每個元素有且僅有一個直接前驅(qū)，有且僅有一個直接后繼。

????????線性表是一種邏輯結(jié)構(gòu)，表示元素之間一對一相鄰的關(guān)系。順序表（數(shù)組）和鏈表是指存儲結(jié)構(gòu)，兩者屬于不同的層面。

線性表的基本操作

????????基本操作的實現(xiàn)取決于采用哪種存儲結(jié)構(gòu)，存儲結(jié)構(gòu)不同，算法實現(xiàn)也不同，比如底層采用數(shù)據(jù)實現(xiàn)和鏈表實現(xiàn)，對應的代碼不一樣，但在上層實現(xiàn)算法邏輯時不關(guān)心底層具體實現(xiàn)，上述方法名可以直接作為偽代碼使用。

線性表的順序表示

（1）順序表定義

# define MaxSize 50? // 定義線性表的最大長度typedef int ElemType;typedef struct{ElemType? data[MaxSize] ;??? // 順序表的元素int?? length ;????????????????? // 順序表的當前長度} SqList;?????????????????????????? ?// 別名

????????線性表的順序存儲又稱為順序表。它是用一組地址連續(xù)的存儲單元，依次存儲線性表中的數(shù)據(jù)元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰。

????????順序表可以是靜態(tài)分配的數(shù)組，也可以是動態(tài)分配的數(shù)組。如果采用動態(tài)分配，就是在使用時按照實際大小申請空間。

#define InitSize 100typedef struct {ElemType?? *data ;??????? // 指示動態(tài)分配數(shù)組的指針int? MaxSize , length ;? // 數(shù)組的最大容量和當前個數(shù)}SeqList;????????????????????? // 動態(tài)分配數(shù)組順序表的類型定義C語言初始化：L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);C++初始化： ?L.data = new ElemType[InitSize] ;

注意：動態(tài)分配并不是鏈式存儲，同樣還是屬于順序存儲結(jié)構(gòu)，其物理結(jié)構(gòu)沒有變化，依然是隨機存取方式，只是分配的空間大小可以在運行時決定。

（2）順序表的特點

順序表最主要的特點是：隨機訪問，即通過首地址和元素序號可以在O(1)時間內(nèi)找到指定的元素

順序表的存儲密度高，每個結(jié)點只存儲數(shù)據(jù)元素，相對于鏈表來說沒有指針域。

順序表邏輯上相鄰的元素物理上也相鄰，所以插入和刪除操作需要移動元素。

順序表基本操作

有效性校驗、邊界檢查：

如下面代碼的“判斷 i 的范圍是否有效”。在函數(shù)體前面，主代碼運行之前，對數(shù)據(jù)的有效性進行檢查，比如是否為空、是否越界等。體現(xiàn)代碼的健壯性，完整性，在考試時如果能多這一步并加上注釋，是加分項。

（1）順序表的插入代碼實現(xiàn)

// 本算法實現(xiàn)將元素 e 插入到順序表 L 中第 i 個位置
bool? ListInsert( SqList?? &L? , int i , ElemType e){if ( i < 1 || i > L.length +1 ){ //? 判斷 i 的范圍是否有效return? false;?}if ( L.length >= MaxSize ){????? ?// 當前存儲空間已滿，不能插入return? false;}//有效性檢查for( int j = L.length ; j >= i : j--){????? //將 第 i 個元素及之后的元素后移L.data[ j ] = L.data[ j-1 ] ;}L.data[ i -1 ] = e; ?// 在位置 i 處放入 eL.length++;?????????? // 線性表的長度 加 1return true;
}

插入算法的平均時間復雜度為O(N)。

最好情況：在表尾插入（即 i = n + 1 ），元素移動語句將不執(zhí)行，時間復雜度為 O(1) 。

最壞情況：在表頭插入（即 i = 1 ），元素移動語句將執(zhí)行 n 次，時間復雜度為 O( n ) 。

（2）順序表的刪除操作代碼

// 本算法實現(xiàn)刪除順序表 L 中第 i 個位置的元素
bool? ListDelete( SqList? &L , int i , int? &e ) {if( i < 1 || i > L.length ){???????????????????? // 判斷 i 的范圍是否有效return false ;}e = L.data[ i -1 ] ;???????????????????????????? // 將被刪除的元素賦值給 efor( int j = i ; j < L.length ; j++ ){????????   // 將第 i 個位置之后的元素前移L.data[ j -1 ] = L.data[ j ]}L.length--;????????????????????????????????????? // 線性表的長度減 1return true;
}

最好情況：刪除表尾元素（即 i = n），無須移動元素，時間復雜度為 O(1)。

最壞情況：刪除表頭元素（即 i = 1），需要移動一個元素外的所有元素，時間復雜度為 O(n) 。

同理刪除操作的平均時間復雜度也是O(N)

（3）按值查找，返回位序。

//本算法實現(xiàn)查找順序表中值為 e 的元素，如果查找成功，返回元素位序，否則返回 0
int? LocateElem( SqList? L? , ElemType e){
int i ;
for( i = 0 ; i < L.length ; i++){if( L.data[ i ] == e){return? i +1 ;???? // 下標為 i 的元素值等于 e ，返回其位序 i + 1}return? 0;?????????????? //退出循環(huán)，說明查找失敗
}

最壞情況：查找的元素在表尾（或不存在）時，需要比較 n 次，時間復雜度為 O(n)。

因此，線性表按值查找算法的平均時間復雜度為 O(n) 。

（4）按下標查找、隨機訪問。

給定下標之后（或給定取第幾個元素）可以直接通過下標訪問l.data[i]，l.data[i-1]；因此隨機訪問的時間復雜度為O(1)。

下一篇文章介紹順序表的鏈式表示