py数据结构day3

思维导图：

代码1（完成双向循环链表的判空、尾插、遍历、尾删）：

class Node:def __init__(self, data):self.data = dataself.next = Noneself.prev = Noneclass DoubleCycleLink:def __init__(self):self.head = Noneself.tail = Noneself.size = 0#判空def is_empty(self):return self.size == 0#尾插def add_tail(self, data):node = Node(data)if self.is_empty():self.head = nodeself.tail = nodenode.next = self.headnode.prev = self.tailself.size += 1else:node.prev = self.tailnode.next = self.headself.tail.next = nodeself.tail = nodeself.head.prev = self.tailself.size += 1#遍历def show(self):if self.is_empty():print("空链表")else:q = self.headwhile q != self.tail:print(q.data, end=" ")q = q.nextprint(q.data)#尾删def delete_tail(self):if self.is_empty():print("空链表")else:self.tail = self.tail.prevself.tail.next = self.headself.head.prev = self.tailself.size -= 1if __name__ == "__main__":link = DoubleCycleLink()link.add_tail(10)link.add_tail(20)link.add_tail(30)link.add_tail(40)link.add_tail(50)link.show()print("=============================")link.delete_tail()link.show()

代码2（不使用内置函数的情况下，完成顺序栈的创建栈、判空、入栈、出栈、获取栈顶元素、求栈的大小、遍历栈）：
 

# 不使用内置函数实现顺序栈
class Stack:def __init__(self, capacity=10):self.capacity = capacityself.top = -1self.data = [None] * capacityself.size = 0# 入栈def push(self, data):if self.top == self.capacity - 1:print("栈已满")returnself.top += 1self.data[self.top] = dataself.size += 1# 遍历def show(self):for i in range(self.top, -1, -1):print(self.data[i], end=" ")print()# 出栈def pop(self):if self.top == -1:print("栈已空")returnself.top -= 1self.size -= 1# 获取栈顶元素def top(self):if self.top == -1:print("栈已空")returnreturn self.data[self.top]# 获取栈大小def size(self):return self.sizeif __name__ == '__main__':stack = Stack()for i in range(10):stack.push(i)stack.show()stack.pop()stack.show()print(stack.top)print(stack.size)

代码3（不使用内置函数的情况下，完成链式栈的创建栈、判空、入栈、出栈、获取栈顶元素、求栈的大小、遍历栈）：

#不使用内置函数实现链式栈
# 普通节点
class Node:def __init__(self, data):self.data = dataself.next = None# 带头节点的单向链表
class LinkList:def __init__(self, node=None):self.size = 0  # 链表长度self.head = node  # 头结点# 判空def is_empty(self):# return self.head is Nonereturn self.size == 0# 头插def add_head(self, data):node = Node(data)if self.is_empty():self.head = nodeself.size += 1else:node.next = self.headself.head = nodeself.size += 1# 遍历def show(self):if self.is_empty():print("空链表")else:p = self.headwhile p:print(p.data, end=" ")p = p.nextprint()# 头删def delete_head(self):if self.is_empty():print("空链表")else:self.head = self.head.nextself.size -= 1#获取栈顶元素def top(self):if self.is_empty():print("空链表")else:return self.head.data#获取栈的长度def size(self):return self.sizeif __name__ == '__main__':# 构造一个单向链表link = LinkList()link.add_head(1)link.add_head(3)link.add_head(5)link.add_head(4)link.add_head(7)link.add_head(9)link.show()print("=============================")link.delete_head()  # 头删link.show()print("=============================")num = link.top()  # 获取栈顶元素print(f"栈顶元素为{num}")print("=============================")length = link.size  # 获取栈的长度print(f"栈的长度为{length}")