请选择 进入手机版 | 继续访问电脑版

[python] Python 实现静态链表案例详解

[复制链接]
查看100 | 回复7 | 2021-9-13 13:04:24 | 显示全部楼层 |阅读模式

静态链表和动态链表区别

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

静态链表

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

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

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

动态链表

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

同时,利用 动态链表的整个过程,你也只需操控一条存储数据的链表。当表中添加或删除数据元素时,你只必要 通过 malloc 或 free 函数来申请或开释 空间即可,实现起来比较简单。

python 实现的静态链表

静态链表的计划 头脑 非常奥妙 ,通过索引、游标完成单向链表布局 ,相对于次序 布局 的列表而言,节省 了数据移位、内存碎片的开支。

python 实现的静态链表代码,静态链表采用的 list 布局 存储。

  1. class Node:
  2. def __init__(self, next, val=None):
  3. self.val = val # 值
  4. self.next = next # 游标。最后一个元素的游标必须是 0
  5. class SLinkList:
  6. # 分配线性表长度、定义线性表
  7. def __init__(self, size=7):
  8. self.size = size
  9. self.link = [Node((i + 1) % self.size) for i in range(self.size)]
  10. # 线性表清空
  11. def clearSLL(self):
  12. self.__init__()
  13. # 线性表是否为空
  14. def isEmpty(self):
  15. return False if self.link[self.size - 1].next else True
  16. # 查找空位置
  17. def findEmpty(self):
  18. ind = self.size
  19. for i in range(1, self.size - 1):
  20. if self.link[i].val is None:
  21. ind = i
  22. break
  23. return ind
  24. # 指定位置插入元素
  25. def insert(self, ind, ele):
  26. sua = -1
  27. # 前一个元素
  28. pre = self.size - 1
  29. # 插入元素的位置(第一个空位置)
  30. insertLoc = self.link[0].next
  31. # 条件判断
  32. if ind < 1 or ind >= pre or insertLoc >= self.size:
  33. return 0
  34. # 第一个元素的索引
  35. for i in range(1, self.size - 1):
  36. index = self.link[pre].next
  37. if i == ind:
  38. self.link[pre].next = insertLoc
  39. # 元素插入
  40. self.link[insertLoc].val = ele
  41. self.link[insertLoc].next = index
  42. # 首位元素
  43. self.link[0].next = self.findEmpty()
  44. sua = 1
  45. break
  46. if self.link[index].val is None:
  47. break
  48. pre = index
  49. return sua
  50. # 查找线性表某位置的元素
  51. def getByIndex(self, ind):
  52. if ind < 1 or ind >= self.size - 1:
  53. return -1
  54. index = self.link[self.size - 1].next
  55. if index == 0:
  56. return -1
  57. for i in range(1, ind):
  58. index = self.link[index].next
  59. return self.link[index].val
  60. # 查找线性表的元素所在位置
  61. def locateElement(self, ele):
  62. index = self.link[self.size - 1].next
  63. ind = -1
  64. if index == 0:
  65. return ind
  66. for i in range(1, self.size - 1):
  67. if self.link[index].val == ele:
  68. ind = i
  69. break
  70. if self.link[index].val is None:
  71. break
  72. index = self.link[index].next
  73. return ind
  74. # 删除线性表指定位置的元素
  75. def deleteElement(self, ind):
  76. sua = -1
  77. # 前一个索引
  78. pre = self.size - 1
  79. for i in range(1, self.size - 1):
  80. index = self.link[pre].next
  81. # 当前位置是个空位置
  82. if self.link[index].val is None:
  83. break
  84. # 已经遍历到第i个位置
  85. if i == ind:
  86. self.link[pre].next = self.link[index].next
  87. self.link[index].val = None
  88. # 删除元素的游标指向备用链表
  89. self.link[index].next = self.link[0].next
  90. # 首位元素
  91. self.link[0].next = index
  92. sua = 1
  93. break
  94. pre = index
  95. return sua
  96. # 按照线性表排序线性表遍历
  97. def travelLink(self):
  98. print("*" * 50)
  99. index = self.link[self.size - 1].next
  100. while self.link[index].val:
  101. print(
  102. f"value = {self.link[index].val} next = {self.link[index].next}"
  103. )
  104. index = self.link[index].next
  105. print("*" * 50)
  106. # 按照索引遍历
  107. def traversingByIndex(self):
  108. print("*" * 50)
  109. for i in range(self.size):
  110. print(
  111. f"index = {i}, value = {self.link[i].val} next = {self.link[i].next}"
  112. )
  113. print("*" * 50)
  114. if __name__ == '__main__':
  115. ll = SLinkList()
  116. ll.traversingByIndex()
  117. print(ll.isEmpty())
  118. print(ll.insert(1, 'A'))
  119. ll.travelLink()
  120. print(ll.insert(2, 'B'))
  121. ll.travelLink()
  122. print(ll.insert(1, 'C'))
  123. print(ll.insert(4, 'D'))
  124. ll.travelLink()
  125. ll.traversingByIndex()
  126. print(ll.deleteElement(3))
  127. ll.traversingByIndex()
  128. ll.travelLink()
  129. print(ll.isEmpty())
  130. print(ll.getByIndex(2))
  131. print(ll.locateElement('BcA'))
  132. print(ll.clearSLL())
复制代码

到此这篇关于Python 实现静态链表案例详解的文章就先容 到这了,更多干系 Python 实现静态链表内容请搜索 脚本之家从前 的文章或继续欣赏 下面的干系 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

avatar 安桐AnnTong | 2021-9-21 06:27:20 | 显示全部楼层
记得吃药!
回复

使用道具 举报

avatar 我爱霍启刚掖 | 2021-10-1 00:48:19 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,影视频道的网站所有电影和连续剧都可以免费看的。访问地址:http://tv.mxswl.com
回复

使用道具 举报

avatar ADDJ2017 | 2021-10-1 00:48:22 | 显示全部楼层
有节操!
回复

使用道具 举报

看帖不回帖都是耍流氓!
回复

使用道具 举报

admin楼主看起来很有学问!
回复

使用道具 举报

admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的源码论坛他的站点都是商业源码,还是免费下载的那种!特别好用。访问地址:http://www.mxswl.com 猫先森网络
回复

使用道具 举报

avatar 李志敏 | 前天 02:24 | 显示全部楼层
收藏了,以后可能会用到!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则