python数据结构四个链表的集合
结点的创建
import os # 创建节点 class Node: def __init__(self, data): self.data = data self.next = None self.prev = None |
创建单链表类
class SingleLinkList: """单链表""" def __init__(self): self.head = Node(None) # 创建链表 def Create(self): while True: try: print("*" * 50) print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]") print("*" * 50) cNode = self.head str1 = input('') strList = str1.split() for i in strList: nNode = Node(int(i)) cNode.next = nNode cNode = cNode.next break except: print('\n 您输入的值有误,请重新输入! \n') # 判断是否为空 def IsEmpty(self): if self.GetLength() == 0: return True else: return False # 获取链表长度 def GetLength(self): cNode = self.head length = 0 while cNode.next is not None: length += 1 cNode = cNode.next return length # 遍历 def TraverseElement(self): print('当前为单链表', end='') print('长度为:' + str(self.GetLength())) cNode = self.head print("[Head->", end="") while cNode.next is not None: cNode = cNode.next print(cNode.data, '->', end=' ') print('None]') # 头部插入 def InsertElementHead(self): Element = input("请输入首端要插入的数据:") cNode = self.head nNode = Node(int(Element)) nNode.next = cNode.next cNode.next = nNode # 尾部插入 def InsertElementInTail(self): cNode = self.head Element = input("请输入尾端要插入的数据:") nNode = Node(int(Element)) while cNode.next is not None: cNode = cNode.next cNode.next = nNode # 指定位置插入 def InsertElement(self): index = int(input('请输入要插入的位置:')) key = int(input("请输入要插入的值:")) cNode = self.head pNode = self.head # 前一个结点 pos = 0 while cNode.next is not None and pos < index: pNode = cNode cNode = cNode.next pos += 1 if index == pos: qNode = Node(key) pNode.next = qNode qNode.next = cNode # 按值删除 def DeleteElement(self): if self.IsEmpty(): print('单链表为空') return key = int(input('请输入要删除的值:')) # pos = 0 cNode = self.head nNode = cNode.next while nNode is not None: if nNode.data is key: cNode.next = nNode.next del nNode nNode = cNode.next else: cNode = nNode nNode = nNode.next # 按位置删除 def DeleteElement2(self): pos = 0 key = int(input('请输入要删除的结点的位置:')) while key < 1 or key > self.GetLength(): key = int(input('你输入的位置超出范围,请重新输入要删除的结点位置:')) cNode = self.head nNode = cNode.next while pos is not key - 1: pos += 1 cNode = nNode nNode = nNode.next cNode.next = nNode.next del nNode # 根据值查找 def FindElement(self): pos = 0 cNode = self.head key = int(input('请输入要查找的值:')) if self.IsEmpty(): print('单链表为空') return while cNode.next is not None and cNode.data != key: cNode = cNode.next pos += 1 if cNode.data == key: print('查找成功,位置为:', pos) else: print('查找失败') # 根据位置查找 def GetElement(self): index = int(input('请输入要查找的位置:')) cNode = self.head pos = 0 while pos != index: cNode = cNode.next pos += 1 print('该单链表的第', index, '个位置的值为', cNode.data, end="\n", ) # 销毁 def ClearElement(self): self.head = 0 |
创建循环单链表类 (继承单链表)
class CSLL(SingleLinkList): """单向循环链表""" def __init__(self): super().__init__() self.head = Node(None) self.head.next = self.head # 创建链表 def Create(self): while True: try: print("*" * 50) print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]") print("*" * 50) cNode = self.head str1 = input('') strList = str1.split() for i in strList: nNode = Node(int(i)) cNode.next = nNode cNode = cNode.next cNode.next = self.head break except: print('\n 您输入的值有误,请重新输入! \n') # 获取链表长度 def GetLength(self): cNode = self.head length = 0 while cNode.next is not self.head: length += 1 cNode = cNode.next return length # 遍历 def TraverseElement(self): print('当前为循环单链表', end='') print('长度为:' + str(self.GetLength())) cNode = self.head print("[Head->", end="") while cNode.next is not self.head: cNode = cNode.next print(cNode.data, '->', end=' ') print('None]') # 尾部插入 def InsertElementInTail(self): cNode = self.head Element = input("请输入尾端要插入的数据:") nNode = Node(int(Element)) while cNode.next is not self.head: cNode = cNode.next cNode.next = nNode nNode.next = self.head # 指定位置插入 def InsertElement(self): index = int(input('请输入要插入的位置:')) key = int(input("请输入要插入的值:")) cNode = self.head pNode = self.head # 前一个结点 pos = 0 if index >= self.GetLength() + 1: print("您输入的位置已在链表末尾,请使用尾插!") while cNode.next is not self.head and pos < index: pNode = cNode cNode = cNode.next pos += 1 if index == pos: qNode = Node(key) pNode.next = qNode qNode.next = cNode # 按值删除 def DeleteElement(self): if self.IsEmpty(): print('单链表为空') return key = int(input('请输入要删除的值:')) # pos = 0 cNode = self.head nNode = cNode.next while nNode is not self.head: if nNode.data is key: cNode.next = nNode.next del nNode nNode = cNode.next else: cNode = nNode nNode = nNode.next # 根据值查找 def FindElement(self): pos = 0 cNode = self.head key = int(input('请输入要查找的值:')) if self.IsEmpty(): print('单链表为空') return while cNode.next is not self.head and cNode.data != key: cNode = cNode.next pos += 1 if cNode.data == key: print('查找成功,位置为:', pos) else: print('查找失败') # 根据位置查找 def GetElement(self): index = int(input('请输入要查找的位置:')) cNode = self.head pos = 0 while pos != index: cNode = cNode.next pos += 1 print('该单链表的第', index, '个位置的值为', cNode.data, end="\n", ) # 销毁 def ClearElement(self): cNode = self.head cNode.next = self.head |
创建双向链表类
# 创建双向链表类 class DLL(SingleLinkList): """双向链表""" def __init__(self): super().__init__() self.head = Node(None) # 创建链表 def Create(self): while True: try: print("*" * 50) print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]") print("*" * 50) cNode = self.head str1 = input('') strList = str1.split() for i in strList: nNode = Node(int(i)) cNode.next = nNode nNode.prev = cNode cNode = cNode.next break except: print('\n 您输入的值有误,请重新输入! \n') # 遍历 def TraverseElement(self): print('当前为双向链表', end='') print('长度为:' + str(self.GetLength())) cNode = self.head print("[Head<->", end="") while cNode.next is not None: cNode = cNode.next print(cNode.data, '<->', end=' ') print('None]') # 头部插入 def InsertElementHead(self): Element = input("请输入首端要插入的数据:") cNode = self.head.next pNode = self.head nNode = Node(int(Element)) nNode.prev = pNode pNode.next = nNode nNode.next = cNode cNode.prev = nNode # 尾部插入 def InsertElementInTail(self): Element = input("请输入尾端要插入的数据:") nNode = Node(int(Element)) cNode = self.head while cNode.next is not None: cNode = cNode.next cNode.next = nNode nNode.prev = cNode # 指定位置插入 def InsertElement(self): index = int(input('请输入要插入的位置:')) key = int(input("请输入要插入的值:")) cNode = self.head pNode = self.head # 前一个结点 pos = 0 while cNode.next is not None and pos < index: pNode = cNode cNode = cNode.next pos += 1 if index == pos: qNode = Node(key) pNode.next = qNode qNode.next = cNode cNode.prev = qNode # 按值删除 def DeleteElement(self): cNode = self.head pNode = self.head data = int(input("请输入要删除的元素值:")) while cNode.next is not None and cNode.data != data: pNode = cNode cNode = cNode.next if cNode.data == data: if cNode.next is None: pNode.next = None del cNode else: pNode.next = cNode.next cNode.next.prev = pNode del cNode # 按位置删除 def DeleteElement2(self): pos = 0 key = int(input('请输入要删除的结点的位置:')) while key < 1 or key > self.GetLength(): key = int(input('你输入的位置超出范围,请重新输入要删除的结点位置:')) cNode = self.head nNode = cNode.next while pos is not key - 1: pos += 1 cNode = nNode nNode = nNode.next cNode.next = nNode.next cNode.prev = nNode.prev del nNode # 销毁 def ClearElement(self): cNode = self.head cNode.next = None |
创建循环双向链表类
class CDLL(DLL): """循环双向链表""" def __init__(self): super().__init__() self.head = Node(None) self.head.next = self.head def GetLength(self): cNode = self.head length = 0 while cNode.next is not self.head: length += 1 cNode = cNode.next return length # 创建链表 def Create(self): while True: try: print("*" * 50) print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]") print("*" * 50) cNode = self.head str1 = input('') strList = str1.split() for i in strList: nNode = Node(int(i)) cNode.next = nNode nNode.prev = cNode nNode.next = self.head self.head.prev = nNode cNode = cNode.next break except: print('\n 您输入的值有误,请重新输入! \n') # 遍历 def TraverseElement(self): print('当前为循环双链表 ', end=' ') print('长度为:' + str(self.GetLength())) cNode = self.head print("[Head<->", end="") while cNode.next is not self.head: cNode = cNode.next print(cNode.data, '<->', end=' ') print('None]') # 尾部插入 def InsertElementInTail(self): Element = input("请输入尾端要插入的数据:") nNode = Node(int(Element)) cNode = self.head while cNode.next is not self.head: cNode = cNode.next cNode.next = nNode nNode.prev = cNode nNode.next = self.head self.head.prev = nNode # 指定位置插入 def InsertElement(self): index = int(input('请输入要插入的位置:')) key = int(input("请输入要插入的值:")) cNode = self.head pNode = self.head # 前一个结点 pos = 0 while cNode.next is not self.head and pos < index: pNode = cNode cNode = cNode.next pos += 1 if index == pos: qNode = Node(key) pNode.next = qNode qNode.prev = pNode qNode.next = cNode cNode.prev = qNode # 按值删除 def DeleteElement(self): cNode = self.head pNode = self.head data = int(input("请输入要删除的元素值:")) while cNode.next is not self.head and cNode.data != data: pNode = cNode cNode = cNode.next if cNode.data == data: if cNode.next is None: pNode.next = None del cNode else: pNode.next = cNode.next cNode.next.prev = pNode del cNode # 销毁 def ClearElement(self): cNode = self.head cNode.next = None |
菜单
def menu(): print("*" * 30) print("python链表") print("*" * 30) print(""" 1、创建 2、插入 3、删除 4、查找 0、结束 """) |
主函数
def main(): global a while True: try: os.system("cls") print("*" * 50) print("\t\tpython链表") print("*" * 50) i = int(input("请选择将要创建的链表:\n1.单链表 2.循环单链表 3.双链表 4.循环双链表 0.退出\n")) while i not in range(0, 5): i = int(input("输入错误! 请重新选择将要创建的链表:")) if i == 1: a = SingleLinkList() elif i == 2: a = CSLL() elif i == 3: a = DLL() elif i == 4: a = CDLL() elif i == 0: return while True: try: os.system('cls') menu() a.TraverseElement() i = int(input("输入您想要进行的操作序号:")) if i == 1: a.Create() input("按任意键返回上级菜单") elif i == 2: while True: print("1.头插") print("2.尾插") print("3.指定插入") i = int(input("输入您想要进行的操作序号:")) if i == 1: a.InsertElementHead() break elif i == 2: a.InsertElementInTail() break elif i == 3: a.InsertElement() break else: print("您的输入有误,请重新输入") input("按任意键返回上级菜单") elif i == 3: while True: print("1.按值删除") print("2.按位置删除") i = int(input("输入您想要进行的操作序号:")) if i == 1: a.DeleteElement() break elif i == 2: a.DeleteElement2() break else: print("您的输入有误,请重新输入") input("按任意键返回上级菜单") elif i == 4: while True: print("1.按值查找") print("2.按位置查找") i = int(input("输入您想要进行的操作序号:")) if i == 1: a.FindElement() break elif i == 2: a.GetElement() break else: print("您的输入有误,请重新输入") input("按任意键返回上级菜单") elif i == 0: break else: input("您输入的有误,请按任意键重试!") except: input("输入有误,按任意键返回菜单!") except: input("输入有误,按任意键返回主菜单!") main() |
本文内容不用于商业目的,如涉及知识产权问题,请权利人联系51Testing小编(021-64471599-8017),我们将立即处理。