***** 在學習順序表之前,讓我們來思考幾個問題 - 列表的下標為什么從零開始 - 為什么列表append比insert快 - 列表append之后,id值為什么不變,也可以說內存地址不變 在程序中，經常需要將一組（通常是同為某個類型的）數據元素作為整體管理和使用，需要創建這種元素組，用變量記錄它們，傳進傳出函數等。一組數據中包含的元素個數可能發生變化（可以增加或刪除元素）。 <br>對于這種需求，最簡單的解決方案便是將這樣一組元素看成一個序列，用元素在序列里的位置和順序，表示實際應用中的某種有意義的信息，或者表示數據之間的某種關系。 <br>這樣的一組序列元素的組織形式，我們可以將其抽象為**線性表**。一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關系。線性表是最基本的數據結構之一，在實際程序中應用非常廣泛，它還經常被用作更復雜的數據結構的實現基礎。 根據線性表的實際存儲方式，分為兩種實現模型： - **順序表**，將元素順序地存放在一塊連續的存儲區里，元素間的順序關系由它們的存儲順序自然表示。 - **鏈表**，將元素存放在通過鏈接構造起來的一系列存儲塊中。 ## 順序表的基本形式  圖a表示的是順序表的基本形式，數據元素本身連續存儲，每個元素所占的存儲單元大小固定相同，元素的下標是其邏輯地址，而元素存儲的物理地址（實際內存地址）可以通過存儲區的起始地址Loc (e0)加上邏輯地址（第i個元素）與存儲單元大小（c）的乘積計算而得，即： **Loc(ei) = Loc(e0) + c\*i** 故，訪問指定元素時無需從頭遍歷，通過計算便可獲得對應地址，其時間復雜度為O(1)。 如果元素的大小不統一，則須采用圖b的元素外置的形式，將實際數據元素另行存儲，而順序表中各單元位置保存對應元素的地址信息（即鏈接）。由于每個鏈接所需的存儲量相同，通過上述公式，可以計算出元素鏈接的存儲位置，而后順著鏈接找到實際存儲的數據元素。**注意，圖b中的c不再是數據元素的大小，而是存儲一個鏈接地址所需的存儲量，這個量通常很小。** 圖b這樣的順序表也被稱為對實際數據的索引，這是最簡單的索引結構。 ## 數組要從0開始編號，而不是從1開始呢？ 從數組存儲的內存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。前面也講到，如果用 a 來表示數組的首地址，a[0] 就是偏移為 0 的位置，也就是首地址，a[k] 就表示偏移 k 個 type_size 的位置，所以計算 a[k] 的內存地址只需要用這個公式： ``` a[k]_address = base_address + k * type_size ``` 但是，如果數組從 1 開始計數，那我們計算數組元素 a[k] 的內存地址就會變為： ``` a[k]_address = base_address + (k-1)*type_size ``` 對比兩個公式，我們不難發現，從 1 開始編號，每次隨機訪問數組元素都多了一次減法運算，對于 CPU 來說，就是多了一次減法指令。數組作為非常基礎的數據結構，通過下標隨機訪問數組元素又是其非常基礎的編程操作，效率的優化就要盡可能做到極致。所以為了減少一次減法操作，數組選擇了從 0 開始編號，而不是從 1 開始。 ## 基本順序表與元素外圍順序表  ## 順序表的結構  一個順序表的完整信息包括兩部分，一部分是表中的元素集合，另一部分是為實現正確操作而需記錄的信息，即有關表的整體情況的信息，這部分信息主要包括元素存儲區的**容量**和當前表中已有的**元素個數**兩項。 ## 順序表的兩種基本實現方式  圖a為一體式結構，存儲表信息的單元與元素存儲區以連續的方式安排在一塊存儲區里，兩部分數據的整體形成一個完整的順序表對象。 一體式結構整體性強，易于管理。但是由于數據元素存儲區域是表對象的一部分，順序表創建后，元素存儲區就固定了。 圖b為分離式結構，表對象里只保存與整個表有關的信息（即容量和元素個數），實際數據元素存放在另一個獨立的元素存儲區里，通過鏈接與基本表對象關聯。 ## 元素存儲區替換 一體式結構由于順序表信息區與數據區連續存儲在一起，所以若想更換數據區，則只能整體搬遷，即整個順序表對象（指存儲順序表的結構信息的區域）改變了。 分離式結構若想更換數據區，只需將表信息區中的數據區鏈接地址更新即可，而該順序表對象不變。 ## 元素存儲區擴充 采用分離式結構的順序表，若將數據區更換為存儲空間更大的區域，則可以在不改變表對象的前提下對其數據存儲區進行了擴充，所有使用這個表的地方都不必修改。只要程序的運行環境（計算機系統）還有空閑存儲，這種表結構就不會因為滿了而導致操作無法進行。人們把采用這種技術實現的順序表稱為動態順序表，因為其容量可以在使用中動態變化。 擴充的兩種策略 - 每次擴充增加固定數目的存儲位置,如每次擴充增加10個元素位置,這種策略可稱為線性增長。 - 特點:節省空間，但是擴充操作頻繁,操作次數多。 - 每次擴充容量加倍,如每次擴充增加一倍存儲空間。 - 特點:減少了擴充操作的執行次數,但可能會浪費空間資源。以空間換時間,推薦的方式。 ## 順序表的操作 ### 增加元素  a. 尾端加入元素，時間復雜度為O(1) b. 非保序的加入元素（不常見），時間復雜度為O(1) c. 保序的元素加入，時間復雜度為O(n) # 保序是插入元素,原先的順序不變 ### 刪除元素  a. 刪除表尾元素，時間復雜度為O(1) b. 非保序的元素刪除（不常見），時間復雜度為O(1) c. 保序的元素刪除，時間復雜度為O(n) ## Python中的順序表 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），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現過多空閑的存儲位置。