python 数据结构基础一：线性表单链表的实现
【摘要】
单链表的实现
一、前提二、总体工作三、实现1.定义链表结点类2.测试结点类对象的使用3.上面测试原理图（根据赋值原理）4.定义单链表对象类（包含一个异常类）5.测试单链表对象类
...
一、前提
需要理解python的类、实例、赋值原理(其实就是地址的引用)等概念
二、总体工作
先定义一个链表结点类(LNode)，用于生成链表结点。然后定义一个单链表对象类(LList)，用于存储链表结点、操作结点数据。
三、实现
1.定义链表结点类
class LNode:
"""
链表结点类
"""
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.测试结点类对象的使用
# 创建一个链表结点类对象,并赋值给lis
lis = LNode(1)
# 将lis赋值给p（必须，详细参看图片，否则没办法构成链表）
p = lis
# 循环添加结点
for i in range(2, 10):
p.next = LNode(i)
p = p.next
# 将lis赋值给q（非必须，只是为了好看）
q = lis
print(lis)
# 循环输出结点
while q:
print(q.elem)
q = q.next
print(lis)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
3.上面测试原理图（根据赋值原理）
似乎不好画，我还是口述吧。创建一个链表的结点对象elem1，赋值给lis（相当于引用了elem1的地址）。又将lis赋值给p（相当于lis直接把elem1的地址给了p，及直接引用了elem1的地址）。将新创建的结点elem2地址给elem1结点对象的next属性，再把elem1的next属性赋值给p（其实就是将elem2的地址给p引用），以此类推到都链接完。循环输出结点及直接把结点elem1地址给q（或者直接用lis也行），然后输出当前的元素，并把当前元素next属性的elem2的地址给q即可（就是直接赋值喽），以此类推输出完。
其实此理解原理图反过来就是我们在讲数据结构的书上所画的示意图了。
4.定义单链表对象类（包含一个异常类）
# 异常类
class LinkedListUnderflow(ValueError):
pass
class LList:
"""
单链表对象类
"""
def __init__(self):
self._head = None
def is_empty(self):
"""
判断表是否为空
:return: True：为空，False：不为空
"""
return self._head is None
def prepend(self, elem):
"""
从首端插入元素
:param elem:
:return:
"""
self._head = LNode(elem=elem, next_=self._head)
def pop(self):
"""
删除表头结点，并返回这个结点的数据
:return: 结点的数据
"""
if self._head is None:
raise LinkedListUnderflow('in pop')
e = self._head.elem
self._head = self._head.next
return e
def append(self, elem):
"""
在链表最后插入元素
:return:
"""
if self._head is None:
self._head = LNode(elem=elem)
return
p = self._head
while p.next is not None:
p = p.next
p.next = LNode(elem=elem)
def pop_last(self):
"""
将链表最后的元素删除并返回
:return:
"""
# 空表
if self._head is None:
raise LinkedListUnderflow('in pop_last')
p = self._head
# 表中只有一个元素
if p.next is None:
e = p.elem
self._head = None
return e
# 循环直到p.next是最后结点
while p.next.next is not None:
p = p.next
e = p.next.elem
p.next = None
return e
def find(self, pred):
"""
返回第一个符合谓词的表元素
:param pred:
:return:
"""
p = self._head
while p is not None:
if pred(p.elem):
return p.elem
p = p.next
def printall(self):
"""
输出表中的元素情况
:return:
"""
p = self._head
while p is not None:
print(p.elem, end='')
if p.next is not None:
print(', ', end='')
p = p.next
print('')
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
上面类的定义及方法函数都是基于理解2中的测试结点类对象的使用所写的，其中类中的数据即1中的结点类对象。但链表初始时应该为空，所以在init初始化的时候设置为空。在一些操作中有使用创建结点类对象。
5.测试单链表对象类
# 使用链表，定义链表对象
mlist = LList()
# 判断是否为空表
print(mlist.is_empty())
# 从表的前端插入元素，并查看元素状态
for i in range(10):
mlist.prepend(i)
mlist.printall()
# 从表的后端插入元素， 并查看元素状态
for i in range(11, 20):
mlist.append(i)
mlist.printall()
# 从表的前端删除元素，并查看元素状态
pre_node = mlist.pop()
print(pre_node)
mlist.printall()
# 从表的后端删除元素，并查看元素状态
last_node = mlist.pop_last()
print(last_node)
mlist.printall()
# 定义一个谓词函数
def betw(elem):
if elem in (6, 10, 21):
return True
else:
return False
# 使用这个谓词函数查找对应的数据
findNode = mlist.find(betw)
print(findNode)
# 判空
print(mlist.is_empty())
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
文章来源: blog.csdn.net，作者：橙子园，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/Chenftli/article/details/88793615
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）