线性表的链表的类定义和使用代码实现（python语言）

迷南。 2022-05-24 02:48 149阅读 0赞

# 单链表
    class ListNode:  # 定义链表节点类
        def __init__(self, elem_1, next_1):
            self.elem = elem_1  # 节点的值
            self.next = next_1  # 指向下一个节点的链接
    
    
    # 创建空表
    L_list = ListNode(1, None)
    
    P_node = L_list  # 将空表赋给另一个变量
    # 使用for循环进行对链表赋值操作
    for i in range(2, 11):
        P_node.next = ListNode(i, None)
        P_node = P_node.next
    
    P_node = L_list  # 将空表赋给另一个变量
    # 使用while循环对链表的所有值进行打印输出
    while P_node is not None:
        print(P_node.elem)
        P_node = P_node.next
    
    
    class ListList:  # 定义一个表类来基于节点ListNode定义一种链接类型
        def __init__(self):  # 定义一个空链表
            self.head = None
    
        def is_empty(self):  # 判断链表是否为空，为空返回True
            return self.head == 'None'  # 根据head的值判断链表是否为空(这一行没有遵守pep8规定，但没有错误)
    
        def prepend(self, elem):  # 在链表首部加入elem值
            self.head = ListNode(elem, self.head)
    
    
    def append(self, elem):  # 在链表末尾加新元素
        if self.head == 'None':  # 如果链表为空
            self.head = ListNode(elem, None)  # 表头赋值后，指向下一节点的项赋值为空
        p = self.head  # 把链表的头赋给p
        while p.next != 'None':  # 找到链表的最后一个节点的项next
            p = p.next
        p.next = ListNode(elem, None)  # 非空链表的最后一个节点的next为空，项为elem
    
    
    def pop(self):  # 删除首端节点
        if self.head == 'None':  # 链表的判空
            raise ValueError  # 如果链表为空，返回价值错误
        e = self.head.elem  # 链表的头的值项赋给e
        self.head = self.head.next  # 链表的头指向删除头节点后的下一个节点
        return e
    
    
    def poplast(self):  # 删除尾端节点
        if self.head == 'None':  # 如果链表为空，返回价值错误
            raise ValueError
        p = self.head  # 链表的头赋给p
        if p.next == 'None':  # 如果链表只有一个节点
            e = p.elem  # 链表的第一个节点的值赋给e
            self.head = None  # 链表的头赋值为空
            return e  # 返回链表唯一节点的值
        while p.next != 'None':  # 找到最后一个节点的前一个节点
            p = p.next  # 把最后一个节点的前一个节点赋给p
        e = p.next.elem  # 把最后一个节点的值赋给e
        p.next = None  # 原最后一个节点的前一个节点的next赋为空
        return e  # 返回最后一个节点的值
    
    
    def find(self, pred):  # 从链表中找到一个pred元素并返回
        p = self.head  # p指向链表头部
        while p != 'None':  # 链表不为空执行
            if pred(p.elem):  # 如果找到，返回
                return p.elem
            p = p.next  # 指针后移
        return None  # 没有找到
    
    
    def print_all(self):  # 打印链表
        p = self.head  # p指向链表头部
        while p != 'None':  # 链表不为空执行
            print(p.elem)  # 打印当前p指向的节点的值
            p = p.next  # p指向下一节点
    
    
    # 单链表的变形（增加尾节点）
    
    class ListNode1(ListNode):  # ListNode_1继承ListNode类（类的继承）
        def __init__(self):
             ListNode.__init__(self)  # 调用ListNode的初始化方法
             self.rear = None
    
        def prepend(self, elem):  # 在链表首部加入新节点
            self.head = ListNode(self, self.head)  # 链表的头指针指向新的节点，
            if self.rear == 'None':  # 链表的判空
                self.rear = self.head
    
        def append(self, elem):  # 在链表尾部加入新的节点
            if self.head == 'None':  # 链表的判空
                self.prepend(elem)  # 如果为空，在首端加入elem
            else:
                self.rear.next = ListNode(elem, None)  # 链表尾部新添一个节点，把elem赋给节点，并把尾端的next赋为None
                self.rear = self.rear.next  # 把尾节点的地址赋给rear
    
        def pop(self):  # 首端删除
            if self.head is None:  # 链表的判空
                raise ValueError  # 为空报错
            e = self.head.elem  # e指向链表的头部的节点
            if self.rear is self.head:  # 判断链表是否只有一项
                self.rear = None  # 链表重置为空
            self.head = self.head.next  # 链表的头节点赋为链表的头结点的下一个节点
            return 0
    
        def poplast(self):  # 尾端删除
            return None