1、線性表簡介

在程序中，經(jīng)常需要將一組（通常是同為某個(gè)類型的）數(shù)據(jù)元素作為整體管理和使用。最簡單的解決方案便是將這樣一組元素看成一個(gè)序列，用元素在序列里的位置和順序，表示實(shí)際應(yīng)用中的某種有意義的信息，或者表示數(shù)據(jù)之間的某種關(guān)系。我們將其抽象為線性表。

根據(jù)線性表的實(shí)際存儲(chǔ)方式，分為兩種實(shí)現(xiàn)模型：

• 順序表，將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示。
• 鏈表，將元素存放在通過鏈接構(gòu)造起來的一系列存儲(chǔ)塊中。

2、順序表怎樣存儲(chǔ)

下面我們將著重于順序表。
還記的上一節(jié)的內(nèi)存嗎？
順序表，作為一種存儲(chǔ)結(jié)構(gòu)，他需要在內(nèi)存中申請空間進(jìn)行存儲(chǔ)，而它的特點(diǎn)就是必須要連續(xù)存儲(chǔ)，也就是要拿出連號(hào)的‘柜子’進(jìn)行存儲(chǔ)，那么雖然內(nèi)存有很多存儲(chǔ)空間，但在其連續(xù)的空間內(nèi)，可能有局部內(nèi)存已經(jīng)被其他東西占用，

假設(shè)我們拿出了03、04兩個(gè)柜子進(jìn)行存儲(chǔ)，但是我們現(xiàn)在需要三個(gè)柜子來存儲(chǔ)，而05的位置已經(jīng)被占用，這時(shí)候，我們就要吧03、04柜子里的東西重新拿出來，再找一個(gè)三個(gè)連續(xù)的柜子放進(jìn)去，比如06~08的位置，此時(shí)，如果我們又要存儲(chǔ)別的東西，就又要重新找滿足要求的連續(xù)的“柜子”。這就是順序表的存儲(chǔ)特性，不過為了避免經(jīng)?！鞍徇w”，采用一中策略：提前開辟更多的位置來等待你存儲(chǔ)，如果滿了，那么就再去新開辟二倍的空間，滿了再二倍，當(dāng)然也會(huì)有個(gè)界限，否則就造成空間浪費(fèi)了。

3、從0開始

li = [1, 2, 3, 4]
假設(shè)我們在一塊連續(xù)的位置存儲(chǔ)了數(shù)組li，那么取li[0]的時(shí)候, 就是先找到li所在的地址Ox03, 然后從這個(gè)地址讀取4個(gè)字節(jié)(因?yàn)槭钦?, 如果是取li[3], 也是先找到li所在的地址Ox03,再往后跳過三個(gè)數(shù)據(jù)類型字節(jié)的位置, li[3] = Ox03 + 3*4Btye所以li[0]的**0 **的意思就是偏移量,所以數(shù)據(jù)是從零開始。

4、元素外置的順序表

上面介紹的是基本的順序表，就是存儲(chǔ)的空間里都是類型相同的數(shù)據(jù)，那么你可能會(huì)問了，明明在Python中數(shù)組里存儲(chǔ)的可以是任何類型的數(shù)據(jù)。這時(shí)候，我們就要寄出元素外置的順序表了，這是個(gè)什么意思呢？其實(shí)這種存儲(chǔ)不同類型數(shù)據(jù)的數(shù)組，其本身并沒有把那些數(shù)據(jù)存儲(chǔ)在自己的空間里，而是把這些數(shù)據(jù)對應(yīng)的地址存在了自己的空間里，這樣自己空間里還是類型一致的數(shù)據(jù)。

假如還是上面的那塊地址，

這次在這里存儲(chǔ)的是四個(gè)內(nèi)存地址，而這些地址又對應(yīng)相應(yīng)的數(shù)據(jù)。

這時(shí)候我們在訪問li[0]的時(shí)候?qū)⑦M(jìn)行已下操作:
首先找到li所對應(yīng)的地址Ox03, 再通過這個(gè)地址存儲(chǔ)的地址Ox10 找到數(shù)據(jù)'abb', 這種存儲(chǔ)地址的地址空間連續(xù)稱作數(shù)據(jù)外置表, 可以通過列表存儲(chǔ)不同類型的數(shù)據(jù)。

5、順序表的實(shí)現(xiàn)

這里Python已經(jīng)內(nèi)置，但我們來考慮自己如何實(shí)現(xiàn)順序表。

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

除了需要數(shù)據(jù)部分, 還需要表頭信息用來存儲(chǔ)表的大小以及已存儲(chǔ)數(shù)據(jù)量。
a> 一體式結(jié)構(gòu)：把表頭信息和數(shù)據(jù)區(qū)連續(xù)存儲(chǔ)
b> 分離式結(jié)構(gòu)：把表的大小與已存儲(chǔ)量以及存儲(chǔ)地址放到一個(gè)地方, 地址指向另一塊存儲(chǔ)位置

優(yōu)劣問題,數(shù)據(jù)存儲(chǔ)問題:

連續(xù): 讀取方便, 當(dāng)存儲(chǔ)數(shù)據(jù)超過預(yù)先支配的大小, 那就需要重新申請一塊連續(xù)空間, 進(jìn)行數(shù)據(jù)搬遷, 釋放老的空間, 表頭也需要改變, 起始地址就會(huì)改變。

分離: 間接讀取,當(dāng)存儲(chǔ)數(shù)據(jù)超過預(yù)先支配的大小, 只需要改變存儲(chǔ)的地址, 并不需要改變表頭的位置。

當(dāng)存儲(chǔ)空間不足的時(shí)候，擴(kuò)充帶來的問題: 擴(kuò)充預(yù)留多少大小。
下面有兩種解決策略。
兩種策略:
1> 每次申請擴(kuò)充固定數(shù)目的位置, 每次都擴(kuò)充10個(gè)空間,
特點(diǎn): 節(jié)省空間, 但是擴(kuò)充操作頻繁, 操作次數(shù)多
2> 每次申請都擴(kuò)充倍數(shù), 4->8->16->32
特點(diǎn): 空間換取時(shí)間

允許擴(kuò)充的順序表叫做動(dòng)態(tài)順序表, 位置不夠了可以取擴(kuò)充位置

6、順序表操作:

增加元素:

a>表尾端加入元素
b>非保序的元素插入
c>保序的元素插入

a>O(1)
b>直接把需求位置的數(shù)據(jù)放到尾端, 再把數(shù)據(jù)放入改位置,不常見, O(1)
c>O(n), 需要把所有數(shù)據(jù)往后移一位, 才能在空位加入元素

刪除元素:
a>刪除表尾元素 O(1)
b>非保序元素刪除 O(1) 刪除元素, 把末尾填入空位
c>保序刪除 O(n) 刪除元素在把每位上移

7、Python中的順序表：list和tuple

a>按下表位置索引：復(fù)雜度O(1)
b>允許加入任意元素, 表對象標(biāo)識(shí)(id地址)不變：表頭和數(shù)據(jù)區(qū)分離式存儲(chǔ)
c>可以存儲(chǔ)不同類型的數(shù)據(jù)：元素外置方式

擴(kuò)充策略:
建立空表(或很小的表), 系統(tǒng)分配一塊能容納8個(gè)元素的存儲(chǔ)區(qū), 進(jìn)行插入時(shí), 如果存儲(chǔ)器滿了, 存儲(chǔ)區(qū)就換一塊4倍大的存儲(chǔ)區(qū), 但是此時(shí)表已經(jīng)很大(閥值50000),則改變策略,采用加一倍的方法, 避免出現(xiàn)過多的空閑位置

小結(jié)

1、順序表屬于線性表的一種。
2、從0開始。
3、存儲(chǔ)同樣類型的數(shù)據(jù)。不同數(shù)據(jù)是如何存儲(chǔ)的？
4、怎么構(gòu)造的？都有什么優(yōu)劣？
5、添加和刪除元素的復(fù)雜度？