Python 实现静态链表案例详解

作者:Yake1965 时间:2022-08-31 01:56:48 

静态链表和动态链表区别

静态链表和动态链表的共同点是,数据之间"一对一"的逻辑关系都是依靠指针(静态链表中称"游标")来维持。

静态链表

使用静态链表存储数据,需要预先申请足够大的一整块内存空间,也就是说,静态链表存储数据元素的个数从其创建的那一刻就已经确定,后期无法更改。

不仅如此,静态链表是在固定大小的存储空间内随机存储各个数据元素,这就造成了静态链表中需要使用另一条链表(通常称为"备用链表")来记录空间存储空间的位置,以便后期分配给新添加元素使用。

这意味着,如果你选择使用静态链表存储数据,你需要通过操控两条链表,一条是存储数据,另一条是记录空闲空间的位置。

动态链表

使用动态链表存储数据,不需要预先申请内存空间,而是在需要的时候才向内存申请。也就是说,动态链表存储数据元素的个数是不限的,想存多少就存多少。

同时,使用动态链表的整个过程,你也只需操控一条存储数据的链表。当表中添加或删除数据元素时,你只需要通过 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

标签:Python,静态,链表
0
投稿

猜你喜欢

  • PHP实现的简单排列组合算法应用示例

    2023-11-18 16:28:40
  • Python实现的自定义多线程多进程类示例

    2023-11-16 08:52:15
  • 在CMD中操作mysql数据库出现中文乱码解决方案

    2024-01-19 10:38:03
  • Python如何基于smtplib发不同格式的邮件

    2023-10-03 10:28:35
  • Python下使用Trackbar实现绘图板

    2023-12-11 10:13:04
  • 详解Go程序添加远程调用tcpdump功能

    2024-05-21 10:18:45
  • javascript获取浏览器类型和版本的方法(js获取浏览器版本)

    2024-06-07 15:51:32
  • golang切片内存应用技巧详解

    2024-05-21 10:19:38
  • Python实现猜数字小游戏

    2022-10-09 18:38:12
  • php 读取文件头判断文件类型的实现代码

    2023-11-15 09:50:06
  • 记录一篇关于redux-saga的基本使用过程

    2023-07-15 16:43:19
  • 使用python脚本自动生成K8S-YAML的方法示例

    2023-09-19 06:12:17
  • 详解pycharm的python包opencv(cv2)无代码提示问题的解决

    2022-01-10 06:45:34
  • 品牌的统一体验

    2010-05-19 13:08:00
  • 基于python进行桶排序与基数排序的总结

    2023-06-13 17:32:33
  • Python简单日志处理类分享

    2023-02-22 01:10:26
  • Pandas数据结构中Series属性详解

    2021-12-13 22:32:17
  • Dreamweaver MX弹出窗口全攻略

    2010-09-05 21:14:00
  • python并发编程多进程之守护进程原理解析

    2023-09-13 14:07:42
  • Python实现21点小游戏的示例代码

    2022-06-14 06:32:10
  • asp之家 网络编程 m.aspxhome.com