如何分析python數(shù)據(jù)結(jié)構(gòu)

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)如何分析python數(shù)據(jù)結(jié)構(gòu)，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

數(shù)據(jù)結(jié)構(gòu)就是設(shè)計(jì)數(shù)據(jù)以何種方式組織并存儲(chǔ)在計(jì)算機(jī)中。
比如：列表、集合、字典等都是一種數(shù)據(jù)結(jié)構(gòu)。

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

棧

棧（Stack）是一個(gè)數(shù)據(jù)集合，只能在一端進(jìn)行插入或刪除操作的列表
棧的特點(diǎn)：后進(jìn)先出（last-in, first-out）
棧的基本操作：

• 進(jìn)棧（壓棧）：push

• 出棧：pop

• 取棧頂：gettop，只是看一下，不把元素移除

棧在python中的實(shí)現(xiàn)，直接用列表即可：

• 進(jìn)棧：append(obj)

• 出棧：pop()，不帶參數(shù)就是出最后一個(gè)

• 取棧頂：list[-1]，查看列表最后一個(gè)元素

以上棧的操作的時(shí)間復(fù)雜度都是O(1)。
不過列表本身沒有棧的限制，依然可以使用列表支持的其他方法。比如 insert(index, obj) 和 pop(index) 可以插入或取出列表任意位置的元素。但是這些操作不是棧的操作，時(shí)間復(fù)雜度是O(n)。

隊(duì)列

隊(duì)列（Queue）是一個(gè)數(shù)據(jù)集合，僅允許在列表的一段進(jìn)行插入，另一端進(jìn)行刪除。
隊(duì)列的性質(zhì)：先進(jìn)先出（First-in, First-out）
還有一種雙向隊(duì)列，隊(duì)列的兩端都允許進(jìn)行進(jìn)隊(duì)和出隊(duì)的操作。

隊(duì)列不能用列表來實(shí)現(xiàn)。如果用列表實(shí)現(xiàn)，入隊(duì)可以是append操作。但是出隊(duì)是pop(0)，這個(gè)操作是把最前面的元素彈出，然后列表前面空了一個(gè)位置，所有元素都要往前移動(dòng)。這樣一次操作的時(shí)間復(fù)雜度是O(n)。

使用下面的模塊可以實(shí)現(xiàn)隊(duì)列：

from collections import deque

這個(gè)隊(duì)列是支持雙向的，兩端都允許進(jìn)隊(duì)和出隊(duì)。操作方法：

• 創(chuàng)建隊(duì)列：queue = deque()，建一個(gè)空隊(duì)列

• queue = deque(li)，通過一個(gè)列表來創(chuàng)建隊(duì)列

• 進(jìn)隊(duì)：append

• 出隊(duì)：popleft

• 隊(duì)首進(jìn)隊(duì)：appendleft

• 隊(duì)尾出隊(duì)：pop

鏈表

每一個(gè)元素都是一個(gè)對(duì)象，每個(gè)對(duì)象稱為一個(gè)節(jié)點(diǎn)，包含有數(shù)據(jù)域item和指向下一個(gè)節(jié)點(diǎn)的指針next。通過各個(gè)節(jié)點(diǎn)之間的相互連接，最終串聯(lián)成一個(gè)鏈表。
節(jié)點(diǎn)的定義：

class Node(object):
    def __init__(self, item=None):
        self.item = item
        self.next = None

節(jié)點(diǎn)的插入和刪除：

# cur_node 是當(dāng)前節(jié)點(diǎn)
# 插入，在當(dāng)前節(jié)點(diǎn)后插入節(jié)點(diǎn)p
p.next = cur_node.next
cur_node.naxt = p
# 刪除，把當(dāng)前節(jié)點(diǎn)后的節(jié)點(diǎn)p刪除
p = cur_node.next
cur_node.nxet = cur_node.next.next
del p

節(jié)點(diǎn)的插入和刪除操作，在鏈表里的時(shí)間復(fù)雜度都是O(1)。但是在列表是是O(n)。這個(gè)就是鏈表存在的意義。

建立鏈表
頭插法，每個(gè)新加入的元素都插入到頭部元素的后面：

def create_link_list_first(li):
    head = Node()
    for item in li:
        p = Node(item)
        p.next = head.next
        head.next = p
    return head

尾插法，每個(gè)新加入的元素都放在鏈表的最后：

def create_link_list_right(li):
    head = Node()
    r = head
    for item in li:
        p = Node(item)
        r.next = p
        r = p
    return head

雙鏈表

雙鏈表是每個(gè)節(jié)點(diǎn)都有2個(gè)指針：一個(gè)指向后面的節(jié)點(diǎn)，一個(gè)指向前面的節(jié)點(diǎn)。
單鏈表中，頭部節(jié)點(diǎn)沒有數(shù)據(jù)域，值是None，尾部節(jié)點(diǎn)的next是None
雙鏈表中，每個(gè)節(jié)點(diǎn)都有數(shù)據(jù)局，頭部和尾部節(jié)點(diǎn)的其中一個(gè)指針是None
插入、刪除、建立鏈表就不展開了

列表和鏈表

下面是兩種數(shù)據(jù)結(jié)構(gòu)的各種基本操作的時(shí)間復(fù)雜度比較：

• 按元素查找：都是O(n)

• 按下標(biāo)查找：列表是O(1)，鏈表是O(n)

• 插入元素：列表是O(n)，鏈表是O(1)

• 刪除元素：列表是O(n)，鏈表是O(1)

集合與字典

哈希表查找

哈希表（Hash Table，又稱為散列表），是一種線性表的存儲(chǔ)結(jié)構(gòu)。通過把每個(gè)對(duì)象的關(guān)聯(lián)字key作為自變量，同個(gè)一個(gè)哈希函數(shù)h(key)，將key映射到下標(biāo)h(key)處，并將該對(duì)象存儲(chǔ)在這個(gè)位置。
關(guān)于這個(gè)哈希函數(shù)h(k)，就不用深究了。就是給一個(gè)表里key，經(jīng)過計(jì)算可以獲得一個(gè)確定的數(shù)（下標(biāo)）。
例如：數(shù)據(jù)集合{1, 6, 7, 9}，假設(shè)存在哈希函數(shù)：h(1) = 0, h(6) = 2, h(7) = 4, h(9) = 5，那么這個(gè)哈希表就被存儲(chǔ)為[1, None, 6, None, 7, 9]。
這樣，當(dāng)需要查找元素6所在的位置時(shí)，通過哈希函數(shù)h(6)就可以獲得該元素所在的下標(biāo)（h(6)=2），因此，不需要做遍歷，直接去2的位置確認(rèn)是否有改元素。這就是一個(gè)O(1)的時(shí)間復(fù)雜度。
哈希沖突：由于哈希表的下標(biāo)范圍有限，但是元素key的值是接近無限的。因此可能會(huì)出現(xiàn)兩個(gè)關(guān)鍵字通過哈希函數(shù)運(yùn)算后得到的是同樣的值。兩個(gè)元素映射到通一個(gè)下標(biāo)，這就造成了哈希沖突。
解決哈希沖突的辦法：

• 拉鏈法：將所有沖突的元素在下標(biāo)處再用鏈表連接起來

• 開放尋址法：再搞個(gè)哈希沖突函數(shù)，通過哈希沖突函數(shù)，得到新的地址。

python中的集合，就是把元素通過哈希函數(shù)得的下標(biāo)后，去下標(biāo)位置確認(rèn)，是否存在值，不存在，則不在集合中。如果存在值，看一下是否一樣（可能有華西沖突），如果在該下標(biāo)處或者是鏈表里，那么該元素就在集合中。

python中的字典

使用哈希表存儲(chǔ)字典，通過哈希函數(shù)將字典的key映射為下標(biāo)。然后可value存儲(chǔ)在key對(duì)應(yīng)的下標(biāo)里。
字典的鍵值對(duì)數(shù)量不多的情況下，幾乎不會(huì)發(fā)生哈希沖突。此時(shí)查找一個(gè)元素的時(shí)間復(fù)雜度為O(1)。

迷宮問題

可以用一個(gè)二維列表表示迷宮。列表中的每個(gè)元素都是迷宮中的一格，可能是通路（可以用0表示），也可能是墻（比如用1表示）。每個(gè)節(jié)點(diǎn)都有4個(gè)方向。給出一個(gè)算法，給出一條從起點(diǎn)到終點(diǎn)的路徑。

maze = [
    [1,1,1,1,1,1,1],
    [1,0,0,0,0,0,1],
    [1,1,0,1,1,0,1],
    [1,0,0,0,0,1,1],
    [1,0,0,1,0,0,1],
    [1,1,1,1,1,1,1]
]

棧實(shí)現(xiàn)

在一個(gè)迷宮的節(jié)點(diǎn)(x, y)上，可以進(jìn)行4個(gè)方向的探查。遍歷下面的這個(gè)列表，依次完成4個(gè)方向的探查：

dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y + 1),
    lambda x, y: (x, y - 1)
]

思路：從一個(gè)節(jié)點(diǎn)開始，任意找下一個(gè)能走的點(diǎn)，當(dāng)找不到能走的點(diǎn)時(shí)，退回上一個(gè)點(diǎn)尋找是否有其他方向能走的點(diǎn)。
方法：創(chuàng)建一個(gè)空棧，首先將入口節(jié)點(diǎn)進(jìn)棧。當(dāng)棧不為空是，循環(huán)。獲取棧頂元素，尋找下一個(gè)可走的節(jié)點(diǎn)，如果找不到可走的節(jié)點(diǎn)，說明當(dāng)前位置是死胡同，進(jìn)行回溯（就是當(dāng)前位置出棧，看前面的點(diǎn)是否還有別的節(jié)點(diǎn)可以走）。之前走過的節(jié)點(diǎn)可以標(biāo)記為-1，防止再走上去。

隊(duì)列實(shí)現(xiàn)

思路：從一個(gè)節(jié)點(diǎn)開始，尋找所有下面能繼續(xù)走的點(diǎn)。然后繼續(xù)尋找，直到找到出口。好比很多人一起探索迷宮，遇到岔路了，就把隊(duì)伍拆分了，繼續(xù)往每個(gè)岔路進(jìn)行探索。
方法：創(chuàng)建一個(gè)空隊(duì)列，將起點(diǎn)位置進(jìn)隊(duì)。在隊(duì)列不為空時(shí)，循環(huán)。出隊(duì)一次，看出隊(duì)的節(jié)點(diǎn)。如果是出口，那么就找到出口了。否則找出出隊(duì)節(jié)點(diǎn)的4個(gè)相鄰的方塊中可走的方塊，這些節(jié)點(diǎn)全部進(jìn)隊(duì)。重復(fù)上面的步驟。
按照上面的方法，最終能夠找到終點(diǎn)。但是沒有輸出從起點(diǎn)到終點(diǎn)的路徑。每次進(jìn)隊(duì)的元素，必須關(guān)聯(lián)到它前一個(gè)讓他入隊(duì)的元素。這樣就可以倒推出一條從終點(diǎn)到起點(diǎn)的路徑了。
這段是我想的，這個(gè)路徑可以用鏈表存。鏈表頭最終就是終點(diǎn)位置，鏈表尾是起點(diǎn)。每個(gè)進(jìn)隊(duì)列的元素，同時(shí)也用頭插法插入鏈表，這樣就關(guān)聯(lián)好上一個(gè)元素了。貌似不用擔(dān)心岔路的問題，從
終點(diǎn)到起點(diǎn)的方向是沒有分叉的。

深度優(yōu)先和廣度優(yōu)先

有兩種搜索的方法：深度優(yōu)先和廣度優(yōu)先。
棧的實(shí)現(xiàn)就是深度優(yōu)先方法。
隊(duì)列的實(shí)現(xiàn)就是廣度優(yōu)先方法。
一般，深度優(yōu)先的實(shí)現(xiàn)就是和棧有關(guān)。廣度優(yōu)先的實(shí)現(xiàn)和隊(duì)列有關(guān)。

上述就是小編為大家分享的如何分析python數(shù)據(jù)結(jié)構(gòu)了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。