线性表的循环单链表使用的代码实现（python语言）

╰+哭是因爲堅強的太久メ 2022-05-24 02:59 137阅读 0赞

# 单链表
    class ListNode:  # 定义链表节点类
        def __init__(self, elem_1, next_1):
            self.elem = elem_1  # 节点的值
            self.next = next_1  # 指向下一个节点的链接
    
    
    class LoopList:  # 定义一个循环单链表
        def __init__(self):
            self.rear = None
    
        def is_empty(self):  # 链表的判空
            return self.rear is None
    
        def prepend(self, elem):  # 链表尾部加上elem节点
            p = ListNode(elem, None)  # 新增节点赋给p
            if self.rear is None:  # 如果链表为空
                p.next = p  # 表中第一个节点建立初始的循环链接
                self.rear = p  # 链表的尾节点的位置赋给链表头部
            else:  # 链表不为空
                p.next = self.rear.next  # 链在尾节点之后，就是新的首节点
                self.rear.next = p
    
    
    def append(self, elem):  # 尾部加入新节点
        self.prepend(elem)
        self.rear = self.rear.next
    
    
    def pop(self):  # 删除循环链表的头节点
        if self.rear is None:  # 如果链表为空则抛出异常
            raise ValueError
        p = self.rear.next  # 指针指向链表的头结点
        if self.rear is p:  # 链表只有一个节点
            self.rear = None  # 删除唯一节点后rear置空
        else:
            self.rear.next = p.next  # 链表的尾节点的下一节点赋为头结点的下一节点（删除了头节点）
        return p.elem
    
    
    def print_all(self):  # 打印输出循环链表的所有节点值
        p = self.rear.next  # p指向头结点
        while True:
            print(p.elem)  # 打印输出当前p所指向的节点的值
            if p is self.rear:  # 已经遍历了所有节点
                break
            p = p.next  # p指针指向下一节点
    
    
    # 使用循环列表的实例
    
    list = LoopList()  # 新建一个循环单链表
    
    for i in range(10):  # 给链表尾部新增10个节点，0--9节点
        list.prepend(i)
    
    for i in range(11, 20):  # 尾部加入新节点
        list.append(i)
    
    while not list.is_empty():  # 删除循环链表并输出链表的每一个节点值
        print(list.pop())