創作不易，來了的客官點點關注，收藏，訂閱一鍵三連?😜
前言
程式=資料結構+演算法，演算法是數學理論和工程實作的雜糅，是一個十分有趣神奇的學問，搞懂演算法用另一種視角看編程，又會是一種全新的感受，如果你也在學習演算法，不妨跟主任萌新超差一起學習，拿下演算法！
系列文章目錄
python每日演算法 | 基數排序PK快速排序，手撕基數排序演算法！
python每日演算法 | 圖文+生動實體詳解桶排序
python每日演算法 | 揭開計數排序的秘密
概述
本期的內容將介紹資料結構基礎知識（一）：堆疊與佇列以及最經典的迷宮問題，
目錄
前言
系列文章目錄
概述
超超python每日演算法思維導圖
資料結構基礎知識
資料結構是什么？
資料結構的邏輯結構
線性結構
串列
堆疊
堆疊是什么
堆疊的基本操作
用python實作堆疊
堆疊的應用：括號匹配問題
佇列
佇列是什么
雙向佇列
佇列的實作方式：環形佇列
用python實作佇列
python佇列內置模塊：deque
佇列的應用：使用deque實作Linux的tail命令
迷宮問題
堆疊：深度優先搜索
代碼實作
佇列：廣度優先搜索
代碼實作
超超python每日演算法思維導圖
?
資料結構基礎知識
資料結構是什么？
資料結構是指相互之間存在著一種或多種關系的資料元素的集合和該集合中資料元素之間的關系組成，簡單來說，資料結構就是設計資料以何種方式組織并存盤在計算機中，
比如：串列、集合與字典等都是一種資料結構，
N.Wirth說過: “程式=資料結構+演算法”
資料結構的邏輯結構
資料結構按照其邏輯結構可分為線性結構、樹結構、圖結構，
線性結構
線性結構：資料結構中的元素存在一對一的相互關系，例如串列，
樹結構：資料結構中的元素存在一對多的相互關系，例如堆，
圖結構：資料結構中的元素存在多對多的相互關系
串列
串列（python中叫串列，其他語言稱陣列）是一種基本資料型別，
關于串列的問題：
串列中的元素是如何存盤的？
32位機器上一個整數占4個位元組，一個地址占4個位元組，64位一個地址占8個位元組，
現有如下串列：
| 1 | 2 | 3 | 4 | 5 |
以32位機器為例，陣列的存盤是這樣的：
若元素1的記憶體地址位100，則元素2的記憶體地址為104，以此類推,那么a[2]=100+2*4=108，
而對于串列，若1的地址為200，2-->300,3--88，串列是現通過查找地址，然后通過一個地址查找對應一個元素，
| 200 | 300 | 88 |
陣列和串列的區別：
1.陣列的元素型別需要一致，串列的元素型別不需要一致；
2.陣列的長度是固定的，python的串列可以無限長，
串列的基本操作：插入元素、洗掉元素……這些操作的時間復雜度是多少？
插入（insert）:O(n)，每次插入都將把前后的元素移動
洗掉（pop）：O(n)，每次洗掉之后會把后面的地址往前移
堆疊
堆疊是什么
堆疊(Stack)是一個資料集合，可以理解為只能在一端進行插入或洗掉操作的串列，
堆疊的特點：后進先出LIFO（last-in, first-out）
?
例如圖中的一摞書，最后一本數是最先進來的，同時也是最先出去的，
堆疊的概念：堆疊頂、堆疊底
?
堆疊的基本操作
進堆疊（壓堆疊）：push，（在一摞書上再放一本書）
出堆疊：pop（將一摞書最上面的書拿走）
取堆疊頂：gettop（我只看最上面的書是什么）
用python實作堆疊
堆疊的實作：使用一般的串列結構即可實作堆疊，
進堆疊：lst.append()
出堆疊：lst.pop()
取堆疊頂：lst[-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)
stack.push(3)
stack.push(4)
print(stack.pop())
print(stack)
print(stack.get_top())
# 輸出結果：
# 4
# <__main__.stack object at 0x000001CC63BBEFD0>
# 3堆疊的應用：括號匹配問題
括號匹配問題：給一個字串，其中包含小括號、中括號、大括號，求該字串中的括號是否匹配，
例如：
()()[]{}-->匹配
([{()}])-->匹配
[](-->不匹配
[(])-->不匹配
# 括號不匹配問題
"""
例如：()[][{()}]
1.堆疊頂"("，與接下來的")"與堆疊頂匹配，堆疊頂出堆疊；
2.接下來堆疊頂"[",與"]"匹配，"["出堆疊
3.堆疊頂："[",接下里"{"進堆疊，緊接著"("進堆疊，")"進堆疊并于"C"堆疊頂匹配，因此堆疊頂出堆疊
4.接下來"}"與堆疊頂"{"匹配，堆疊頂出堆疊
5."]"進堆疊，與堆疊頂"["匹配，堆疊頂出堆疊
"""
def brace_match(str1):
match_dict = {')':'(','}':'{',']':'['} # 建立匹配機制
stack = Stack()
for i in str1:
if i in {'(','[','{'}: # 左部分進堆疊
stack.push(i)
else: # i in {')','}',']'}
if stack.is_empty():
return False
elif stack.get_top() == match_dict[i]:
stack.pop()
else: # 進堆疊字符與堆疊頂不匹配
return False
if stack.is_empty:
return True
else:
return False
print(brace_match("{{[()]}}"))
# 輸出：
# True
print(brace_match("{{[()]{()}}}"))
# 輸出：
# True
print(brace_match("{[)]{()}}"))
# 輸出
# False佇列
佇列是什么
佇列(Queue)：佇列是一個資料集合，僅允許在串列的一端進行插入，另一端進行洗掉，
進行插入的一端稱為隊尾(rear)，插入動作稱為進隊或入隊
進行洗掉的一端稱為隊頭(front)，洗掉動作稱為出隊
佇列的性質：先進先出(First-in, First-out)
?
雙向佇列
雙向佇列的兩端都支持進隊和出隊操作，雙向佇列的基本操作：
隊首進隊
隊首出隊
隊尾進隊
隊尾出隊
佇列的實作方式：環形佇列
?
如圖所示位環形佇列的出隊進隊程序，rear=front是隊空，
1.A進隊，rear-->+1
2.BCDEFGH進隊， rear依次加1
3.ABCD出隊，front-->5,隊首-->F,隊尾-->H
4.IJKM進隊-->near以此加1
5.當P進隊后，發生隊滿，（為什么rear和front沒有重合？為了確保是隊慷訓是隊滿，）
因此隊滿-->rear + 1= front, 對空：rear = front
環形佇列：當隊尾指標front == Maxsize（佇列的長度） - 1時，再前進一個位置就自動到0.
隊首指標前進1：front = (front + 1) % MaxSize
隊尾指標前進1：rear = (rear + 1) % MaxSize
隊空條件：rear == front
隊滿條件：(rear + 1) % MaxSize == front
用python實作佇列
class Queue:
def __init__(self,size=100): #佇列長度為100
self.size = size
self.queue = [0 for i in range(size)]
self.rear = 0 # 隊尾指標
self.front = 0 # 對首指標
def push(self,element): # 進隊
if not self.is_filled(): # 確保隊不滿
self.rear = (self.rear+1) % self.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is filled")
def pop(self): # 出隊
if not self.is_empty(): # 確保隊不空
self.front = (self.front + 1) % self.size
return self.queue[self.front]
else:
raise IndexError("Queue is empty.")
def is_empty(self): # 判斷隊空
return self.rear == self.front
def is_filled(self): # 判斷隊滿
return (self.rear + 1) % self.size == self.front
q = Queue(5)
for i in range(4):
q.push(i)
print(q.pop())
q.push(13)
print(q.pop())
q2 = Queue(5)
for i in range(5):
q.push(i)
print(q.is_filled())
# 輸出結果
# 0
# 1
# IndexError: Queue is filledpython佇列內置模塊：deque
佇列的內置模塊：deque
from collections import deque
q = deque()
q.append(1) # 隊尾進隊
print(q.popleft()) # 隊首出隊
# 輸出結果
# 1
# print(q.popleft()) # 隊空情況
# 輸出結果
# IndexError: pop from an empty deque
q = deque([1,2,3,4) # 長度為4的佇列
q.append(5) # 隊尾進隊
print(q)
print(q.popleft()) # 隊首出隊
# 輸出結果
# deque([1, 2, 3, 4, 5], maxlen=5)
# 1
# 用于雙向佇列
# q.appendleft() # 隊首進隊
# q.pop() # 隊尾出隊佇列的應用：使用deque實作Linux的tail命令
test:
“
cc
1314
hi
I am chaochao
follow chaochao,day day up together
“
def tail(n):
with open("test",'r') as f:
q = deque(f,n)
return q
# print(tail(1))
# 輸出結果
# deque(['chaochao'], maxlen=1)
for line in tail(3):
print(line,end="")
# 輸出結果
# hi
# I am chaochao
# follow chaochao,day day up together迷宮問題
?
給一個二維串列，表示迷宮（0表示通道，1表示圍墻），給出演算法，求一條走出迷宮的路徑，
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]
]
堆疊：深度優先搜索
回溯法思路：（一條路走到黑）從一個節點開始，任意找下一個能走的點，當找不到能走的點時，退回上一個點尋找是否有其他方向的點，使用堆疊存盤當前路徑，
代碼實作
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]
]
# 四個方向的表示
dir_lst = [
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] # 當前坐標，串列形式
# 判斷是否已經走到了終點
if curNode[0] == x2 and curNode[1]== y2:
for i in stack:
print(i)
return True
"""
四個方向表示：
左-->(x-1,y),右-->(x+1,y),上-->(x,y-1)，下-->(x,y+1)
"""
for dir in dir_lst:
nextNode = dir(curNode[0],curNode[1])
# 如果下一個點能走
if maze[nextNode[0]][nextNode[1]] == 0:
stack.append(nextNode)
# 標記走過的點，如 此值為2代表已經走過
maze[nextNode[0]][nextNode[1]] = 2
break # 找到可以走的點就break
else:
maze[nextNode[0]][nextNode[1]] = 2
stack.pop() # 堆疊頂出堆疊，回溯隨后回圈找可以走的點
else:
print("無路可走")
return False
# 驗證
maze_path(1,1,8,8)
# 輸出結果
# (1, 1)
# (2, 1)
# (3, 1)
# (4, 1)
# (5, 1)
# (5, 2)
# (5, 3)
# (6, 3)
# (6, 4)
# (6, 5)
# (7, 5)
# (8, 5)
# (8, 6)
# (8, 7)
# (8, 8)佇列：廣度優先搜索
思路：從一個節點開始，尋找所有接下來能繼續走的點，繼續不斷尋找，直到找到出口，使用佇列存盤當前正在考慮的節點，佇列存盤的是當前的點，
?
對列如下存盤：
| 當前位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 前一個點位置 | -1（默認） | 0 | 1 | 2（3讓它來） | 2（3讓它來） | 3（4讓它來的） | 4（5讓他來的） |
代碼實作
from collections import deque
maze2 = [
[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):
curNode = path[-1] # 最后一個節點
realpath = [] # 路徑
while curNode[2] != -1: # 即上一個節點部署終點時
realpath.append(curNode[0:2])
curNode = path[curNode[2]]
realpath.append(curNode[0:2]) # 起點
realpath.reverse() # 倒敘串列
for i in realpath:
print(i)
def maze_path_queue(x1,y1,x2,y2):
queue = deque()
queue.append((x1,y1,-1))
path = [] # 出隊的節點放到path串列
while len(queue) > 0: # 隊不空時回圈
curNode = queue.popleft()
path.append(curNode)
if curNode[0] == x2 and curNode[1] == y2: # 到達終點
print_r(path) # 到達終點，并輸出路徑
return True
for dir in dirs:
nextNode = dir(curNode[0],curNode[1])
if maze2[nextNode[0]][nextNode[1]] == 0:
queue.append((nextNode[0],nextNode[1],len(path[-1])-1)) # 后續節點進隊，記錄哪個節點帶她來
maze2[nextNode[0]][nextNode[1]] = 2 # 標記此點已經走過
else:
print("無路可走")
return False
maze_path_queue(1,1,6,8)創作不易，客官點個贊，評論一下吧！超超和你一起加油?😜
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/299989.html
標籤：python