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

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設、高性價比白銀區(qū)網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式白銀區(qū)網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設找我們，業(yè)務覆蓋白銀區(qū)地區(qū)。費用合理售后完善，十年實體公司更值得信賴。

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

程序 = 數(shù)據(jù)結構 + 算法

棧

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

• 進棧（壓棧）：push

• 出棧：pop

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

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

• 進棧：append(obj)

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

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

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

隊列

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

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

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

from collections import deque

這個隊列是支持雙向的，兩端都允許進隊和出隊。操作方法：

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

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

• 進隊：append

• 出隊：popleft

• 隊首進隊：appendleft

• 隊尾出隊：pop

鏈表

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

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

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

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

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

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

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

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

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

雙鏈表

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

列表和鏈表

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

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

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

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

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

集合與字典

哈希表查找

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

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

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

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

python中的字典

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

迷宮問題

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

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]
]

棧實現(xiàn)

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

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)
]

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

隊列實現(xiàn)

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

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

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

上述就是小編為大家分享的如何分析python數(shù)據(jù)結構了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

本文題目：如何分析python數(shù)據(jù)結構
鏈接地址：http://aaarwkj.com/article18/gpjedp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供、品牌網(wǎng)站建設、靜態(tài)網(wǎng)站、網(wǎng)站設計、網(wǎng)站收錄、移動網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)