什麼是Python中的順序表

1、順序表介紹

順序表是最簡單的一種線性結構，邏輯上相鄰的數據在計算機內的存儲位置也是相鄰的，可以快速定位第幾個元素，中間不允許有空，所以插入、刪除時需要移動大量元素。順序表可以分配一段連續的存儲空間Maxsize，用elem記錄基地址，用length記錄實際的元素個數，即順序表的長度

上圖1表示的是順序表的基本形式，數據元素本身連續存儲，每個元素所佔的存儲單元大小固定相同，元素的下標是其邏輯地址，而元素存儲的物理地址（實際內存地址）可以通過存儲區的起始地址Loc (e0)加上邏輯地址（第i個元素）與存儲單元大小（c）的乘積計算而得，即：Loc(element i) = Loc(e0) + c*i

所以，訪問指定元素時無需從頭遍歷，通過計算便可獲得對應地址，其時間複雜度為O(1)。

如果元素的大小不統一，則須採用圖2的元素外置的形式，將實際數據元素另行存儲，而順序表中各單元位置保存對應元素的地址信息（即鏈接）。由於每個鏈接所需的存儲量相同，通過上述公式，可以計算出元素鏈接的存儲位置，而後順著鏈接找到實際存儲的數據元素。注意，圖2中的c不再是數據元素的大小，而是存儲一個鏈接地址所需的存儲量，這個量通常很小。

圖2這樣的順序表也被稱為對實際數據的索引，這是最簡單的索引結構。

2、順序表的結構

一個順序表的完整信息包括兩部分，一部分是表中的元素集合，另一部分是為實現正確操作而需記錄的信息，即有關表的整體情況的信息，這部分信息主要包括元素存儲區的容量和當前表中已有的元素個數兩項。

3、順序表的兩種基本實現方式

1為一體式結構，存儲表信息的單元與元素存儲區以連續的方式安排在一塊存儲區裡，兩部分數據的整體形成一個完整的順序表對象。一體式結構整體性強，易於管理。但是由於數據元素存儲區域是表對象的一部分，順序表創建後，元素存儲區就固定了。

2為分離式結構，表對象裡只保存與整個表有關的信息（即容量和元素個數），實際數據元素存放在另一個獨立的元素存儲區裡，通過鏈接與基本表對象關聯。

4、元素存儲區替換

一體式結構由於順序表信息區與數據區連續存儲在一起，所以若想更換數據區，則只能整體搬遷，即整個順序表對象（指存儲順序表的結構信息的區域）改變了。分離式結構若想更換數據區，只需將表信息區中的數據區鏈接地址更新即可，而該順序表對象不變。

5、元素存儲區擴充

採用分離式結構的順序表，若將數據區更換為存儲空間更大的區域，則可以在不改變表對象的前提下對其數據存儲區進行了擴充，所有使用這個表的地方都不必修改。只要程序的運行環境（計算機系統）還有空閒存儲，這種表結構就不會因為滿了而導致操作無法進行。人們把採用這種技術實現的順序表稱為動態順序表，因為其容量可以在使用中動態變化。

擴充的兩種策略

每次擴充增加固定數目的存儲位置，如每次擴充增加10個元素位置，這種策略可稱為線性增長。

特點：節省空間，但是擴充操作頻繁，操作次數多。

每次擴充容量加倍，如每次擴充增加一倍存儲空間。

特點：減少了擴充操作的執行次數，但可能會浪費空間資源。以空間換時間，推薦的方式。

6、順序表的增刪改查操作的Python代碼實現

 # 創建順序表class Sequence_Table(): # 初始化 def __init__(self): self.date = [None]*100 self.length = 0 # 判斷是否已經滿了 def isFull(self): if self.length>100: print("該順序表已滿，無法添加元素") return 1 else: return 0 # 按下表索引查找 def selectByIndex(self,index): if index>=0 and index<=self.length-1: return self.date[index] else: print("你輸入的下標不對，請重新輸入 ") return 0 # 按元素查下標 def selectByNum(self,num): isCOntain= 0 for i in range(0,self.length): if self.date[i] == num: isCOntain= 1 print("你要查找的元素下標是%d "%i) if isCOntain== 0: print("沒有找你你要的數據") # 追加數據 def addNum(self,num): if self.isFull() == 0: self.date[self.length] = num self.length += 1 # 打印順序表 def printAllNum(self): for i in range(self.length): print("a[%s]=%s"%(i,self.date[i]),end=" ") print(" ") # 按下標插入數據 def insertNumByIndex(self,num,index): if indexself.length: return 0 self.length += 1 for i in range(self.length-1,index,-1): temp = self.date[i] self.date[i] = self.date[i-1] self.date[i-1] = temp self.date[index] = num return 1 # 按下標刪除數據 def delectNumByIndex(self,index): if self.length <= 0: print("該順序表內沒有數據，不用刪除") for i in range(index,self.length-1): temp = self.date[i] self.date[i] = self.date[i + 1] self.date[i + 1] = temp self.date[self.length-1] = 0 self.length -= 1def main(): # 創建順序表對象 seq_t = Sequence_Table() # 插入三個元素 seq_t.addNum(1) seq_t.addNum(2) seq_t.addNum(3) # 打印驗證 seq_t.printAllNum() # 按照索引查找 num = seq_t.selectByIndex(2) print("你要查找的數據是%d " % num) # 按照索引插入數據 seq_t.insertNumByIndex(4, 1) seq_t.printAllNum() # 按照數字查下標 seq_t.selectByNum(4) #刪除數據 seq_t.delectNumByIndex(1) seq_t.printAllNum() if __name__ == "__main__": main()

運行結果為：

a[0]=1 a[1]=2 a[2]=3
你要查找的數據是3
a[0]=1 a[1]=4 a[2]=2 a[3]=3
你要查找的元素下標是1
a[0]=1 a[1]=2 a[2]=3

7、順序表的增刪改查操作的C語言代碼實現

 #include// 1、定義順序表的儲存結構 typedef struct { //用數組存儲線性表中的元素 int data[100]; // 順序表中的元素個數 int length; }Sequence_table,*p_Sequence_table; // 2、順序表的初始化， void initSequenceTable(p_Sequence_table T) { // 判斷傳過來的表是否為空，為空直接退出 if (T == NULL) { return; } // 設置默認長度為0 T->length = 0; } // 3、求順序表的長度 int lengthOfSequenceTable(p_Sequence_table T) { if (T==NULL) { return 0; } return T->length; } // 4、判斷順序表是否已滿 int isFull(p_Sequence_table T) { if (T->length>=100) { printf("該順序表已經裝滿，無法再添加元素"); return 1; } return 0; } // 5、按序號查找 int selectSequenceTableByIndex(p_Sequence_table T,int index) { if (index>=0&&indexlength-1) { return T->data[index]; } printf("你輸入的序號不對，請重新輸入 "); return 0; } // 6、按內容查找是否存在 void selectSequenceTableByNum(p_Sequence_table T,int num) { int isCOntain= 0; for (int i=0; ilength; i++) { if (T->data[i] == num) { isCOntain= 1; printf("你要找的元素的下標是:%d ",i); } } if (isCOntain== 0) { printf("沒有找到你要的數據 "); } } // 7、添加元素（在隊尾添加） void addNumber(p_Sequence_table T,int num) { // 順序表還沒有滿的時候 if (isFull(T) == 0) { T->data[T->length] = num; T->length++; } } // 8、順序表的遍歷 void printAllNumOfSequenceTable(p_Sequence_table T) { for (int i = 0; ilength; i++) { printf("T[%d]=%d ",i,T->data[i]); } printf(" "); } //9、插入操作 int insertNumByIndex(p_Sequence_table T, int num,int index) { if (indexT->length) { return 0; } T->length++; for (int i = T->length-1; i>index; i--) { int temp = T->data[i]; T->data[i] = T->data[i-1]; T->data[i-1] = temp; } T->data[index] = num; return 1; } // 10、刪除元素 void delectNum(p_Sequence_table T,int index) { if (T->length <= 0) { printf("該順序表中沒有數據，不用刪除"); } for (int i = index;ilength-1; i++) { int temp = T->data[i]; T->data[i] = T->data[i+1]; T->data[i+1] = temp; } T->data[T->length-1] = 0; T->length--; } int main(int argc, const char * argv[]) { // 創建順序表的結構體 Sequence_table seq_t; // 初始化 initSequenceTable(&seq_t); // 添加數據 addNumber(&seq_t, 1); addNumber(&seq_t, 2); addNumber(&seq_t, 3); // 打印驗證 printAllNumOfSequenceTable(&seq_t); // 根據索引下標查內容 int num = selectSequenceTableByIndex(&seq_t, 2); printf("你查的數據是:%d ",num); // 插入 insertNumByIndex(&seq_t, 4, 1); printAllNumOfSequenceTable(&seq_t); // 根據內容查下標 selectSequenceTableByNum(&seq_t, 4); // 根據下標刪除數據 delectNum(&seq_t, 1); printAllNumOfSequenceTable(&seq_t); return 0; }

運行結果為：

T[0]=1 T[1]=2 T[2]=3
你查的數據是:3
T[0]=1 T[1]=4 T[2]=2 T[3]=3
你要找的元素的下標是:1
T[0]=1 T[1]=2 T[2]=3

知識點擴展：

Python中的list和tuple兩種類型採用了順序表的實現技術，具有前面討論的順序表的所有性質。

tuple是不可變類型，即不變的順序表，因此不支持改變其內部狀態的任何操作，而其他方面，則與list的性質類似。

list的基本實現技術

Python標準類型list就是一種元素個數可變的線性表，可以加入和刪除元素，並在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特徵：

基於下標（位置）的高效元素訪問和更新，時間複雜度應該是O(1)；

為滿足該特徵，應該採用順序表技術，表中元素保存在一塊連續的存儲區中。

允許任意加入元素，而且在不斷加入元素的過程中，表對象的標識（函數id得到的值）不變。

為滿足該特徵，就必須能更換元素存儲區，並且為保證更換存儲區時list對象的標識id不變，只能採用分離式實現技術。

在Python的官方實現中，list就是一種採用分離式技術實現的動態順序表。這就是為什麼用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

在Python的官方實現中，list實現採用瞭如下的策略：在建立空表（或者很小的表）時，系統分配一塊能容納8個元素的存儲區；在執行插入操作（insert或append）時，如果元素存儲區滿就換一塊4倍大的存儲區。但如果此時的表已經很大（目前的閥值為50000），則改變策略，採用加一倍的方法。引入這種改變策略的方式，是為了避免出現過多空閒的存儲位置。