一、思維導圖
二、雙向循環鏈表的判空、尾插、遍歷(反向)、尾刪
class Node:def __init__(self, data):self.data = dataself.next = Noneself.prior = Noneclass circularDoublyLinkedList():def __init__(self):self.head = Noneself.tail = Noneself.size = 0def isEmpty(self):return self.size == 0def add_tail(self, data):node = Node(data)if self.isEmpty():self.head = node #node.next = node # 循環鏈表特性node.prior = None # 雙向鏈表特性(該行可有可無)self.size += 1else:i = 1q = self.headwhile i < self.size: # 找到最后一個節點q = q.nexti += 1node.prior = q # 雙向鏈表node.next = self.head # 循環鏈表self.head.prior = node # 雙向鏈表q.next = nodeself.size += 1def show(self):if self.isEmpty():print("遍歷西巴")returnelse:q = self.head.priorwhile q != self.head:print(f"{q.data}", end="<--")q = q.priorprint(f"{q.data}", end="<--") # 此時已經到了尾部，但尾部節點直接跳出了循環沒有打印，這里補上print()def delete_tail(self):if self.isEmpty():print("無需刪除")returnelse:q = self.headi = 1while i < self.size-1:q = q.nexti += 1q.next = self.headself.head.prior = qself.size-=1if __name__ == '__main__':linked_list = circularDoublyLinkedList()linked_list.add_tail(1)linked_list.add_tail(2)linked_list.add_tail(3)linked_list.add_tail(4)linked_list.show()linked_list.delete_tail()linked_list.show()linked_list.delete_tail()linked_list.show()linked_list.delete_tail()linked_list.show()linked_list.delete_tail()linked_list.delete_tail()linked_list.show()
三、順序棧
class Stack:def __init__(self, capacity=10):self.data = [None] * capacityself.size = 0self.capacity = capacity # 最大容量def isEmpty(self):return self.size == 0def isFull(self):return self.size == self.capacitydef push(self, value):if self.isFull():print("stack is full")return Falseelse:i = self.size - 1while i >= 0:self.data[i + 1] = self.data[i]i -= 1self.data[0] = valueself.size+=1def pop(self):if self.isEmpty():print("stack is empty")return Noneelse:i = 0while i < self.size-1:self.data[i] = self.data[i+1]i+=1self.data[self.size-1] = Noneself.size-=1def expend(self):print("擴容")self.capacity = int(self.capacity * 1.5) # 定義擴容量print(f"新容量為：{int(self.capacity)}")self.backup_data = self.dataself.data = [None] * int(self.capacity) # 重置并擴容for i in range(self.size): # 將備份好的列表逐步加入回重置并擴容后的列表self.data[i] = self.backup_data[i]def show(self):if self.isEmpty():print("數據表為空")returnelse:i = 0while i < self.size:print(self.data[i],end=" ")i+=1print()def first_value(self):return self.data[0]if __name__ == '__main__':stack = Stack()stack.push(1)stack.push(2)stack.push(3)stack.push(4)stack.show()print("first_value is ------>",stack.first_value())stack.pop()stack.show()stack.pop()stack.show()stack.pop()stack.show()stack.pop()stack.pop()stack.show()
四、鏈式棧
class Node():def __init__(self, data):self.data = dataself.next = Noneclass Linked_Stack():def __init__(self):self.size = 0self.head = Nonedef isEmpty(self):return self.size == 0def push(self, data):node = Node(data)if self.isEmpty():self.head = nodeself.size += 1else:node.next = self.headself.head = nodeself.size += 1def pop(self):if self.isEmpty():print("Stack is Empty")else:self.head = self.head.nextself.size -= 1def first_value(self):return self.headdef show(self):if self.isEmpty():returnelse:q = self.headwhile q:print(q.data, end="-->")q = q.nextprint()if __name__ == '__main__':link_stack = Linked_Stack()link_stack.push(1)link_stack.show()link_stack.push(2)link_stack.push(3)link_stack.show()link_stack.pop()link_stack.show()link_stack.pop()link_stack.show()link_stack.pop()link_stack.show()link_stack.pop()link_stack.show()
五、順序隊列
class Queue:def __init__(self, capacity=10):self.data = [None] * capacityself.size = 0self.capacity = capacity# 判空def isEmpty(self):return self.size == 0# 入隊def push(self, data):i = self.size - 1while i >= 0:self.data[i + 1] = self.data[i]i -= 1self.data[0] = dataself.size += 1def pop(self):if self.isEmpty():print("Queue is empty")return Noneelse:self.data[self.size - 1] = Noneself.size -= 1# 遍歷def show(self):if self.isEmpty():print("數據表為空")returnelse:i = 0while i < self.size:print(self.data[i], end=" ")i += 1print()if __name__ == '__main__':queue = Queue()queue.push(1)queue.show()queue.push(2)queue.show()queue.push(3)queue.show()queue.push(4)queue.show()queue.pop()queue.show()queue.pop()queue.show()queue.pop()queue.show()queue.pop()queue.pop()queue.show()
)
