常用数据结构

一、链表

在 Python 中，列表是动态数组。这意味着列表和链表的内存使用都非常相似。

二、栈

1.栈(stack)，有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素

2.特点：只能允许在容器的一端(称为栈顶端指标—— top) 进行加入数据(push)和输出数据(pop) 的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
3.由于栈数据结构只允许在一端进行操作，因而按照先进后出（后进先出）的原理运作。

• 2.1 栈结构的实现
  （1）Stack()创建一个新的空栈
  （2）push(item)添加一个新的元素item到栈顶
  （3）pop()弹出栈顶元素
  （4）peek()返回栈顶元素
  （5）is_empty()判断栈是否为空
  （6）size()返回栈的元素个数

• 2.2.代码实现：

class Stack(object):
    #定义初始化方法
    def __init__(self):
        #初始化一个空列表
        self._list=[]
    #压栈
    def push(self,item):
        self._list.append(item)
 
    #弹出元素
    def pop(self):
        return self._list.pop()
 
    #返回栈顶元素
    def peek(self):
        return self._list[len(self._list)-1]
 
    #判断栈顶是否为空
    def is_empty(self):
        return self._list==[]
 
    #计算栈的大小
    def size(self):
        return len(self._list)
if __name__=="__main__":
    stack=Stack()
    print("栈是否为空：",stack.is_empty())
    #压栈
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    print("栈是否为空：",stack.is_empty())
    print("栈的长度：",stack.size())
    #弹出
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

栈是否为空： True
栈是否为空： False
栈的长度： 4
4
3
2
1

三、队列是什么？

1.队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

2.队列是遵循先进先出的原理简称，允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作

• 3.1队列的实现
  1.实现步骤：

（1）Queue()创建一个空的队列

（2）enqueue(item)向队列中添加元素item

（3）dequeue()从队列头部删除一个元素

（4）is_empty判断一个队列是否为空

（5）size()返回队列大小

• 3.2.代码实现

class Queue(object):
    #定义初始化方法
    def __init__(self):
        self._list=[]
    #进队
    def enqueue(self,item):
        #self._list.append(item)
        self._list.insert(0,item)
    #出队
    def dequeue(self):
        #return self._list.pop()
        return self._list.pop()
    #判断是否为空
    def is_empty(self):
        return self._list==[]
    #计算队列大小
    def size(self):
        return len(self._list)
 
if __name__=="__main__":
    queue=Queue()
    print("队列是否为空：",queue.is_empty())
    #进队
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    print("队列是否为空：", queue.is_empty())
    #出队
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())

队列是否为空： True
队列是否为空： False
1
2
3

四、树

image.png

• 结点：使用树结构存储的每一个数据元素都被称为“结点”。例如，图 1（A）中，数据元素 A 就是一个结点；

• 父结点（双亲结点）、子结点和兄弟结点：对于图 1（A）中的结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A 结点的子结点（也称“孩子结点”）。对于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。

• 结点A就是整棵树的根结点。

• 一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。

4.1树的种类

• 无序树：树中任意节点的子节点之间没有顺序关系，称为无序树
• 有序树：树中任意节点的子节点之间有顺序关系，称为有序树
  • 二叉树：每个节点最多含有两个子树的树称为二叉树
  • 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其他各层的节点数目均已达到最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树称为完 全二叉树，其中满二叉树的定义是所有叶子节点都在最底层的完全二叉树
  • 平衡二叉树（AVL树）：当且仅当任何节点的两颗子树的高度差不大于1的二叉树
  • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树

image.png

简单地理解，满足以下两个条件的树就是二叉树：
本身是有序树；
树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

4.2 树的实现

# 定义二叉树节点
class Node(object):
    """二叉树结点的定义"""

    def __init__(self, item):
        self.elem = item
        self.lChild = None
        self.rChild = None


class Tree(object):
    """二叉树"""

    def __init__(self):
        self.root = None  # 根结点

    def add(self, item):
        """添加结点"""
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]  # 队列
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lChild is None:
                cur_node.lChild = node
                return
            else:
                queue.append(cur_node.lChild)
            if cur_node.rChild is None:
                cur_node.rChild = node
                return
            else:
                queue.append(cur_node.rChild)

    def breadth_travel(self):
        """利用队列实现树的层次遍历（广度遍历）"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem, end=" ")
            if cur_node.lChild is not None:
                queue.append(cur_node.lChild)
            if cur_node.rChild is not None:
                queue.append(cur_node.rChild)

    def preorder(self, node):
        """前序遍历（深度遍历）(中 -> 左 -> 右)"""
        if node is None:
            return
        print(node.elem, end=" ")
        self.preorder(node.lChild)
        self.preorder(node.rChild)

    def inorder(self, node):
        """中序遍历（深度遍历）(左 -> 中 -> 右)"""
        if node is None:
            return
        self.inorder(node.lChild)
        print(node.elem, end=" ")  # 此处可认为 node.elem 就是我们要处理的结点
        self.inorder(node.rChild)

    def postorder(self, node):
        """后序遍历（深度遍历）(左 -> 右 -> 中)"""
        if node is None:
            return
        self.postorder(node.lChild)
        self.postorder(node.rChild)
        print(node.elem, end=" ")

if __name__ == "__main__":
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    print("广度优先遍历")
    tree.breadth_travel()
    print("先序遍历")
    tree.preorder(tree.root)
    print("中序遍历")
    tree.inorder(tree.root)
    print("后序遍历")
    tree.postorder(tree.root)

image.png