设为首页收藏本站
开启辅助访问 软件测试门户软件测试培训软件测试论坛测试解决方案文章资料精选软件测试博客软件测试招聘

51Testing软件测试论坛

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

QQ登录

只需一步，快速开始

微信登录，快人一步

手机号码，快捷登录

51Testing软件测试论坛 »软件测试论坛 › [软件测试综合栏目] › [软件测试新手上路] › Python数据结构:四种链表的集合
返回列表 发新帖
查看: 3376|回复: 0
打印 上一主题 下一主题

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

[复制链接]
lsekfe
  • TA的每日心情
    无聊
    3 天前

    • 签到天数: 1050 天

    连续签到: 1 天

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

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

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

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

    5. 　　    def __init__(self):

    7. 　　        super().__init__()

    9. 　　        self.head = Node(None)

    11. 　　        self.head.next = self.head

    13. 　　    # 创建链表

    15. 　　    def Create(self):

    17. 　　        while True:

    19. 　　            try:

    21. 　　                print("*" * 50)

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

    25. 　　                print("*" * 50)

    27. 　　                cNode = self.head

    29. 　　                str1 = input('')

    31. 　　                strList = str1.split()

    33. 　　                for i in strList:

    35. 　　                    nNode = Node(int(i))

    37. 　　                    cNode.next = nNode

    39. 　　                    cNode = cNode.next

    41. 　　                cNode.next = self.head

    43. 　　                break

    45. 　　            except:

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

    49. 　　    # 获取链表长度

    51. 　　    def GetLength(self):

    53. 　　        cNode = self.head

    55. 　　        length = 0

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

    59. 　　            length += 1

    61. 　　            cNode = cNode.next

    63. 　　        return length

    65. 　　    # 遍历

    67. 　　    def TraverseElement(self):

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

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

    73. 　　        cNode = self.head

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

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

    79. 　　            cNode = cNode.next

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

    83. 　　        print('None]')

    85. 　　    # 尾部插入

    87. 　　    def InsertElementInTail(self):

    89. 　　        cNode = self.head

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

    93. 　　        nNode = Node(int(Element))

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

    97. 　　            cNode = cNode.next

    99. 　　        cNode.next = nNode

    101. 　　        nNode.next = self.head

    103. 　　    # 指定位置插入

    105. 　　    def InsertElement(self):

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

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

    111. 　　        cNode = self.head

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

    115. 　　        pos = 0

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

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

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

    123. 　　            pNode = cNode

    125. 　　            cNode = cNode.next

    127. 　　            pos += 1

    129. 　　        if index == pos:

    131. 　　            qNode = Node(key)

    133. 　　            pNode.next = qNode

    135. 　　            qNode.next = cNode

    137. 　　    # 按值删除

    139. 　　    def DeleteElement(self):

    141. 　　        if self.IsEmpty():

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

    145. 　　            return

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

    149. 　　        # pos = 0

    151. 　　        cNode = self.head

    153. 　　        nNode = cNode.next

    155. 　　        while nNode is not self.head:

    157. 　　            if nNode.data is key:

    159. 　　                cNode.next = nNode.next

    161. 　　                del nNode

    163. 　　                nNode = cNode.next

    165. 　　            else:

    167. 　　                cNode = nNode

    169. 　　                nNode = nNode.next

    171. 　　    # 根据值查找

    173. 　　    def FindElement(self):

    175. 　　        pos = 0

    177. 　　        cNode = self.head

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

    181. 　　        if self.IsEmpty():

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

    185. 　　            return

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

    189. 　　            cNode = cNode.next

    191. 　　            pos += 1

    193. 　　        if cNode.data == key:

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

    197. 　　        else:

    199. 　　            print('查找失败')

    201. 　　    # 根据位置查找

    203. 　　    def GetElement(self):

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

    207. 　　        cNode = self.head

    209. 　　        pos = 0

    211. 　　        while pos != index:

    213. 　　            cNode = cNode.next

    215. 　　            pos += 1

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

    219. 　　    # 销毁

    221. 　　    def ClearElement(self):

    223. 　　        cNode = self.head

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

    3. 　　class DLL(SingleLinkList):

    5. 　　    """双向链表"""

    7. 　　    def __init__(self):

    9. 　　        super().__init__()

    11. 　　        self.head = Node(None)

    13. 　　    # 创建链表

    15. 　　    def Create(self):

    17. 　　        while True:

    19. 　　            try:

    21. 　　                print("*" * 50)

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

    25. 　　                print("*" * 50)

    27. 　　                cNode = self.head

    29. 　　                str1 = input('')

    31. 　　                strList = str1.split()

    33. 　　                for i in strList:

    35. 　　                    nNode = Node(int(i))

    37. 　　                    cNode.next = nNode

    39. 　　                    nNode.prev = cNode

    41. 　　                    cNode = cNode.next

    43. 　　                break

    45. 　　            except:

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

    49. 　　    # 遍历

    51. 　　    def TraverseElement(self):

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

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

    57. 　　        cNode = self.head

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

    61. 　　        while cNode.next is not None:

    63. 　　            cNode = cNode.next

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

    67. 　　        print('None]')

    69. 　　    # 头部插入

    71. 　　    def InsertElementHead(self):

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

    75. 　　        cNode = self.head.next

    77. 　　        pNode = self.head

    79. 　　        nNode = Node(int(Element))

    81. 　　        nNode.prev = pNode

    83. 　　        pNode.next = nNode

    85. 　　        nNode.next = cNode

    87. 　　        cNode.prev = nNode

    89. 　　    # 尾部插入

    91. 　　    def InsertElementInTail(self):

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

    95. 　　        nNode = Node(int(Element))

    97. 　　        cNode = self.head

    99. 　　        while cNode.next is not None:

    101. 　　            cNode = cNode.next

    103. 　　        cNode.next = nNode

    105. 　　        nNode.prev = cNode

    107. 　　    # 指定位置插入

    109. 　　    def InsertElement(self):

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

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

    115. 　　        cNode = self.head

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

    119. 　　        pos = 0

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

    123. 　　            pNode = cNode

    125. 　　            cNode = cNode.next

    127. 　　            pos += 1

    129. 　　        if index == pos:

    131. 　　            qNode = Node(key)

    133. 　　            pNode.next = qNode

    135. 　　            qNode.next = cNode

    137. 　　            cNode.prev = qNode

    139. 　　    # 按值删除

    141. 　　    def DeleteElement(self):

    143. 　　        cNode = self.head

    145. 　　        pNode = self.head

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

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

    151. 　　            pNode = cNode

    153. 　　            cNode = cNode.next

    155. 　　        if cNode.data == data:

    157. 　　            if cNode.next is None:

    159. 　　                pNode.next = None

    161. 　　                del cNode

    163. 　　            else:

    165. 　　                pNode.next = cNode.next

    167. 　　                cNode.next.prev = pNode

    169. 　　                del cNode

    171. 　　    # 按位置删除

    173. 　　    def DeleteElement2(self):

    175. 　　        pos = 0

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

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

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

    183. 　　        cNode = self.head

    185. 　　        nNode = cNode.next

    187. 　　        while pos is not key - 1:

    189. 　　            pos += 1

    191. 　　            cNode = nNode

    193. 　　            nNode = nNode.next

    195. 　　        cNode.next = nNode.next

    197. 　　        cNode.prev = nNode.prev

    199. 　　        del nNode

    201. 　　    # 销毁

    203. 　　    def ClearElement(self):

    205. 　　        cNode = self.head

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

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

    5. 　　    def __init__(self):

    7. 　　        super().__init__()

    9. 　　        self.head = Node(None)

    11. 　　        self.head.next = self.head

    13. 　　    def GetLength(self):

    15. 　　        cNode = self.head

    17. 　　        length = 0

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

    21. 　　            length += 1

    23. 　　            cNode = cNode.next

    25. 　　        return length

    27. 　　    # 创建链表

    29. 　　    def Create(self):

    31. 　　        while True:

    33. 　　            try:

    35. 　　                print("*" * 50)

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

    39. 　　                print("*" * 50)

    41. 　　                cNode = self.head

    43. 　　                str1 = input('')

    45. 　　                strList = str1.split()

    47. 　　                for i in strList:

    49. 　　                    nNode = Node(int(i))

    51. 　　                    cNode.next = nNode

    53. 　　                    nNode.prev = cNode

    55. 　　                    nNode.next = self.head

    57. 　　                    self.head.prev = nNode

    59. 　　                    cNode = cNode.next

    61. 　　                break

    63. 　　            except:

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

    67. 　　    # 遍历

    69. 　　    def TraverseElement(self):

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

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

    75. 　　        cNode = self.head

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

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

    81. 　　            cNode = cNode.next

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

    85. 　　        print('None]')

    87. 　　    # 尾部插入

    89. 　　    def InsertElementInTail(self):

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

    93. 　　        nNode = Node(int(Element))

    95. 　　        cNode = self.head

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

    99. 　　            cNode = cNode.next

    101. 　　        cNode.next = nNode

    103. 　　        nNode.prev = cNode

    105. 　　        nNode.next = self.head

    107. 　　        self.head.prev = nNode

    109. 　　    # 指定位置插入

    111. 　　    def InsertElement(self):

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

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

    117. 　　        cNode = self.head

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

    121. 　　        pos = 0

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

    125. 　　            pNode = cNode

    127. 　　            cNode = cNode.next

    129. 　　            pos += 1

    131. 　　        if index == pos:

    133. 　　            qNode = Node(key)

    135. 　　            pNode.next = qNode

    137. 　　            qNode.prev = pNode

    139. 　　            qNode.next = cNode

    141. 　　            cNode.prev = qNode

    143. 　　    # 按值删除

    145. 　　    def DeleteElement(self):

    147. 　　        cNode = self.head

    149. 　　        pNode = self.head

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

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

    155. 　　            pNode = cNode

    157. 　　            cNode = cNode.next

    159. 　　        if cNode.data == data:

    161. 　　            if cNode.next is None:

    163. 　　                pNode.next = None

    165. 　　                del cNode

    167. 　　            else:

    169. 　　                pNode.next = cNode.next

    171. 　　                cNode.next.prev = pNode

    173. 　　                del cNode

    175. 　　    # 销毁

    177. 　　    def ClearElement(self):

    179. 　　        cNode = self.head

    181. 　　        cNode.next = None
    复制代码

    菜单
    1. def menu():

    3. 　　    print("*" * 30)

    5. 　　    print("python链表")

    7. 　　    print("*" * 30)

    9. 　　    print("""    1、创建

    11. 　　    2、插入

    13. 　　    3、删除

    15. 　　    4、查找

    17. 　　    0、结束

    19. 　　        """)
    复制代码

    主函数
    1. def main():

    3. 　　    global a

    5. 　　    while True:

    7. 　　        try:

    9. 　　            os.system("cls")

    11. 　　            print("*" * 50)

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

    15. 　　            print("*" * 50)

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

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

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

    23. 　　            if i == 1:

    25. 　　                a = SingleLinkList()

    27. 　　            elif i == 2:

    29. 　　                a = CSLL()

    31. 　　            elif i == 3:

    33. 　　                a = DLL()

    35. 　　            elif i == 4:

    37. 　　                a = CDLL()

    39. 　　            elif i == 0:

    41. 　　                return

    43. 　　            while True:

    45. 　　                try:

    47. 　　                    os.system('cls')

    49. 　　                    menu()

    51. 　　                    a.TraverseElement()

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

    55. 　　                    if i == 1:

    57. 　　                        a.Create()

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

    61. 　　                    elif i == 2:

    63. 　　                        while True:

    65. 　　                            print("1.头插")

    67. 　　                            print("2.尾插")

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

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

    73. 　　                            if i == 1:

    75. 　　                                a.InsertElementHead()

    77. 　　                                break

    79. 　　                            elif i == 2:

    81. 　　                                a.InsertElementInTail()

    83. 　　                                break

    85. 　　                            elif i == 3:

    87. 　　                                a.InsertElement()

    89. 　　                                break

    91. 　　                            else:

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

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

    97. 　　                    elif i == 3:

    99. 　　                        while True:

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

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

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

    107. 　　                            if i == 1:

    109. 　　                                a.DeleteElement()

    111. 　　                                break

    113. 　　                            elif i == 2:

    115. 　　                                a.DeleteElement2()

    117. 　　                                break

    119. 　　                            else:

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

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

    125. 　　                    elif i == 4:

    127. 　　                        while True:

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

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

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

    135. 　　                            if i == 1:

    137. 　　                                a.FindElement()

    139. 　　                                break

    141. 　　                            elif i == 2:

    143. 　　                                a.GetElement()

    145. 　　                                break

    147. 　　                            else:

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

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

    153. 　　                    elif i == 0:

    155. 　　                        break

    157. 　　                    else:

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

    161. 　　                except:

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

    165. 　　        except:

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

    169. 　　main()
    复制代码


    分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
    微信
    收藏收藏1
    【你来问我来答第140期】：敏捷测试的奥秘与挑战：问答专场！
    回复

    使用道具 举报

    返回列表 发新帖

    本版积分规则

    关闭

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

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

    GMT+8, 2024-11-24 12:51 , Processed in 0.076793 second(s), 24 queries .

    Powered by Discuz! X3.2

    © 2001-2024 Comsenz Inc.

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