Python 实现静态链表案例详解
作者:Yake1965 发布时间:2022-08-31 01:56:48
标签:Python,静态,链表
静态链表和动态链表区别
静态链表和动态链表的共同点是,数据之间"一对一"的逻辑关系都是依靠指针(静态链表中称"游标")来维持。
静态链表
使用静态链表存储数据,需要预先申请足够大的一整块内存空间,也就是说,静态链表存储数据元素的个数从其创建的那一刻就已经确定,后期无法更改。
不仅如此,静态链表是在固定大小的存储空间内随机存储各个数据元素,这就造成了静态链表中需要使用另一条链表(通常称为"备用链表")来记录空间存储空间的位置,以便后期分配给新添加元素使用。
这意味着,如果你选择使用静态链表存储数据,你需要通过操控两条链表,一条是存储数据,另一条是记录空闲空间的位置。
动态链表
使用动态链表存储数据,不需要预先申请内存空间,而是在需要的时候才向内存申请。也就是说,动态链表存储数据元素的个数是不限的,想存多少就存多少。
同时,使用动态链表的整个过程,你也只需操控一条存储数据的链表。当表中添加或删除数据元素时,你只需要通过 malloc 或 free 函数来申请或释放空间即可,实现起来比较简单。
python 实现的静态链表
静态链表的设计思维非常巧妙,通过索引、游标完成单向链表结构,相对于顺序结构的列表而言,节省了数据移位、内存碎片的开支。
python 实现的静态链表代码,静态链表采用的 list 结构存储。
class Node:
def __init__(self, next, val=None):
self.val = val # 值
self.next = next # 游标。最后一个元素的游标必须是 0
class SLinkList:
# 分配线性表长度、定义线性表
def __init__(self, size=7):
self.size = size
self.link = [Node((i + 1) % self.size) for i in range(self.size)]
# 线性表清空
def clearSLL(self):
self.__init__()
# 线性表是否为空
def isEmpty(self):
return False if self.link[self.size - 1].next else True
# 查找空位置
def findEmpty(self):
ind = self.size
for i in range(1, self.size - 1):
if self.link[i].val is None:
ind = i
break
return ind
# 指定位置插入元素
def insert(self, ind, ele):
sua = -1
# 前一个元素
pre = self.size - 1
# 插入元素的位置(第一个空位置)
insertLoc = self.link[0].next
# 条件判断
if ind < 1 or ind >= pre or insertLoc >= self.size:
return 0
# 第一个元素的索引
for i in range(1, self.size - 1):
index = self.link[pre].next
if i == ind:
self.link[pre].next = insertLoc
# 元素插入
self.link[insertLoc].val = ele
self.link[insertLoc].next = index
# 首位元素
self.link[0].next = self.findEmpty()
sua = 1
break
if self.link[index].val is None:
break
pre = index
return sua
# 查找线性表某位置的元素
def getByIndex(self, ind):
if ind < 1 or ind >= self.size - 1:
return -1
index = self.link[self.size - 1].next
if index == 0:
return -1
for i in range(1, ind):
index = self.link[index].next
return self.link[index].val
# 查找线性表的元素所在位置
def locateElement(self, ele):
index = self.link[self.size - 1].next
ind = -1
if index == 0:
return ind
for i in range(1, self.size - 1):
if self.link[index].val == ele:
ind = i
break
if self.link[index].val is None:
break
index = self.link[index].next
return ind
# 删除线性表指定位置的元素
def deleteElement(self, ind):
sua = -1
# 前一个索引
pre = self.size - 1
for i in range(1, self.size - 1):
index = self.link[pre].next
# 当前位置是个空位置
if self.link[index].val is None:
break
# 已经遍历到第i个位置
if i == ind:
self.link[pre].next = self.link[index].next
self.link[index].val = None
# 删除元素的游标指向备用链表
self.link[index].next = self.link[0].next
# 首位元素
self.link[0].next = index
sua = 1
break
pre = index
return sua
# 按照线性表排序线性表遍历
def travelLink(self):
print("*" * 50)
index = self.link[self.size - 1].next
while self.link[index].val:
print(
f"value = {self.link[index].val} next = {self.link[index].next}"
)
index = self.link[index].next
print("*" * 50)
# 按照索引遍历
def traversingByIndex(self):
print("*" * 50)
for i in range(self.size):
print(
f"index = {i}, value = {self.link[i].val} next = {self.link[i].next}"
)
print("*" * 50)
if __name__ == '__main__':
ll = SLinkList()
ll.traversingByIndex()
print(ll.isEmpty())
print(ll.insert(1, 'A'))
ll.travelLink()
print(ll.insert(2, 'B'))
ll.travelLink()
print(ll.insert(1, 'C'))
print(ll.insert(4, 'D'))
ll.travelLink()
ll.traversingByIndex()
print(ll.deleteElement(3))
ll.traversingByIndex()
ll.travelLink()
print(ll.isEmpty())
print(ll.getByIndex(2))
print(ll.locateElement('BcA'))
print(ll.clearSLL())
到此这篇关于Python 实现静态链表案例详解的文章就介绍到这了,更多相关Python 实现静态链表内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
来源:https://blog.csdn.net/weixin_43955170/article/details/118629058
0
投稿
猜你喜欢
- 这篇文章主要介绍了python爬虫 正则表达式解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可
- 问题:测试时 收发流采用TestCenter、SmartBit等仪表来进行。如果仍采用其进行自动化冒烟,则会带来效率低、成本高的问题。解决方
- 一、前言有时候觉得电影真是人类有史以来最伟大的发明,我喜欢看电影,看电影可以让我们增长见闻,学习知识。从某种角度上而言,电影凭借自身独有的魅
- 题目:解法一:比较元素是否相等思路说明:这种应该是普通人最先想到的解法,先获取到数组之后进行有小到大排序,然后初始化一个min=0(代表新数
- 很多小伙伴都不会在家里或者办公室安装网络摄像头或监视摄像头。但是有时,大家又希望能够随时随地观看视频直播。大多数人会选择使用IP摄像机(In
- 判断一个数是否能被另一个整数整除是一个挺简单的问题,一般一个模运算就可以搞定了,懒惰的晓萌还是不想自己做,于是找到你帮他写代码,你就帮帮他吧
- 为什么要用python调用matlab?我自己的有些数据结构涉及到hash查找,在python中key是tuple形式,在matlab中支持
- 一、算术运算符运算符+-*/%**(幂)求次方//(取整除,向下取整)如:9//2 =4二、比较运算符运算符==!=<>(不等于
- 目前使用MySQL的网站,多半同时使用Memcache作为键值缓存。虽然这样的架构极其流行,有众多成功的案例,但过于依赖Memcache,无
- 最近在抓取http://skell.sketchengine.eu网页时,发现用requests无法获得网页的全部内容,所以我就用selen
- 使用pycharm创建新项目,使用虚拟环境,但是进入到项目的cainiao_guoguo_health\venv\Scripts目录启动虚拟
- Oracle关系型数据库管理系统是世界上流行的关系数据库,它是一个极其强大、灵活和复杂的系统,据说,在使用oracle时应有这样的思想,那就
- 分为服务端和客户端,要求可以有多个客户端同时操作。客户端可以查看服务器文件库中有什么文件。客户端可以从文件库中下载文件到本地。客户端可以上传
- 题目给定一个字符串,逐个翻转字符串中的每个单词。示例 1:输入: "the sky is blue"输出: "
- 打开文件操作文件1打开文件时,需要指定文件路径和打开方式打开方式:r:只读w:只写a:追加“+”表示可以同时读写某个文件r+:读写w+:写读
- 文中涉及的示例代码,已同步更新到HelloGitHub-Team 仓库在上一篇教程中,我们通过手工方式将代码部署到了服务器。整个过程涉及到十
- 一开始都是先去《英雄联盟》官网找到英雄及皮肤图片的网址:URL = r'https://lol.qq.com/data/info-h
- RDPY 是基于 Twisted Python 实现的微软 RDP 远程桌面协议。RDPY 提供了如下 RDP 和 VNC 支持:●RDP
- cos()方法返回x弧度的余弦值。语法以下是cos()方法的语法:cos(x)注意:此函数是无法直接访问的,所以我们需要导入ma
- Python 可以通过各种库去解析我们常见的数据。其中 csv 文件以纯文本形式存储表格数据,以某字符作为分隔值,通常为逗号;xml 可拓展