數(shù)據(jù)結(jié)構(gòu)與算法(python)
在此之前先明確一下:a=10表示的是10是占用的內(nèi)存空間, a表示的是指向10內(nèi)存空間的地址. 區(qū)別c語(yǔ)言,a是內(nèi)存空間的別名, 而python中類似window中的快捷方式.可以使用id()來(lái)查看內(nèi)存地址, 變量名指向的是后面的量, 變量名只是一個(gè)地址.
順序表
在程序中，經(jīng)常需要將一組（通常是同為某個(gè)類型的）數(shù)據(jù)元素作為整體管理和使用，需要?jiǎng)?chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化（可以增加或刪除元素）。
對(duì)于這種需求，最簡(jiǎn)單的解決方案便是將這樣一組元素看成一個(gè)序列，用元素在序列里的位置和順序，表示實(shí)際應(yīng)用中的某種有意義的信息，或者表示數(shù)據(jù)之間的某種關(guān)系。
這樣的一組序列元素的組織形式，我們可以將其抽象為線性表。一個(gè)線性表是某類元素的一個(gè)集合，還記錄著元素之間的一種順序關(guān)系。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實(shí)際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)。
根據(jù)線性表的實(shí)際存儲(chǔ)方式，分為兩種實(shí)現(xiàn)模型：
- 順序表，將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示。
- 鏈表，將元素存放在通過(guò)鏈接構(gòu)造起來(lái)的一系列存儲(chǔ)塊中。
順序表的基本形式
圖a表示的是順序表的基本形式，數(shù)據(jù)元素本身連續(xù)存儲(chǔ)，每個(gè)元素所占的存儲(chǔ)單元大小固定相同，元素的下標(biāo)是其邏輯地址，而元素存儲(chǔ)的物理地址（實(shí)際內(nèi)存地址）可以通過(guò)存儲(chǔ)區(qū)的起始地址Loc (e0)加上邏輯地址（第i個(gè)元素）與存儲(chǔ)單元大?。╟）的乘積計(jì)算而得，即：
Loc(ei) = Loc(e0) + c*i
故，訪問(wèn)指定元素時(shí)無(wú)需從頭遍歷，通過(guò)計(jì)算便可獲得對(duì)應(yīng)地址，其時(shí)間復(fù)雜度為O(1)。
如果元素的大小不統(tǒng)一，則須采用圖b的元素外置的形式，將實(shí)際數(shù)據(jù)元素另行存儲(chǔ)，而順序表中各單元位置保存對(duì)應(yīng)元素的地址信息（即鏈接）。由于每個(gè)鏈接所需的存儲(chǔ)量相同，通過(guò)上述公式，可以計(jì)算出元素鏈接的存儲(chǔ)位置，而后順著鏈接找到實(shí)際存儲(chǔ)的數(shù)據(jù)元素。注意，圖b中的c不再是數(shù)據(jù)元素的大小，而是存儲(chǔ)一個(gè)鏈接地址所需的存儲(chǔ)量，這個(gè)量通常很小。
圖b這樣的順序表也被稱為對(duì)實(shí)際數(shù)據(jù)的索引，這是最簡(jiǎn)單的索引結(jié)構(gòu)。
順序表的結(jié)構(gòu)與實(shí)現(xiàn)
順序表的結(jié)構(gòu)
一個(gè)順序表的完整信息包括兩部分，一部分是表中的元素集合，另一部分是為實(shí)現(xiàn)正確操作而需記錄的信息，即有關(guān)表的整體情況的信息，這部分信息主要包括元素存儲(chǔ)區(qū)的容量和當(dāng)前表中已有的元素個(gè)數(shù)兩項(xiàng)。
順序表的兩種實(shí)現(xiàn)方式
圖a為一體式結(jié)構(gòu)，存儲(chǔ)表信息的單元與元素存儲(chǔ)區(qū)以連續(xù)的方式安排在一塊存儲(chǔ)區(qū)里，兩部分?jǐn)?shù)據(jù)的整體形成一個(gè)完整的順序表對(duì)象。
一體式結(jié)構(gòu)整體性強(qiáng)，易于管理。但是由于數(shù)據(jù)元素存儲(chǔ)區(qū)域是表對(duì)象的一部分，順序表創(chuàng)建后，元素存儲(chǔ)區(qū)就固定了。
圖b為分離式結(jié)構(gòu)，表對(duì)象里只保存與整個(gè)表有關(guān)的信息（即容量和元素個(gè)數(shù)），實(shí)際數(shù)據(jù)元素存放在另一個(gè)獨(dú)立的元素存儲(chǔ)區(qū)里，通過(guò)鏈接與基本表對(duì)象關(guān)聯(lián)。
元素存儲(chǔ)區(qū)替換
一體式結(jié)構(gòu)由于順序表信息區(qū)與數(shù)據(jù)區(qū)連續(xù)存儲(chǔ)在一起，所以若想更換數(shù)據(jù)區(qū)，則只能整體搬遷，即整個(gè)順序表對(duì)象（指存儲(chǔ)順序表的結(jié)構(gòu)信息的區(qū)域）改變了。
分離式結(jié)構(gòu)若想更換數(shù)據(jù)區(qū)，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可，而該順序表對(duì)象不變。
元素存儲(chǔ)區(qū)擴(kuò)充
采用分離式結(jié)構(gòu)的順序表，若將數(shù)據(jù)區(qū)更換為存儲(chǔ)空間更大的區(qū)域，則可以在不改變表對(duì)象的前提下對(duì)其數(shù)據(jù)存儲(chǔ)區(qū)進(jìn)行了擴(kuò)充，所有使用這個(gè)表的地方都不必修改。只要程序的運(yùn)行環(huán)境（計(jì)算機(jī)系統(tǒng)）還有空閑存儲(chǔ)，這種表結(jié)構(gòu)就不會(huì)因?yàn)闈M了而導(dǎo)致操作無(wú)法進(jìn)行。人們把采用這種技術(shù)實(shí)現(xiàn)的順序表稱為動(dòng)態(tài)順序表，因?yàn)槠淙萘靠梢栽谑褂弥袆?dòng)態(tài)變化。
擴(kuò)充的兩種策略
-
每次擴(kuò)充增加固定數(shù)目的存儲(chǔ)位置，如每次擴(kuò)充增加10個(gè)元素位置，這種策略可稱為線性增長(zhǎng)。
特點(diǎn)：節(jié)省空間，但是擴(kuò)充操作頻繁，操作次數(shù)多。
-
每次擴(kuò)充容量加倍，如每次擴(kuò)充增加一倍存儲(chǔ)空間。
特點(diǎn)：減少了擴(kuò)充操作的執(zhí)行次數(shù)，但可能會(huì)浪費(fèi)空間資源。以空間換時(shí)間，推薦的方式。
順序表的操作
增加元素
如圖所示, 為順序表增加新元素111的三種方式.
a. 尾端加入元素，時(shí)間復(fù)雜度為O(1)
b. 非保序的加入元素（不常見(jiàn)），時(shí)間復(fù)雜度為O(1)
c. 保序的元素加入，時(shí)間復(fù)雜度為O(n)
其實(shí)可以直接用list套進(jìn)來(lái), list本身就是順序表.
刪除元素
a. 刪除表尾元素，時(shí)間復(fù)雜度為O(1)
b. 非保序的元素刪除（不常見(jiàn)），時(shí)間復(fù)雜度為O(1)
c. 保序的元素刪除，時(shí)間復(fù)雜度為O(n)
python中的順序表
Python中的list和tuple兩種類型采用了順序表的實(shí)現(xiàn)技術(shù)，具有前面討論的順序表的所有性質(zhì)。
tuple是不可變類型，即不變的順序表，因此不支持改變其內(nèi)部狀態(tài)的任何操作，而其他方面，則與list的性質(zhì)類似。
list的基本實(shí)現(xiàn)技術(shù)
Python標(biāo)準(zhǔn)類型list就是一種元素個(gè)數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：
-
基于下標(biāo)（位置）的高效元素訪問(wèn)和更新，時(shí)間復(fù)雜度應(yīng)該是O(1)；
為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲(chǔ)區(qū)中。
-
允許任意加入元素，而且在不斷加入元素的過(guò)程中，表對(duì)象的標(biāo)識(shí)（函數(shù)id得到的值）不變。
為滿足該特征，就必須能更換元素存儲(chǔ)區(qū)，并且為保證更換存儲(chǔ)區(qū)時(shí)list對(duì)象的標(biāo)識(shí)id不變，只能采用分離式實(shí)現(xiàn)技術(shù)。
在Python的官方實(shí)現(xiàn)中，list就是一種采用分離式技術(shù)實(shí)現(xiàn)的動(dòng)態(tài)順序表。這就是為什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。
在Python的官方實(shí)現(xiàn)中，list實(shí)現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時(shí)，系統(tǒng)分配一塊能容納8個(gè)元素的存儲(chǔ)區(qū)；在執(zhí)行插入操作（insert或append）時(shí)，如果元素存儲(chǔ)區(qū)滿就換一塊4倍大的存儲(chǔ)區(qū)。但如果此時(shí)的表已經(jīng)很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過(guò)多空閑的存儲(chǔ)位置。
使用python來(lái)實(shí)現(xiàn)順序表
這里直接定義一個(gè)列表就可以實(shí)現(xiàn)了(list_a=[1,2,3]就能實(shí)現(xiàn)基本功能), 這里就不再演示了. 等著后面的鏈表再使用python封裝. 已經(jīng)封裝好了的就不用再去封裝了.
其實(shí)python的內(nèi)置類型已經(jīng)替我們封裝好了, 沒(méi)有必要我們自己再去封裝.
- 插入 append, insert, extend
- 刪除 pop, remove, clear
- 修改 直接賦值就好, 就可以替換
- 查找 簡(jiǎn)單的for循環(huán)判斷
- 排序 sort, reverse
