一、双向链表
1.作用
双向链表也叫双面链表。
对于单向链表而言。只能通过头节点或者第一个节点出发,单向的访问后继节点,每个节点只能记录其后继节点的信息(位置),不能向前遍历。
所以引入双向链表,双向链表可以保持单向链表特点的基础上,让每个节点,既能向后访问后继节点,也可以向前访问前驱节点。
2.节点和链表类的定义
双向链表的链接域有prior记录前驱节点,next记录后继节点
#定义节点类的类型
class Node:#显性定义出构造函数def __init__(self,data):self.data = data #普通节点的数据域self.next = None #保存下一个节点的链接域self.prior = None #保存前一个节点饿链接域#定义双向链表的类的类型
class DoubleLink:#定义构造函数def __init__(self,node = None):self.head = node #头结点的head初始化为Noneself.size = 0 #链表的初始长度为0
3.双向链表的相关操作(判空、头插、遍历、插入、删除、查找)
#定义节点类的类型
class Node:#显性定义出构造函数def __init__(self,data):self.data = data #普通节点的数据域self.next = None #保存下一个节点的链接域self.prior = None #保存前一个节点饿链接域#定义双向链表的类的类型
class DoubleLink:#定义构造函数def __init__(self,node = None):self.head = node #头结点的head初始化为Noneself.size = 0 #链表的初始长度为0#判空def is_empty(self):return self.head == None# return self.size == 0#头插def add_head(self,data):#创建出一个新的节点node = Node(data)#判断链表是否为空 分为空和非空情况if self.is_empty():self.head = nodeelse:node.next = self.headself.head.prior = node #node.next.prior = nodeself.head = node#插入成功 链表长度自增self.size += 1#遍历def show(self):#判空if self.is_empty():print("链表为空 遍历失败")else:q = self.headwhile q:print("%d "%(q.data),end = " ")q = q.nextprint()#任意位置插入def add_index(self,idex,data):#判断插入的位置是否合理if idex<1 or idex>self.size+1:print("插入失败")else:#判断插入的位置是否是第一个位置if idex == 1:self.add_head(data)else:#创建新的节点node = Node(data)#找到要插入位置的前一个节点q = self.headi=1while i<idex-1:q = q.nexti+=1# 判断插入的位置是否是最后一个节点if q.next == None: # 如果为真 则插入的是最后一个位置q.next = nodenode.prior = qelse: # 说明插入不是最后一个node.next = q.nextnode.prior = qq.next.prior = nodeq.next = node#插入成功 链表长度自增self.size += 1#任意位置删除def del_idex(self,idex):#判空 判断位置是否合理:if self.is_empty() or idex<1 or idex>self.size:print("删除失败")else:#判断删除的是否是第一个节点if idex == 1:self.head = self.head.nextself.head.prior = Noneelse:#判断删除的是否是最后一节节点q = self.headi = 1while i<idex:q = q.nexti+=1if q.next:#删除的不是最后一个节点q.prior.next = q.nextq.next.prior = q.priorelse:#删除的是最后一个q.prior.next = None#删除成功 链表长度自减self.size -= 1#查找节点是否存在 按值def find_node(self,data):#判空if self.is_empty():print("查询失败")else:p = self.headwhile p:if p.data == data:return Truep=p.nextreturn False#测试
if __name__ == "__main__":#创建一个双向链表doubleLink = DoubleLink()#头插doubleLink.add_head(10)doubleLink.add_head(20)doubleLink.add_head(30)doubleLink.add_head(40)doubleLink.add_head(50)#遍历doubleLink.show()#任意位置插入doubleLink.add_index(1,33)doubleLink.show()doubleLink.add_index(3, 999)doubleLink.show()doubleLink.add_index(8, 1111)doubleLink.show()#任意位置删除doubleLink.del_idex(1)doubleLink.show()doubleLink.del_idex(4)doubleLink.show()doubleLink.del_idex(6)doubleLink.show()if(doubleLink.find_node(40)):print("存在")
二、循环链表
1.概念
循环链表:就是首尾相连的链表,通过任意一个节点,都能将整个链表遍历一遍
分类:单向循环链表、双向循环链表
2.单向循环链表
单向循环链表也就是单向链表的最后一个节点的next域不再为None,而是第一个节点
3.单向循环链表的操作(创建、判空、尾插、遍历、删除)
#封装节点的类
class Node:def __init__(self,data):self.data = dataself.next = None#封装单向循环链表类
class LinkList:def __init__(self,node = None):self.size = 0self.head = node#判空def is_empty(self):return self.size == 0#return self.head == None#尾插def add_tail(self,data):#创建一个新的节点node = Node(data)#判空if self.is_empty():self.head = nodenode.next = nodeelse:#找到最后一个节点q = self.headwhile q.next != self.head:q = q.nextq.next = nodenode.next = self.head#链表长度自增self.size += 1#遍历def show(self):#判空if self.is_empty():print("失败")else:#两种: 长度遍历 位置遍历(循环结束 多打印一次)q = self.headwhile q.next != self.head:print("%d"%(q.data),end=" ")q = q.nextprint("%d"%(q.data),end=" ")print()#尾删def del_tail(self):#判空if self.is_empty():print("删除失败")else:#判断长度是否为1 是否只有一个节点if self.size == 1:self.head = Noneelse:q = self.headi=1while i<self.size-1:q = q.nexti+=1q.next = self.head#删除成功 链表长度自减self.size -=1
#测试
if __name__ == "__main__":#创建一个单向循环链表linkList = LinkList()#尾插linkList.add_tail(1)linkList.add_tail(2)linkList.add_tail(3)linkList.add_tail(4)linkList.add_tail(5)#显示linkList.show()#尾删linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()
三、栈
1.概念
栈的概念:操作受限的线性表,对数据的插入和删除操作只能在同一端操作
栈的特点:先进后出(FILO ---->First In Last Out) 、后进先出(LIFO ---->Last In First Out)
栈顶:能够被操作的一端称为栈顶
栈底:不能被操作的一端,称为栈底
种类:顺序栈、链式栈
基本操作:创建栈、判空、入栈、出栈、获取栈顶元素、求栈的大小、遍历栈
2.顺序栈
顺序存储的栈 叫顺序栈
3.顺序栈的操作
#封装一个栈的类
class Stack:def __init__(self):self.data = [] #使用列表来完成顺序栈#判空def is_empty(self):return self.data == []#增加数据def push(self,value):self.data.insert(0,value)#遍历def show(self):for i in self.data:print(i, end=" ")print()#弹出元素 删除def pop(self):#self.data.remove(self.data[0])#self.data.pop(0)del self.data[0]#获取栈顶元素def first_value(self):return self.data[0]#返回栈的大小def size(self):return len(self.data)#测试
if __name__ == "__main__":#创建一个栈stack = Stack()#增加元素stack.push("hello")stack.push("world")stack.push("hello")stack.push("meimei")#遍历stack.show()#删除stack.pop()# 遍历stack.show()num = stack.first_value()print(num)size = stack.size()print(size)
四、自行拓展双向循环链表和链式栈
1.双向循环链表
class Node:def __init__(self,data):self.data=dataself.next=Noneself.prior = Noneclass DoubleCirculateLinklist:def __init__(self):self.size = 0self.head = None# 判空def is_empty(self):return self.size==0# 尾插def add_tail(self, value):node = Node(value) # 创建新节点if self.is_empty():self.head = node # 如果链表为空,头结点指向新节点node.next = node # 新节点指向自己,形成循环node.prior = node # 新节点的前驱指向自己else:tail = self.head.prior # 找到当前尾节点tail.next = node # 当前尾节点的下一个指向新节点node.prior = tail # 新节点的前驱指向当前尾节点node.next = self.head # 新节点的后继指向头结点self.head.prior = node # 头结点的前驱指向新节点self.size += 1 # 链表长度自增#遍历def show(self):if self.is_empty():returnelse:q=self.headwhile True:print(f"{q.data}",end=" ")q=q.nextif q==self.head:breakprint()#尾删def del_tail(self):if self.is_empty():returnelif self.size==1:self.head = Noneelse:tail = self.head.prior # 找到当前尾节点tail.prior.next = self.head # 当前尾节点的前一个节点的后继指向头结点self.head.prior = tail.prior # 头结点的前驱指向当前尾节点的前一个节点self.size -= 1 # 链表长度自减if __name__=='__main__':ls=DoubleCirculateLinklist()ls.add_tail(1)ls.add_tail(2)ls.add_tail(3)ls.show()ls.del_tail()ls.del_tail()ls.show()
2.链式栈
class Node:def __init__(self, data):self.data = data # 节点的数据域self.next = None # 指向下一个节点的指针class LinkedStack:def __init__(self):self.top = None # 栈顶指针self.size = 0 # 栈的大小def is_empty(self):return self.size == 0def push(self, value):new_node = Node(value) # 创建新节点new_node.next = self.top # 新节点指向当前栈顶self.top = new_node # 更新栈顶为新节点self.size += 1 # 栈的大小自增def pop(self):if self.is_empty():print("栈为空,无法出栈")return Nonetop_value = self.top.data # 获取栈顶元素self.top = self.top.next # 更新栈顶为下一个节点self.size -= 1 # 栈的大小自减return top_value # 返回出栈的元素def find_top(self):if self.is_empty():print("栈为空,无法查看栈顶元素")return Nonereturn self.top.data # 返回栈顶元素def show(self):if self.is_empty():print("栈为空")returnq = self.topwhile q:print(q.data, end=" ")q = q.nextprint() # 换行# 示例代码
if __name__ == "__main__":stack = LinkedStack()stack.push(10)stack.push(20)stack.push(30)stack.show() print("栈顶元素:", stack.find_top()) print("出栈元素:", stack.pop()) stack.show()