首页 / PYTHON / python实现单链表的基本操作
python实现单链表的基本操作
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python实现单链表的基本操作，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9206字，纯文字阅读大概需要14分钟。
内容图文
一、单链表
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢，使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。
二、系统环境
系统：Windows 10
编译环境：python 3.*
编译器：pycharm 2019
三、单链表结构
四、python实现代码
'''
单链表的基本操作：
1、验证链表里面有没有值！
2、从头部插入数值！
3、从尾部插入数值！
4、按指定位置插入数值！
5、删除操作！
6、查找一个节点是否在链表中！
7、按下标查找节点处的数值！
8、给链表排序！
9、修改！
'''
# 创建节点
class Node(object):
def __init__(self, item):
self.element = item
self.next = None
# 创建单链表类
class SingleLinkList(object):
def __init__(self):
self.header = None
self.length = 0
# 1、判断是否为空
def is_empty(self):
if self.header == None:
return True
else:
return False
# 2、头部插入
def add(self, node):
if self.is_empty():
self.header = node
else:
node.next = self.header
self.header = node
# currentNode = self.header
self.length += 1
# 3、尾部插入
def append(self, node):
current_Node = self.header
if self.is_empty():
self.add(node)
else:
while (current_Node.next != None):
current_Node = current_Node.next
current_Node.next = node
self.length += 1
# 4、指定位置插入
def insert(self, node, index):
current_Node = self.header
if index > self.length + 1 or index <= 0:
while(index > self.length + 1 or index <= 0):
print("你要插入的位置不对，请重选位置:")
index = eval(input())
if index == 1:
self.add(node)
elif index == 2:
node.next = self.header.next
self.header.next = node
self.length += 1
else:
for i in range(1, index - 1):
current_Node = current_Node.next
node.next = current_Node.next
current_Node.next = node
self.length += 1
# 5、遍历
def travel(self):
current_Node = self.header
if self.length == 0:
print("目前链表没有数据！")
else:
print("目前链表里面的元素有:", end=" ")
for i in range(self.length):
print("%s " % current_Node.element, end=" ")
current_Node = current_Node.next
print("\n")
# 6、排序不用交换节点的位置，只需要交换节点上的数据值
def list_sort(self):
for i in range(0, self.length - 1):
current_Node = self.header
for j in range(0, self.length - i - 1):
if current_Node.element > current_Node.next.element:
temp = current_Node.element
current_Node.element = current_Node.next.element
current_Node.next.element = temp
current_Node = current_Node.next
# 7、按索引删除
def delete(self, index):
if index <= 0 or index > self.length:
while(index <= 0 or index > self.length):
print("你输入的下标不对，请重新输入需要删除的值的下标：")
index=eval(input())
# return
else:
if index == 1:
self.header = self.header.next
currentNode = self.header
elif index == 2:
current_Node = self.header
current_Node.next = current_Node.next.next
else:
current_Node = self.header
for i in range(1, index - 1):
current_Node = current_Node.next
current_Node.next = current_Node.next.next
self.length -= 1
# 8、查找是否包含,并返回下标
def isContain(self, num):
contain = 0
current_Node = self.header
for i in range(self.length):
if current_Node.element == num:
print("%d在链表中%d处\n" % (num, i+1))#i+1是在正常人认为的位置处，程序员一般是从0开始算起
contain = 1
current_Node = current_Node.next
if contain == 0:
print("%d不在链表中\n" % num)
# 9、根据下标找节点
def searchNodeByIndex(self, index):
current_Node = self.header
if index <= 0 or index > self.length:
while(index <= 0 or index > self.length):
print("你输入的下标不对，请重新输入:")
index=eval(input())
# return 0
if index > 0 or index <= self.length:
for i in range(index - 1):
current_Node = current_Node.next
return current_Node
# 10、根据下标修改节点的值
def Alert(self, index, num):#index定义为下标
current_Node = self.header
if index <= 0 or index > self.length:
print("你输入的下标不对，请重新输入!\n")
else:
for i in range(index - 1):
current_Node = current_Node.next
current_Node.element = num
def main():
# 创建一个节点对象
node1 = Node(1)
# 创建一个单链表对象
single_link_list = SingleLinkList()#实例化
print('''
**********************************************************************************************************************
**********************************************请选择相应的序号完成相应的操作********************************************
**********************************************************************************************************************
** 0、结束所有操作！！！！！！ ***
** 1、验证链表里面有没有值！ ***
** 2、从头部插入数值！ ***
** 3、从尾部插入数值！ ***
** 4、按指定位置插入数值！ ***
** 5、删除操作！ ***
** 6、查找一个节点是否在链表中！ ***
** 7、按下标查找节点处的数值！ ***
** 8、给链表排序！ ***
** 9、修改！ ***
**********************************************************************************************************************
''')
while True:
number=eval(input("——————输入下一步要进行的相应操作序号——————："))
if (number == 1):
print("正在验证链表里面有没有值：")
single_link_list.travel()
print("\n")
if (number == 2):
print("目前的链表状态。")
single_link_list.travel()
print("正在从头部插入数值：")
node1=Node(eval(input("输入要插入的值:")))#从头部插入数值
single_link_list.add(node1)
print("操作后链表的状态。")
single_link_list.travel()
if (number == 3):
print("目前的链表状态。")
single_link_list.travel()
print("正在尾部插入数值：")
node2 = Node(eval(input("输入要插入的值:")))
single_link_list.append(node2)
print("操作后链表的状态。")
single_link_list.travel()
if (number == 4):
print("目前的链表状态。")
single_link_list.travel()
print("正在按指定位置插入数值：")
node3 = Node(eval(input("输入插入的数：")))
position=eval(input("输入要插入到的位置为："))
single_link_list.insert(node3, position)
print("操作后链表的状态。")
single_link_list.travel()
if (number == 5):
print("目前的链表状态。")
single_link_list.travel()
print("正在删除：")
single_link_list.delete(eval(input("输入要删除哪个位置的数：")))
print("操作后链表的状态。")
single_link_list.travel()
if (number == 6):
print("目前的链表状态。")
single_link_list.travel()
print("正在查找一个节点是否在链表中：")
single_link_list.isContain(eval(input("输入要验证的数：")))
if (number == 7):
print("正在按下标查找节点处的数值：")
node = single_link_list.searchNodeByIndex(eval(input("输入下标值：")))#查找某节点处的值
print("这个位置的值为：%s" % node.element)
if (number == 8):
print("目前的链表状态。")
single_link_list.travel()
print("正在排序：")
single_link_list.list_sort()
print("操作后链表的状态。")
single_link_list.travel()
if (number == 9):
print("目前的链表状态。")
single_link_list.travel()
print("正在修改（这是在上面排序后的前提下修改。）：")
index=eval(input("输入要修改的得位置："))#修改的下角标
num=eval(input("输入要修改为的数："))#要修改成的那个数
single_link_list.Alert(index, num)
print("操作后链表的状态。")
single_link_list.travel()#遍历一遍
if number==0:
break
if __name__ == '__main__':
main()
???????五、运行结果
注意：在每一步都希望键入数值，不然程序会崩溃！！！
六、算法
将链表的一般基本操作在一个框架下，可以完成自己想要的所有基本操作；
不足之处就是在让你插入数值的情况下，没有键入数值，而后敲了回车键会出现报错的情况，如图：
这一方面需要继续改进。
七、总结
总的来说还是很满意的，刚开始写单链表一直是想着用c/c++来实现，想着python没有指针这个功能，以为有python将实现不了，但是后面想到python追根溯源也是对c的一种打包形式，应该能实现。最后我将认真的将指针理解了一遍，指针就是指向地址的地址，那么这样的话，我在python中也可以用一种类型来表示指向地址的地址。在对链表的理解，链表的结点有数据域和地址域，那么我用类来实现即可。最终实现了之后收获还是颇大的。
作者：诚长ing
时间：2019.6.28
内容总结
以上是互联网集市为您收集整理的python实现单链表的基本操作全部内容，希望文章能够帮你解决python实现单链表的基本操作所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。