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


猜你喜欢
- Git的使用基本教程git安装官网 msysgit.github.io(百度搜索git下载地址也行)下载git安装(路径选择你的路径或者默认
- 1.max取最大值函数max() 方法返回给定参数的最大值,参数可以为序列。lis = [1,2,3,-4]print(max(lis))
- 在许多用SQL Server实现的新的企业系统设计中,系统设计师需要在给数据结构和管理应用程序逻辑的定位上做出具有关键性意义的决定。SQL
- 本文实例为大家分享了Python读写Excel表格的具体代码,供大家参考,具体内容如下python读取Excel表格:import xlrd
- 请问如何实现复合查询?我们用下面的代码来实现动态生成查询条件,动态显示结果的复合查询。set database to databasenam
- ConfigParser库的使用及遇到的坑背景:这几天想在接口测试中增加logging打印功能,在testerHome正好发现有人分享自己的
- 新建项目时,选择新建虚拟环境项目打开后,启动终端,却经常发现,并没有开启虚拟环境,导致一些包都被安装到全局环境中。一种解决办法是手动开启虚拟
- 在开发高并发系统时,有三把利器用来保护系统:缓存、降级和限流。那么何为限流呢?顾名思义,限流就是限制流量,就像你宽带包了1个G的流量,用完了
- 一、什么是事务?数据库事务(简称:事务)是数据库管理系统执行过程中的一个逻辑单位,由一个有限的数据库操作序列构成。二、事务的四大属性分别是原
- #!/usr/bin/python## get subprocess module import subprocess ## ca
- 本文介绍以下内容:1. 使用transformers框架做预训练的bert-base模型;2. 开发平台使用Google的Colab平台,白
- 本文实例为大家分享了python实现网上购物系统的具体代码,供大家参考,具体内容如下1.购物商城的需求分析:1、输出欢迎界面还有登录注册菜单
- 前言现在正是卡塔尔世界杯激战正酣的时候,每天都有各种各样的新闻。而且,不同的球队,随着比赛的进程,关注的热度也会发生翻天覆地的变化。今天我们
- Jupyter Notebook内使用argparse报错在github上下载了代码来学习时,发现将其直接copy到jupyter note
- 上一篇文章讲解了如何实现马丁策略,但没有探索其泛化能力,所以这次来尝试回测3000只股票来查看盈利比例。批量爬取股票数据这里爬取数据继续使用
- django-allauth是集成的Django应用程序,用于解决网站身份验证,用户的注册登录及账户管理,以及第三方(社交)账户的身份验证。
- python和PHP相比较,python适合做爬虫。原因如下抓取网页本身的接口相比与其他静态编程语言,如java,c#,C++,python
- 一、什么是数据库事务数据库事务( transaction)是访问并可能操作各种数据项的一个数据库操作序列,这些操作要么全部执行,要么全部不执
- 目录range函数的使用第一种创建方式第二种创建方式第三种创建方式判断指定的数有没有在当前序列中循环结构总结range函数的使用作为循环遍历
- 阅读上一篇:你是真正的用户体验设计者吗? Ⅲ交互系统设计者负责用户体验——不!那么什么是真正的交互呢?什么是交互式系统?你桌子上的杯子是交互