Python数据结构:四种链表的集合
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()
页:
[1]
