1值戳、線性表簡介
在程序中对竣，經(jīng)常需要將一組（通常是同為某個類型的）數(shù)據(jù)元素作為整體管理和使用。最簡單的解決方案便是將這樣一組元素看成一個序列钦无，用元素在序列里的位置和順序，表示實際應(yīng)用中的某種有意義的信息盖袭，或者表示數(shù)據(jù)之間的某種關(guān)系失暂。我們將其抽象為線性表。
根據(jù)線性表的實際存儲方式鳄虱，分為兩種實現(xiàn)模型：
- 順序表趣席，將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關(guān)系由它們的存儲順序自然表示醇蝴。
- 鏈表宣肚，將元素存放在通過鏈接構(gòu)造起來的一系列存儲塊中。
2悠栓、順序表怎樣存儲
下面我們將著重于順序表霉涨。
還記的上一節(jié)的內(nèi)存嗎？
順序表惭适，作為一種存儲結(jié)構(gòu)笙瑟，他需要在內(nèi)存中申請空間進(jìn)行存儲，而它的特點就是必須要連續(xù)存儲癞志，也就是要拿出連號的‘柜子’進(jìn)行存儲往枷，那么雖然內(nèi)存有很多存儲空間，但在其連續(xù)的空間內(nèi)凄杯，可能有局部內(nèi)存已經(jīng)被其他東西占用错洁，
| 0x03 | 0x04 | XXXX |
| 0x06 | 0x07 | 0x08 |
| XXXX | 0x10 | 0x11 |
假設(shè)我們拿出了03、04兩個柜子進(jìn)行存儲戒突，但是我們現(xiàn)在需要三個柜子來存儲屯碴，而05的位置已經(jīng)被占用，這時候膊存，我們就要吧03导而、04柜子里的東西重新拿出來，再找一個三個連續(xù)的柜子放進(jìn)去隔崎，比如06~08的位置今艺，此時，如果我們又要存儲別的東西爵卒，就又要重新找滿足要求的連續(xù)的“柜子”虚缎。這就是順序表的存儲特性，不過為了避免經(jīng)臣寂耍“搬遷”遥巴，采用一中策略：提前開辟更多的位置來等待你存儲千康，如果滿了，那么就再去新開辟二倍的空間铲掐，滿了再二倍拾弃，當(dāng)然也會有個界限，否則就造成空間浪費了摆霉。
3豪椿、從0開始
| 0x03 | 1 | 0x04 | 2 |
| 0x05 | 3 | 0x06 | 4 |
li = [1, 2, 3, 4]
假設(shè)我們在一塊連續(xù)的位置存儲了數(shù)組li，那么取li[0]的時候, 就是先找到li所在的地址Ox03, 然后從這個地址讀取4個字節(jié)(因為是整型), 如果是取li[3], 也是先找到li所在的地址Ox03,再往后跳過三個數(shù)據(jù)類型字節(jié)的位置, li[3] = Ox03 + 3*4Btye所以li[0]的**0 **的意思就是偏移量,所以數(shù)據(jù)是從零開始携栋。
4搭盾、元素外置的順序表
上面介紹的是基本的順序表，就是存儲的空間里都是類型相同的數(shù)據(jù)婉支，那么你可能會問了鸯隅，明明在Python中數(shù)組里存儲的可以是任何類型的數(shù)據(jù)。這時候向挖，我們就要寄出元素外置的順序表了蝌以，這是個什么意思呢？其實這種存儲不同類型數(shù)據(jù)的數(shù)組何之，其本身并沒有把那些數(shù)據(jù)存儲在自己的空間里跟畅，而是把這些數(shù)據(jù)對應(yīng)的地址存在了自己的空間里，這樣自己空間里還是類型一致的數(shù)據(jù)溶推。
假如還是上面的那塊地址徊件，
| 0x03 | 0x10 | 0x04 | 0x31 |
| 0x05 | 0x52 | 0x06 | 0x43 |
這次在這里存儲的是四個內(nèi)存地址，而這些地址又對應(yīng)相應(yīng)的數(shù)據(jù)蒜危。
| 0x10 | ‘a(chǎn)bb’ | 0x31 | 233 |
| 0x52 | {1, 2} | 0x43 | {'ha':'ho'} |
這時候我們在訪問li[0]的時候?qū)⑦M(jìn)行已下操作:
首先找到li所對應(yīng)的地址Ox03, 再通過這個地址存儲的地址Ox10 找到數(shù)據(jù)'abb', 這種存儲地址的地址空間連續(xù)稱作數(shù)據(jù)外置表, 可以通過列表存儲不同類型的數(shù)據(jù)虱痕。
5、順序表的實現(xiàn)
這里Python已經(jīng)內(nèi)置舰褪，但我們來考慮自己如何實現(xiàn)順序表皆疹。
順序表的兩種基本實現(xiàn)方式
除了需要數(shù)據(jù)部分, 還需要表頭信息用來存儲表的大小以及已存儲數(shù)據(jù)量。
a> 一體式結(jié)構(gòu)：把表頭信息和數(shù)據(jù)區(qū)連續(xù)存儲
b> 分離式結(jié)構(gòu)：把表的大小與已存儲量以及存儲地址放到一個地方, 地址指向另一塊存儲位置
優(yōu)劣問題,數(shù)據(jù)存儲問題:
連續(xù): 讀取方便, 當(dāng)存儲數(shù)據(jù)超過預(yù)先支配的大小, 那就需要重新申請一塊連續(xù)空間, 進(jìn)行數(shù)據(jù)搬遷, 釋放老的空間, 表頭也需要改變, 起始地址就會改變占拍。
分離: 間接讀取,當(dāng)存儲數(shù)據(jù)超過預(yù)先支配的大小, 只需要改變存儲的地址, 并不需要改變表頭的位置。
當(dāng)存儲空間不足的時候捎迫，擴(kuò)充帶來的問題: 擴(kuò)充預(yù)留多少大小晃酒。
下面有兩種解決策略。
兩種策略:
1> 每次申請擴(kuò)充固定數(shù)目的位置, 每次都擴(kuò)充10個空間,
特點: 節(jié)省空間, 但是擴(kuò)充操作頻繁, 操作次數(shù)多
2> 每次申請都擴(kuò)充倍數(shù), 4->8->16->32
特點: 空間換取時間
允許擴(kuò)充的順序表叫做動態(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)識(id地址)不變：表頭和數(shù)據(jù)區(qū)分離式存儲
c>可以存儲不同類型的數(shù)據(jù)：元素外置方式
擴(kuò)充策略:
建立空表(或很小的表), 系統(tǒng)分配一塊能容納8個元素的存儲區(qū), 進(jìn)行插入時, 如果存儲器滿了, 存儲區(qū)就換一塊4倍大的存儲區(qū), 但是此時表已經(jīng)很大(閥值50000),則改變策略,采用加一倍的方法, 避免出現(xiàn)過多的空閑位置
小結(jié)
1、順序表屬于線性表的一種彰导。
2蛔翅、從0開始敲茄。
3、存儲同樣類型的數(shù)據(jù)山析。不同數(shù)據(jù)是如何存儲的堰燎？
4、怎么構(gòu)造的笋轨？都有什么優(yōu)劣秆剪？
5、添加和刪除元素的復(fù)雜度爵政？
