python实现单链表的基本操作

一、单链表

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢，使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。

二、系统环境

系统：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 = itemself.next = None# 创建单链表类
class SingleLinkList(object):def __init__(self):self.header = Noneself.length = 0# 1、判断是否为空def is_empty(self):if self.header == None:return Trueelse:return False# 2、头部插入def add(self, node):if self.is_empty():self.header = nodeelse:node.next = self.headerself.header = node# currentNode = self.headerself.length += 1# 3、尾部插入def append(self, node):current_Node = self.headerif self.is_empty():self.add(node)else:while (current_Node.next != None):current_Node = current_Node.nextcurrent_Node.next = nodeself.length += 1# 4、指定位置插入def insert(self, node, index):current_Node = self.headerif 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.nextself.header.next = nodeself.length += 1else:for i in range(1, index - 1):current_Node = current_Node.nextnode.next = current_Node.nextcurrent_Node.next = nodeself.length += 1# 5、遍历def travel(self):current_Node = self.headerif self.length == 0:print("目前链表没有数据！")else:print("目前链表里面的元素有:", end=" ")for i in range(self.length):print("%s " % current_Node.element, end=" ")current_Node = current_Node.nextprint("\n")# 6、排序不用交换节点的位置，只需要交换节点上的数据值def list_sort(self):for i in range(0, self.length - 1):current_Node = self.headerfor j in range(0, self.length - i - 1):if current_Node.element > current_Node.next.element:temp = current_Node.elementcurrent_Node.element = current_Node.next.elementcurrent_Node.next.element = tempcurrent_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())#   returnelse:if index == 1:self.header = self.header.nextcurrentNode = self.headerelif index == 2:current_Node = self.headercurrent_Node.next = current_Node.next.nextelse:current_Node = self.headerfor i in range(1, index - 1):current_Node = current_Node.nextcurrent_Node.next = current_Node.next.nextself.length -= 1# 8、查找是否包含,并返回下标def isContain(self, num):contain = 0current_Node = self.headerfor i in range(self.length):if current_Node.element == num:print("%d在链表中%d处\n" % (num, i+1))#i+1是在正常人认为的位置处，程序员一般是从0开始算起contain = 1current_Node = current_Node.nextif contain == 0:print("%d不在链表中\n" % num)# 9、根据下标找节点def searchNodeByIndex(self, index):current_Node = self.headerif index <= 0 or index > self.length:while(index <= 0 or index > self.length):print("你输入的下标不对，请重新输入:")index=eval(input())#   return 0if index > 0 or index <= self.length:for i in range(index - 1):current_Node = current_Node.nextreturn current_Node# 10、根据下标修改节点的值def Alert(self, index, num):#index定义为下标current_Node = self.headerif index <= 0 or index > self.length:print("你输入的下标不对，请重新输入!\n")else:for i in range(index - 1):current_Node = current_Node.nextcurrent_Node.element = numdef 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:breakif __name__ == '__main__':main()

五、运行结果

注意：在每一步都希望键入数值，不然程序会崩溃！！！

六、算法

将链表的一般基本操作在一个框架下，可以完成自己想要的所有基本操作；

不足之处就是在让你插入数值的情况下，没有键入数值，而后敲了回车键会出现报错的情况，如图：

这一方面需要继续改进。

七、总结

总的来说还是很满意的，刚开始写单链表一直是想着用c/c++来实现，想着python没有指针这个功能，以为有python将实现不了，但是后面想到python追根溯源也是对c的一种打包形式，应该能实现。最后我将认真的将指针理解了一遍，指针就是指向地址的地址，那么这样的话，我在python中也可以用一种类型来表示指向地址的地址。在对链表的理解，链表的结点有数据域和地址域，那么我用类来实现即可。最终实现了之后收获还是颇大的。

作者：诚长ing

时间：2019.6.28