一、什麼是順序表
将元素順序的存放在一塊連續的存儲區中，元素間的順序關系由它們的存儲順序自然表示。
（一）順序表的形式
順序表由于存儲的元素類型不同，分成：
- 基本順序表
- 元素外置順序表
為什麼要這樣分呢？因為元素類型不同占用的每個單元大小不同。
1、基本順序表
資料元素本身連續存儲，每個元素所占的存儲單元大小固定相同，元素的下标是其邏輯位址，而元素存儲的實體位址（實際記憶體位址）可以通過存儲區的起始位址Loc (e0)加上邏輯位址（第i個元素）與存儲單元大小（c）的乘積計算而得：
Loc(ei) = Loc(e0) + c*i
比如，清單li=[23,56,100,200]的存儲： 
一個整數占4個位元組，一個位元組占32位，是以4Byte=32位，上面4個整數在記憶體中以順序表的形式存儲，通過存儲區的起始位置0x13可以找到後面的任意位置的元素，是以通路指定元素時無需從頭周遊，通過計算便可獲得對應位址，其時間複雜度為O(1)。
2、元素外置順序表
針對元素大小不統一，比如li = [15,"abc",56,12.32]，裡面整型、字元串、浮點型占用的位元組不同，但是順序表是存儲的是連續的機關大小相同的元素，此時考慮使用元素外置的順序表：
- 右邊存儲的是具體的資料，因為元素種類不同，是以在記憶體中不一定是連續的
- 左邊順序表中存儲的是右邊資料的記憶體位址
- 因為記憶體位址元素可以申請一塊連續的空間來存，并且元素種類、大小一樣
這樣通過元素連結的存儲位置，而後順着連結找到實際存儲的資料元素。
（二）順序表的結構與實作
1、順序表的結構
一個完整的順序表包含兩部分内容：
- 元資訊（容量和元素個數）
- 元素集合
2、順序表的兩種基本實作方式
順序表中有兩種基本實作方式：一體式結構、分離式結構。
- 一體式結構
存儲表資訊的單元與元素存儲區以連續的方式安排在一塊存儲區裡，兩部分資料的整體形成一個完整的順序表對象。
- 分離式結構
表對象裡隻儲存與整個表有關的資訊（即容量和元素個數），實際資料元素存放在另一個獨立的元素存儲區裡，通過連結與基本表對象關聯。
一體式結構由于順序表元資訊區與資料區是在一起的，是以如果想更換資料區隻能整體搬遷，這樣的話整個順序表對象（指存儲順序表的元資訊的區域）就改變了；分離式結構若想更換資料區，隻需要将元資訊中的資料區的連結位址更新即可，順序表表對象不用變化。
另外，如果對順序表中的資料區進行擴充有兩種政策：
- 線性增長
每次增加強定數量的存儲位置，比如每次增加20個存儲位置；該方式節約空間，但是操作頻繁
- 倍增
每次在原先容量的基礎上進行成本增長，比如：8-->16,16-->32，該方式減少了操作次數，但是可能會浪費空間，以空間換時間。
二、Python中的順序表
Python中的list和tuple采用的就是順序表的實作技術，隻不過tuple是不可變類型，即是不可變的順序表。
list是一種采用分離式技術的動态順序表，list的實作采用了如下的政策：
在建立空表時，系統配置設定一塊容内8個元素的存儲區，在執行插入（insert/append）操作，如果存儲區滿就換一塊4倍大的空間；但如果此時的表已經很大，則改變政策，采用加一倍的方法。引入這種改變政策的方式，是為了避免出現過多空閑的存儲位置。
作者：iveBoy
出處：http://www.cnblogs.com/shenjianping/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須在文章頁面給出原文連接配接，否則保留追究法律責任的權利。