首先來看「線性表」定義：

線性表(List)：零個或多個數(shù)據元素的有序排列。

關于線性表的基本操作：

• Data：線性表的數(shù)據對象集合為{a1, a2, ……, an}，每個元素的 類型均為 DataType 。其中，除***個元素 a1 外，每一個元素有且只有一個直接前驅元素，除了 ***一個元素 an 外，每一個元素都有且只有一個直接后繼元素。數(shù)據元素之間的關系是一一對應的。
• InitList( *L )：初始化操作，建立一個空的線性表 L 。
• ListEmpty( L )：若線性表為空，返回 true ，否則返回 false 。
• ClearList ( *L )：將線性表清空。
• GetElem( L, i, *e )：將線性表 L 中第 i 個位置的元素值返回給 e 。
• LocateElem( L, e )：在線性表 L 中查找與給定值 e 相等的元素，如果查找成功，返回該元素在表中序號表示成功；否則，返回 0 表示失敗。
• ListInsert( *L, i, e )：在線性表 L 中的第 i 個位置插入新元素 e 。
• ListDelete( *L, i, *e)：刪除線性表 L 中第 i 個位置元素，并用 e 返回其值。
• ListLength( L )：返回線性表 L 的元素個數(shù)。

[[231850]]

關于線性表集合 A(La) 和 B(Lb) 的并集操作：

/* 將所有的在線性表 Lb 中但不在 La 中的數(shù)據元素插入到 La 中 */ 
void union( List *La, List Lb ){ 
   int La_len, Lb_len, i; 
   ElemType e;     /* 聲明與 La 和 Lb 相同的數(shù)據元素 e */ 
   La_len = ListLength( La ); 
   Lb_len = ListLength( Lb );     
   for( i = 0 ; i <= Lb_len ; i++ ){ 
       GetElem( Lb, i, e);     /* 取 Lb 中第 i 個數(shù)據元素賦給 e */ 
       if( !LocateElem( La, e, equal))      /* La 中不存在和 e 相同數(shù)據元素 */ 
           ListInsert( La, ++La_len, e);     /* 插入 */ 
   } 
} 

順序儲存方式

順序儲存方式是在一定的內存空間中，把相同的數(shù)據類型的數(shù)據依次存放在這塊內存空間中。

線性表順序儲存的結構代碼：

#define MAXSEZE 20      /* 存儲空間初始分配量 */ 
typedef int ElemType;       /* ElemType 類型根據實際情況而定，這里假設為 int */ 
typedef struct{ 
   ElemType data[MAXSIZE];     /* 數(shù)組存儲數(shù)據元素，***值為 MAXSEZE */ 
   int length;     /* 線性表當前長度 */ 
}SqList; 

在這里我們發(fā)現(xiàn)描述順序儲存結構需要三個屬性：

• 存儲空間的起始位置：數(shù)組 data，它的存數(shù)位置就是存儲空間的存儲位置。
• 線性表的***儲存容量：數(shù)組長度 MAXSIZE。
• 線性表的當前長度：length。

數(shù)組長度與線性表長度區(qū)別：

數(shù)組的長度是存放線性表的儲存空間的長度，存儲分配后這個量一般是不變的。 線性表的長度是線性表黃總數(shù)據元素的個數(shù)，隨著線性表插入和刪除操作的進行，這個量是變化的。

地址計算方法：

假設每個數(shù)據元素占 c 個存儲單元(LOC 表示獲取存儲位置的函數(shù)。

LOC( a(i+1) ) = LOC( ai ) + c; 

所以對于第 i 個數(shù)據元素 ai 的地址可以由 a1 推算得出：

LOC( ai ) = LOC( a1 ) + (i-1) * c 

順序存儲結構的插入與刪除操作

插入操作：

算法思路：

1. 如果插入位置不合理，拋出異常；
2. 如果線性表長度大于等于數(shù)組長度，則拋出異常或動態(tài)增加容量；
3. 從***一個元素開始向前遍歷到第 i 個位置，分別將他們都像后移動一個位置；
4. 將要插入元素填入位置 i 處；
5. 表長增加 1 。

#define OK 1 
#define ERROR 0 
#define TRUE 1 
#define FALSE 0 
typedef int Status; 
/* Status 是函數(shù)的類型，其值是函數(shù)結果狀態(tài)碼，如 OK 等 */ 
/* 初始條件：順序線性表 L 已存在，1 <= i <= ListLength( L ) */ 
/* 操作結果：在 L 中第 i 個位置之前插入新的數(shù)據元素 e，L 的長度加 1  */ 
Status ListInsert(SqList *L, int i, ElemType e){ 
   int k; 
   if(L.length == MAXSEZE) 
       return ERROR; 
   if(i < 1 || i > L.length + 1) 
       return ERROR; 
   if(i <= L.length){ 
       for(k = L.length - 1; k > i - 1; k--){ 
           L.data[k+1] = L.data[k]; 
       } 
   } 
   L.data[i-1] = e;    /* 將新元素插入 */ 
   L.length++; 
} 

刪除操作：

算法思路：

1. 如果刪除位置不合理，拋出異常；
2. 取出刪除元素；
3. 從刪除元素位置開始遍歷到***一個元素位置，分別將他們向前移動一個位置；
4. 表長減 1 。

/* `` */ 
/* 操作結果：刪除 L 的第 i 個元素，并用 e 返回其值，L 的長度減 1 */ 
Status ListDelete (SqList *L, int i, ElemType *e){ 
   int k; 
   if(L.length == 0)   /* 線性表為空 */ 
       return ERROR; 
   if(i < 1 || i > L.length) 
       return ERROR; 
   *e = L.data[i-1]; 
   if(i < L.length){ 
       for( k = i ; k < L.length ; k++){ 
           L.data[k-1] = l.data[k]; 
       } 
   } 
   L.length--; 
   return OK; 
} 

時間復雜度：

根據上次學習，可以推導出 線性表的順序儲存結構在存，讀數(shù)據時，不管哪個位置時間復雜度都是 O(1)；而插入刪除時時間復雜度都是 O(n)。這就說明，它比較適合元素個數(shù)不太變化，而更多的是存取數(shù)據的應用。當然，它的優(yōu)缺點還不僅這些...

線性表順序存儲結構的優(yōu)缺點：

優(yōu)點：

• 無須為表示表中元素之間的邏輯關系而增加額外的存儲空間
• 可以快速的存取表中任一位置的元素

缺點：

• 插入和刪除操作需要移動大量元素
• 當線性表長度變化較大時，難以確定儲存空間的容量
• 造成存儲空間的“碎片”