線性表概念

線性表可以看做抽象的數(shù)據(jù)類型?？梢钥醋鲇懈F個元素排列成的列表，這個列表可以包含零個或多個元素。
在一個非空的線性表中存在唯一的首元素和尾元素，除了首元素外其他任意元素都有一個前驅(qū)元素；處尾元素外其他任意元素都有后一個繼元素。

線性表的基本操作：

判空is_empty(self)；長度len(self)；表前插入元素prepend(self, item)；表后插入元素append(self, item)；任意位置插入元素insert(self, elem, i)；刪除第一個元素del_first(self)；刪除最后一個元素del_last(self)；刪除任意元素del(self, i)；查找任意元素search(self, i)；

線性表的實現(xiàn)方式

順序表，鏈接表（鏈表）。順序表是在內(nèi)存中開辟一大塊連續(xù)的空間作為存儲區(qū)；而鏈表則是鏈接一系列的存儲空間來存儲元素

順序表

順序表的兩種布局

順序表的兩種基本形式.png

a中順序表對象的存儲對象類型相同且存儲區(qū)起始位置為l0，表元素地址計算公式為l0+c*i，其中i為存儲對象的大小。對于不同占用不同內(nèi)存大小的存儲對象可以采用b方式。b順序表各單元保存相應元素的引用信息，引用信息的大小是相同的。

基本操作

• 創(chuàng)建
  創(chuàng)建空表時，需要分配一塊元素內(nèi)存，記錄表的容量并將元素計數(shù)設置為0。創(chuàng)建好存儲去后應立即設置表的信息域。

• 加入元素
  順序表增加元素.png

  不需要保留原有的順序，操作時間復雜度為O(1)，保序時間復雜度為O(n)

• 刪除元素
  順序表增加元素.png

  尾部刪除和非保序定位刪除時間復雜度為O(1)，保序定位刪除的時間復雜度為O(n)。

順序表實現(xiàn)方式

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

1. 一體式存儲表的信息與元素存儲區(qū)連續(xù)的排列在一起，整體性強易于管理。表一旦創(chuàng)建存儲區(qū)的大小確定，存儲量滿后需要重新創(chuàng)建一個更大的空間，需要修改原來元素的所有存儲位置。
2. 分離式通過兩個對象實現(xiàn)，創(chuàng)建和管理相對復雜。改變?nèi)萘窟^程：
   • 申請更大的存儲空間
   • 把表中已有的元素復制到新的存儲區(qū)。
   • 用新的元素存儲區(qū)替換原來的元素存儲區(qū)
   • 加入新的元素

存儲區(qū)的擴充策略

1. 固定擴充：操作次數(shù)多節(jié)約空間
2. 加倍擴充：空間換時間

Python中的list和tuple

python中的list和tuple都采用順序表結(jié)構(gòu)。其中tuple是不可變結(jié)構(gòu)不支持內(nèi)部操作。
list采用連續(xù)表（訪問：O(1)時間復雜度，順序不變），分離式技術（更換存儲區(qū)id不變）

總結(jié)

1. 順序表可以實現(xiàn)O(1)時間的元素訪問。
2. 順序表的建立需要提前考慮元素存儲區(qū)的大小，一旦確定了存取塊的大小，可容納單元不會隨著元素的插入/刪除而改變。若存儲塊很大卻只存儲很少的元素會造成存儲空間的浪費。
3. 插入或刪除表元素需要移動表內(nèi)的元素，效率低。