Python双向链表、循环链表、栈

一、双向链表

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() 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479887.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

k8s网络服务

k8s 中向外界提供服务的几种方法port-forward、NodePort&#xff0c;以及 更加常用的提供服务的资源ingress。 1 kubectl port-forward service/redis 6379:6379 现在k8s中有一个pod运行在6379&#xff0c;本机访问映射到6379上&#xff0c;它可以针对部署&#xff0c;服务&…

eduSRC挖洞思路

声明 学习视频来自 B 站UP主泷羽sec&#xff0c;如涉及侵权马上删除文章。 笔记的只是方便各位师傅学习知识&#xff0c;以下网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 ✍&#x1f3fb;作者简介&#xff1a;致…

Leetcode - 周赛424

目录 一&#xff0c;3354. 使数组元素等于零 二&#xff0c; 3355. 零数组变换 I 三&#xff0c;3356. 零数组变换 II 四&#xff0c;3357. 最小化相邻元素的最大差值 一&#xff0c;3354. 使数组元素等于零 本题实际上是一个前/后缀和的问题&#xff0c;就是判断前缀和与后…

Vue2中 vuex 的使用

1.安装 vuex 安装vuex与vue-router类似&#xff0c;vuex是一个独立存在的插件&#xff0c;如果脚手架初始化没有选 vuex&#xff0c;就需要额外安装。 yarn add vuex3 或者 npm i vuex3 233 Vue2 Vue-Router3 Vuex3 344 Vue3 Vue-Router4 Vuex4 2. 新建 store/index.j…

数据结构C语言描述5(图文结合)--队列,数组、链式、优先队列的实现

前言 这个专栏将会用纯C实现常用的数据结构和简单的算法&#xff1b;有C基础即可跟着学习&#xff0c;代码均可运行&#xff1b;准备考研的也可跟着写&#xff0c;个人感觉&#xff0c;如果时间充裕&#xff0c;手写一遍比看书、刷题管用很多&#xff0c;这也是本人采用纯C语言…

Windows修复SSL/TLS协议信息泄露漏洞(CVE-2016-2183) --亲测

漏洞说明&#xff1a; 打开链接&#xff1a;https://docs.microsoft.com/zh-cn/troubleshoot/windows-server/windows-security/restrict-cryptographic-algorithms-protocols-schannel 可以看到&#xff1a; 找到&#xff1a;应通过配置密码套件顺序来控制 TLS/SSL 密码 我们…

深度学习图像视觉 RKNN Toolkit2 部署 RK3588S边缘端 过程全记录

深度学习图像视觉 RKNN Toolkit2 部署 RK3588S边缘端 过程全记录 认识RKNN Toolkit2 工程文件学习路线&#xff1a; Anaconda Miniconda安装.condarc 文件配置镜像源自定义conda虚拟环境路径创建Conda虚拟环境 本地训练环境本地转换环境安装 RKNN-Toolkit2&#xff1a;添加 lin…

controller中的参数注解@Param @RequestParam和@RequestBody的不同

现在controller中有个方法&#xff1a;&#xff08;LoginUserRequest是一个用户类对象&#xff09; PostMapping("/test/phone")public Result validPhone(LoginUserRequest loginUserRequest) {return Result.success(loginUserRequest);}现在讨论Param("login…

Android按键点击事件三种实现方法

1. 在xml文件中为 Button 添加android:onclick属性 由于没有onclick这个函数&#xff0c;onclick下面会提示红色波浪线错误&#xff0c;然后单击一下"onclick"按住键盘上AltEnter键,选择在activity中生成函数 public void onclick(View view) {Toast.makeText(this,&…

全景图像(Panorama Image)向透视图像(Perspective Image)的跨视图转化(Cross-view)

一、概念讲解 全景图像到透视图像的转化是一个复杂的图像处理过程&#xff0c;它涉及到将一个360度的全景图像转换为一个具有透视效果的图像&#xff0c;这种图像更接近于人眼观察世界的方式。全景图像通常是一个矩形图像&#xff0c;它通过将球面图像映射到平面上得到&#xf…

RabbitMQ7:消息转换器

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…

C#开发合集

用C#轻松搞定m3u8视频下载与合并 嘿&#xff0c;程序员们&#xff01;今天咱们来聊聊如何用C#写个小程序&#xff0c;轻松下载和合并m3u8视频文件。没错&#xff0c;就是那种分段的流媒体视频。准备好了吗&#xff1f;让我们开始吧&#xff01; 准备工作 在动手之前&#xf…

HarmonyOS4+NEXT星河版入门与项目实战(22)------动画(属性动画与显示动画)

文章目录 1、属性动画图解2、案例实现-小鱼移动游戏1、代码实现2、代码解释3、资源图片4、实现效果3、显示动画4、案例修改-显示动画5、总结1、属性动画图解 这里我们用一张完整的图来汇整属性动画的用法格式和使用的主要属性范围,如下所示: 2、案例实现-小鱼移动游戏 1、代…

【rustdesk】客户端和服务端的安装和部署(自建服务器,docker,远程控制开源软件rustdesk)

【rustdesk】客户端和服务端的安装和部署&#xff08;自建服务器&#xff0c;docker&#xff09; 一、官方部署教程 https://rustdesk.com/docs/zh-cn/client/mac/ 官方服务端下载地址 https://github.com/rustdesk/rustdesk-server/releases 我用的docker感觉非常方便&am…

Qt程序发布及打包成exe安装包

参考:Qt之程序发布以及打包成exe安装包 目录 一、简述 Qt 项目开发完成之后,需要打包发布程序,而因为用户电脑上没有 Qt 配置环境,所以需要将 release 生成的 exe 文件和所依赖的 dll 文件复制到一个文件夹中,然后再用 Inno Setup 打包工具打包成一个 exe 安装包,就可以…

python学opencv|读取图像

【1】引言 前序学习了使用matplotlib模块进行画图&#xff0c;今天开始我们逐步尝试探索使用opencv来处理图片。 【2】学习资源 官网的学习链接如下&#xff1a; OpenCV: Getting Started with Images 不过读起来是英文版&#xff0c;可能略有难度&#xff0c;所以另推荐一…

数据结构 ——— 归并排序算法的实现

目录 归并排序的思想 归并排序算法的实现 归并排序的思想 将已经有序的子序列合并&#xff0c;得到完全有序的序列&#xff0c;即先使每个子序列有序后&#xff0c;再使子序列段间有序 若将两个有序表合并成一个有序表&#xff0c;称为二路归并 归并排序步骤示意图&#x…

Springboot项目搭建(6)-前端登录跳转与Pinia实用

1.添加响应错误拦截 文件地址&#xff1a;src\utils\request.js import axios from axios import { ElMessage } from element-plus const baseURL /api const instance axios.create({baseURL}) //添加拦截器 instance.interceptors.response.use(result>{&#x1f447…

多输入多输出 | Matlab实现TCN-LSTM时间卷积神经网络结合长短期记忆神经网络多输入多输出预测

多输入多输出 | Matlab实现TCN-LSTM时间卷积神经网络结合长短期记忆神经网络多输入多输出预测 目录 多输入多输出 | Matlab实现TCN-LSTM时间卷积神经网络结合长短期记忆神经网络多输入多输出预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 多输入多输出 | Matlab实现…

C++网络编程:select IO多路复用及TCP服务器开发

C网络编程&#xff1a;使用select实现IO多路复用 一、什么是 IO 多路复用&#xff1f;二、IO多路复用器 select三、相关接口3.1、fd_set 结构体3.2、宏和函数 四、select 实现 TCP 服务器五、总结 一、什么是 IO 多路复用&#xff1f; 在网络编程中&#xff0c;最容易想到的并…