1.概念

數(shù)據(jù)結構是計算機科學中的一個核心概念，它是指數(shù)據(jù)的組織、管理和存儲方式，以及數(shù)據(jù)元素之間的關系。數(shù)據(jù)結構通常用于允許高效的數(shù)據(jù)插入、刪除和搜索操作。

數(shù)據(jù)結構大致分為幾大類：

線性結構：數(shù)組、鏈表、棧、隊列等。

非線性結構：樹、二叉樹、堆、圖等。

散列：哈希表。

索引：B樹、B+樹等。

2.常見數(shù)據(jù)結構

2.1 棧

棧（stack），它是一種運算受限的線性表，遵循后進先出（Last In First Out，LIFO）原則的數(shù)據(jù)結構。

• LIFO(last in first out)表示就是后進入的元素, 第一個彈出?？臻g. 類似于自動餐托盤, 最后放上的托盤, 往往先把拿出去使用.

• 其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。

• 向一個棧插入新元素又稱作進棧、入?；驂簵?#xff0c;它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；

• 從一個棧刪除元素又稱作出?；蛲藯?#xff0c;它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

棧常見的操作

• push(element): 添加一個新元素到棧頂位置.

• pop()：移除棧頂?shù)脑?#xff0c;同時返回被移除的元素。

• peek()：返回棧頂?shù)脑?#xff0c;不對棧做任何修改（這個方法不會移除棧頂?shù)脑?#xff0c;僅僅返回它）。

• isEmpty()：如果棧里沒有任何元素就返回true，否則返回false。

• clear()：移除棧里的所有元素。

• size()：返回棧里的元素個數(shù)。這個方法和數(shù)組的length屬性很類似。

2.1.1 入棧

2.1.2 出棧

2.1.3 代碼分析

1. 使用數(shù)組來模擬棧

2. 定義一個 空數(shù)組

3. 入棧的操作，當有數(shù)據(jù)加入到棧時，判斷數(shù)組長度是否達到閾值，是則拋棧已滿的異常，否則將數(shù)據(jù)追加到數(shù)組的尾部;

4. 出棧的操作，判斷棧是否空，是則拋棧已空的異常，否則從數(shù)組尾部移除一個數(shù)據(jù)，并返回該數(shù)據(jù);

代碼實現(xiàn)：

class Stack:def __init__(self, size):self.items = []self.size = size
?def isFull(self):return len(self.items) == self.size
?def push(self, element):if self.isFull():raise Exception('stack is full')
?self.items.append(element)
?def pop(self):if self.isEmpty():raise Exception('stack is empty')
?return self.items.pop()
?def peek(self):if self.isEmpty():raise Exception('stack is empty')return self.items[-1]
?def isEmpty(self):return len(self.items) == 0
?def clear(self):self.items.clear()
?
?
if __name__ == '__main__':stack = Stack(20)stack.push(1)stack.push(2)print(stack.peek())

2.2 鏈表

鏈表是一條相互鏈接的數(shù)據(jù)節(jié)點表。每個節(jié)點由兩部分組成：數(shù)據(jù)和指向下一個節(jié)點的指針。

2.1 鏈表的優(yōu)缺點

優(yōu)點：

1. 物理存儲單元上非連續(xù)，而且采用動態(tài)內(nèi)存分配，能夠有效的分配和利用內(nèi)存資源；

2. 節(jié)點刪除和插入簡單，不需要內(nèi)存空間的重組。

缺點：

1. 不能進行索引訪問，只能從頭結點開始順序查找；

2. 數(shù)據(jù)結構較為復雜，需要大量的指針操作，容易出錯。

2.2 單向鏈表

2.2.1 插入

尾部插入

從頭結點開始逐個遍歷鏈表，直到找到next=null，表示為最后一個節(jié)點，再將最后節(jié)點的next指向新增節(jié)點。

頭部插入

如果頭節(jié)點的next=null表示鏈表為空，直接將頭節(jié)點的next指向新增節(jié)點

如果頭節(jié)點的next!=null，表示頭節(jié)點后已存在后續(xù)節(jié)點，需要將新增節(jié)點插入到頭節(jié)點和后續(xù)節(jié)點中間：

1.獲取頭節(jié)點的后續(xù)節(jié)點，定義一個臨時節(jié)點，將該節(jié)點指向臨時節(jié)點

2.將頭節(jié)點的next指向新增節(jié)點

3.新增節(jié)點的next指向臨時節(jié)點

2.2.2 遍歷

從頭結點開始，通過next遍歷，直到next=null

2.2.3 刪除

2.2.4 代碼實現(xiàn)

class Node:def __init__(self, data=None):if data is not None:self.data = dataself.next = None
?
?
class LinkedList:def __init__(self):head = Node()self.head = head
?def append(self, data):new_node = Node(data)# 如果鏈表為空，則在頭部后插入if self.head.next is None:self.head.next = new_nodeelse:node = self.head.nextwhile node.next is not None:node = node.nextnode.next = new_node
?def prepend(self, data):new_node = Node(data)if self.head.next is None:self.head.next = new_nodeelse:new_node.next = self.head.nextself.head.next = new_node
?def remove(self, data):if self.head.next is None:raise Exception('Linked List is empty')node = self.head.nextwhile node.data != data:node = node.nextnode.next = node.next.next
?def display(self):node = self.head.nextwhile True:print(node.data)if node.next is None:breaknode = node.next
?
?
if __name__ == '__main__':list = LinkedList()list.append(1)list.append(2)list.prepend(3)list.display()

2.3 隊列

隊列(Queue)，它是一種運算受限的線性表,先進先出(FIFO First In First Out)

• 隊列是一種受限的線性結構

• 受限之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作

Python標準庫中的queue模塊提供了多種隊列實現(xiàn)，包括普通隊列、雙端隊列、優(yōu)先隊列等。

2.3.1 普通隊列

queue.Queue 是 Python 標準庫 queue 模塊中的一個類，適用于多線程環(huán)境。它實現(xiàn)了線程安全的 FIFO（先進先出）隊列。

案例：

import queue
?
q = queue.Queue()
q.put(1)
q.put(3)
q.put(2)
?
print(q.qsize())
print(q.get())
print(q.get())
print(q.get())

2.3.2 雙端隊列

雙端隊列（Deque，Double-Ended Queue）是一種具有隊列和棧性質(zhì)的數(shù)據(jù)結構，它允許我們在兩端進行元素的添加（push）和移除（pop）操作。在Python中，雙端隊列可以通過collections模塊中的deque類來實現(xiàn)。

deque是一個雙端隊列的實現(xiàn)，它提供了在兩端快速添加和移除元素的能力。

案例：

from collections import deque
?
?
q = deque()
?
q.append(1)
q.append(2)
q.appendleft(3)
q.appendleft(4)
?
print(q.pop())
print(q.popleft())

當結合使用appendleft和popleft時，你實際上是在實現(xiàn)一個棧（Stack）的數(shù)據(jù)結構，因為棧是后進先出（LIFO）的，而這兩個操作正好模擬了棧的“壓?！焙汀皬棗！毙袨?。append和pop結合使用同理。

2.3.3 優(yōu)先隊列

優(yōu)先隊列（Priority Queue）是一種特殊的隊列，其中的元素按照優(yōu)先級進行排序。優(yōu)先級最高的元素總是最先出隊。Python 標準庫中提供了 queue.PriorityQueue 和 heapq 模塊來實現(xiàn)優(yōu)先隊列。

queue.PriorityQueue

queue.PriorityQueue 是 Python 標準庫 queue 模塊中的一個類，適用于多線程環(huán)境。它實現(xiàn)了線程安全的優(yōu)先隊列。

案例：

import queue
?
q = queue.PriorityQueue()
# 向隊列中添加元素，元素是一個元組 (priority, item)，其中 priority 是優(yōu)先級，item 是實際的數(shù)據(jù)
q.put((1,'item1'))
q.put((3,'item3'))
q.put((2,'item2'))
?
print(q.get())
print(q.get())
print(q.get())

heapq

heapq 模塊是 Python 標準庫中的一個模塊，提供了基于堆的優(yōu)先隊列實現(xiàn)。heapq 模塊不是線程安全的，適用于單線程環(huán)境。

案例：

import heapq
?
# 創(chuàng)建一個列表作為堆
heap = []
?
# 向堆中添加元素，元素是一個元組 (priority, item)
heapq.heappush(heap, (3, 'Task 3'))
heapq.heappush(heap, (1, 'Task 1'))
heapq.heappush(heap, (2, 'Task 2'))
?
# 從堆中取出元素
print(heapq.heappop(heap)) ?# 輸出: (1, 'Task 1')
print(heapq.heappop(heap)) ?# 輸出: (2, 'Task 2')
print(heapq.heappop(heap)) ?# 輸出: (3, 'Task 3')

2.4 樹

2.4.1 概念和術語

模擬樹結構

• 公司組織架構:

  

• 紅樓夢家譜

  

• 我們再將里面的數(shù)據(jù)移除, 僅僅抽象出來結構, 那么就是我們要學習的樹結構

  

術語

在描述樹的各個部分的時候有很多術語。

• 為了讓介紹的內(nèi)容更容易理解, 需要知道一些樹的術語.

• 不過大部分術語都與真實世界的樹相關, 或者和家庭關系相關(如父節(jié)點和子節(jié)點), 所以它們比較容易理解.

我們先來看一下樹的結構

樹的定義:

• 樹（Tree）: n（n≥0）個結點構成的有限集合。

  • 當n=0時，稱為空樹；

  • 對于任一棵非空樹（n> 0），它具備以下性質(zhì)：

  • 樹中有一個稱為“根（Root）”的特殊結點，用 root 表示；

  • 其余結點可分為m(m>0)個互不相交的有限集T1，T2，... ，Tm，其中每個集合本身又是一棵樹，稱為原來樹的“子樹（SubTree）”

  注意:

  • 子樹之間不可以相交

  • 除了根結點外，每個結點有且僅有一個父結點；

  • 一棵N個結點的樹有N-1條邊。

樹的術語:

• 1.結點的度（Degree）：結點的子樹個數(shù).

• 2.樹的度：樹的所有結點中最大的度數(shù). (樹的度通常為結點的個數(shù)N-1)

• 3.葉子結點（Leaf）：度為0的結點. (也稱為葉子結點)

• 4.父結點（Parent）：有子樹的結點是其子樹的根結點的父結點

• 5.子結點（Child）：若A結點是B結點的父結點，則稱B結點是A結點的子結點；子結點也稱孩子結點。

• 6.兄弟結點（Sibling）：具有同一父結點的各結點彼此是兄弟結點。

• 7.路徑和路徑長度：從結點n1到nk的路徑為一個結點序列n1 , n2,… , nk, ni是 ni+1的父結點。路徑所包含邊的個數(shù)為路徑的長度。

• 8.結點的層次（Level）：規(guī)定根結點在1層，其它任一結點的層數(shù)是其父結點的層數(shù)加1。

• 9.樹的深度（Depth）：樹中所有結點中的最大層次是這棵樹的深度。

2.4.2 二叉樹

2.4.2.1 概念

二叉樹的定義

• 二叉樹可以為空, 也就是沒有結點.

• 若不為空，則它是由根結點和稱為其左子樹TL和右子樹TR的兩個不相交的二叉樹組成。

二叉樹有五種形態(tài):

• 注意c和d是不同的二叉樹, 因為二叉樹是有左右之分的.

2.4.2.2 特性

• 二叉樹有幾個比較重要的特性, 在筆試題中比較常見:

  • 一個二叉樹第 i 層的最大結點數(shù)為：2^(i-1), i >= 1;

  • 深度為k的二叉樹有最大結點總數(shù)為： 2^k - 1, k >= 1;

  • 對任何非空二叉樹 T，若n0表示葉結點的個數(shù)、n2是度為2的非葉結點個數(shù)，那么兩者滿足關系n0 = n2 + 1。

    

2.4.2.3 特殊的二叉樹

滿二叉樹(Full Binary Tree）

• 在二叉樹中, 除了最下一層的葉結點外, 每層節(jié)點都有2個子結點, 就構成了滿二叉樹.

完全二叉樹(Complete Binary Tree)

• 除二叉樹最后一層外, 其他各層的節(jié)點數(shù)都達到最大個數(shù).

• 且最后一層從左向右的葉結點連續(xù)存在, 只缺右側(cè)若干節(jié)點.

• 滿二叉樹是特殊的完全二叉樹.

• 下面不是完全二叉樹, 因為D節(jié)點還沒有右結點, 但是E節(jié)點就有了左右節(jié)點.

  

2.4.2.4 二叉樹的存儲

二叉樹的存儲常見的方式是鏈表.

鏈表存儲:

• 二叉樹最常見的方式還是使用鏈表存儲.

• 每個結點封裝成一個Node, Node中包含存儲的數(shù)據(jù), 左結點的引用, 右結點的引用.

2.4.2.5 二叉樹遍歷

前序遍歷（Pre-order Traversal）、中序遍歷（In-order Traversal）和后序遍歷（Post-order Traversal）是二叉樹的三種基本遍歷方式。

遍歷規(guī)則：

前序遍歷，按照以下順序訪問節(jié)點：根節(jié)點、左子樹、右子樹。

中序遍歷，按照以下順序訪問節(jié)點：左子樹、根節(jié)點、右子樹。

后序遍歷，按照以下順序訪問節(jié)點：左子樹、右子樹、根節(jié)點。

2.4.3 二叉查找樹

二叉查找樹（Binary Search Tree, BST）是一種特殊的二叉樹，它具有以下性質(zhì)：

1. 每個節(jié)點都有一個鍵值（key）。

2. 對于每個節(jié)點，其左子樹中的所有節(jié)點的鍵值都小于該節(jié)點的鍵值。

3. 對于每個節(jié)點，其右子樹中的所有節(jié)點的鍵值都大于該節(jié)點的鍵值。

4. 左子樹和右子樹也分別是二叉查找樹。

5. 二叉查找樹不允許出現(xiàn)鍵值相等的結點。

二叉查找樹的主要操作包括插入、刪除和遍歷。代碼實現(xiàn)如下：

2.4.3.1 創(chuàng)建二叉查找樹節(jié)點

class TreeNode:def __init__(self, key):self.key = keyself.left = Noneself.right = None

• key: 節(jié)點的鍵值。

• left: 指向左子節(jié)點的指針。

• right: 指向右子節(jié)點的指針。

2.4.3.2 創(chuàng)建二叉查找樹類

class BinarySearchTree:def __init__(self):self.root = None

• root: 指向二叉搜索樹的根節(jié)點。初始時為 None。

2.4.3.3 插入節(jié)點

插入操作的步驟：

1. 如果樹為空：直接將新節(jié)點作為根節(jié)點。

2. 如果樹不為空：

   • 從根節(jié)點開始，根據(jù)新節(jié)點的鍵值與當前節(jié)點的鍵值的比較結果，決定向左子樹還是右子樹移動。

   • 如果新節(jié)點的鍵值小于當前節(jié)點的鍵值，如果當前節(jié)點沒有左子樹，則將新節(jié)點插入到當前節(jié)點的左子樹，否則向左子樹移動。

   • 如果新節(jié)點的鍵值大于當前節(jié)點的鍵值，如果當前節(jié)點沒有右子樹，則將新節(jié)點插入到當前節(jié)點的右子樹，否則向右子樹移動。

   • 重復上述步驟，直到找到一個空位置，將新節(jié)點插入到該位置。

def insert(self, key):if self.root is None:self.root = TreeNode(key)else:self._insert(self.root, key)
?
def _insert(self, node, key):if key < node.key:if node.left is None:node.left = TreeNode(key)else:self._insert(node.left, key)elif key > node.key:if node.right is None:node.right = TreeNode(key)else:self._insert(node.right, key)

• insert(key): 公開的插入方法。如果樹為空，則創(chuàng)建一個新節(jié)點作為根節(jié)點；否則，調(diào)用 _insert 方法進行遞歸插入。

• _insert(node, key): 遞歸插入方法。根據(jù)鍵值的大小，遞歸地在左子樹或右子樹中插入新節(jié)點。

2.4.3.4 查找節(jié)點

def search(self, key):return self._search(self.root, key)
?
def _search(self, node, key):if node is None or node.key == key:return nodeif key < node.key:return self._search(node.left, key)return self._search(node.right, key)

2.4.3.5 刪除節(jié)點

刪除邏輯：

1.遞歸查找待刪除節(jié)點

• 如果待刪除節(jié)點的鍵值小于當前節(jié)點的鍵值，遞歸地在左子樹中查找并刪除。

• 如果待刪除節(jié)點的鍵值大于當前節(jié)點的鍵值，遞歸地在右子樹中查找并刪除。

2.找到待刪除節(jié)點

刪除操作的步驟可以分為以下幾種情況：

1. 待刪除節(jié)點是葉子節(jié)點（沒有子節(jié)點）：直接刪除該節(jié)點。

2. 待刪除節(jié)點只有一個子節(jié)點：用其子節(jié)點替換該節(jié)點。

3. 待刪除節(jié)點有兩個子節(jié)點：

   • 找到右子樹中的最小節(jié)點（即后繼節(jié)點）。

   • 用后繼節(jié)點的鍵值替換待刪除節(jié)點的鍵值。

   • 刪除后繼節(jié)點（后繼節(jié)點要么是葉子節(jié)點，要么只有一個右子節(jié)點）。

假設我們有以下二叉搜索樹：

 ? ? ?  50/  \30 ?  70/  \  /  \20  40 60  80

刪除節(jié)點 20

1. 找到鍵值為 20 的節(jié)點。

2. 該節(jié)點是葉子節(jié)點，直接刪除。

刪除后的樹：

 ? ? ?  50/  \30 ?  70\  /  \40 60  80

刪除節(jié)點 30

1. 找到鍵值為 30 的節(jié)點。

2. 該節(jié)點有一個右子節(jié)點 40，用 40 替換 30。

刪除后的樹：

 ? ? ?  50/  \40 ?  70/  \60  80

刪除節(jié)點 50

1. 找到鍵值為 50 的節(jié)點。

2. 該節(jié)點有兩個子節(jié)點，找到右子樹中的最小節(jié)點 60（即后繼節(jié)點）。

3. 用 60 替換 50。

4. 刪除右子樹中的 60。

刪除后的樹：

 ? ? ?  60/  \40 ?  70\80

def delete(self, key):self.root = self._delete(self.root, key)
?
def _delete(self, node, key):if node is None:return node
?if key < node.key:node.left = self._delete(node.left, key)elif key > node.key:node.right = self._delete(node.right, key)else:# 找到要刪除的節(jié)點# 情況 1: 節(jié)點是葉子節(jié)點if node.left is None and node.right is None:return None# 情況 2: 節(jié)點只有一個子節(jié)點elif node.left is None:return node.rightelif node.right is None:return node.left# 情況 3: 節(jié)點有兩個子節(jié)點temp = self._min_value_node(node.right)node.key = temp.keynode.right = self._delete(node.right, temp.key)
?return node
?
def _min_value_node(self, node):current = nodewhile current.left is not None:current = current.leftreturn current

2.4.3.6 中序遍歷

先遍歷左子樹，然后訪問當前節(jié)點，最后遍歷右子樹。

def inorder_traversal(self):result = []self._inorder_traversal(self.root, result)return result
?
def _inorder_traversal(self, node, result):if node:self._inorder_traversal(node.left, result)result.append(node.key)self._inorder_traversal(node.right, result)

2.4.3.7 前序遍歷

先訪問根節(jié)點、然后遍歷左子樹、最后遍歷右子樹。

def preorder_search(self):result = []if self.root is None:return Noneself._preorder_search(self.root, result)return result
?
def _preorder_search(self,node,result):if node is None:return Noneresult.append(node.key)self._preorder_search(node.left,result)self._preorder_search(node.right,result)