python算法与数据结构-循环链表

妖狐艹你老母 2023-10-06 12:41 4阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2][]

求链表长度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3][]

需要考虑的特殊情况，空链表或者链表当中只有一个节点的时候。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 4][]

添加元素:

除了头部指向新节点，单向循环链表也需要尾节点指向新的节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 5][]

删除元素如下所示:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 8][]

代码如下所示:

# -*-coding=utf-8-*-
    class Node(object):
        """单链表的节点"""
        def __init__(self, elem):
            # item存放数据元素
            self.elem = elem
            # next是下一个节点的标识
            self.next = None
    
    
    class SingleCycleLinkList(object):
        """单链表"""
        # head是头节点属性,_head在Python中加两个下划线就是私有属性
        # 这个node是用户传进来的
        def __init__(self, node=None):
            self.__head = node
            if node:
                 node.next = node
    
        def is_empty(self):
            """判断是否为空"""
            return self.__head==None
    
        def length(self):
            """链表长度"""
            if self.is_empty():
                return 0
            # cur游标，用来移动遍历节点
            cur = self.__head
            # count 记录数量
            count = 1
            # 尾节点指向self.__head表示循环了一次，当未循环一次未到达尾部时
            while cur.next != self.__head:
                count += 1
                # 将cur后移一个节点
                cur = cur.next
            return count
    
        def travel(self):
            """遍历整个链表"""
            #空链表打印
            if self.is_empty():
                return
            cur = self.__head
            while cur.next != self.__head:
                #添加这个这个，后期打印就不换行了
                print(cur.elem,end=" ")
                cur = cur.next
            #退出循环,cur指向尾节点，但尾结点的元素未打印
            print(cur.elem)
            # pass
    
        def append(self, item):
            """链表尾部添加元素，尾插法"""
            node = Node(item)
            # 这个if条件是空链表的意思，我们需要考虑特殊条件
            # 先判断链表是否为空，若是空链表，则将_head指向新节点
            if self.is_empty():
                self.__head = node
                node.next = node
            # 若不为空，则找到尾部，将尾节点的next指向新节点
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                node.next = self.__head
                cur.next = node
    
        def add(self,item):
            """链表头部添加元素，头插法"""
            # 先创建一个保存item值的节点
            node = Node(item)
            if self.is_empty(): #空链表的情况
                #一般的链表有两个位置，都需要设置一下
                self.__head = node
                node.next = node #这句话是指向自身的意思
            else:
                # 将新节点的链接域next指向头节点，即_head指向的位置
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                #退出循环,cur指向尾节点
                node.next = self.__head
                self.__head = node
                #cur.next = node #这句话跟下面的一句话意思相同，但是不容易理解
                cur.next = self.__head
        #中间位置插入元素，不涉及到尾部链接，就是一个单链表的形式
        #pos是指定的位置,item是保存的元素
        def insert(self,pos,item):
            """链表指定位置添加元素
            :param pos 从0开始
            """
            # 若指定位置pos为第一个元素之前，则执行头部插入
            if pos<=0: #头插法
                self.add(item)
            # 若指定位置超过链表尾部，则执行尾部插入
            elif pos > (self.length()-1):#尾插法
                self.append(item)
            # 找到指定位置
            else:
                # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
                prev = self.__head
                count = 0
                while count<(pos-1):
                    count+=1
                    prev = prev.next
                #当循环退出后,prev指向pos-1位置
                node = Node(item)
                # 先将新节点node的next指向插入位置的节点
                # prev.next存储的是下一个节点的地址，因为是在任意位置插入的，新节点node需要连接下一个节点，node.next指向了下一个节点
                node.next = prev.next
                # 将插入位置的前一个节点的next指向新节点
                prev.next = node
    
        def search(self,item):
            """查找节点是否存在"""
            """链表查找节点是否存在，并返回True或者False"""
            if self.is_empty():
                return  False
            cur = self.__head
            while cur.next != self.__head:
                if cur.elem == item:
                     return  True
                else:
                    cur = cur.next
            #退出循环,cur指向尾节点，需要比较一下最后一个元素是否等于item,等于返回true
            if cur.elem == item:
                return True
            return False
        def remove(self,item):
            """删除节点"""
            if self.is_empty():
                return
            cur = self.__head
            pre = None
            while cur.next != self.__head:
                # 找到了指定元素
                if cur.elem == item:
                    #先判断此节点是否是头节点
                    #头节点 # 如果第一个就是删除的节点
                    if cur == self.__head:
                        #头节点的情况
                        #找尾节点
                        rear = self.__head
                        while rear.next != self.__head:
                             rear = rear.next
                        # 将头指针指向头节点的后一个节点
                        self.__head = cur.next
                        rear.next = self.__head
                    else:#中间节点
                         # 将删除位置前一个节点的next指向删除位置的后一个节点
                         pre.next = cur.next
                    #break  # 删除后再退出循环,需要一个总的break退出
                    return #break只是循环退出，这里需要一个函数退出，就是return
                else:
                    # 继续按链表后移节点
                    pre = cur
                    cur = cur.next
            #退出循环,cur指向尾节点
            if cur.elem == item:
                if cur == self.__head:
                    #这块还有问题，当有好几个节点，走到尾节点的时候
                    #链表只有一个节点
                    self.__head = None
                else:
                    # 将删除位置前一个节点的next指向删除位置的后一个节点
                    #pre.next = cur.next #这句话跟下面一句话的意思一样
                    pre.next = self.__head
    
    if __name__ == "__main__":
        # node = Node(100)
        ll = SingleCycleLinkList()
        print(ll.is_empty()) #True
        print(ll.length())   #0
    
        ll.append(1)
        print(ll.is_empty()) #False
        print(ll.length())   #1
        #
        ll.append(2)
        ll.add(8)
        ll.append(3)
        ll.append(4)
        ll.append(5)
        ll.append(6)
        #8 1 2 3 4 5 6
        ll.insert(-1,9)
        ll.travel()      #9 8 1 2 3 4 5 6
        ll.insert(3, 100)
        ll.travel()      #9 8 1 100 2 3 4 5 6
        ll.insert(10,200)
        ll.travel()      #9 8 1 100 2 3 4 5 6 200
        ll.remove(100)
        ll.travel()      #9 8 1 2 3 4 5 6 200
        ll.remove(9)
        ll.travel()      #8 1 2 3 4 5 6 200
        ll.remove(200)
        ll.travel()      #8 1 2 3 4 5 6

参考资料:网上的教程

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200709141420316.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200709141534856.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200709141604882.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200709141640618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200709141751929.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020070914200369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200709142358111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200709142408736.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200709142648561.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70