該書隨書源碼的語言為C；我參考書中內容和配套源碼，寫了一套Python格式的配套源碼。這套配套源碼並非直接翻譯C語言的配套源碼，而是結合我的理解略作了修改。
SinglyLinkedNode 單鏈表結點
<code>class SinglyLinkedNode:
"""單鏈表結點"""
__slots__ = "value", "next" # 使用__slots__減少內存佔用
def __init__(self, value, next: "SinglyLinkedNode" = None):
self.value = value # 數據域
self.next = next # 指針域
def __str__(self):
return str(self.value) + "->" + str(self.next)/<code>SinglyLinkedOperate 單鏈表的基本操作：讀取、插入、刪除、整表創建
<code> from typing import List from LinkedList.SinglyLinkedNode import SinglyLinkedNode # 單鏈表的讀取(給定讀取座標) def get_node_by_index(head: "SinglyLinkedNode", index: int): for _ in range(index + 1): # 尋找第index個結點(從0開始計數)的前一個結點，如果鏈表長度不足則不刪除 if not head.next: return None head = head.next else: return head.value # 單鏈表的添加操作(在給定結點後添加) def add_node_by_prev(prev: "SinglyLinkedNode", value): node = SinglyLinkedNode(value) # 使用給定值初始化新結點(node) node.next = prev.next # 令新結點(node)指向給定結點(prev)的下一個結點 prev.next = node # 令給定結點(prev)指向新結點(node) # 單鏈表的添加操作(給定插入座標) def add_node_by_index(head: "SinglyLinkedNode", index: int, value): idx = -1 # 因為從頭結點開始遍歷，故使用頭結點的座標-1 while idx < index and head.next: # 尋找第index個結點(從0開始計數)，如果鏈表長度不足則添加在鏈表尾部 head = head.next idx += 1 add_node_by_prev(head, value) # 在第index個結點後添加新結點 # 單鏈表的刪除操作(在給定結點後刪除) def delete_node_by_prev(prev: "SinglyLinkedNode"): prev.next = prev.next.next # 令給定結點(prev)直接指向被刪除結點的下一個結點 # 單鏈表的刪除操作(給定刪除座標) def delete_node_by_index(head: "SinglyLinkedNode", index: int): for _ in range(index): # 尋找第index個結點(從0開始計數)的前一個結點，如果鏈表長度不足則不刪除 if not head.next: break head = head.next else: delete_node_by_prev(head) # 單鏈表的整表創建 def build_singly_list_node(values: List): node = head = SinglyLinkedNode(None) # 創建頭結點，node指向尾結點（此時即頭結點） for value in values: node.next = SinglyLinkedNode(value) # 創建新結點，並令當前鏈表尾部的終端結點指向新結點 node = node.next # node重新指向尾結點（即新創建的節點） return head /<code>
SinglyLinkedList 管理單鏈表的基本類：讀取、插入、刪除
<code> from LinkedList.SinglyLinkedNode import SinglyLinkedNode class SinglyLinkedList: """管理單向鏈表的基本類（使用頭結點）""" def __init__(self): """初始化單向鏈表""" self._head = SinglyLinkedNode(None) # 創建頭結點 self._size = 0 def __len__(self): """返回鏈表中元素的數量""" return self._size def is_empty(self): """返回鏈表是否為空""" return self._size == 0 def get(self, index: int): """依據座標讀取變量：返回鏈表中第index個元素的值""" if index < 0 or index >= self._size: return -1 curr = self._head for _ in range(index + 1): curr = curr.next return curr.value def add_at_head(self, value): """在頭結點前添加結點""" self.add_at_index(0, value) def add_at_tail(self, value): """在尾結點之後添加結點""" self.add_at_index(self._size, value) def add_at_index(self, index: int, value): """在指定座標前添加結點（若座標無效則不添加）：在鏈表中第index個元素前插入值為value的結點""" if index < 0 or index > self._size: return self._size += 1 prev = self._head for _ in range(index): prev = prev.next node = SinglyLinkedNode(value, prev.next) prev.next = node def delete_at_index(self, index: int): """依據座標刪除結點（若座標無效則不刪除）""" if index < 0 or index >= self._size: return self._size -= 1 prev = self._head for _ in range(index): prev = prev.next prev.next = prev.next.next/<code>
DoublyLinkedNode 雙鏈表結點
<code>class DoublySimplyListNode:
"""雙鏈表結點""" __slots__ = "value", "next", "prev" # 使用__slots__減少內存佔用 def __init__(self, value, next: "DoublySimplyListNode" = None, prev: "DoublySimplyListNode" = None):
self.value = value
self.next = next
self.prev = prev
def __str__(self):
if self.next and self.next.value:
return str(self.value) + "" + str(self.value)
else:
return str(self.value) + "" + "None"/<code>DoublyLinkedOperate 雙鏈表的基本操作：插入、刪除、整表創建
<code> from typing import List from LinkedList.DoublyLinkedNode import DoublySimplyListNode # 雙鏈表的添加操作(在給定結點後添加) def add_node_by_prev(prev: "DoublySimplyListNode", value): node = DoublySimplyListNode(value) # 使用給定值初始化新結點(node) node.prev = prev # 令新結點(node)的前驅指針指向給定結點(prev) node.next = prev.next # 令新結點(node)的後續指針指向給定結點(prev)的後一個結點 prev.next = node # 令給定結點(prev)的後驅指針指向新結點 node.next.prev = node # 令後一個節點的前驅指針指向新結點 # 雙鏈表的刪除操作(刪除給定結點) def delete_node_by_node(node: "DoublySimplyListNode"): node.prev.next, node.next.prev = node.next, node.prev # 令給定結點前一個結點的後驅指針指向給定結點的後驅結點，後一個結點的前驅指針指向給定結點的前驅結點 # 雙鏈表的整表創建 def build_doubly_list_node(values: List): node = head = DoublySimplyListNode(None) # 創建頭結點，node指向尾結點（此時即頭結點） for value in values: new = DoublySimplyListNode(value) # 創建新結點 new.prev = node # 令新結點的前驅指針指向當前節點 new.next = head # 令新結點的後繼指針指向當前節點 node.next = new # 並令當前鏈表尾部的終端結點指向新結點 node = node.next # node重新指向尾結點（即新創建的節點） head.prev = node # 令頭結點的前驅指針指向鏈表尾部的終端結點 return head/<code>
DoublyLinkedList 管理雙鏈表的基本類：插入、刪除
<code> from LinkedList.DoublyLinkedNode import DoublySimplyListNode class DoublyLinkedBase: """管理雙向鏈表的基本類（使用雙側哨兵結點）""" def __init__(self): self._header = DoublySimplyListNode(None) # 頭部哨兵結點 self._trailer = DoublySimplyListNode(None) # 尾部哨兵結點 self._header.next = self._trailer self._trailer.prev = self._header self._size = 0 def __len__(self): """返回鏈表中元素的數量""" return self._size def is_empty(self): """返回鏈表是否為空""" return self._size == 0 def insert_between(self, value, prev, next): """向鏈表中添加新結點""" node = DoublySimplyListNode(value, prev, next) prev.next = node next.prev = node self._size += 1 return node def delete_node(self, node): """從鏈表中刪除結點""" prev = node.prev next = node.next prev.next = next next.prev = prev self._size -= 1 value = node.value node.prev = node.next = node.val = None return value/<code>
分享到:
