Python数据结构与算法（第二天）
12.基本順序表與元素外圍順序表
int a=1，整型，4個字節（32位）? ? 0000 0000 0000 0000 0000 0000 0000 0001
lnt =7，2100，390
?
13.內存、類型本質、連續存儲
?順序表的基本形式
14.順序表的一體式結構與分離式結構
順序表的結構
一個順序表的完整信息包括兩部分，一部分是表中的元素集合，另一部分是為實現正確操作而需記錄的信息，即有關表的整體情況的信息，這部分信息主要包括元素存儲區的容量和當前表中已有的元素個數兩項。
順序表的兩種基本實現方式
?圖a為一體式結構，存儲表信息的單元與元素存儲區以連續的方式安排在一塊存儲區里，兩部分數據的整體形成一個完整的順序表對象。
一體式結構整體性強，易于管理。但是由于數據元素存儲區域是表對象的一部分，順序表創建后，元素存儲區就固定了。
圖b為分離式結構，表對象里只保存與整個表有關的信息（即容量和元素個數），實際數據元素存放在另一個獨立的元素存儲區里，通過鏈接與基本表對象關聯。
15.順序表數據區替換與擴充
元素存儲區替換
一體式結構由于順序表信息區與數據區連續存儲在一起，所以若想更換數據區，則只能整體搬遷，即整個順序表對象（指存儲順序表的結構信息的區域）改變了。
分離式結構若想更換數據區，只需將表信息區中的數據區鏈接地址更新即可，而該順序表對象不變。
元素存儲區擴充
擴充對于一體式，表頭、內存都要改地址，擴充對于分體式，表頭不改地址，內存要改地址。采用分離式結構的順序表，若將數據區更換為存儲空間更大的區域，則可以在不改變表對象的前提下對其數據存儲區進行了擴充，所有使用這個表的地方都不必修改。只要程序的運行環境（計算機系統）還有空閑存儲，這種表結構就不會因為滿了而導致操作無法進行。人們把采用這種技術實現的順序表稱為動態順序表，因為其容量可以在使用中動態變化。
擴充的兩種策略
（1）每次擴充增加固定數目的存儲位置，如每次擴充增加10個元素位置，這種策略可稱為線性增長。
特點：節省空間，但是擴充操作頻繁，操作次數多。
（2）每次擴充容量加倍，如每次擴充增加一倍存儲空間。
特點：減少了擴充操作的執行次數，但可能會浪費空間資源。以空間換時間，推薦的方式。
16.順序表添加與刪除元素_Python列表的實現
增加元素
如圖所示，為順序表增加新元素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的性質類似。
list的基本實現技術
Python標準類型list就是一種元素個數可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：
（1）基于下標（位置）的高效元素訪問和更新，時間復雜度應該是O(1)；為滿足該特征，應該采用順序表技術，表中元素保存在一塊連續的存儲區中。
（2）允許任意加入元素，而且在不斷加入元素的過程中，表對象的標識（函數id得到的值）不變。為滿足該特征，就必須能更換元素存儲區，并且為保證更換存儲區時list對象的標識id不變，只能采用分離式實現技術。
在Python的官方實現中，list就是一種采用分離式技術實現的動態順序表。這就是為什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。
在Python的官方實現中，list實現采用了如下的策略：在建立空表（或者很小的表）時，系統分配一塊能容納8個元素的存儲區；在執行插入操作（insert或append）時，如果元素存儲區滿就換一塊4倍大的存儲區。但如果此時的表已經很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現過多空閑的存儲位置。
總結
以上是生活随笔為你收集整理的Python数据结构与算法（第二天）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python基础知识（第十一天）
- 下一篇： Python数据结构与算法（第三天）