python 进阶——多种数据结构的封装(链表、栈、队列、二叉树)

Source

一、链表的封装:

数组和链表的区分:

图示区分
数组是有下标索引和data两部分组成:
在这里插入图片描述
链表是有data和指向下一个数据的指针地址两部分组成
在这里插入图片描述

表格区分

** 链表 数组
内存占用 不需要连续的内存空间 需要连续的内存空间
大小可变 链表的大小可动态变化 数组大小固定,不能动态扩展
增删 较快,只需要修改前一个元素的指针即可 较慢,需要移动修改元素只有的所有元素
查询 较慢,只能遍历查找 较快,可以通过下标直接访问
在访问方式上 必须是顺序访问,不能随机访问 可以随机访问其中的元素
空间的使用上 可以随意扩大 不能

时间复杂度的不同

时间复杂度 数组 链表
增加元素 O(n) O(1)
删除元素 O(n) O(1)
修改元素 O(1) O(n)
查看元素 O(1) O(n)

链表的封装:

val表示值;next表示指向的下一个内存地址

# 封装节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def travel(self, head):
        """遍历链表里面的每一个元素"""
        while head:   #判断head,也就是下一个内存地址是否存在,不存在的时候即遍历完成
            print(head.val, end=',')
            head = head.next

两数相加:

代码需求:
在这里插入图片描述

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def travel(self, head):
        """遍历链表里面的每一个元素"""
        while head:
            print(head.val, end=',')
            head = head.next

def create_l1():   #生成l1链表的函数
    # l1 = 2,4,3
    l1 = ListNode()
    node1 = ListNode(val=2)   #生成三个独立的节点
    node2 = ListNode(val=4)
    node3 = ListNode(val=3)
    l1.next = node1        # 通过next把独立的节点连接起来
    node1.next = node2
    node2.next = node3
    return  l1.next

def create_l2():   # 生成l2链表的函数
    # l2 = 5, 6, 4
    l2 = ListNode()
    node1 = ListNode(val=5)
    node2 = ListNode(val=6)
    node3 = ListNode(val=4)
    l2.next = node1
    node1.next = node2
    node2.next = node3
    return  l2.next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:    #求和的函数
    res = 0   #定义一个相加的结果
    l3 = ListNode()  # 定义求和之后的链表l3
    cur = l3  # 下文作解释
    while(l1 or l2):  #l1和l2两者存在一个就可以加到res上
        if(l1):
            res += l1.val  # res=2  
            l1 = l1.next
        if(l2):
            res += l2.val # res=2+5=7
            l2 = l2.next
        l3.next = ListNode(res%10)   #有进位时该位置收到的是个位的结果,所以需要取余
        l3 = l3.next   #移动指针,按次序的输入res的结果,为了防止覆盖数据
        # res=8, 进位为0, 8//10=0
        # res=14, 进位为1, 14//10=1
        res  //= 10   #为了防止有进位,即十位数为1,则下次循环的res初始值为1,所以输入res对10整除后的结果
    if res == 1:
        l3.next = ListNode(1)  # 循环结束后,最后一位依然有进位的话,l3会比l1和l2多一位,多出的一位的值就是进位的1
    return cur.next  
    """
    大家就会有疑问了,为什么不直接返回l3?
    因为代码中每循环一次,l3的指针就会往后移一位,所以循环结束后指针就会在最后一位
    (前提是最后一位没有进位,有进位的话指针就是在倒数第二位),这时直接返回l3的话,
    只会输出指针处的值,故将l3的内容存入cur。
    此处返回cur.next的原因是:初始定义cur = l3,故第一位为0,是没有意义的。
    """

if __name__ == '__main__':   # 在模块内部运行
    l1 = create_l1()
    l2 = create_l2()
    l3 = addTwoNumbers(l1, l2)
    l3.travel(l3) #调用ListNode类的遍历所用的方法

运行结果:
在这里插入图片描述

二、栈的封装:

  • 栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许进行操作的一端称为“栈顶”, 另一固定端称为“栈底”,当栈中没有元素时称为“空栈”。向一个栈内插入元素称为是进栈,push; 从一个栈删除元素称为是出栈,pop。特点 :后进先出(LIFO)。

入栈:如下图,入栈的顺序就是a1->a2->a3->a4->a5
出栈:删除栈顶的元素
在这里插入图片描述

栈的封装:

我们用列表的操作模拟实现栈的封装:

class Stack(object):
    """栈的封装"""

    def __init__(self):
        self.stack = []  

    def push(self, value):
        """入栈"""
        self.stack.append(value)  #用列表追加模拟入栈的顺序,即列表的第一位表示栈底,最后一位表示栈顶
        print(f"入栈元素为{value}")

    def pop(self):
        """出栈"""
        if self.is_empty():
            raise  Exception("栈为空")
        item = self.stack.pop()   #pop默认删除最后一个元素,即‘栈顶’元素
        print(f"出栈元素为{item}")
        return  item

    def is_empty(self):
        """判断栈是否为空"""
        return  len(self.stack) == 0   #即长度是否为0

    def top(self):
        """返回栈顶元素"""
        if self.is_empty():
            raise  Exception("栈为空")
        return  self.stack[-1]   #即列表‘入栈’时追加的最后一位

    def __len__(self):
        """魔术方法, len(object)自动执行的方法,查看长度"""
        return  len(self.stack)

#  上面为栈的封装部分,下面的部分是实际的演示,为了更好的理解。

if __name__ == '__main__':   
    stack = Stack()  
    stack.push(1)  
    stack.push(2)
    stack.push(3)  #入栈三个元素
    print(len(stack))  # 3
    stack.pop()
    print(stack.is_empty()) # False
    print(stack.top())  # 2

运行结果:
在这里插入图片描述

三、队列的封装:

  • 队列是限制在一端进行插入操作和另一端删除操作的线性表,允许进行插入操作的一端称为“队尾”, 允许进行删除操作的一端称为“队头”,,当队列中没有元素时称为“空队”。特点 :先进先出(FIFO)。

在这里插入图片描述

队列的封装:

同样我们列表的操作也能模拟实现队列的封装:

class Queue(object):
    """
    队列的封装
    1. 列表的左侧队尾
    2. 列表的右侧队头
    """
    def __init__(self):
        self.queue = []

    def enqueue(self, value):
        """入队"""
        self.queue.insert(0, value)   #从队尾进,即从列表0的位置插入元素
        print("入队元素为:", value)

    def dequeue(self):
        """出队"""
        if self.is_empty():
            raise  Exception("队列为空")
        item = self.queue.pop()  #从队头出,即列表-1的位置删除元素
        print("出队元素:", item)
        return  item

    def __len__(self):
        """获取队列的长度"""
        return  len(self.queue)

    def first(self):
        """获取队头元素"""
        if self.is_empty():
            raise Exception("队列为空")
        return  self.queue[-1]


    def last(self):
        """获取队尾元素"""
        if self.is_empty():
            raise Exception("队列为空")
        return  self.queue[0]

    def is_empty(self):
        """判断队列是否为空"""
        return  len(self.queue) == 0

#  上面为队列的封装部分,下面的部分是实际的演示,为了更好的理解。

if __name__ == '__main__':
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    print(queue.is_empty()) # False
    queue.dequeue()  # 1出队, 队列只剩32
    print(queue.first())  # 2
    print(queue.last())  # 3

运行结果:
在这里插入图片描述

四、二叉树的封装:

二叉树是树的特殊一种,具有如下特点:

  • 1、每个结点最多有两颗子树,结点的度最大为2。
  • 2、左子树和右子树是有顺序的,次序不能颠倒。
  • 3、即使某结点只有一个子树,也要区分左右子树。

此处主要演示实际二叉树的封装,对二叉树的分类和性质不做过多解释。

二叉树的遍历:

项目 Value
前序遍历 先访问根结点,再先序遍历左子树,最后再先序遍历右子树,即根—左—右。
中序遍历 先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树,即左—根—右。
后序遍历 先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点,即左—右—根。

在这里插入图片描述
以上图二叉树为例:

项目 Value
前序遍历 1,2,4,8,9,5,10,3,6,7
中序遍历 8,4,9,2,10,5,1,6,3,7
后序遍历 8,9,4,10,5,2,6,7,3,1

二叉树的封装:

class Node(object):
    """节点类"""
    def __init__(self, val=None, left=None, right=None):  #生成节点时,要定义左节点和右节点
        self.val = val
        self.left = left
        self.right = right

class BinaryTree(object):
    """封装二叉树"""
    def __init__(self, root): 
        self.root = root     

    def pre_travel(self, root):
        """前序遍历: 根左右"""
        if (root != None):
            print(root.val, end = ',')
            self.pre_travel(root.left)
            self.pre_travel(root.right)


    def in_travel(self, root):
        """中序遍历: 左根右"""
        if (root != None):
            self.in_travel(root.left)
            print(root.val, end = ',')
            self.in_travel(root.right)

    def last_travel(self, root):
        """后序遍历: 左右根"""
        if (root != None):
            self.last_travel(root.left)
            self.last_travel(root.right)
            print(root.val, end = ',')

实现下图二叉树的遍历:

在这里插入图片描述

class Node(object):
    """节点类"""
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTree(object):
    """封装二叉树"""
    def __init__(self, root):
        self.root = root

    def pre_travel(self, root):
        """前序遍历: 根左右"""
        if (root != None):
            print(root.val, end = ',')
            self.pre_travel(root.left)
            self.pre_travel(root.right)


    def in_travel(self, root):
        """中序遍历: 左根右"""
        if (root != None):
            self.in_travel(root.left)
            print(root.val, end = ',')
            self.in_travel(root.right)

    def last_travel(self, root):
        """后序遍历: 左右根"""
        if (root != None):
            self.last_travel(root.left)
            self.last_travel(root.right)
            print(root.val, end = ',')


if __name__ == '__main__':
    node1 = Node(1)  
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node5 = Node(5)
    node6 = Node(6)
    node7 = Node(7)
    node8 = Node(8)
    node9 = Node(9)
    node10 = Node(10)  #生成10个独立的节点

    bt = BinaryTree(root=node1)  
    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right= node5
    node3.left = node6
    node3.right = node7
    node4.left = node8
    node4.right = node9
    node5.left = node10  # 建立该二叉树的节点关系


    bt.pre_travel(node1)
    print('前序遍历')

    bt.in_travel(node1)
    print('中序遍历')

    bt.last_travel(node1)
    print('后序遍历')

运行结果:
在这里插入图片描述