数据结构和算法-7-单向循环列表

雨点打透心脏的1/2处 2022-01-15 00:23 149阅读 0赞

前面一篇介绍了单链表，这个单链表是基础，这篇我们来看看单链表的变种，单向循环链表，和前面唯一的区别就是列表最后一个节点指向头节点，形成一个环形。

1.单向循环列表

单链表的一个变型是单向循环链表，链表中最后一个节点的next域不再为Node，而是指向链表的头节点，形成一个环。

![20190614103852874.png][]

2.代码实现

还是前面单链表的大部分方法的实现代码，先来看看头部插入元素和尾部插入元素，链表长度，判断为空和遍历这几个方法的实现过程

运行结果：

11 8 5
    3

下面来看看查找元素和删除元素

# coding:utf-8
    
    
    class Node(object):
        """单链表的节点"""
        def __init__(self, item):
            """item存放数据元素"""
            self.item = item
            self.next = None
    
    
    class SingleCycleLinkList(object):
        """单向循环链表"""
        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
            else:
                count = 1
                cur = self.__head
                # 判断当cur不等于头节点，计数加1
                while cur.next != self.__head:
                    count += 1
                    cur = cur.next
                return count
    
        def travel(self):
            """遍历"""
            if self.is_empty():
                print("空链表")
            else:
                cur = self.__head
                while cur.next != self.__head:
                    print(cur.item, end=" ")
                    cur = cur.next
                # 退出循环，cur指向尾节点，尾节点需要单独打印，否则就丢了最后节点数据
                print(cur.item)
    
        def add(self, item):
            """头部添加元素"""
            node = Node(item)
            # 如果是空链表
            if self.is_empty():
                self.__head = node
                node.next = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 结束循环，这个时候cur就来到最后一个节点
                node.next = self.__head
                self.__head = node
                cur.next = node
    
        def append(self, item):
            """尾部插入元素"""
            node = Node(item)
            # 先判断是否是空节点
            if self.is_empty():
                self.__head = node
                node.next = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 退出循环，cur表示最后节点
                node.next = self.__head
                self.__head = node
                cur.next = node
    
        def search(self, item):
            """查找元素item是否存在"""
            cur = self.__head
            while cur.next != self.__head:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            # 退出循环，cur指向最后一个节点
            if cur.item == item:
                return True
            else:
                return False
    
        def remove(self, item):
            """删除元素"""
            if self.is_empty():
                return
            else:
                cur = self.__head
                pre = None
                while cur.next != self.__head:
                    if cur.item == item:
                        # 先判断此节点是否为头节点
                        if cur == self.__head:
                            # 头节点的情况
                            # 先找出尾节点
                            rear = self.__head
                            while rear.next != self.__head:
                                rear = rear.next
                            # 退出循环，rear指向尾部节点
                            self.__head = cur.next
                            rear.next = self.__head
                        else:
                            # 中间节点
                            pre.next = cur.next
                        break
                    else:
                        pre = cur
                        cur = cur.next
                # 退出循环，尾部元素单独判断
                if cur.item == item:
                    # 尾节点删除
                    # 这里还要考虑如果链表中只有一个节点，如何删除
                    if cur == self.__head:
                        # 代表 链表中只有一个节点
                        self.__head = None
                    else:
                        pre.next = cur.next
    
    
    
    if __name__ == "__main__":
        s = SingleCycleLinkList()
        s.add(5)
        s.append(8)
        s.add(11)
        s.travel()
        print(s.length())
        print(s.search(5))
        s.remove(5)
        s.travel()
        s.remove(8)
        s.travel()
        s.remove(11)
        s.travel()

输出结果，上面修改了遍历没考虑空链表的bug

11 8 5
    3
    True
    11 8
    11
    空链表

看了一下方法，还漏了一下insert方法，其实这里insert方法和前面一篇是一样，不需要修改

# coding:utf-8
    
    
    class Node(object):
        """单链表的节点"""
        def __init__(self, item):
            """item存放数据元素"""
            self.item = item
            self.next = None
    
    
    class SingleCycleLinkList(object):
        """单向循环链表"""
        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
            else:
                count = 1
                cur = self.__head
                # 判断当cur不等于头节点，计数加1
                while cur.next != self.__head:
                    count += 1
                    cur = cur.next
                return count
    
        def travel(self):
            """遍历"""
            if self.is_empty():
                print("空链表")
            else:
                cur = self.__head
                while cur.next != self.__head:
                    print(cur.item, end=" ")
                    cur = cur.next
                # 退出循环，cur指向尾节点，尾节点需要单独打印，否则就丢了最后节点数据
                print(cur.item)
    
        def add(self, item):
            """头部添加元素"""
            node = Node(item)
            # 如果是空链表
            if self.is_empty():
                self.__head = node
                node.next = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 结束循环，这个时候cur就来到最后一个节点
                node.next = self.__head
                self.__head = node
                cur.next = node
    
        def append(self, item):
            """尾部插入元素"""
            node = Node(item)
            # 先判断是否是空节点
            if self.is_empty():
                self.__head = node
                node.next = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 退出循环，cur表示最后节点
                node.next = self.__head
                self.__head = node
                cur.next = node
    
        def insert(self, pos, item):
            """指定位置pos处插入新元素"""
            if pos <= 0:
                # 头插入
                self.add(item)
            elif pos > (self.length() - 1):
                # 尾插入
                self.append(item)
            else:
                # 中间位置插入
                pre = self.__head
                count = 0
                while count < (pos - 1):
                    count += 1
                    pre = pre.next
                # 当循环退出，pre指向pos-1位置
                node = Node(item)
                node.next = pre.next
                pre.next = node
    
    
        def search(self, item):
            """查找元素item是否存在"""
            cur = self.__head
            while cur.next != self.__head:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            # 退出循环，cur指向最后一个节点
            if cur.item == item:
                return True
            else:
                return False
    
        def remove(self, item):
            """删除元素"""
            if self.is_empty():
                return
            else:
                cur = self.__head
                pre = None
                while cur.next != self.__head:
                    if cur.item == item:
                        # 先判断此节点是否为头节点
                        if cur == self.__head:
                            # 头节点的情况
                            # 先找出尾节点
                            rear = self.__head
                            while rear.next != self.__head:
                                rear = rear.next
                            # 退出循环，rear指向尾部节点
                            self.__head = cur.next
                            rear.next = self.__head
                        else:
                            # 中间节点
                            pre.next = cur.next
                        break
                    else:
                        pre = cur
                        cur = cur.next
                # 退出循环，尾部元素单独判断
                if cur.item == item:
                    # 尾节点删除
                    # 这里还要考虑如果链表中只有一个节点，如何删除
                    if cur == self.__head:
                        # 代表 链表中只有一个节点
                        self.__head = None
                    else:
                        pre.next = cur.next
    
    
    
    if __name__ == "__main__":
        s = SingleCycleLinkList()
        s.add(5)
        s.append(8)
        s.add(11)
        s.travel()
        print("插入一个元素到头位置")
        s.insert(0,3)
        s.travel()
        print("插入一个元素到尾部")
        s.insert(4, 13)
        s.travel()
        print("插入一个元素到中间位置")
        s.insert(2, 7)
        s.travel()

运行结果

11 8 5
    插入一个元素到头位置
    3 11 8 5
    插入一个元素到尾部
    13 3 11 8 5
    插入一个元素到中间位置
    13 3 7 11 8 5

[20190614103852874.png]: /images/20220114/c6ec2f1208fc4a66a1846d9beea2ee0d.png