如何分析python數據結構

這期內容當中小編將會給大家帶來有關如何分析python數據結構，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

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

程序 = 數據結構 + 算法

棧

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

• 進棧（壓棧）：push

• 出棧：pop

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

棧在python中的實現，直接用列表即可：

• 進棧：append(obj)

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

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

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

隊列

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

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

使用下面的模塊可以實現隊列：

from collections import deque

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

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

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

• 進隊：append

• 出隊：popleft

• 隊首進隊：appendleft

• 隊尾出隊：pop

鏈表

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

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

節點的插入和刪除：

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

節點的插入和刪除操作，在鏈表里的時間復雜度都是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

雙鏈表

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

列表和鏈表

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

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

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

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

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

集合與字典

哈希表查找

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

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

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

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

python中的字典

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

迷宮問題

可以用一個二維列表表示迷宮。列表中的每個元素都是迷宮中的一格，可能是通路（可以用0表示），也可能是墻（比如用1表示）。每個節點都有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]
]

棧實現

在一個迷宮的節點(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)
]

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

隊列實現

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

深度優先和廣度優先

有兩種搜索的方法：深度優先和廣度優先。
棧的實現就是深度優先方法。
隊列的實現就是廣度優先方法。
一般，深度優先的實現就是和棧有關。廣度優先的實現和隊列有關。

上述就是小編為大家分享的如何分析python數據結構了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。