【數據結構】

什么是數據結構？

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

PS:“程序=數據結構+算法”

列表：

在其他編程語言中稱為“數組”，是一種基本的數據結構類型。

列表是一種線性表，是固定長度的。

一個整數，在32位機器中，占用4個字節，在64位機器中，占用8個字節。

列表在內存中開得格子要一樣大：

第一是為了存地址，地址是一樣大得。64位機器是一個格子占用8個字節。

第二是為了查找，如li[2] 在64位機器中等于li+2*8

列表和數組有兩種不同：

元素類型不同

可以無限append。如果格子空間不夠，再開一個以前兩倍的空間

關于列表的問題：

列表中元素是如何存儲的？

是連續存儲得，地址在內存中是連續得。

列表提供了哪些基本的操作？

append、pop、remove、insert、index、直接通過下標查找。

這些操作的時間復雜度是多少？

按下標查詢，復雜度O(1)

插入(insert)，復雜度O(n)

刪除(remove)，復雜度O(n) , pop()是O(1), pop(-2)是O(n)

添加(append), 復雜度O(1)

查找(index),復雜度O(n)

棧：

棧(Stack)是一個數據集合，可以理解為只能在一端進行插入或刪除操作的列表。

棧的特點：后進先出(last-in, first-out)

棧的概念：棧頂、棧底

棧的基本操作：

進棧(壓棧)：push

出棧：pop

取棧頂：gettop

棧的Python實現

不需要自己定義，使用列表結構即可。

進棧函數：append

出棧函數：pop

查看棧頂函數：li[-1]

棧的應用：

一、word操作：

Ctrl + C 之后，會先從撤銷棧pop刪除，append重做棧

Ctr + Y 之后，會把重做棧中pop刪除，append撤銷棧。

只加值得時候，只有撤銷棧。

二、括號匹配問題

括號匹配問題：給一個字符串，其中包含小括號、中括號、大括號，求該字符串中的括號是否匹配。

例如：

()()[]{} 匹配

([{()}]) 匹配

[]( 不匹配

[(]) 不匹配

代碼實現：

def check_kuohao(s):

stack = []

for char in s:

if char in {'(','[','{'}:

stack.append(char)

elif char == ')':

if len(stack) > 0 and stack[-1] == '(':

stack.pop()

else:

return False

elif char == ']':

if len(stack) > 0 and stack[-1] == '[':

stack.pop()

else:

return False

elif char == '}':

if len(stack) > 0 and stack[-1] == '{':

stack.pop()

else:

return False

if len(stack) == 0:

return True

else:

return False

s="{[()]}"

print(check_kuohao(s))

三、迷宮問題

給一個二維列表，表示迷宮(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,1,1,1,1,1],

[1,1,0,0,0,0,0,0,0,1],

[1,1,1,1,1,1,1,1,1,1]

]

解決思路：

在一個迷宮節點(x,y)上，可以進行四個方向的探查：maze[x-1][y], maze[x+1][y], maze[x][y-1], maze[x][y+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,1,1,1,1,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 mgmaze(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 p in stack:

print(p)

return True

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:

stack.pop()

maze[curNode[0]][curNode[1]] = 2 #死路一條

return False

print(mgmaze(1,1,8,8))

隊列：

隊列(Queue)是一個數據集合，僅允許在列表的一端進行插入，另一端進行刪除。

進行插入的一端稱為隊尾(rear)，插入動作稱為進隊或入隊。

進行刪除的一端稱為隊頭(front)，刪除動作稱為出隊

隊列的性質：先進先出(First-in, First-out)

雙向隊列：隊列的兩端都允許進行進隊和出隊操作。

隊列能否簡單用列表實現？為什么？

不能

使用方法：from collections import deque

創建隊列：queue = deque(li)

進隊：append

出隊：popleft

雙向隊列隊首進隊：appendleft

雙向隊列隊尾進隊：pop

隊列的實現原理：

初步設想：列表+兩個下標指針

創建一個列表和兩個變量，front變量指向隊首，rear變量指向隊尾。初始時，front和rear都為0。

進隊操作：元素寫到li[rear]的位置，rear自增1。

出隊操作：返回li[front]的元素，front自減1。

這種實現的問題？

隊列的實現原理——環形隊列

改進方案：將列表首尾邏輯上連接起來。

環形隊列：當隊尾指針front == Maxsize + 1時，再前進一個位置就自動到0。

實現方式：求余數運算

隊首指針前進1：front = (front + 1) % MaxSize

隊尾指針前進1：rear = (rear + 1) % MaxSize

隊空條件：rear == front

隊滿條件：(rear + 1) % MaxSize == front

隊列的應用——迷宮問題

思路：從一個節點開始，尋找所有下面能繼續走的點。繼續尋找，直到找到出口。

方法：創建一個空隊列，將起點位置進隊。在隊列不為空時循環：出隊一次。如果當前位置為出口，則結束算法；否則找出當前方塊的4個相鄰方塊中可走的方塊，全部進隊。

代碼實現：

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,1,1,1,1,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 mgpath(x1, y1, x2, y2):

queue = deque()

path = []

queue.append((x1, y1, -1))

while len(queue) > 0:

curNode = queue.popleft()

path.append(curNode)

if curNode[0] == x2 and curNode[1] == y2:

#到達終點

print(path)

return True

for dir in dirs:

nextNode = dir(curNode[0], curNode[1])

if maze[nextNode[0]][nextNode[1]] == 0: #找到下一個方塊

queue.append((*nextNode, len(path) - 1))

maze[nextNode[0]][nextNode[1]] = -1 # 標記為已經走過

return False

集合與字典

集合是對值進行哈希，字典是對鍵進行哈希。它們兩個進行查找得時候，就比列表快。

md5就是一種哈希算法。

集合與字典都是通過哈希表查找。

哈希表(Hash Table，又稱為散列表)，是一種線性表的存儲結構。通過把每個對象的關鍵字k作為自變量，通過一個哈希函數h(k)，將k映射到下標h(k)處，并將該對象存儲在這個位置。

例如：數據集合{1,6,7,9}，假設存在哈希函數h(x)使得h(1) = 0, h(6) = 2, h(7) = 4, h(9) = 5，那么這個哈希表被存儲為[1,None, 6, None, 7, 9]。

當我們查找元素6所在的位置時，通過哈希函數h(x)獲得該元素所在的下標(h(6) = 2)，因此在2位置即可找到該元素。

哈希函數種類有很多，這里不做深入研究。

哈希沖突或者哈希碰撞：由于哈希表的下標范圍是有限的，而元素關鍵字的值是接近無限的，因此可能會出現h(102) = 56， h(2003) = 56這種情況。此時，兩個元素映射到同一個下標處，造成哈希沖突。

解決哈希沖突：

在Python中的字典：a = {'name': 'Alex', 'age': 18, 'gender': 'Man'}

使用哈希表存儲字典，通過哈希函數將字典的鍵映射為下標。假設h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4，則哈希表存儲為[None, 18, None, ’Alex’, ‘Man’]

在字典鍵值對數量不多的情況下，幾乎不會發生哈希沖突，此時查找一個元素的時間復雜度為O(1)。

補充：

數據存儲分為物理存儲方式和邏輯存儲方式。

數據的物理結構包括順序存儲的存儲和鏈式存儲的存儲。

線性結構

數據結構的的邏輯結構分為線性結構和數據結構。線性結構是n個數據元素的有序(次序)集合。

線性結構是一個有序數據元素的集合，數據元素之間存在著“一對一”的線性關系的數據結構。通俗一點就是一個數據結構只有一個前置節點和一個后置節點得時候，就是線性數據結構。

非線性結構的邏輯特征是一個結點元素可能對應多個直接前驅和多個后繼。通俗一點就是一個數據結構有多個前置節點和多個后置節點。

樹形數據結構，就是由一個前置數據節點，多個后置節點。

圖形數據結構，有多個前置節點和多個后置節點。

常用的線性結構有：線性表，棧，隊列，雙隊列，數組，串。

常用的非線性結構有：二維數組，多維數組，廣義表，樹(二叉樹)，圖。

例子：

傳統文本(例如書籍中的文章和計算機的文本文件)都是線性結構，閱讀是需要注意順序閱讀，而超文本則是一個非線性結構。在制作文本時，可將寫作素材按內部聯系劃分成不同關系的單元，然后用制作工具將其組成一個網型結構。閱讀時，不必按線性方式順序往下讀，而是有選擇的閱讀自己感興趣的部分。

在超文本文件中，可以用一些單詞，短語或圖像作為連接點。這些連接點通常同其他顏色顯示或加下劃線來區分，這些形式的文件就成為超文本文件。通過非線性結構，可能實現頁面任意跳轉。

有一個以上根結點的數據結構一定是非線性結構。

總結

以上是生活随笔為你收集整理的python什么是数据结构_〖Python〗-- 数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。