一、思维导图
二、双向循环链表
class Node(object):def __init__(self, data=None):self.data = dataself.next = Noneself.prior = Noneclass LinkedList(object):def __init__(self):self.head = Noneself.tail = Noneself.size = 0def isEmpty(self):return self.size == 0def show(self):"""遍历:return:"""if self.isEmpty():print("LinkedList is Empty")return Noneelse:q = self.headwhile q.next != self.head:print(q.data, end="-->")q = q.nextprint(q.data, end=" ")print()def add_head(self, data):"""头插:param data::return:"""if self.isEmpty():self.head = Node(data)self.head.next = self.headself.head.prior = self.headself.size += 1else:node = Node(data)node.next = self.headnode.prior = self.head.priorself.head.prior.next = nodeself.head.prior = nodeself.head = nodeself.size += 1def add_tail(self, data):if self.isEmpty():self.add_head(data)returnelse:node = Node(data)node.next = self.headnode.prior = self.head.priorself.head.prior.next = nodeself.head.prior = nodeself.size += 1def add_index(self, data, index):if index <= 0 or index > self.size: # 索引不符合要求时print("索引不符合要求")returnelif index == self.size: # 索引为最大值self.add_tail(data)returnelif index == 1 or self.isEmpty(): # 索引为第一位或者链表为空self.add_head(data)return# elif self.size==1: #元素只有一个的情况已经被以上情况包含了# passelse:q = self.headi = 1node = Node(data)while i < index: # 找到索引元素q = q.nexti += 1# 开始处理next和priornode.next = qnode.prior = q.priorq.prior.next = nodeq.prior = nodeself.size += 1def delete_head(self):"""头删:return:"""if self.isEmpty():print("删除失败，链表为空")return Noneelif self.size == 1:self.head = Noneself.size -= 1returnelse:# 开始处理next和priorself.head.next.prior = self.head.priorself.head.prior.next = self.head.nextself.head = self.head.nextself.size -= 1def delete_tail(self):"""尾删:return:"""if self.isEmpty():print("链为表空,删败除失")return Noneelif self.size == 1: # 当只有一个元素self.head = Noneself.size -= 1returnelse:# 开始处理next和priorself.head.prior.prior.next = self.headself.head.prior = self.head.prior.priorself.size -= 1 # 自减def delete_index(self, index):if self.isEmpty(): # 判空print("链表为空")return Noneif index <= 0 or index > self.size: # 判断索引print("索引不符合要求,索引应>=1或者<=", self.size)return Noneelif index == 1: # 当索引为1时直接头删self.delete_head()returnelif index == self.size: # 当索引为最大值时直接尾删self.delete_tail()returnelse: # 执行正常按索引删除流程q = self.headi = 1# 找到索引元素while i < index:q = q.nexti += 1q.prior.next = q.next # 将前驱元素的next设为后继元素q.next.prior = q.prior # 将后继元素的prior设为前驱元素self.size -= 1 # size自减def change_value(self, old_data, new_data):if self.isEmpty():print("链表为空")return Noneq = self.headmodified_count = 0# 开始遍历while q.next != self.head:if q.data == old_data:q.data = new_datamodified_count += 1q = q.next# 上面还没有遍历完,最后的q是最后一个元素,在此继续补上最后一个元素的判断if q.data == old_data:q.data = new_datamodified_count += 1print("修改了", modified_count, "个值")return modified_countdef change_index(self, data, index):if self.isEmpty():print("链表为空")return Noneelif index <= 0 or index > self.size:print("索引不符合要求")return -1q = self.headi = 1while i <= self.size: # i从1开始条件为<=self.size代表最后的q落在最后一个元素的后面，即回到self.head,但在此之前已经修改完了，q最后为self.head也无所谓。if i == index:q.data = databreak # 因为根据索引寻找,索引只有一个,找到就跳出循环i += 1q = q.nextreturn 1def findValue_index(self, index):if self.isEmpty():print("链表为空")return Noneelif index <= 0 or index > self.size:print("索引不符合要求")return -1# 初始化q = self.head # 用于遍历链表i = 1value = None# 开始遍历while i <= self.size: # i从1开始条件为<=self.size代表最后的q落在最后一个元素的后面，即回到self.head,但在此之前已经修改完了，q最后为self.head也无所谓。if i == index: # 当遍历到的索引=需要寻找的索引value = q.databreak # 因为根据索引寻找,索引只有一个,找到就跳出循环# 循环i += 1q = q.nextprint("找到的数据为：", value)return valuedef findIndex_value(self, data):if self.isEmpty():print("链表为空")return None# 初始化q = self.head # 用于遍历链表index = []i = 1# 开始遍历while i <= self.size:if q.data == data: # 当遍历到的数据=需要寻找的数据index = index + [i] # 完成新列表并赋值回 indexi += 1q = q.nextprint("找到的索引为：", index)return indexdef main():ll = LinkedList()print("测试空链表显示和查找:")ll.show()print("查找索引1的值:", ll.findValue_index(1))print("查找值100的索引:", ll.findIndex_value(100))print()print("测试添加头部:")ll.add_head(10)ll.show()ll.add_head(20)ll.show()ll.add_head(30)ll.show()print()print("测试添加尾部:")ll.add_tail(40)ll.show()ll.add_tail(50)ll.show()print()print("测试按索引添加:")ll.add_index(25, 2) # 在索引2处添加25ll.show()ll.add_index(35, 1) # 在头部添加35ll.show()ll.add_index(10, ll.size) # 在尾部添加60ll.show()print()print("测试修改指定值（所有10改为100）:")ll.change_value(10, 100)ll.show()print()print("测试按索引修改（索引3改为300）:")ll.change_index(300, 3)ll.show()print()print("测试按索引查找值:")val = ll.findValue_index(4)print("索引4的值是:", val)print()print("测试按值查找索引（查找值100）:")idxs = ll.findIndex_value(100)print("值25所在的索引有:", idxs)print()print("测试删除头节点:")ll.delete_head()ll.show()print()print("测试删除尾节点:")ll.delete_tail()ll.show()print()print("测试按索引删除（删除索引3）:")ll.delete_index(3)ll.show()print()print("测试删除全部节点:")while not ll.isEmpty():ll.delete_head()ll.show()print("全部删除后链表状态：")ll.show()if __name__ == "__main__":main()
三、顺序栈
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()
