数据结构与算法笔记（二）—— 顺序表
一、順序表的形式
在程序中，經(jīng)常需要將一組（通常是同為某個類型的）數(shù)據(jù)元素作為整體管理和使用，需要創(chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個數(shù)可能發(fā)生變化（可以增加或刪除元素)。
對于這種需求，最簡單的解決方案便是將這樣一組元素看成一個序列，用元素在序列里的位置和順序，表示實際應(yīng)用中的某種有意義的信息，或者表示數(shù)據(jù)之間的某種關(guān)系。
這樣的一組序列元素的組織形式，我們可以將其抽象為線性表。一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關(guān)系。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)基礎(chǔ)。
根據(jù)線性表的實際存儲方式，分為兩種實現(xiàn)模型:
- 順序表：將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關(guān)系由它們的存儲順序自然表示。
- 鏈表：將元素存放在通過鏈接構(gòu)造起來的一系列存儲塊中。
1.1、順序表的基本形式
圖a表示的是順序表的基本形式，數(shù)據(jù)元素本身連續(xù)存儲，每個元素所占的存儲單元大小固定相同，元素的下標(biāo)是其邏輯地址，而元素存儲的物理地址（實際內(nèi)存地址）可以通過存儲區(qū)的起始地址Loc (e0)加上邏輯地址（第i個元素）與存儲單元大小（c）的乘積計算而得，即：
Loc(ei) = Loc(e0) + c*i
故，訪問指定元素時無需從頭遍歷，通過計算便可獲得對應(yīng)地址，其時間復(fù)雜度為O(1)。
如果元素的大小不統(tǒng)一，則須采用圖b的元素外置的形式，將實際數(shù)據(jù)元素另行存儲，而順序表中各單元位置保存對應(yīng)元素的地址信息（即鏈接）。由于每個鏈接所需的存儲量相同，通過上述公式，可以計算出元素鏈接的存儲位置，而后順著鏈接找到實際存儲的數(shù)據(jù)元素。注意，圖b中的c不再是數(shù)據(jù)元素的大小，而是存儲一個鏈接地址所需的存儲量，這個量通常很小。
圖b這樣的順序表也被稱為對實際數(shù)據(jù)的索引，這是最簡單的索引結(jié)構(gòu)。
二、順序表的結(jié)構(gòu)與實現(xiàn)
2.1、順序表的結(jié)構(gòu)
一個順序表的完整信息包括兩部分，一部分是表中的元素集合，另一部分是為實現(xiàn)正確操作而需記錄的信息，即有關(guān)表的整體情況的信息，這部分信息主要包括元素存儲區(qū)的容量和當(dāng)前表中已有的元素個數(shù)兩項。
2.2、順序表的兩種基本實現(xiàn)方式
圖a為一體式結(jié)構(gòu)，存儲表信息的單元與元素存儲區(qū)以連續(xù)的方式安排在一塊存儲區(qū)里，兩部分?jǐn)?shù)據(jù)的整體形成一個完整的順序表對象。
一體式結(jié)構(gòu)整體性強，易于管理。但是由于數(shù)據(jù)元素存儲區(qū)域是表對象的一部分，順序表創(chuàng)建后，元素存儲區(qū)就固定了。
圖b為分離式結(jié)構(gòu)，表對象里只保存與整個表有關(guān)的信息（即容量和元素個數(shù))，實際數(shù)據(jù)元素存放在另一個獨立的元素存儲區(qū)里，通過鏈接與基本表對象關(guān)聯(lián)。
2.3、元素存儲區(qū)替換
一體式結(jié)構(gòu)由于順序表信息區(qū)與數(shù)據(jù)區(qū)連續(xù)存儲在一起，所以若想更換數(shù)據(jù)區(qū)，則只能整體搬遷，即整個順序表對象(指存儲順序表的結(jié)構(gòu)信息的區(qū)域)改變了。
分離式結(jié)構(gòu)若想更換數(shù)據(jù)區(qū)，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可，而該順序表對象不變。
2.4、元素存儲區(qū)擴(kuò)充
采用分離式結(jié)構(gòu)的順序表，若將數(shù)據(jù)區(qū)更換為存儲空間更大的區(qū)域，則可以在不改變表對象的前提下對其數(shù)據(jù)存儲區(qū)進(jìn)行了擴(kuò)充，所有使用這個表的地方都不必修改。只要程序的運行環(huán)境（計算機系統(tǒng)）還有空閑存儲，這種表結(jié)構(gòu)就不會因為滿了而導(dǎo)致操作無法進(jìn)行。人們把采用這種技術(shù)實現(xiàn)的順序表稱為動態(tài)順序表，因為其容量可以在使用中動態(tài)變化。
擴(kuò)充的兩種策略：
- 每次擴(kuò)充增加固定數(shù)目的存儲位置，如每次擴(kuò)充增加10個元素位置，這種策略可稱為線性增長。
特點：節(jié)省空間，但是擴(kuò)充操作頻繁，操作次數(shù)多。 - 每次擴(kuò)充容量加倍，如每次擴(kuò)充增加一倍存儲空間。
特點：減少了擴(kuò)充操作的執(zhí)行次數(shù)，但可能會浪費空間資源。以空間換時間，推薦的方式。
三、順序表的操作
3.1、增加元素
如圖所示，為順序表增加新元素111的三種方式：
3.2、刪除元素
四、python中的順序表
Python中的 list 和 tuple 兩種類型采用了順序表的實現(xiàn)技術(shù)，具有前面討論的順序表的所有性質(zhì)。
tuple 是不可變類型，即不變的順序表，因此不支持改變其內(nèi)部狀態(tài)的任何操作，而其他方面，則與 list 的性質(zhì)類似。
4.1、list 的基本實現(xiàn)技術(shù)
Python標(biāo)準(zhǔn)類型 list 就是一種元素個數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征:
- 基于下標(biāo)（位置）的高效元素訪問和更新，時間復(fù)雜度應(yīng)該是O(1);
為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲區(qū)中。 - 允許任意加入元素，而且在不斷加入元素的過程中，表對象的標(biāo)識（函數(shù)id得到的值）不變。
為滿足該特征，就必須能更換元素存儲區(qū)，并且為保證更換存儲區(qū)時 list 對象的標(biāo)識id不變，只能采用分離式實現(xiàn)技術(shù)。
在Python的官方實現(xiàn)中，list就是一種采用分離式技術(shù)實現(xiàn)的動態(tài)順序表。這就是為什么用list.append(x)(或 list.insert(len(list),x)，即尾部插入）比在指定位置插入元素效率高的原因。
在Python的官方實現(xiàn)中，list實現(xiàn)采用了如下的策略︰在建立空表（或者很小的表）時，系統(tǒng)分配一塊能容納8個元素的存儲區(qū)；在執(zhí)行插入操作（insert或append）時，如果元素存儲區(qū)滿就換一塊4倍大的存儲區(qū)。但如果此時的表已經(jīng)很大（目前的閥值為50000)，則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過多空閑的存儲位置。
《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的数据结构与算法笔记（二）—— 顺序表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 数据结构与算法笔记（一）—— 引入概念、
- 下一篇： 数据结构与算法笔记（三）—— 链表(单链