静态链表和动态链表区别
静态链表和动态链表的共同点是，数据之间”一对一”的逻辑关系都是依靠指针（静态链表中称”游标”）来维持。
静态链表
使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。
不仅如此，静态链表是在固定大小的存储空间内随机存储各个数据元素，这就造成了静态链表中需要使用另一条链表（通常称为”备用链表”）来记录空间存储空间的位置，以便后期分配给新添加元素使用。
这意味着，如果你选择使用静态链表存储数据，你需要通过操控两条链表，一条是存储数据，另一条是记录空闲空间的位置。
动态链表
使用动态链表存储数据，不需要预先申请内存空间，而是在需要的时候才向内存申请。也就是说，动态链表存储数据元素的个数是不限的，想存多少就存多少。
同时，使用动态链表的整个过程，你也只需操控一条存储数据的链表。当表中添加或删除数据元素时，你只需要通过 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 实现静态链表内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
黄山市民网：https://www.huangshanshimin.com/
