順序表

在程序中，經常需要將一組（通常是同為某個類型的）數據元素作為整體管理和使用，需要創建這種元素組，用變量記錄它們，傳進傳出函數等。一組數據中包含的元素個數可能發生變化（可以增加或刪除元素）。

根據線性表的實際存儲方式，分為兩種實現模型：

順序表，將元素順序地存放在一塊連續的存儲區里，元素間的順序關系由它們的存儲順序自然表示。

鏈表，將元素存放在通過鏈接構造起來的一系列存儲塊中。

順序表的形式

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

Loc(ei) = Loc(e0) + c*i

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

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

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

順序表的兩種實現

圖a為一體式結構，存儲表信息的單元與元素存儲區以連續的方式安排在一塊存儲區里，兩部分數據的整體形成一個完整的順序表對象。

一體式結構整體性強，易于管理。但是由于數據元素存儲區域是表對象的一部分，順序表創建后，元素存儲區就固定了。

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

順序表的操作

添加元素

為順序表增加新元素111的三種方式

a. 尾端加入元素，時間復雜度為O(1)
b. 非保序的加入元素（不常見），時間復雜度為O(1)
c. 保序的元素加入，時間復雜度為O(n)

刪除元素

a. 刪除表尾元素，時間復雜度為O(1)
b. 非保序的元素刪除（不常見），時間復雜度為O(1)
c. 保序的元素刪除，時間復雜度為O(n)

Python中的順序表

Python中的list和tuple兩種類型采用了順序表的實現技術，具有前面討論的順序表的所有性質。
tuple是不可變類型，即不變的順序表，因此不支持改變其內部狀態的任何操作，而其他方面，則與list的性質類似。

總結

以上是生活随笔為你收集整理的Python数据结构与算法(四)--顺序表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。