一、思维导图
二、双向循环链表的判空、尾插、遍历(反向)、尾删
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()
