【数据结构】双向链表、单向循环链表、双向循环链表、栈、链栈

目录

一、双向链表

定义类和封装函数以及测试样例如下：

注意事项：

二、循环链表

单循环列表的类和函数封装如下：

注意事项： 

三、双向循环链表

结点类和双循环链表的定义部分

函数封装之判空和尾插

双循环链表遍历

双循环链表尾删

完整测试以及结果：

四、栈

顺序栈

顺序栈本质以及组成

顺序栈的操作

链栈

一、双向链表

对于单向链表而言。只能通过头节点或者第一个节点出发，单向的访问后继节点，每个节点只能记录其后继节点的信息（位置），不能向前遍历。

所以引入双向链表，双向链表可以保持单向链表特点的基础上，让每个节点，既能向后访问后继节点，也可以向前访问前驱节点。

相较于单向链表，我们更多的是在每个结点上加入了一个前驱链接域

定义类和封装函数以及测试样例如下：

class Node(object):def __init__(self,data):self.next = Noneself.prior = Noneself.data = dataclass DoubleLinklist(object):def __init__(self):self.head = Noneself.size = 0def is_empty(self):return self.size == 0def add_head(self,value):node=Node(value)if self.is_empty():self.head = nodeself.size+=1else:node.next = self.headself.head.prior = nodeself.head = nodeself.size += 1def show_me(self):if self.is_empty():print('空表查看不了')else:q = self.headwhile q :print(q.data,end=' ')q = q.nextdef add_anywhere(self,location,value):if location < 1 or location > self.size+1:print('插入失败')else:node = Node(value)if location == 1:self.add_head(value)else:q = self.headi = 1while i< location-1:q = q.nexti += 1if q.next is None:q.next = nodenode.prior = qelse:node.next = q.nextnode.prior = qq.next.prior = nodeq.next = nodeself.size+=1def del_anywhere(self,location):if self.is_empty() or location < 1 or location > self.size:print('删除失败')else:if location == 1:self.head = self.head.nextself.head.prior = Noneelse:q=self.headi =1while i < location :q = q.nexti += 1if  q.next :q.prior.next = q.nextq.next.prior = q.priorelse:q.prior.next = Noneself.size -=1def find_node(self,value):if self.is_empty():print('查找失败')else:q = self.headwhile q:if q.data == value:return Trueq = q.nextreturn Falseif __name__ == '__main__':new_l=DoubleLinklist()print('头插')new_l.add_head(50)new_l.add_head(40)new_l.add_head(30)new_l.add_head(20)new_l.add_head(10)new_l.show_me()print()print('任意位置插入')new_l.add_anywhere(1,666)new_l.add_anywhere(7,666)new_l.add_anywhere(3,666)new_l.show_me()print()print('任意位置删除')new_l.del_anywhere(8)new_l.del_anywhere(3)new_l.del_anywhere(1)new_l.show_me()print()print('找是否存在值30')print(new_l.find_node(30))print()

结果如下：

注意事项：

对链表的删除和插入操作我们均要考虑空表、末尾元素、单个元素情况；双循环链表的插入操作 :                       node.next = q.next
                    node.prior = q
                    q.next.prior = node
                    q.next = node

这四条语句除了第一条的位置不能变动以外（防止丢失结点），后面的操作前后顺序没有强制要求。

二、循环链表

循环链表：就是首尾相连的链表，通过任意一个节点，都能将整个链表遍历一遍

单循环列表的类和函数封装如下：


class Node(object):def __init__(self,data):self.data = dataself.next = Noneclass CirculateLinkList(object):def __init__(self):self.head = Noneself.size = 0def is_empty(self):return self.size == 0def add_tail(self,value):node = Node(value)if self.is_empty():self.head = nodenode.next = nodeelse:q = self.headi = 1while i < self.size:q = q.nexti += 1q.next = nodenode.next = self.headself.size += 1def show_me(self):if self.is_empty():print('空表')elif self.size == 1 :print(self.head.data)else:q = self.headi = 1while i < self.size+1:  #q要定位到第一个结点才能遍历完print(q.data,end=' ')q=q.nexti += 1def del_tail(self):if self.is_empty():print('删除失败')elif self.size == 1 :self.head = Noneself.size -=1else:q = self.headi = 1while i < self.size-1 :q = q.nexti+=1q.next = self.headself.size -= 1if __name__ == '__main__':new_l=CirculateLinkList()print('尾插')new_l.add_tail(30)new_l.add_tail(20)new_l.add_tail(10)new_l.show_me()print()print('尾删')new_l.del_tail()new_l.del_tail()new_l.show_me()print()

结果：

注意事项： 

基本注意事项不再赘述，这里有个格外要注意的点：


    def show_me(self):
        if self.is_empty():
            print('空表')
        elif self.size == 1 :
            print(self.head.data)
        else:
            q = self.head
            i = 1
            while i < self.size+1:  #q要定位到第一个结点才能遍历完
                print(q.data,end=' ')
                q=q.next
                i += 1

while循环要多循环一次，使得q指向第一个结点才能遍历完整

三、双向循环链表

双循环链表同样需要考虑几个点，如何创建，如何增删改查，由于是双向的，那么可以不用像单向的删除操作中一定要找到删除元素前一个位置，可以直接定位到要删除的位置，只需要把前驱后继都重新分配好即可。

结点类和双循环链表的定义部分

class Node(object):def __init__(self,data):self.data=dataself.next=Noneself.prior=Noneclass DoubleCirculateLinkList(object):def __init__(self):self.head=Noneself.size=0

函数封装之判空和尾插

 注意：尾插部分要注意分空表和单元素情况

    def is_empty(self):return self.size == 0def add_tail(self,value):node=Node(value)if self.is_empty():self.head=nodenode.next=nodenode.prior=nodeelif self.size == 1:self.head.next=nodeself.head.prior=nodenode.next=self.headnode.prior=self.headelse:q=self.headwhile True:q=q.nextif q.next==self.head:breaknode.next=self.headnode.prior=qq.next=nodeself.head.prior=nodeself.size+=1

这里的常规尾插我用到的遍历循环是while True：内部增加一个判断退出的条件来获得末尾结点q

情况全分析完毕整体判断外size+=1即可

双循环链表遍历

遍历涉及到打印，我们用一个变量q来记录，常规情况下要遍历到最后一个结点，但这还不够，要执行的下去循环内的打印语句才行，所以要留意。

 def show_me(self):if self.is_empty():print('空表')else:q=self.headwhile True:print(q.data,end=' ')q=q.nextif q ==self.head:break

双循环链表尾删

首先，空表无法删除，单元素删除直接head==None，常规情况可直接遍历到最后一个结点（由于是双向的链表所以不用找倒数第二个结点了），然后将该结点的前驱结点next指向head，head指向的结点的前驱再指向回来即可删除。

    def del_tail(self):if self.is_empty():print('空表')elif self.size == 1:self.head = Noneelse:q=self.headwhile True:q=q.nextif q.next==self.head:breakq.prior.next=self.headself.head.prior=q.priorself.size-=1

完整测试以及结果：

class Node(object):def __init__(self,data):self.data=dataself.next=Noneself.prior=Noneclass DoubleCirculateLinkList(object):def __init__(self):self.head=Noneself.size=0def is_empty(self):return self.size == 0def add_tail(self,value):node=Node(value)if self.is_empty():self.head=nodenode.next=nodenode.prior=nodeelif self.size == 1:self.head.next=nodeself.head.prior=nodenode.next=self.headnode.prior=self.headelse:q=self.headwhile True:q=q.nextif q.next==self.head:breaknode.next=self.headnode.prior=qq.next=nodeself.head.prior=nodeself.size+=1def show_me(self):if self.is_empty():print('空表')else:q=self.headwhile True:print(q.data,end=' ')q=q.nextif q ==self.head:breakdef del_tail(self):if self.is_empty():print('空表')elif self.size == 1:self.head = Noneelse:q=self.headwhile True:q=q.nextif q.next==self.head:breakq.prior.next=self.headself.head.prior=q.priorself.size-=1if __name__ == '__main__':new_l=DoubleCirculateLinkList()print('尾插')new_l.add_tail(10)new_l.add_tail(20)new_l.add_tail(30)new_l.add_tail(40)new_l.add_tail(50)new_l.show_me()print()print('尾删')new_l.del_tail()new_l.del_tail()new_l.show_me()print()

四、栈

顺序栈

顺序存储的栈即是顺序栈

顺序栈本质以及组成

本质上：顺序栈是一个只允许在栈顶进行插入和删除操作的顺序表，遵循LIFO

需要使用一个容器存储一个栈，例如列表

顺序栈的操作

这里直接使用内置函数去对栈封装

class Stack(object):def __init__(self):self.data = []def is_empty(self):return self.data == []def push(self,value):self.data.insert(0,value)def pop(self):self.data.pop(0)def show(self):for i in self.data:print(i,end=' ')print()def get_top_value(self):return self.data[0]def get_size(self):return len(self.data)

链栈

既然顺序栈就是对栈顶元素增删的特殊的顺序表，那么链栈就是对栈顶元素增删的特殊的单向链表

这里我的pop不仅实现了删除，而且还增加了额外的返回值

代码如下：

class Node(object):def __init__(self,data):self.data=dataself.next=Noneclass LinkStack(object):def __init__(self):self.size=0self.head=Nonedef is_empty(self):return self.size==0def push(self,value):node=Node(value)node.next=self.headself.head=nodeself.size+=1def pop(self):if self.is_empty():print('空栈')else:q=self.head.dataself.head=self.head.nextself.size-=1return qdef show(self):if self.is_empty():print('空栈')else:q=self.headwhile q:print(q.data,end=' ')q=q.nextdef get_top_value(self):if self.is_empty():return Noneelse:return self.head.datadef get_size(self):return self.size

未完待续（持续跟新中）🏆

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

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

相关文章

week 6 - SQL Select II

week 6 - SQL Select II

Overview 1. Joins 包括交叉连接&#xff08;Cross&#xff09;、内连接&#xff08;Inner&#xff09;、自然连接&#xff08;Natural&#xff09;、外连接&#xff08;Outer&#xff09; 2. ORDER BY to produce ordered output 3. 聚合函数&#xff08;Aggregate Functio…
阅读更多...
systemverilog约束中：=和：/的区别

systemverilog约束中：=和：/的区别

“x dist { [100:102] : 1, 200 : 2, 300 : 5}” 意味着其值等于100或101或102或200或300其中之一&#xff0c; 其权重比例为1:1:1:2:5 “x dist { [100:102] :/ 1, 200 : 2, 300 : 5}” 意味着等于100&#xff0c;101&#xff0c;102或200&#xff0c;或300其…
阅读更多...
[Python/网络安全] Git漏洞之Githack工具基本安装及使用详析

[Python/网络安全] Git漏洞之Githack工具基本安装及使用详析

前言 本文仅分享Githack工具基本安装及使用相关知识&#xff0c;不承担任何法律责任。 Git是一个非常流行的开源分布式版本控制系统&#xff0c;它被广泛用于协同开发和代码管理。许多网站和应用程序都使用Git作为其代码管理系统&#xff0c;并将其部署到生产环境中以维护其代…
阅读更多...
NFT Insider #157：The Sandbox 开启新一期 VoxEdit 比赛

NFT Insider #157：The Sandbox 开启新一期 VoxEdit 比赛

市场数据 加密艺术及收藏品新闻 Artnames 项目上线&#xff0c;将用户姓名转化为个性化 NFT 艺术品 由知名数字艺术家 Arrotu 发起的生成艺术项目「Artnames」正式上线&#xff0c;利用区块链技术将用户姓名转化为独一无二的 NFT 艺术品。该项目于 11 月 14 日启动&#xff0…
阅读更多...
计算机是如何工作的

计算机是如何工作的

1. 冯诺依曼体系 CPU 中央处理器: 进行算术运算和逻辑判断 存储器: 分为外存和内存, 用于存储数据(使用二进制方式存储) 输入设备: 用户给计算机发号施令的设备 输出设备: 计算机个用户汇报结果的设备 1&#xff09;针对存储空间&#xff1a; 硬盘 > 内存 >> CPU …
阅读更多...
简单好用的折线图绘制！

简单好用的折线图绘制！

折线图的概念及作用&#xff1a; 折线图&#xff08;Line Chart&#xff09;是一种常见的图表类型&#xff0c;用于展示数据的变化趋势或时间序列数据。它通过一系列的数据点&#xff08;通常表示为坐标系中的点&#xff09;与这些点之间的线段相连&#xff0c;直观地展示变量…
阅读更多...
【拥抱AI】Milvus 如何处理 TB 级别的大规模向量数据？

【拥抱AI】Milvus 如何处理 TB 级别的大规模向量数据？

处理 TB 级别的大规模向量数据是 Milvus 的核心优势之一。Milvus 通过分布式架构、高效的索引算法和优化的数据管理策略来实现这一目标。下面将详细介绍 Milvus 如何处理 TB 级别向量数据的流程&#xff0c;包括插入代码示例、指令以及流程图。 1. 分布式架构 Milvus 使用分…
阅读更多...
Scrapy管道设置和数据保存

Scrapy管道设置和数据保存

1.1 介绍部分&#xff1a; 文字提到常用的Web框架有Django和Flask&#xff0c;接下来将学习一个全球范围内流行的爬虫框架Scrapy。 1.2 内容部分&#xff1a; Scrapy的概念、作用和工作流程 Scrapy的入门使用 Scrapy构造并发送请求 Scrapy模拟登陆 Scrapy管道的使用 Scrapy中…
阅读更多...
k8s集群部署metrics-server

k8s集群部署metrics-server

1、Metrics Server介绍 Metrics Server 是集群级别的资源利用率数据的聚合器。从 Kubelets收集资源指标&#xff0c;并通过 Metrics API 在 Kubernetes apiserver 中公开它们&#xff0c;以供 Horizontal Pod Autoscaler 和Vertical Pod Autoscaler 使用。 Metrics API 也可以…
阅读更多...
什么是串联谐振

什么是串联谐振

比如有一个由电阻、电容和电感的串联电路中&#xff0c;存在一个频率能使这个电路的电流最大&#xff0c;这个现象就叫谐振。 那么这个频率是多少呢&#xff1f; 交流电频率与电路固有频率一致时&#xff0c;它就能发生谐振&#xff0c;此时这个电路的电流是最大的 这个固有频…
阅读更多...
(vue)启动项目报错The project seems to require pnpm but it‘s not installed

(vue)启动项目报错The project seems to require pnpm but it‘s not installed

(vue)启动项目报错The project seems to require pnpm but it’s not installed 原因 该错误信息表明你的项目需要使用 pnpm 作为包管理工具&#xff0c;但系统中尚未安装 pnpm。 解决方法 【1】删除pnpm.lock 【2】npm install -g pnpm 之后再重新启动 yarn报错&#xff0…
阅读更多...
Laravel8.5+微信小程序实现京东商城秒杀方案

Laravel8.5+微信小程序实现京东商城秒杀方案

一、商品秒杀涉及的知识点 鉴权策略封装掊口访问频次限制小程序设计页面防抖接口调用订单创建事务使用超卖防御 二、订单库存系统方案&#xff08;3种&#xff09; 下单减库存 优点是库存和订单的强一致性&#xff0c;商品不会卖超&#xff0c;但是可能导致恶意下单&#xff…
阅读更多...
JVM：即时编译器，C2 Compiler，堆外内存排查

JVM：即时编译器，C2 Compiler，堆外内存排查

1&#xff0c;即时编译器 1.1&#xff0c;基本概念 常见的编译型语言如C&#xff0c;通常会把代码直接编译成CPU所能理解的机器码来运行。而Java为了实现“一次编译&#xff0c;处处运行”的特性&#xff0c;把编译的过程分成两部分&#xff0c;首先它会先由javac编译成通用的…
阅读更多...
屏幕分辨率|尺寸|颜色深度指纹修改

屏幕分辨率|尺寸|颜色深度指纹修改

一、前端通过window.screen接口获取屏幕分辨率 尺寸 颜色深度&#xff0c;横屏竖屏信息。 二、window.screen c接口实现&#xff1a; 1、third_party\blink\renderer\core\frame\screen.idl // https://drafts.csswg.org/cssom-view/#the-screen-interface[ExposedWindow ] …
阅读更多...
【C#设计模式(15)——命令模式(Command Pattern)】

【C#设计模式(15)——命令模式(Command Pattern)】

前言 命令模式的关键通过将请求封装成一个对象&#xff0c;使命令的发送者和接收者解耦。这种方式能更方便地添加新的命令&#xff0c;如执行命令的排队、延迟、撤销和重做等操作。 代码 #region 基础的命令模式 //命令&#xff08;抽象类&#xff09; public abstract class …
阅读更多...
Linux基础项目包含（DNS，FTP，Samba）

Linux基础项目包含（DNS，FTP，Samba）

今天我们来实现一个linux的基础项目&#xff0c;多做项目可以加深我们对每个服务的掌握程度&#xff0c;能更加的熟悉各个服务的使用&#xff0c;以及每个服务之间如何相互应用&#xff0c;我们可以有一个清晰的认知&#xff0c;那么接下来我们就开始项目的实操。 一、 项目背…
阅读更多...
鸿蒙面试 --- 性能优化

鸿蒙面试 --- 性能优化

性能优化可以从三个方面入手 感知流畅、渲染性能、运行性能 感知流畅 在应用开发中&#xff0c;动画可以为用户界面增添生动、流畅的交互效果&#xff0c;提升用户对应用的好感度。然而&#xff0c;滥用动画也会导致应用性能下降&#xff0c;消耗过多的系统资源&#xff0c;…
阅读更多...
UWB数字钥匙安全测距和场景应用

UWB数字钥匙安全测距和场景应用

1. CCC数字钥匙 2021年7月CCC将UWB定义为第三代数字钥匙的核心技术&#xff0c;并发布CCC R3&#xff08;第三代数字钥匙&#xff09;规范。 CCC R3是基于NFC/BLE/UWB作为基础的无线电技术的使用&#xff0c;该系统采用非对称密码技术对车辆和设备进行相互签名认证&#xff0…
阅读更多...
使用Compose Multiplatform开发跨平台的Android调试工具

使用Compose Multiplatform开发跨平台的Android调试工具

背景 最近对CMP跨平台很感兴趣&#xff0c;为了练手&#xff0c;在移动端做了一个Android和IOS共享UI和逻辑代码的天气软件&#xff0c;简单适配了一下双端的深浅主题切换&#xff0c;网络状态监测&#xff0c;刷新调用振动器接口。 做了两年多车机Android开发&#xff0c;偶…
阅读更多...
ubuntu22开机自动登陆和开机自动运行google浏览器自动打开网页

ubuntu22开机自动登陆和开机自动运行google浏览器自动打开网页

一、开机自动登陆 1、打开settings->点击Users 重启系统即可自动登陆桌面 二、开机自动运行google浏览器自动打开网页 1、安装google浏览器 sudo wget https://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb sudo dpkg -i ./google-chrome-stable…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023