51Testing软件测试论坛

 找回密码
 (注-册)加入51Testing

QQ登录

只需一步,快速开始

微信登录,快人一步

手机号码,快捷登录

查看: 3368|回复: 0
打印 上一主题 下一主题

[转贴] Python数据结构:四种链表的集合

[复制链接]
  • TA的每日心情
    擦汗
    3 天前
  • 签到天数: 1042 天

    连续签到: 4 天

    [LV.10]测试总司令

    跳转到指定楼层
    1#
    发表于 2020-10-16 09:39:49 | 只看该作者 回帖奖励 |正序浏览 |阅读模式
     python数据结构四个链表的集合
      结点的创建
    1. import os

    2.   # 创建节点
    3.   class Node:
    4.       def __init__(self, data):
    5.           self.data = data
    6.           self.next = None
    7.           self.prev = None
    复制代码
    创建单链表类
    1. class SingleLinkList:

    2.       """单链表"""
    3.       def __init__(self):
    4.           self.head = Node(None)
    5.       # 创建链表
    6.       def Create(self):
    7.           while True:
    8.               try:
    9.                   print("*" * 50)
    10.                   print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]")
    11.                   print("*" * 50)
    12.                   cNode = self.head
    13.                   str1 = input('')
    14.                   strList = str1.split()
    15.                   for i in strList:
    16.                       nNode = Node(int(i))
    17.                       cNode.next = nNode
    18.                       cNode = cNode.next
    19.                   break
    20.               except:
    21.                   print('\n 您输入的值有误,请重新输入! \n')
    22.       # 判断是否为空
    23.       def IsEmpty(self):
    24.           if self.GetLength() == 0:
    25.               return True
    26.           else:
    27.               return False
    28.       # 获取链表长度
    29.       def GetLength(self):
    30.           cNode = self.head
    31.           length = 0
    32.           while cNode.next is not None:
    33.               length += 1
    34.               cNode = cNode.next
    35.           return length
    36.       # 遍历
    37.       def TraverseElement(self):
    38.           print('当前为单链表', end='')
    39.           print('长度为:' + str(self.GetLength()))
    40.           cNode = self.head
    41.           print("[Head->", end="")
    42.           while cNode.next is not None:
    43.               cNode = cNode.next
    44.               print(cNode.data, '->', end=' ')
    45.           print('None]')
    46.       # 头部插入
    47.       def InsertElementHead(self):
    48.           Element = input("请输入首端要插入的数据:")
    49.           cNode = self.head
    50.           nNode = Node(int(Element))
    51.           nNode.next = cNode.next
    52.           cNode.next = nNode
    53.       # 尾部插入
    54.       def InsertElementInTail(self):
    55.           cNode = self.head
    56.           Element = input("请输入尾端要插入的数据:")
    57.           nNode = Node(int(Element))
    58.           while cNode.next is not None:
    59.               cNode = cNode.next
    60.           cNode.next = nNode
    61.       # 指定位置插入
    62.       def InsertElement(self):
    63.           index = int(input('请输入要插入的位置:'))
    64.           key = int(input("请输入要插入的值:"))
    65.           cNode = self.head
    66.           pNode = self.head  # 前一个结点
    67.           pos = 0
    68.           while cNode.next is not None and pos < index:
    69.               pNode = cNode
    70.               cNode = cNode.next
    71.               pos += 1
    72.           if index == pos:
    73.               qNode = Node(key)
    74.               pNode.next = qNode
    75.               qNode.next = cNode
    76.       # 按值删除
    77.       def DeleteElement(self):
    78.           if self.IsEmpty():
    79.               print('单链表为空')
    80.               return
    81.           key = int(input('请输入要删除的值:'))
    82.           # pos = 0
    83.           cNode = self.head
    84.           nNode = cNode.next
    85.           while nNode is not None:
    86.               if nNode.data is key:
    87.                   cNode.next = nNode.next
    88.                   del nNode
    89.                   nNode = cNode.next
    90.               else:
    91.                   cNode = nNode
    92.                   nNode = nNode.next
    93.       # 按位置删除
    94.       def DeleteElement2(self):
    95.           pos = 0
    96.           key = int(input('请输入要删除的结点的位置:'))
    97.           while key < 1 or key > self.GetLength():
    98.               key = int(input('你输入的位置超出范围,请重新输入要删除的结点位置:'))
    99.           cNode = self.head
    100.           nNode = cNode.next
    101.           while pos is not key - 1:
    102.               pos += 1
    103.               cNode = nNode
    104.               nNode = nNode.next
    105.           cNode.next = nNode.next
    106.           del nNode
    107.       # 根据值查找
    108.       def FindElement(self):
    109.           pos = 0
    110.           cNode = self.head
    111.           key = int(input('请输入要查找的值:'))
    112.           if self.IsEmpty():
    113.               print('单链表为空')
    114.               return
    115.           while cNode.next is not None and cNode.data != key:
    116.               cNode = cNode.next
    117.               pos += 1
    118.           if cNode.data == key:
    119.               print('查找成功,位置为:', pos)
    120.           else:
    121.               print('查找失败')
    122.       # 根据位置查找
    123.       def GetElement(self):
    124.           index = int(input('请输入要查找的位置:'))
    125.           cNode = self.head
    126.           pos = 0
    127.           while pos != index:
    128.               cNode = cNode.next
    129.               pos += 1
    130.           print('该单链表的第', index, '个位置的值为', cNode.data, end="\n", )
    131.       # 销毁
    132.       def ClearElement(self):
    133.           self.head = 0
    复制代码
    创建循环单链表类 (继承单链表)
    1. class CSLL(SingleLinkList):

    2.       """单向循环链表"""

    3.       def __init__(self):

    4.           super().__init__()

    5.           self.head = Node(None)

    6.           self.head.next = self.head

    7.       # 创建链表

    8.       def Create(self):

    9.           while True:

    10.               try:

    11.                   print("*" * 50)

    12.                   print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]")

    13.                   print("*" * 50)

    14.                   cNode = self.head

    15.                   str1 = input('')

    16.                   strList = str1.split()

    17.                   for i in strList:

    18.                       nNode = Node(int(i))

    19.                       cNode.next = nNode

    20.                       cNode = cNode.next

    21.                   cNode.next = self.head

    22.                   break

    23.               except:

    24.                   print('\n 您输入的值有误,请重新输入! \n')

    25.       # 获取链表长度

    26.       def GetLength(self):

    27.           cNode = self.head

    28.           length = 0

    29.           while cNode.next is not self.head:

    30.               length += 1

    31.               cNode = cNode.next

    32.           return length

    33.       # 遍历

    34.       def TraverseElement(self):

    35.           print('当前为循环单链表', end='')

    36.           print('长度为:' + str(self.GetLength()))

    37.           cNode = self.head

    38.           print("[Head->", end="")

    39.           while cNode.next is not self.head:

    40.               cNode = cNode.next

    41.               print(cNode.data, '->', end=' ')

    42.           print('None]')

    43.       # 尾部插入

    44.       def InsertElementInTail(self):

    45.           cNode = self.head

    46.           Element = input("请输入尾端要插入的数据:")

    47.           nNode = Node(int(Element))

    48.           while cNode.next is not self.head:

    49.               cNode = cNode.next

    50.           cNode.next = nNode

    51.           nNode.next = self.head

    52.       # 指定位置插入

    53.       def InsertElement(self):

    54.           index = int(input('请输入要插入的位置:'))

    55.           key = int(input("请输入要插入的值:"))

    56.           cNode = self.head

    57.           pNode = self.head  # 前一个结点

    58.           pos = 0

    59.           if index >= self.GetLength() + 1:

    60.               print("您输入的位置已在链表末尾,请使用尾插!")

    61.           while cNode.next is not self.head and pos < index:

    62.               pNode = cNode

    63.               cNode = cNode.next

    64.               pos += 1

    65.           if index == pos:

    66.               qNode = Node(key)

    67.               pNode.next = qNode

    68.               qNode.next = cNode

    69.       # 按值删除

    70.       def DeleteElement(self):

    71.           if self.IsEmpty():

    72.               print('单链表为空')

    73.               return

    74.           key = int(input('请输入要删除的值:'))

    75.           # pos = 0

    76.           cNode = self.head

    77.           nNode = cNode.next

    78.           while nNode is not self.head:

    79.               if nNode.data is key:

    80.                   cNode.next = nNode.next

    81.                   del nNode

    82.                   nNode = cNode.next

    83.               else:

    84.                   cNode = nNode

    85.                   nNode = nNode.next

    86.       # 根据值查找

    87.       def FindElement(self):

    88.           pos = 0

    89.           cNode = self.head

    90.           key = int(input('请输入要查找的值:'))

    91.           if self.IsEmpty():

    92.               print('单链表为空')

    93.               return

    94.           while cNode.next is not self.head and cNode.data != key:

    95.               cNode = cNode.next

    96.               pos += 1

    97.           if cNode.data == key:

    98.               print('查找成功,位置为:', pos)

    99.           else:

    100.               print('查找失败')

    101.       # 根据位置查找

    102.       def GetElement(self):

    103.           index = int(input('请输入要查找的位置:'))

    104.           cNode = self.head

    105.           pos = 0

    106.           while pos != index:

    107.               cNode = cNode.next

    108.               pos += 1

    109.           print('该单链表的第', index, '个位置的值为', cNode.data, end="\n", )

    110.       # 销毁

    111.       def ClearElement(self):

    112.           cNode = self.head

    113.           cNode.next = self.head
    复制代码
      创建双向链表类
    1. # 创建双向链表类

    2.   class DLL(SingleLinkList):

    3.       """双向链表"""

    4.       def __init__(self):

    5.           super().__init__()

    6.           self.head = Node(None)

    7.       # 创建链表

    8.       def Create(self):

    9.           while True:

    10.               try:

    11.                   print("*" * 50)

    12.                   print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]")

    13.                   print("*" * 50)

    14.                   cNode = self.head

    15.                   str1 = input('')

    16.                   strList = str1.split()

    17.                   for i in strList:

    18.                       nNode = Node(int(i))

    19.                       cNode.next = nNode

    20.                       nNode.prev = cNode

    21.                       cNode = cNode.next

    22.                   break

    23.               except:

    24.                   print('\n 您输入的值有误,请重新输入! \n')

    25.       # 遍历

    26.       def TraverseElement(self):

    27.           print('当前为双向链表', end='')

    28.           print('长度为:' + str(self.GetLength()))

    29.           cNode = self.head

    30.           print("[Head<->", end="")

    31.           while cNode.next is not None:

    32.               cNode = cNode.next

    33.               print(cNode.data, '<->', end=' ')

    34.           print('None]')

    35.       # 头部插入

    36.       def InsertElementHead(self):

    37.           Element = input("请输入首端要插入的数据:")

    38.           cNode = self.head.next

    39.           pNode = self.head

    40.           nNode = Node(int(Element))

    41.           nNode.prev = pNode

    42.           pNode.next = nNode

    43.           nNode.next = cNode

    44.           cNode.prev = nNode

    45.       # 尾部插入

    46.       def InsertElementInTail(self):

    47.           Element = input("请输入尾端要插入的数据:")

    48.           nNode = Node(int(Element))

    49.           cNode = self.head

    50.           while cNode.next is not None:

    51.               cNode = cNode.next

    52.           cNode.next = nNode

    53.           nNode.prev = cNode

    54.       # 指定位置插入

    55.       def InsertElement(self):

    56.           index = int(input('请输入要插入的位置:'))

    57.           key = int(input("请输入要插入的值:"))

    58.           cNode = self.head

    59.           pNode = self.head  # 前一个结点

    60.           pos = 0

    61.           while cNode.next is not None and pos < index:

    62.               pNode = cNode

    63.               cNode = cNode.next

    64.               pos += 1

    65.           if index == pos:

    66.               qNode = Node(key)

    67.               pNode.next = qNode

    68.               qNode.next = cNode

    69.               cNode.prev = qNode

    70.       # 按值删除

    71.       def DeleteElement(self):

    72.           cNode = self.head

    73.           pNode = self.head

    74.           data = int(input("请输入要删除的元素值:"))

    75.           while cNode.next is not None and cNode.data != data:

    76.               pNode = cNode

    77.               cNode = cNode.next

    78.           if cNode.data == data:

    79.               if cNode.next is None:

    80.                   pNode.next = None

    81.                   del cNode

    82.               else:

    83.                   pNode.next = cNode.next

    84.                   cNode.next.prev = pNode

    85.                   del cNode

    86.       # 按位置删除

    87.       def DeleteElement2(self):

    88.           pos = 0

    89.           key = int(input('请输入要删除的结点的位置:'))

    90.           while key < 1 or key > self.GetLength():

    91.               key = int(input('你输入的位置超出范围,请重新输入要删除的结点位置:'))

    92.           cNode = self.head

    93.           nNode = cNode.next

    94.           while pos is not key - 1:

    95.               pos += 1

    96.               cNode = nNode

    97.               nNode = nNode.next

    98.           cNode.next = nNode.next

    99.           cNode.prev = nNode.prev

    100.           del nNode

    101.       # 销毁

    102.       def ClearElement(self):

    103.           cNode = self.head

    104.           cNode.next = None
    复制代码
     创建循环双向链表类
    1. class CDLL(DLL):

    2.       """循环双向链表"""

    3.       def __init__(self):

    4.           super().__init__()

    5.           self.head = Node(None)

    6.           self.head.next = self.head

    7.       def GetLength(self):

    8.           cNode = self.head

    9.           length = 0

    10.           while cNode.next is not self.head:

    11.               length += 1

    12.               cNode = cNode.next

    13.           return length

    14.       # 创建链表

    15.       def Create(self):

    16.           while True:

    17.               try:

    18.                   print("*" * 50)

    19.                   print("*请依次输入若干数据后按回车键确认[数据之间以空格隔开]")

    20.                   print("*" * 50)

    21.                   cNode = self.head

    22.                   str1 = input('')

    23.                   strList = str1.split()

    24.                   for i in strList:

    25.                       nNode = Node(int(i))

    26.                       cNode.next = nNode

    27.                       nNode.prev = cNode

    28.                       nNode.next = self.head

    29.                       self.head.prev = nNode

    30.                       cNode = cNode.next

    31.                   break

    32.               except:

    33.                   print('\n 您输入的值有误,请重新输入! \n')

    34.       # 遍历

    35.       def TraverseElement(self):

    36.           print('当前为循环双链表  ', end=' ')

    37.           print('长度为:' + str(self.GetLength()))

    38.           cNode = self.head

    39.           print("[Head<->", end="")

    40.           while cNode.next is not self.head:

    41.               cNode = cNode.next

    42.               print(cNode.data, '<->', end=' ')

    43.           print('None]')

    44.       # 尾部插入

    45.       def InsertElementInTail(self):

    46.           Element = input("请输入尾端要插入的数据:")

    47.           nNode = Node(int(Element))

    48.           cNode = self.head

    49.           while cNode.next is not self.head:

    50.               cNode = cNode.next

    51.           cNode.next = nNode

    52.           nNode.prev = cNode

    53.           nNode.next = self.head

    54.           self.head.prev = nNode

    55.       # 指定位置插入

    56.       def InsertElement(self):

    57.           index = int(input('请输入要插入的位置:'))

    58.           key = int(input("请输入要插入的值:"))

    59.           cNode = self.head

    60.           pNode = self.head  # 前一个结点

    61.           pos = 0

    62.           while cNode.next is not self.head and pos < index:

    63.               pNode = cNode

    64.               cNode = cNode.next

    65.               pos += 1

    66.           if index == pos:

    67.               qNode = Node(key)

    68.               pNode.next = qNode

    69.               qNode.prev = pNode

    70.               qNode.next = cNode

    71.               cNode.prev = qNode

    72.       # 按值删除

    73.       def DeleteElement(self):

    74.           cNode = self.head

    75.           pNode = self.head

    76.           data = int(input("请输入要删除的元素值:"))

    77.           while cNode.next is not self.head and cNode.data != data:

    78.               pNode = cNode

    79.               cNode = cNode.next

    80.           if cNode.data == data:

    81.               if cNode.next is None:

    82.                   pNode.next = None

    83.                   del cNode

    84.               else:

    85.                   pNode.next = cNode.next

    86.                   cNode.next.prev = pNode

    87.                   del cNode

    88.       # 销毁

    89.       def ClearElement(self):

    90.           cNode = self.head

    91.           cNode.next = None
    复制代码

    菜单
    1. def menu():

    2.       print("*" * 30)

    3.       print("python链表")

    4.       print("*" * 30)

    5.       print("""    1、创建

    6.       2、插入

    7.       3、删除

    8.       4、查找

    9.       0、结束

    10.           """)
    复制代码

    主函数
    1. def main():

    2.       global a

    3.       while True:

    4.           try:

    5.               os.system("cls")

    6.               print("*" * 50)

    7.               print("\t\tpython链表")

    8.               print("*" * 50)

    9.               i = int(input("请选择将要创建的链表:\n1.单链表  2.循环单链表  3.双链表  4.循环双链表  0.退出\n"))

    10.               while i not in range(0, 5):

    11.                   i = int(input("输入错误! 请重新选择将要创建的链表:"))

    12.               if i == 1:

    13.                   a = SingleLinkList()

    14.               elif i == 2:

    15.                   a = CSLL()

    16.               elif i == 3:

    17.                   a = DLL()

    18.               elif i == 4:

    19.                   a = CDLL()

    20.               elif i == 0:

    21.                   return

    22.               while True:

    23.                   try:

    24.                       os.system('cls')

    25.                       menu()

    26.                       a.TraverseElement()

    27.                       i = int(input("输入您想要进行的操作序号:"))

    28.                       if i == 1:

    29.                           a.Create()

    30.                           input("按任意键返回上级菜单")

    31.                       elif i == 2:

    32.                           while True:

    33.                               print("1.头插")

    34.                               print("2.尾插")

    35.                               print("3.指定插入")

    36.                               i = int(input("输入您想要进行的操作序号:"))

    37.                               if i == 1:

    38.                                   a.InsertElementHead()

    39.                                   break

    40.                               elif i == 2:

    41.                                   a.InsertElementInTail()

    42.                                   break

    43.                               elif i == 3:

    44.                                   a.InsertElement()

    45.                                   break

    46.                               else:

    47.                                   print("您的输入有误,请重新输入")

    48.                           input("按任意键返回上级菜单")

    49.                       elif i == 3:

    50.                           while True:

    51.                               print("1.按值删除")

    52.                               print("2.按位置删除")

    53.                               i = int(input("输入您想要进行的操作序号:"))

    54.                               if i == 1:

    55.                                   a.DeleteElement()

    56.                                   break

    57.                               elif i == 2:

    58.                                   a.DeleteElement2()

    59.                                   break

    60.                               else:

    61.                                   print("您的输入有误,请重新输入")

    62.                           input("按任意键返回上级菜单")

    63.                       elif i == 4:

    64.                           while True:

    65.                               print("1.按值查找")

    66.                               print("2.按位置查找")

    67.                               i = int(input("输入您想要进行的操作序号:"))

    68.                               if i == 1:

    69.                                   a.FindElement()

    70.                                   break

    71.                               elif i == 2:

    72.                                   a.GetElement()

    73.                                   break

    74.                               else:

    75.                                   print("您的输入有误,请重新输入")

    76.                           input("按任意键返回上级菜单")

    77.                       elif i == 0:

    78.                           break

    79.                       else:

    80.                           input("您输入的有误,请按任意键重试!")

    81.                   except:

    82.                       input("输入有误,按任意键返回菜单!")

    83.           except:

    84.               input("输入有误,按任意键返回主菜单!")

    85.   main()
    复制代码


    分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
    收藏收藏1
    回复

    使用道具 举报

    本版积分规则

    关闭

    站长推荐上一条 /1 下一条

    小黑屋|手机版|Archiver|51Testing软件测试网 ( 沪ICP备05003035号 关于我们

    GMT+8, 2024-11-10 06:42 , Processed in 0.062973 second(s), 24 queries .

    Powered by Discuz! X3.2

    © 2001-2024 Comsenz Inc.

    快速回复 返回顶部 返回列表