1、順序表介紹

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

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

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

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

圖2這樣的順序表也被稱為對實際數(shù)據(jù)的索引，這是最簡單的索引結(jié)構(gòu)。

2、順序表的結(jié)構(gòu)

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

3、順序表的兩種基本實現(xiàn)方式

1為一體式結(jié)構(gòu)，存儲表信息的單元與元素存儲區(qū)以連續(xù)的方式安排在一塊存儲區(qū)里，兩部分?jǐn)?shù)據(jù)的整體形成一個完整的順序表對象。一體式結(jié)構(gòu)整體性強，易于管理。但是由于數(shù)據(jù)元素存儲區(qū)域是表對象的一部分，順序表創(chuàng)建后，元素存儲區(qū)就固定了。

2為分離式結(jié)構(gòu)，表對象里只保存與整個表有關(guān)的信息（即容量和元素個數(shù)），實際數(shù)據(jù)元素存放在另一個獨立的元素存儲區(qū)里，通過鏈接與基本表對象關(guān)聯(lián)。

4、元素存儲區(qū)替換

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

5、元素存儲區(qū)擴充

采用分離式結(jié)構(gòu)的順序表，若將數(shù)據(jù)區(qū)更換為存儲空間更大的區(qū)域，則可以在不改變表對象的前提下對其數(shù)據(jù)存儲區(qū)進行了擴充，所有使用這個表的地方都不必修改。只要程序的運行環(huán)境（計算機系統(tǒng)）還有空閑存儲，這種表結(jié)構(gòu)就不會因為滿了而導(dǎo)致操作無法進行。人們把采用這種技術(shù)實現(xiàn)的順序表稱為動態(tài)順序表，因為其容量可以在使用中動態(tài)變化。

擴充的兩種策略

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

特點：節(jié)省空間，但是擴充操作頻繁，操作次數(shù)多。

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

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

6、順序表的增刪改查操作的Python代碼實現(xiàn)

# 創(chuàng)建順序表class Sequence_Table(): # 初始化 def __init__(self): self.date = [None]*100 self.length = 0 # 判斷是否已經(jīng)滿了 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('你輸入的下標(biāo)不對，請重新輸入n') return 0 # 按元素查下標(biāo) def selectByNum(self,num): isContain = 0 for i in range(0,self.length): if self.date[i] == num: isContain = 1 print('你要查找的元素下標(biāo)是%dn'%i) if isContain == 0: print('沒有找你你要的數(shù)據(jù)') # 追加數(shù)據(jù) 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('n') # 按下標(biāo)插入數(shù)據(jù) def insertNumByIndex(self,num,index): if index<0 or index>self.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 # 按下標(biāo)刪除數(shù)據(jù) def delectNumByIndex(self,index): if self.length <= 0: print('該順序表內(nèi)沒有數(shù)據(jù)，不用刪除') 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(): # 創(chuàng)建順序表對象 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('你要查找的數(shù)據(jù)是%dn' % num) # 按照索引插入數(shù)據(jù) seq_t.insertNumByIndex(4, 1) seq_t.printAllNum() # 按照數(shù)字查下標(biāo) seq_t.selectByNum(4) #刪除數(shù)據(jù) seq_t.delectNumByIndex(1) seq_t.printAllNum() if __name__ == '__main__': main()

運行結(jié)果為：

a[0]=1 a[1]=2 a[2]=3 你要查找的數(shù)據(jù)是3a[0]=1 a[1]=4 a[2]=2 a[3]=3 你要查找的元素下標(biāo)是1a[0]=1 a[1]=2 a[2]=3

7、順序表的增刪改查操作的C語言代碼實現(xiàn)

#include<stdio.h>// 1、定義順序表的儲存結(jié)構(gòu)typedef struct{ //用數(shù)組存儲線性表中的元素 int data[100]; // 順序表中的元素個數(shù) int length;}Sequence_table,*p_Sequence_table;// 2、順序表的初始化，void initSequenceTable(p_Sequence_table T){ // 判斷傳過來的表是否為空，為空直接退出 if (T == NULL) { return; } // 設(shè)置默認長度為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('該順序表已經(jīng)裝滿，無法再添加元素'); return 1; } return 0;}// 5、按序號查找int selectSequenceTableByIndex(p_Sequence_table T,int index){ if (index>=0&&index<=T->length-1) { return T->data[index]; } printf('你輸入的序號不對，請重新輸入n'); return 0;}// 6、按內(nèi)容查找是否存在void selectSequenceTableByNum(p_Sequence_table T,int num){ int isContain = 0; for (int i=0; i<T->length; i++) { if (T->data[i] == num) { isContain = 1; printf('你要找的元素的下標(biāo)是:%dn',i); } } if (isContain == 0) { printf('沒有找到你要的數(shù)據(jù)n'); }}// 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; i<T->length; i++) { printf('T[%d]=%d ',i,T->data[i]); } printf('n');}//9、插入操作int insertNumByIndex(p_Sequence_table T, int num,int index){ if (index<0||index>T->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('該順序表中沒有數(shù)據(jù)，不用刪除'); } for (int i = index;i<T->length-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[]) { // 創(chuàng)建順序表的結(jié)構(gòu)體 Sequence_table seq_t; // 初始化 initSequenceTable(&seq_t); // 添加數(shù)據(jù) addNumber(&seq_t, 1); addNumber(&seq_t, 2); addNumber(&seq_t, 3); // 打印驗證 printAllNumOfSequenceTable(&seq_t); // 根據(jù)索引下標(biāo)查內(nèi)容 int num = selectSequenceTableByIndex(&seq_t, 2); printf('你查的數(shù)據(jù)是:%dn',num); // 插入 insertNumByIndex(&seq_t, 4, 1); printAllNumOfSequenceTable(&seq_t); // 根據(jù)內(nèi)容查下標(biāo) selectSequenceTableByNum(&seq_t, 4); // 根據(jù)下標(biāo)刪除數(shù)據(jù) delectNum(&seq_t, 1); printAllNumOfSequenceTable(&seq_t); return 0;}

運行結(jié)果為：

T[0]=1 T[1]=2 T[2]=3 你查的數(shù)據(jù)是:3T[0]=1 T[1]=4 T[2]=2 T[3]=3 你要找的元素的下標(biāo)是:1T[0]=1 T[1]=2 T[2]=3

知識點擴展：

Python中的list和tuple兩種類型采用了順序表的實現(xiàn)技術(shù)，具有前面討論的順序表的所有性質(zhì)。

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

list的基本實現(xiàn)技術(shù)

Python標(biāo)準(zhǔn)類型list就是一種元素個數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：

基于下標(biāo)（位置）的高效元素訪問和更新，時間復(fù)雜度應(yīng)該是O(1)；

為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲區(qū)中。

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

為滿足該特征，就必須能更換元素存儲區(qū)，并且為保證更換存儲區(qū)時list對象的標(biāo)識id不變，只能采用分離式實現(xiàn)技術(shù)。

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

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

以上就是什么是Python中的順序表的詳細內(nèi)容，更多關(guān)于Python中順序表詳解的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！