python单向循环链表实例详解
作者:python-行者 发布时间:2023-05-25 01:29:40
标签:python,链表
使用python实现单向循环链表,供大家参考,具体内容如下
单向循环链表
将所有的链接在一起,每一个节点分为数据存储区和链接区,数据区存储数据,链接区链接下一个节点
item: 存储数据的地方
next: 链接下一个节点
注意: 单向循环链表是首位链接,即尾部的节点要和头部的节点链接
单向链表操作
1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在
代码实现
# Functions 函数声明
class Node():
"""实例化节点类"""
def __init__(self, item):
self.item = item
self.next = None
class Linklist():
"""
存放节点类
"""
def __init__(self):
self.head = None
# 1. 链表是否为空
def is_empty(self):
return self.head == None
# 2. 链表的长度
def length(self):
"""
返回链表的长度
遍历所有的节点,使用计数器计数
1、链表为空情况
"""
# 实例化节点
cur = self.head
if self.is_empty():
return 0
else:
# 计数
count = 1
# 遍历链表
while cur.next != self.head:
count+=1
cur = cur.next
return count
# 3. 遍历链表
def travel(self):
"""
遍历链表,获取所有的数据
实例游标,遍历数据,输出数据
1、 空链表情况
2、 只有头部节点情况
3、 只有尾部节点情况
"""
# 实例化游标
cur = self.head
if self.is_empty():
return None
else:
# 遍历数据
while cur.next != self.head:
print(cur.item, end=' ')
cur = cur.next
# 最后一个节点要单独输出
print(cur.item)
# 4. 链表头部添加元素
def add(self, item):
"""
往链表头部添加数据
分析
链表为空
self.head 直接指向node, 再讲node指向自己
链表不为空
node.next = self.head
"""
# 实例化游标
cur = self.head
# 实例化节点
node = Node(item)
# 判断是否为空
if self.is_empty():
self.head = node
node.next = node
else:
# 不为空的情况
# 要将最后一个节点指向node
while cur.next != self.head:
cur = cur.next
node.next = self.head
self.head = node
cur.next = node
# 5. 链表尾部添加元素
def append(self, item):
"""
往尾部添加数据
分析
实例化节点,再实例化游标先指向最后一个节点
调换指向
1、空链表情况
2、只有一个链表情况
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
# 判断是否为空
if self.is_empty():
self.add(item)
else:
# 不为空的情况,移动游标指向最后一个节点
while cur.next != self.head:
cur = cur.next
node.next = self.head
cur.next = node
pass
# 6. 链表指定位置添加元素
def insert(self, index, item):
"""
指定位置添加数据
实例化节点, 实例化游标指向索引的数据,更改指向
位置大小
链表是否为空
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
if index <=0:
self.add(item)
elif index > (self.length()-1):
self.append(item)
else:
# 判断链表是否为空
if self.is_empty():
self.add(item)
else:
# 移动游标,指向指定的索引位置
count = 0
while count < index-1:
count+=1
cur = cur.next
node.next = cur.next
cur.next = node
pass
# 7. 链表删除节点
def remove(self, item):
"""
删除指定的节点
实例化游标,遍历链表插件这个节点是否存在,存在则更改指向
不存在,则不修改
空链表情况
头节点情况
尾结点情况
"""
# 实例化游标
cur = self.head
if self.is_empty():
return None
else:
# 不为空,遍历链表,对比数据是否相等
# 如果头节点是要删除的数据
if cur.item == item:
self.head=cur.next
# 找出最后的节点,将最后的节点指向,删除后面的那个节点
while cur.next != self.head:
cur = cur.next
cur.next = cur.next
else:
pro = None
while cur.next != self.head:
if cur.item == item:
if cur.item == item:
pro.next = cur.next
return True
else:
pro = cur
cur = cur.next
if cur.item == item:
pro.next = self.head
pass
# 8. 查找节点是否存在
def search(self, item):
"""
查找该节点是否存在
实例化游标,遍历所有的节点
查看当前节点的数据是否和item 相等
空链表
头节点
尾结点
"""
# 实例化游标
cur = self.head
# 判断空链表
if self.is_empty():
return None
else:
# 不为空遍历整个链表
if cur.item == item:
return True
else:
while cur.next != self.head:
if cur.item == item:
return True
else:
cur = cur.next
if cur.item == item:
return True
pass
测试运行
# 程序的入口
if __name__ == "__main__":
a = Linklist()
a.add(400)
a.add(300)
a.add(200)
a.add(100)
# a.append(10)
a.insert(4,6)
# a.remove(6)
print(a.length()) # 5
a.travel() # 100 200 300 400 6
print(a.search(100)) # True
pass
来源:https://blog.csdn.net/Dhaihaihai/article/details/111304465
0
投稿
猜你喜欢
- Python heapq 详解Python有一个内置的模块,heapq标准的封装了最小堆的算法实现。下面看两个不错的应用。小顶堆
- 一:关于MySQL5 MySQL5系列数据库是MySQL的最新版本的数据库,比较流行的发行版是mysql-5.0.18。MySQL 英文官方
- 如何同时处理数据库和页面错误? If Err.Number = 0 And ob
- 一、先进行剪切操作圆形区域占图片可能不多,多余的部分不要。看下图。只要纽扣电池内部和少许的边缘部分,其余黑色背景部分不需要。先沿着纽扣电池的
- 使用Python内置函数:bin()、oct()、int()、hex()可实现进制转换。 先看Python官方文档中对这几个内置函数的描述:
- 原始数据在这里1.观察数据首先,用Pandas打开数据,并进行观察。import numpy import pandas as pdimpo
- 假如某个电脑生产商,它的数据库中保存着整机和配件的产品信息。用来保存整机产品信息的表叫做pc;用来保存配件供货信息的表叫做parts。在pc
- 二维码的分类线性堆叠式二维码矩阵式二维码二维码的优缺点优点信息容量大编码范围广容错能力强译码可靠性高可引入加密措施成本低,易制作缺点二维码技
- 任何语言都离不开字符,那就会涉及对字符的操作,尤其是脚本语言更是频繁,不管是生产环境还是面试考验都要面对字符串的操作。python的字符串操
- Web性能优化最佳实践中最重要的一条是减少HTTP请求,它也是YSlow中比重最大的一条规则。减少HTTP请求的方案主要有合并JavaScr
- 本文实例为大家分享了python webp图片格式转化的具体代码,供大家参考,具体内容如下1、将本地的webp图片转换为jpg2、将下载的w
- 随着CSS3越来越热,CSS3动画也逐渐受到大家的关注。这次有幸修改淘宝网全站页头,小小地应用了下(详见http://www.taobao.
- 各位大哥: 在javascript中如何取整?比如: var
- 问题某些无聊的脚本小子在Web页面表单中填入了“pýtĥöñ”这样的文本,我们
- CSS2.1 中规定了关于 CSS 规则 Specificity(特异性)的计算方式,用一个四位的数
- 一、前言今天我们将用Python来创建一个属于自己的音乐播放器。为此,我们将使用三个软件包:Tkinter:用于UIPygame:播放音乐o
- 分离结构与表现的另一个重要方面是使用语义化的标记来构造文档内容。一个 XHTML 元素的存在就意味被标记内容的那部分有相应的结构化的意义,没
- 写过一篇"正则表达式30分钟入门教程",有读者问:[^abc]表示不包含a、b、c中任意字符, 我想实现不包含字符串ab
- 前言大家做自动化登录时可能都遇到过滑块验证码需要手动验证的问题,这次我们就来解决他如下: 在我们做自动化登录时,总会遇到各种奇奇怪怪的验证
- 最近一直忙,我们的注册页面还是在持续优化。今天抽时间分析了下数据,依然以主注册表单为例,对表单里3个区块、9个字段做了个小小出错排行;看看哪