python常用代码_Python常用算法学习(4) 数据结构（原理+代码）-最全总结
數據結構簡介
1，數據結構
數據結構是指相互之間存在著一種或多種關系的數據元素的集合和該集合中數據元素之間的關系組成。簡單來說，數據結構就是設計數據以何種方式組織并存貯在計算機中。比如：列表，集合與字典等都是一種數據結構。而之前已經學習過列表，字典，集合，元組等，這里就簡單說一下不再贅述。
N.Wirth：“程序=數據結構+算法”
數據：數據即信息的載體，是能夠輸入到計算機中并且能被計算機識別，存儲和處理的符號總稱。
數據元素：數據元素是數據的基本單位，又稱之為記錄(Record)，一般，數據元素若由若干基本型(或稱字段，域，屬性)組成。
2，數據結構的分類
數據結構按照其邏輯結構可分為線性結構，樹結構，圖結構
- 線性結構：數據結構中的元素存在一對一的相互關系
- 樹結構：數據結構中的元素存在一對多的相互關系
- 圖結構：數據結構中的元素存在多對多的相互關系
3，存儲結構
1，特點
- 1，是數據的邏輯結構在計算機存儲器中的映象(或表示)
- 2，存儲結構是通過計算機程序來實現，因而是依賴于具體的計算機語言的
2，存儲結構分類
- 1，順序存儲(Sequential Storage)：將數據結構中各元素按照其邏輯順序存放于存儲器一片連續的存儲空間中。
- 2，鏈式存儲(Linkend Storage)：將數據結構中各元素分布到存儲器的不通電，用記錄下一個結點位置的方式建立他們之間的聯系，由此得到的存儲結構為鏈式存儲結果。
- 3，索引存儲(Indexed Storage)：在存儲數據的同時，建立一個附加的索引表，即索引存儲結構=數據文件+索引表。
常用的數據結構
1，列表
列表(其他語言稱為數組，但是數組和Python的列表還是有區別的)是一種基本數據類型。
列表，在Python中稱為list，使用中括號包含，其中內部元素使用逗號分隔，內部元素可以是任何類型包含空。
1.1 數組和列表不同點
- 1，數組元素類型要相同，而Python列表不需要
- 2，數組長度固定，而Python列表可以增加
Python列表操作方法請參考此博客：https://www.cnblogs.com/wj-1314/p/8433116.html
2，元組
元組，Python中類為tuple。使用小括號包含，內部元素使用逗號分隔，可為任意值。與列表不同之處為，其內部元素不可修改，而且不能做刪除，更新操作。
注意：當元組中元素只有一個時，結尾要加逗號，若不加逗號，Python解釋器都將解釋成元素本身的類型，而非元組類型。
舉個例子：
>>> a = (1,2,3)>>> b = ('1',[2,3])>>> c = ('1','2',(3,4))>>> d = ()>>> e = (1,)2.1 元組的操作
通過下標操作
如下，做出更改和刪除會報異常：
>>> c[0] = 1Traceback (most recent call last):??File?"", line 1,?in?TypeError:?'tuple'?object?does not support item assignment?>>> del c[0]Traceback (most recent call last):??File?"", line 1,?in?TypeError:?'tuple'?object?doesn't support item deletion2.2 運算符及內建函數操作
元組本身是不可變，但是可以通過 + 來構成新的元組。
>>> a(1, 2, 3)>>> b('1', [2, 3])>>> a + b(1, 2, 3,?'1', [2, 3])可以通過使用內建函數 len 獲取元組長度，可以使用 * 元素來實現元素的重復
>>> a = (1,2,3)>>> len(a)3>>> a*3(1, 2, 3, 1, 2, 3, 1, 2, 3)元組也支持 in 和 not in 成員運算符。
3，集合
集合用于包含一組無序的對象，與列表和元組不同，集合是無序的，也無法通過數字進行索引。此外，集合中的元素不能重復。set和dict一樣，只是沒有 value，相當于 dict 的 key 集合，由于 dict 的 key 是不重復的，且 key 是不可變對象，因此 set 有如下特性：
- 1，不重復，(互異性)，也就是說集合是天生去重的
- 2，元素為不可變對象，(確定性，元素必須可 hash)
- 3，集合的元素沒有先后之分，(無序性)
Python的集合與數學中的集合一樣，也有交集，并集和合集。
舉例如下：
>>> s1 = {1,2,3,4,5}>>> s2 = {1,2,3}>>> s3 = {4,5}>>> s1&s2?? # 交集{1, 2, 3}>>> s1|s2?? # 并集{1, 2, 3, 4, 5}?>>> s1 - s2? # 差差集{4, 5}>>> s3.issubset(s1)?? # s3 是否為s1 的子集True>>> s1.issuperset(s2)? # s1 是否為 s2 的超集True更多集合相關的操作參考博客：https://www.cnblogs.com/wj-1314/p/8423273.html
4，棧
棧(Stack)是一個數據集合，可以理解為只能在一段進行插入或刪除操作的列表。
棧的特點：后進先出 LIFO(Last-in， First-out)
棧的概念有：棧頂，棧底
棧的基本操作：
對棧的理解，就像是一摞書，只能從上面放和取。
4.1 棧的實現
使用一般列表結構即可實現棧：
那現在我們寫一個類實現它：
class?Stack:?????def __init__(self):????????self.stack = []?????def push(self, element):????????self.stack.append(element)?????def pop(self):????????# 移除列表中的一個元素(默認最后一個)，并返回該元素的值????????return?self.stack.pop()?????def get_top(self):????????if?len(self.stack) > 0:????????????return?self.stack[-1]????????else:????????????return?None?stack = Stack()stack.push(1)stack.push(2)print(stack.pop())?? # 24.2 棧的應用——括號匹配問題
我們可以通過棧來解決括號匹配的問題，就是解決IDE實現括號未匹配成功報錯的問題。
代碼：
class?Stack:?????def __init__(self):????????self.stack = []?????def push(self,element):????????return?self.stack.append(element)?????def pop(self):????????return?self.stack.pop()?????def get_top(self):????????if?len(self.stack) > 0:????????????return?self.stack[-1]????????else:????????????return?None?????def is_empty(self):????????return?len(self.stack) == 0?def brace_match(s):????match = {'}':?'{',?']':?'[',?')':?'('}????stack = Stack()????for?ch?in?s:????????if?ch?in?{'(',?'[',?'{'}:????????????stack.push(ch)????????else:????????????if?stack.is_empty():????????????????return?False????????????elif stack.get_top() == match[ch]:????????????????stack.pop()????????????else:????????????????return?False?????if?stack.is_empty():????????return?True????else:????????return?False?print(brace_match('{[{()}]}'))5，隊列
隊列(Queue)是一個數據集合，僅允許在列表的一端進行插入，另一端進行刪除。進行插入的一端稱為隊尾(rear)，插入動作稱為進隊或者入隊。進行刪除的一端稱為對頭(front)，刪除動作稱為出隊。
隊列的性質：先進先出(First-in , First-out)
隊列可以并發的派多個線程，對排列的線程處理，并切每個需要處理線程只需要將請求的數據放入隊列容器的內存中，線程不需要等待，當排列完畢處理完數據后，線程在準時來取數據即可，請求數據的線程只與這個隊列容器存在關系，處理數據的線程down掉不會影響到請求數據的線程，隊列會派給其他線程處理這份數據，它實現了解耦，提高效率。隊列內會有一個順序的容器，列表與這個容器是有區別的，列表中數據雖然是排列的，但數據被取走后還會保留，而隊列中這些容器的數據被取后將不會保留。當必須在多個線程之間安全的交換信息時，隊列在線程編程中特別有用。
5.1 隊列的實現
隊列能否用列表簡單實現？為什么？
隊列其實就是一個先進先出的線性表，只能在隊首執行刪除操作，在隊尾執行插入操作，用列表表示隊列，用 append() 方法實現在隊尾插入元素，用 pop(0)方法實現在隊首刪除元素。
觀察上圖，我們會發現是把列表的最左邊(最上邊)當做了隊列的首，把最右邊(最下邊)當做了尾巴(左首右尾，上首下尾)，用 insert()或者 append()方法實現隊尾插入元素，用 pop()方法實現隊尾刪除元素。
環形隊列的實現方式
環形隊列：當隊尾指針 front == MaxSize + 1 時，再前進一個位置就自動到0。
- 隊首指針前進1： front = (front + 1) % MaxSize
- 隊尾指針前進1： rear = (rear + 1) % MaxSize
- 隊空條件： front == rear
- 隊滿條件： (rear + 1) % MaxSize == front
雙向隊列的完整用法：
# _*_coding:utf-8_*_?# 創建雙向隊列from?collections import deque?d = deque()?# append(往右邊添加一個元素)d.append(1)d.append(2)print(d)? # deque([1, 2])?# appendleft(往左邊添加一個元素)d.appendleft(11)d.appendleft(22)print(d)? # deque([22, 11, 1, 2])?# clear清空隊列d.clear()print(d)? # deque([])?# 淺copy copyd.append(1)new_d = d.copy()print(new_d)? # deque([1])?#? count(返回指定元素的出現次數)d.append(1)d.append(1)print(d)? # deque([1, 1, 1])print(d.count(1))? # 3?# extend(從隊列右邊擴展一個列表的元素)d.append(2)d.extend([3, 4, 5])print(d)? # deque([1, 1, 1, 2, 3, 4, 5])?# extendleft(從隊列左邊擴展一個列表的元素)d.extendleft([3, 4, 5])print(d)? # deque([5, 4, 3, 1, 1, 1, 2, 3, 4, 5])?#? index(查找某個元素的索引位置)d.clear()d.extend(['a',?'b',?'c',?'d',?'e'])print(d)print(d.index('e'))print(d.index('c', 0, 3))? # 指定查找區間'''deque(['a',?'b',?'c',?'d',?'e'])42'''?#? insert(在指定位置插入元素)d.insert(2,?'z')print(d)# deque(['a', 'b', 'z', 'c', 'd', 'e'])?# pop(獲取最右邊一個元素，并在隊列中刪除)x = d.pop()print(x)print(d)'''edeque(['a',?'b',?'z',?'c',?'d'])'''?# popleft(獲取最左邊一個元素，并在隊列中刪除)print(d)x = d.popleft()print(x)print(d)'''deque(['a',?'b',?'z',?'c',?'d'])adeque(['b',?'z',?'c',?'d'])'''?# remove(刪除指定元素)print(d)d.remove('c')print(d)'''deque(['b',?'z',?'c',?'d'])deque(['b',?'z',?'d'])'''?# reverse(隊列反轉)print(d)d.reverse()print(d)'''deque(['b',?'z',?'d'])deque(['d',?'z',?'b'])'''?# rotate(把右邊元素放到左邊)d.extend(['a',?'b',?'c',?'d',?'e'])print(d)d.rotate(2)? # 指定次數，默認1次print(d)'''deque(['d',?'z',?'b',?'a',?'b',?'c',?'d',?'e'])deque(['d',?'e',?'d',?'z',?'b',?'a',?'b',?'c'])'''Python四種類型的隊列
Queue：FIFO 即 first in first out 先進先出
LifoQueue：LIFO 即 last in first out 后進先出
PriorityQueue：優先隊列，級別越低，越優先
deque：雙邊隊列
導入三種隊列，包
from?queue import Queue,LifoQueue,PriorityQueueQueue：先進先出隊列
#基本FIFO隊列? 先進先出 FIFO即First in First Out,先進先出#maxsize設置隊列中，數據上限，小于或等于0則不限制，容器中大于這個數則阻塞，直到隊列中的數據被消掉q = Queue(maxsize=0)?#寫入隊列數據q.put(0)q.put(1)q.put(2)?#輸出當前隊列所有數據print(q.queue)#刪除隊列數據，并返回該數據q.get()#輸也所有隊列數據print(q.queue)?# 輸出:# deque([0, 1, 2])# deque([1, 2])LifoQueue：后進先出隊列：
#LIFO即Last in First Out,后進先出。與棧的類似，使用也很簡單,maxsize用法同上lq = LifoQueue(maxsize=0)?#隊列寫入數據lq.put(0)lq.put(1)lq.put(2)?#輸出隊列所有數據print(lq.queue)#刪除隊尾數據，并返回該數據lq.get()#輸出隊列所有數據print(lq.queue)?#輸出:# [0, 1, 2]# [0, 1]優先隊列
# 存儲數據時可設置優先級的隊列# 優先級設置數越小等級越高pq = PriorityQueue(maxsize=0)?#寫入隊列，設置優先級pq.put((9,'a'))pq.put((7,'c'))pq.put((1,'d'))?#輸出隊例全部數據print(pq.queue)?#取隊例數據，可以看到，是按優先級取的。pq.get()pq.get()print(pq.queue)?#輸出：[(9,?'a')]雙邊隊列
#雙邊隊列dq = deque(['a','b'])?#增加數據到隊尾dq.append('c')#增加數據到隊左dq.appendleft('d')?#輸出隊列所有數據print(dq)#移除隊尾，并返回print(dq.pop())#移除隊左，并返回print(dq.popleft())#輸出:deque(['d',?'a',?'b',?'c'])cd6，鏈表
當我們存儲一大波數據時，我們很多時候是使用數組，但是當我們執行插入操作的時候就是非常麻煩，比如，有一堆數據1,2,3,5,6,7 我們要在3和5之間插入4，如果用數組，我們會怎么辦？當然是將5之后的數據往后退一位，然后再插入4，這樣非常麻煩，但是如果用鏈表，就直接在3和5之間插入4即可。
所以鏈表的節點結構如下：
data為自定義的數據，next為下一個節點的地址。head保存首位節點的地址。
首先可以看一個小鏈表，定義鏈表：
class?Node:????def __init__(self, item):????????self.item = item????????self.next = None?a = Node(1)b = Node(2)c = Node(3)# 通過next 將 a,b,c聯系起來a.next = bb.next = c# 打印a的下一個的下一個結果是什么print(a.next.next.item) # 3當然，我們不可能這樣next來調用鏈表，使用循環等，下面繼續學習。
鏈表永遠有一個頭結點，head
頭插法和尾插法的代碼如下：
class?Node:????def __init__(self, item):????????self.item = item????????self.next = None?# 頭插法# 這里我們使用 li 進行循環插入def create_linklist_head(li):????head = Node(li[0])????for?element?in?li[1:]:????????node = Node(element)????????node.next = head? # 將頭結點 給剛插入的節點????????head = node?????? # 然后將插入的節點設置為頭結點????return?head?# 尾插法def create_linklist_tail(li):????head = Node(li[0])????tail = head????for?element?in?li[1:]:????????node = Node(element)????????tail.next = node????????tail = node????return?head?def print_linklist(lk):????while?lk:????????print(lk.item, end=',')????????lk = lk.next????print('*********')?lk = create_linklist_head([1, 2, 3, 4])# print(lk.item)? # 4print_linklist(lk)? # 4,3,2,1,*********?lk = create_linklist_tail([1, 2, 3, 4, 5])print_linklist(lk)? # 1,2,3,4,5,插入如下，非常簡單，所以時間復雜度也低。
6.1 關于鏈表的方法
1，判斷是否為空：isEmpty()
def isEmpty(self):????return?(self.length == 0)2，增加一個節點(在鏈表尾添加)：append()
def append(self, dataOrNode):????item = None????if?isinstance(dataOrNode, Node):????????item = dataOrNode????else:????????item = Node(dataOrNode)?????????if?not self.head:????????self.head = item????????self.length += 1????else:????????node = self.head????????while?node._next:????????????node = node._next????????node._next = item????????self.length += 13，刪除一個節點：delete()
# 刪除一個節點之后，記得把鏈表長度減一def delete(self, index):????if?self.isEmpty():????????print("this chain table is empty")????????return?????if?index < 0 or index >= self.length:????????print('Error: out of index')????????return?????# 要注意刪除第一個節點的情況，如果有空的頭節點就不用這樣????if?index == 0:????????self.head = self.head._next????????self.length -= 1????????return?????# prev 為保存前導節點????# node 為保存當前節點????# 當j 與index 相等時就相當于找到要刪除的節點????j = 0????node = self.head????prev = self.head????while?node._next and j < index:????????prev = node????????node = node._next????????j += 1?????????if?j == index:????????prev._next = node._next????????self.length -= 14，修改一個節點：update()
def update(self, index, data):????if?self.isEmpty() or index < 0 or index >= self.length:????????print?'error: out of index'????????return????j = 0????node = self.head????while?node._next and j < index:????????node = node._next????????j += 1?????if?j == index:????????node.data = data5，查找一個節點：getItem()
def getItem(self, index):????if?self.isEmpty() or index < 0 or index >= self.length:????????print?"error: out of index"????????return????j = 0????node = self.head????while?node._next and j < index:????????node = node._next????????j += 1?????return?node.data6，查找一個節點的索引：getIndex()
def getIndex(self, data):????j = 0????if?self.isEmpty():????????print?"this chain table is empty"????????return????node = self.head????while?node:????????if?node.data == data:????????????return?j????????node = node._next????????j += 1?????if?j == self.length:????????print?"%s not found"?% str(data)????????return7，插入一個節點：insert()
def insert(self, index, dataOrNode):????if?self.isEmpty():????????print?"this chain tabale is empty"????????return?????if?index < 0 or index >= self.length:????????print?"error: out of index"????????return?????item = None????if?isinstance(dataOrNode, Node):????????item = dataOrNode????else:????????item = Node(dataOrNode)?????if?index == 0:????????item._next = self.head????????self.head = item????????self.length += 1????????return?????j = 0????node = self.head????prev = self.head????while?node._next and j < index:????????prev = node????????node = node._next????????j += 1?????if?j == index:????????item._next = node????????prev._next = item????????self.length += 18，清空鏈表：clear()
def clear(self):????self.head = None????self.length = 06.2 雙鏈表
6.3 鏈表復雜度分析
順序表(列表/數組)與鏈表
鏈表與順序表
- 鏈表在插入和刪除的操作上明顯快于順序表
- 鏈表的內存可以更加靈活地分配(可以試利用鏈表重新實現棧和隊列)
- 鏈表這種鏈式存儲的數據結構對樹和圖的結構有很大的啟發性
7，哈希表(Hash table)
眾所周知，HashMap是一個用于存儲 Key-Value鍵值對的集合，每一個鍵值對也叫Entry，這些鍵值對(Entry)分散存儲在一個數組當中，這個數組就是HashMap的主干。
使用哈希表可以進行非常快速的查找操作，查找時間為常數，同時不需要元素排列有序；Python的內建數據類型：字典就是用哈希表實現的。
Python中的這些東西都是哈希原理：字典(dictionary)、集合(set)、計數器(counter)、默認字典Defaut dict)、有序字典(Order dict).
哈希表示一個高效的查找的數據結構，哈希表一個通過哈希函數來計算數據存儲位置的數據結構，通常支持如下操作：
- insert(key, value)：插入鍵值對(key, value)
- get(key)：如果存在鍵為key的鍵值對則返回其value，否則返回空值
- delete(key)：刪除鍵為key的鍵值對
直接尋址表
直接尋址技術缺點：
哈希
直接尋址表：key為k的元素放到k位置上
改進直接尋址表：哈希(Hashing)
- 構建大小為m的尋址表T
- key為k的元素放到 h(k)位置上
- h(k) 是一個函數，其將域U映射到表 T[0, 1, ... , m-1]
哈希表
哈希表(Hash Table，又稱為散列表)，是一種線性表的存儲結構。哈希表由一個直接尋址表和一個哈希函數組成。哈希函數h(k)將元素關鍵字 k 作為自變量，返回元素的存儲下標。
假設有一個長度為7的哈希表，哈希函數 h(k)=k%7.元素集合 {14, 22, 3, 5}的存儲方式如下圖：
代碼如下：
class?LinkList:????class?Node:????????def __init__(self, item=None):????????????self.item = item????????????self.next = None?????class?LinkListIterator:????????def __init__(self, node):????????????self.node = node????????def __next__(self):????????????if?self.node:????????????????cur_node = self.node????????????????self.node = cur_node.next????????????????return?cur_node.item????????????else:????????????????raise StopIteration????????def __iter__(self):????????????return?self?????def __init__(self, iterable=None):????????self.head = None????????self.tail = None????????if?iterable:????????????self.extend(iterable)?????def append(self, obj):????????s = LinkList.Node(obj)????????if?not self.head:????????????self.head = s????????????self.tail = s????????else:????????????self.tail.next = s????????????self.tail = s?????def extend(self, iterable):????????for?obj?in?iterable:????????????self.append(obj)?????def find(self, obj):????????for?n?in?self:????????????if?n == obj:????????????????return?True????????else:????????????return?False?????def __iter__(self):????????return?self.LinkListIterator(self.head)?????def __repr__(self):????????return?"<>"??# 類似于集合的結構class?HashTable:????def __init__(self, size=101):????????self.size = size????????self.T = [LinkList()?for?i?in?range(self.size)]?????def h(self, k):????????return?k % self.size?????def insert(self, k):????????i = self.h(k)????????if?self.find(k):????????????print('Duplicated Insert')????????else:????????????self.T[i].append(k)?????def find(self, k):????????i = self.h(k)????????return?self.T[i].find(k)7.1 哈希表的應用
1，集合與字典
字典與集合都是通過哈希表來實現的。比如：
dic_res = {'name':'james',?'age':32,?'gender':?'Man'}使用哈希表存儲字典，通過哈希表將字典的鍵映射為下標，假設 h('name')=3，h('age')=4，則哈希表存儲為：
[None, 32, None,?'james',?'Man']如果發生哈希沖突，則通過拉鏈法或開發尋址法解決。
2，md5算法
MD5(Message-Digest Algorithm 5)曾經是密碼學中常用的哈希函數，可以把任意長度的數據映射為128位的哈希值，其曾經包含如下特征：
- 1，同樣的消息，其MD5值必定相同；
- 2，可以快速計算出任意給定消息的MD5值；
- 3，除非暴力的枚舉所有可能的消息，否則不可能從哈希值反推出消息本身；
- 4，兩天消息之間即使只有微小的差別，其對應的MD5值也應該是完全不同，完全不相關的；
- 5，不能再有意義的時間內人工的構造兩個不同的消息，使其具有相同的MD5值
3，md5
應用舉例：文件的哈希值
算出文件的哈希值，若兩個文件的哈希值相同，則可認為這兩個文件時相同的，因此：
- 1，用戶可以利用它來驗證下載的文件是否完整
- 2，云存儲服務商可以利用它來判斷用戶要上次的文件是否已經存在于服務器上，從而實現秒傳的功能，同時避免存儲過多相同的文件副本。
4，SHA2算法
歷史上MD5和SHA-1曾經是使用最為廣泛的 cryptographic hash function，但是隨著密碼學的發展，這兩個哈希函數的安全性相繼受到了各種挑戰。
因此現在安全性較重要的場合推薦使用 SHA-A等新的更安全的哈希函數。
SHA-2包含了一系列的哈希函數：SHA-224， SHA-256， SHA-384，SHA-512，SHA-512/224，SHA-512/256，其對應的哈希值長度分別為 224， 256， 384 or 512位。
SHA-2 具有和 MD5 類似的性質。
5，SHA2算法應用舉例
例如在比特幣系統中，所有參與者需要共同解決如下問題：對于一個給定的字符串U，給定的目標哈希值H，需要計算一個字符串V，使得 U+ V的哈希值與H的差小于一個給定值D。此時，只能通過暴力枚舉V來進行猜測。首先計算出結果的人可獲得一定獎金。而某人首先計算成功的概率與其擁有的計算量成正比，所以其獲得的獎金的期望值與其擁有的計算量成正比。
棧和隊列的應用——迷宮問題
給出一個二維列表，表示迷宮(0表示通道，1表示圍墻)。給出算法，求一條走出迷宮的路徑。
將其轉化為數組如下：
那有兩種思路，一種是使用棧(深度優先搜索)來存儲當前路徑，也可以稱為回溯法。但是深度優先有一個缺點，就是雖然能找到路徑，但是不能保證是最短路徑，其優點就是簡單，容易理解。
另一種方法就是隊列，
1，棧——深度優先搜索
回溯法
思路：從一個節點開始，任意找下一個能走的點，當炸不到能走的點時，退回上一個點尋找是否有其他方向的點。
使用棧存儲當前路徑
如下圖所示：
代碼如下：
# _*_coding:utf-8_*_?maze = [????[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],????[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],????[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],????[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],????[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],????[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],????[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],????[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],????[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],????[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]?# 這里我們封裝一個列表,用來表示走迷宮的四個方向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),? # 表示向右走]??def maze_path(x1, y1, x2, y2):????stack = []????stack.append((x1, y1))????while?(len(stack) > 0):????????curNode = stack[-1]? # 當前節點是 stack最后一個位置????????if?curNode[0] == x2 and curNode[1] == y2:????????????return?True? # 如果有路則返回TRUE，沒有路則返回FALSE????????# x,y當前坐標，四個方向上下左右分別是：x-1,y? x+1,y? x, y-1? x,y+1????????for?dir?in?dirs:????????????nextNode = dir(curNode[0], curNode[1])????????????# 如果下一個節點能走????????????if?maze[nextNode[0]][nextNode[1]] == 0:????????????????stack.append(nextNode)????????????????maze[nextNode[0]][nextNode[1]] = 2? # 2表示已經走過了????????????????break????????else:? # 如果一個都找不到，就需要回退了????????????maze[nextNode[0]][nextNode[1]] = 2????????????stack.pop()? # 棧頂出棧，也就是回退?????else:????????print("沒有路")????????return?False??maze_path(1, 1, 8, 8)2，隊列——廣度優先搜索
思路：從下一個節點開始，尋找所有接下來能繼續走的點，繼續不斷尋找，直到找到出口。
使用隊列存儲當前正在考慮的節點
思路圖如下：
或者這樣：
可以通過如下方式理解：
代碼如下：
# _*_coding:utf-8_*_from?collections import deque?maze = [????[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],????[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],????[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],????[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],????[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],????[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],????[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],????[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],????[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],????[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]?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),? # 表示向右走]?def print_r(path):????real_path = []? # 用來存儲真實的路徑????i = len(path) - 1? # 用i指向path的最后一個下標????while?i >= 0:????????real_path.append(path[i][0:2])????????i = path[i][2]????real_path.reverse()?# 起點坐標(x1, y1)? 終點坐標(x2, y2)def maze_path_queue(x1, y1, x2, y2):????queue = deque()????path = []????# -1? 為當前path的路徑的下標????queue.append((x1, y1, -1))????while?len(queue) > 0:? # 當隊列不空時循環????????# append是從右邊加入的，popleft()從左邊出去????????cur_Node = queue.popleft()????????path.append(cur_Node)????????if?cur_Node[0] == x2 and cur_Node[1] == y2:????????????# 如果當前節點等于終點節點，則說明到達終點????????????print_r(path)????????????return?True?????????# 隊列是找四個方向，每個能走就繼續????????for?dir?in?dirs:????????????# 下一個方向的節點坐標????????????next_node = dir(cur_Node[0], cur_Node[1])????????????if?maze[next_node[0]][next_node[1]] == 0:????????????????queue.append((next_node[0], next_node[1], len(path) - 1))????????????????maze[next_node[0]][next_node[1]] = 2? # 標記為已走過????return?False? # 如果隊列結束了，空了，還沒找到路徑，則為FALSE??maze_path_queue(1, 1, 8, 8)總結
以上是生活随笔為你收集整理的python常用代码_Python常用算法学习(4) 数据结构（原理+代码）-最全总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 抖音下架课程虚拟商品：原因或为配合“苹果
- 下一篇： 别骂了！曝iOS 17将添加几个用户最需