ITPub博客

首页 > IT职业 > IT生活 > python之数据结构与算法分析

python之数据结构与算法分析

IT生活 作者:专注的阿熊 时间:2021-04-30 16:29:27 0 删除 编辑

python 实现单向链表

class Node(object):

     def __init__(self, elem):

         """

         :param elem: 表元素域

         next :下一结点链接域

         cursor(cur) :游标

         """

         self.elem = elem

         # 定义 next 指向空

         self.next = None

class SingleLinkList(object):

     """

     单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域 ( 元素域 ) 和一个链接域。这个链接指向链表中的下一一个节点,外汇跟单gendan5.com而最后 - 个节点的链接域则指向一个空值。

     表元素域 elem 用来存放具体的数据。

     链接域 next 用来存放下一个节点的位置 (python 中的标识 )

     变量 p 指向链表的头节点 ( 首节点 ) 的位置,从 p 出发能找到表中的任意节点。

     """

     def __init__(self, node=None):

         self.__head = node  # node.elem node.next

     def is_empty(self):

         """ 链表是否为空    """

         return self.__head is None

     def length(self):

         """ 链表长度 """

         # cur 游标,用来移动遍历节点

         cur = self.__head

         count = 0

         while cur is not None:

             count += 1

             cur = cur.next

             # count 记录数量

         return count

     def travel(self):

         """ 遍历整个链表 """

         cur = self.__head

         while cur is not None:

             print(cur.elem, end=' ')

             cur = cur.next

     def add(self, item):

         """ 链表头部添加元素:头插法 """

         node = Node(item)

         node.next = self.__head

         self.__head = node

     def append(self, item):

         """ 链表尾部添加元素 : 尾插法 """

         node = Node(item)

         # 下一结点链接域不为空

         if self.is_empty():

             self.__head = node

         else:

             cur = self.__head

             while cur.next is not None:

                 cur = cur.next

             cur.next = node

     def insert(self, pos, item):

         """

         pos: pos 0 开始

         pre: 指定节点前一节点,相当于游标

         node :插入的指定节点

         指定位置添加元素

         """

         # if pos<=0 头插法

         if pos <= 0:

             self.add(item)

         # elif pos>(self.length()-1) 尾插法

         elif pos > (self.length() - 1):

             self.append(item)

         # else 插入法

         else:

             pre = self.__head

             count = 0

             # 当循环退出后, pre 指向 pos-1

             while count < (pos - 1):

                 count += 1

                 pre = pre.next

             node = Node(item)

             node.next = pre.next

             pre.next = node

     def remove(self, item):

         """ 删除元素 """

         # 考虑删除头部、尾部、中间节点

         cur = self.__head

         pre = None

         while cur is not None:

             if cur.elem == item:

                 # 先判断是否是头节点

                 if cur == self.__head:

                     self.__head = cur.next

                 else:

                     pre.next = cur.next

                 break

             else:

                 pre = cur

                 cur = cur.next

     def search(self, item):

         """ 查找节点是否存在 """

         # 1. 创建游标

         cur = self.__head

         # 2. 遍历游标

         while cur is not None:

             # 3. cur.elem = item

             if cur.elem == item:

                 return True

             else:

                 cur = cur.next

         return False

if __name__ == '__main__':

     ll = SingleLinkList()

     ll.is_empty()

     l1 = ll.length()

     print(l1)

     ll.append(55)

     ll.is_empty()

     l2 = ll.length()

     print(l2)

     ll.append(2)

     ll.add(8)

     ll.append(3)

     ll.append(4)

     ll.append(5)

     # 55 1 8 2 3 4

     ll.insert(-1, 9)  # 9 8 55 2 1 8 2345

     ll.insert(2, 100)  # 9 8 100 55 2 1 8 2345

     ll.travel()


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69946337/viewspace-2770711/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2019-08-23

  • 博文量
    223
  • 访问量
    126444