Python——数据结构与算法-时间复杂度&空间复杂度-链表&树状结构

1.数据结构和算法简介

• 程序

  可以理解为：程序 = 数据结构 + 算法

• 概述/目的:
  都可以提高程序的效率(性能)

• 数据结构

  指的是 存储, 组织数据的方式.

• 算法

  指的是 为了解决实际业务问题而思考 思路和方法, 就叫: 算法.

2.算法的5大特性介绍

• 概述:
  为了解决实际业务问题, 而考虑出来的方法和思路, 就叫: 算法.
  算法具有独立性, 即: 它是解决问题的思路(思想)和方法, 不依赖于语言

• 5大特性

  • 有输入, 需要传入1或者多个参数
  • 有输出, 需要返回1个或者多个结果
  • 有穷性, 执行一定次数循环后, 会自动终止, 不会死循环.
  • 确定性, 每一步都有其具体的含义, 不会出现二义性.
  • 可行性, 每一步都是可执行的, 且会在一定次数后结束.

  问： 如何衡量算法的优劣？
      答案：
          不能单纯的只依靠程序的执行时间， 因为程序执行时也会受到机器， 硬件， 其它软件的影响.
          所以我们可以假定 计算机执行每个步骤的时间都是固定的, 只考虑算法的 执行步骤即可.
          即:  算法的总执行时间 = 算法的总执行步骤 * 每个步骤执行的时间
  

3.时间复杂度介绍:

​ 概述:
​ 它可以反应1个算法的优劣, 它表示1个算法随着问题规模的变化而表现出来的趋势.

 细节:
        1. 如非特殊说明, 我们考虑时间复杂度都是考虑: 最坏时间复杂度, 它算是算法的一种保证.
        2. 常见的时间复杂度, 效率从高到低分别是:
            O(1) > O(logn) > O(n) > O(nlogn) > O(n²) > O(n³)
        3. 空间复杂度(了解)指的是: 算法的运算过程中, 临时占用空间的大小, 也是用大O标记法标记的, 具体如下:
            O(1) < O(logn) < O(n) < O(n²) < O(n³)
        4. 扩展一个开发思想, 叫: 时空转换, 即: 拿时间 换 空间, 还是 拿空间 换 时间.
        5. 程序 = 数据结构 + 算法

​ 大O标记法:
​ 忽略次要条件, 只考虑主要条件(随着问题规模变化而变化的内容), 就会得到: 大O标记法, 标记的效率.
​ 例如, 如下的代码:

import time
# 需求: 已知 a + b + c = 1000, 且 a^2 + b^2 = c^2, 请求出 a, b, c可能得所有组合.
# 1. 获取开始时间.
start = time.time()
# 2. 具体的计算过程

# # 方式1: 穷举法实现, 241秒
# for a in range(1001):
#     for b in range(1001):
#         for c in range(1001):
#             if a ** 2 + b ** 2 == c ** 2 and a + b + c == 1000:
#                 print(a, b, c)

# 方式2: 穷举法实现, 123秒
# for a in range(1001):
#     for b in range(1001):
#         for c in range(1001):
#             if a + b + c == 1000 and a ** 2 + b ** 2 == c ** 2:
#                 print(a, b, c)

# 方式3: 代入法, 0.3秒
for a in range(1001):
    for b in range(1001):
        c = 1000 - a - b
        if a ** 2 + b ** 2 == c ** 2:
            print(a, b, c)

        if a ** 2 + b ** 2 == c ** 2:
            print(a, b, c)

# 3. 获取结束时间.
end = time.time()
# 4. 打印结果.
print(f"耗时: {end - start} 秒!")

4.数据结构

数据结构介绍:
    概述:
        数据结构 = 存储 和 组织数据的 方式.
    分类:
        线性结构
        非线性结构

线性结构:
    特点:
        每个节点只能有1个子节点(后继节点) 和 1个父节点(前驱节点).
    代表:
        栈, 队列, 链表...
    分类:
        顺序表
        链表

线性结构之顺序表介绍:
    概述:
        它属于线性结构的一种, 例如: 栈, 队列都属于顺序表.
    特点:
        所有元素在内存中以 连续的内存空间 来存储.
    举例:
        你们部门出去旅游, 共10个人, 开10个房间, 要求: 10个房间在同一层, 且是连续的房间.
    根据存储数据的方式, 又分为:
        一体式存储: 地址值 和 数据存储在一起.
        分离式存储: 地址值 和 数据分开存储.
    顺序表-扩容策略解释:
        1. 每次扩容增加固定的条数目.    属于拿时间 换 空间.
        2. 每次扩容容量翻倍.           属于拿空间 换 时间.
        细节:
            顺序表主要存储 数据区 和 信息区,  数据区和信息区在一起的叫: 一体式存储, 分开存储的叫: 分离式存储.
    顺序表的增删操作:
        方式1: 末尾增删.          时间复杂度: O(1)
        方式2: 中间增删(非保序)    时间复杂度: O(1)
        方式3: 中间增删(保序)      时间复杂度: O(n)
        
树状结构(Tree)介绍:
    概述:
        它属于数据结构之 非线性结构的一种, 父节点可以多个子节点(后继节点).
    特点:
        1. 有且只能有1个根节点.
        2. 每个节点都可以有1个父节点及任意个子节点. 前提: 根节点除外.
        3. 没有子节点的节点称之为: 叶子节点.
    二叉树介绍:
        概述:
            每个节点最多只能有2个子节点.
        分类:
            完全二叉树:  除了最后1层, 其它层的节点都是满的.
            满二叉树:    包括最后1层, 所有层的节点都是满的.
            不完全二叉树: 某层(不仅仅是最后1层)的节点数量不满.
        常用的二叉树:
            平衡二叉树:  防止树退化成链表.  指的是: 任意节点的两颗子树的高度差不超过1.
            排序二叉树:  主要是对元素排序的.
        存储方式:
            更推荐使用 链表的方式来存储, 每个节点由3部分组成, 分别是: 元素域(数值域), 左子树(地址域), 右子树(地址域)
            针对于 多叉树的情况, 可以将其转成二叉树, 然后再来存储.

1.链表

链表是一种重要的线性数据结构，它不同于数组，以动态分配的方式存储数据。每个节点包含数据部分和指向下一个节点的指针，因此链表不需要连续的内存空间，可以方便地进行插入和删除操作。下面详细介绍链表的概念、类型、操作及其实现。

链表的基本概念

链表由一系列节点组成，每个节点包含两部分：

1. 数据（data）： 存储节点的数据。
2. 指针（next）： 存储指向下一个节点的引用。

链表的第一个节点称为头节点（head），最后一个节点的next指针指向None，表示链表结束。

链表的优势: 相比数组，链表在插入和删除操作上更加高效，尤其是在头部和尾部的操作。链表不需要连续的内存空间。
链表的劣势: 链表的查找效率较低，必须从头节点开始逐个遍历。此外，由于每个节点需要额外存储指针，链表的内存开销相对较高。


单向链表: 每个节点由 1个数值域和1个地址域组成, 且每个节点的地址域指向下个节点的地址. 最后1个节点的地址域为: None

单向循环链表: 每个节点由 1个数值域和1个地址域组成, 且每个节点的地址域指向下个节点的地址. 最后1个节点的地址域为: 第1个节点的地址

双向链表: 每个节点由 1个数值域和2个地址域组成, 且每个节点的地址域分别指向前1个节点的地址 和 后1个节点的地址.
		第1个节点的(前)地址域为: None,  最后1个节点的(后)地址域为: None

双向循环链表:每个节点由 1个数值域和2个地址域组成, 且每个节点的地址域分别指向前1个节点的地址 和 后1个节点的地址.
            第1个节点的(前)地址域为: 最后1个节点的地址,  最后1个节点的(后)地址域为: 第1个节点的地址.

链表的类型

1. 单向链表（Singly Linked List）
   • 每个节点只包含指向下一个节点的指针。
   • 操作简单，但只能从头节点开始逐个遍历到末尾。
2. 双向链表（Doubly Linked List）
   • 每个节点包含两个指针：一个指向下一个节点，一个指向前一个节点。
   • 这种结构使得可以双向遍历链表，插入和删除更加灵活。
3. 循环链表（Circular Linked List）
   • 链表中的最后一个节点的next指针指向头节点，形成一个环。
   • 循环链表可以是单向的或双向的，适合某些需要循环处理数据的场景。
4. 带头节点和不带头节点的链表
   • 带头节点：链表在第一个有效节点前有一个头节点，头节点不存储数据，但使操作更方便。
   • 不带头节点：链表的第一个节点就是第一个数据节点。

链表的基本操作

1. 创建链表 创建链表时需要初始化链表的头节点，通常可以通过一个类来实现。
2. 插入节点
   • 头插法：在链表头部插入节点。
   • 尾插法：在链表尾部插入节点。
   • 中间插入：在指定位置插入节点。
3. 删除节点
   • 头节点删除：删除头节点并将头指针指向下一个节点。
   • 尾节点删除：删除尾节点，找到倒数第二个节点并将其next指向None。
   • 中间删除：删除链表中指定位置的节点。
4. 查找节点 遍历链表，找到数据与目标匹配的节点。
5. 遍历链表 从头节点开始，顺序访问链表中的每个节点，直到链表末尾（单向链表）或循环一周（循环链表）。

单向链表

# 定义链表的节点类
class Node:
    def __init__(self, data):
        # 节点包含两个属性：数据和指向下一个节点的指针
        self.data = data  # 存储节点的数据
        self.next = None  # 存储下一个节点的引用，初始为None

# 定义单向链表类
class SinglyLinkedList:
    def __init__(self):
        # 初始化链表时，链表为空，因此头节点设置为None
        self.head = None

    # 在链表头部插入节点
    def insert_at_head(self, data):
        # 创建新节点，将数据存储在节点中
        new_node = Node(data)
        # 新节点的next指针指向当前的头节点
        new_node.next = self.head
        # 更新头节点为新节点，表示链表的起点发生了改变
        self.head = new_node

    # 在链表尾部插入节点
    def insert_at_end(self, data):
        # 创建新节点，数据存储在节点中
        new_node = Node(data)
        # 先检查链表是否为空。如果链表为空，则直接将新节点作为头节点
        if not self.head:
            self.head = new_node
            return
        # 如果链表非空，遍历链表直到找到最后一个节点，将最后一个节点的next指针指向新节点
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        # 将最后一个节点的next指向新节点
        last_node.next = new_node

    # 删除具有特定数据的节点
    def delete_node(self, key):
        # 用临时变量指向头节点
        temp = self.head
        
        # 先检查头节点是否为要删除的节点。如果头节点就是要删除的节点
        if temp and temp.data == key:
            # 将头节点指向下一个节点（删除头节点）
            self.head = temp.next
            temp = None  # 释放被删除节点的内存
            return
        
        # 否则，查找要删除的节点
        prev = None  # 保存当前节点的前一个节点
        while temp and temp.data != key:
            prev = temp
            temp = temp.next
        
        # 如果没有找到节点
        if temp is None:
            return
        
        # 将前一个节点的next指向要删除节点的下一个节点
        prev.next = temp.next
        temp = None  # 释放被删除节点的内存
        
    # 指定位置 添加元素
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            # 从头开始遍历
            cur = self.head
            # 初始位置为 0
            count = 0
            # 找到要插入 位置的前一个索引
            while count < pos-1:
                cur = cur.next
                count += 1
            # 此时已经找到
            # 将新节点的next指针指向插入位置原来的下一个节点。然后，将前一个节点的next指针指向新节点。
            new_node = SingleNode(item)
            new_node.next = cur.next
            cur.next = new_node

    # 查找链表中是否存在特定数据
    def search(self, key):
        # 用临时变量指向头节点
        current = self.head
        # 遍历链表，查找节点数据是否等于key
        while current:
            if current.data == key:
                return True  # 找到数据，返回True
            current = current.next  # 移动到下一个节点
        return False  # 未找到数据，返回False

    # 遍历并打印链表中的所有节点
    def traverse(self):
        # 用临时变量指向头节点
        current = self.head
        # 遍历链表，打印每个节点的数据
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")  # 最后输出None表示链表结束

# 测试链表功能
linked_list = SinglyLinkedList()

# 插入节点到链表头部
linked_list.insert_at_head(3)  # 链表：3 -> None
linked_list.insert_at_head(2)  # 链表：2 -> 3 -> None

# 插入节点到链表尾部
linked_list.insert_at_end(4)   # 链表：2 -> 3 -> 4 -> None

# 遍历链表
linked_list.traverse()  # 输出: 2 -> 3 -> 4 -> None

# 删除节点
linked_list.delete_node(3)     # 删除值为3的节点，链表变为：2 -> 4 -> None

# 遍历链表
linked_list.traverse()  # 输出: 2 -> 4 -> None

# 搜索节点
print(linked_list.search(2))   # 输出: True
print(linked_list.search(3))   # 输出: False

双向链表

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        new_node.prev = last_node

    def delete_node(self, key):
        temp = self.head
        if temp and temp.data == key:
            self.head = temp.next
            if self.head:
                self.head.prev = None
            temp = None
            return
        while temp and temp.data != key:
            temp = temp.next
        if temp is None:
            return
        if temp.next:
            temp.next.prev = temp.prev
        if temp.prev:
            temp.prev.next = temp.next
        temp = None

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# 测试
dll = DoublyLinkedList()
dll.insert_at_head(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.traverse()  # 输出: 1 <-> 2 <-> 3 <-> None
dll.delete_node(2)
dll.traverse()  # 输出: 1 <-> 3 <-> None

2.树状结构(Tree)介绍:

​ 概述:
​ 它属于数据结构之 非线性结构的一种, 父节点可以多个子节点(后继节点).

特点:
1. 有且只能有1个根节点.
2. 每个节点都可以有1个父节点及任意个子节点. 前提: 根节点除外.
3. 没有子节点的节点称之为: 叶子节点.

二叉树介绍:
        概述:
            每个节点最多只能有2个子节点.
        分类:
            完全二叉树:  除了最后1层, 其它层的节点都是满的.
            满二叉树:    包括最后1层, 所有层的节点都是满的.
            不完全二叉树: 某层(不仅仅是最后1层)的节点数量不满.
        常用的二叉树:
            平衡二叉树:  防止树退化成链表.  指的是: 任意节点的两颗子树的高度差不超过1.
            排序二叉树:  主要是对元素排序的.
        存储方式:
            更推荐使用 链表的方式来存储, 每个节点由3部分组成, 分别是: 元素域(数值域), 左子树(地址域), 右子树(地址域)
            针对于 多叉树的情况, 可以将其转成二叉树, 然后再来存储.
"""

# 案例: 自定义代码, 模拟树状结构.
# 1. 定义节点类.
class Node(object):
    # 初始化属性
    def __init__(self, item):
        self.item = item  # 数值域, 存储节点内容的
        self.lchild = None  # 节点的 左子树(的地址), left
        self.rchild = None  # 节点的 右子树(的地址), right


# 2. 创建 二叉树类.
class BinaryTree(object):
    # 2.1 初始化属性
    def __init__(self, root=None):
        self.root = root  # 充当根节点

    # 2.2 定义add函数(), 表示往: 添加元素
    def add(self, item):
        # 1. 判断根节点是否存在, 如果不存在, 则该(新节点)就是 根节点.
        if self.root is None:
            self.root = Node(item)
            return  # 细节: 添加后, 本次添加动作完毕, 记得终止.

        # 2. 走到这里, 说明根节点存在, 我们需要找到 "缺失的节点", 就是新节点要添加的位置.
        # 创建1个队列, 用于记录已存在的节点.
        queue = []
        # 把根节点加到队列中.
        queue.append(self.root)

        # 3.循环遍历队列, 直至 把新元素添加到合适的位置.
        while True:
            # 4. 获取队列的第1个元素(如果首次操作, 则是在获取 根节点)
            node = queue.pop(0)
            # 5. 判断当前节点的左子树是否存在.
            if node.lchild is None:
                # 5.1 如果当前节点的 左子树不存在, 就把新节点添加到这里.
                node.lchild = Node(item)
                return  # 细节: 添加后, 本次添加动作完毕, 记得终止.
            else:
                # 5.2 如果当前节点的 左子树存在, 就将其添加到队列中.
                queue.append(node.lchild)

            # 6. 判断当前节点的右子树是否存在.
            if node.rchild is None:
                # 6.1 如果当前节点的 右子树不存在, 就把新节点添加到这里.
                node.rchild = Node(item)
                return  # 细节: 添加后, 本次添加动作完毕, 记得终止.
            else:
                # 6.2 如果当前节点的 右子树存在, 就将其添加到队列中.
                queue.append(node.rchild)

    # 2.3 定义 breadth_travel(), 表示: 广度优先遍历
    def breadth_travel(self):
        # 1. 判断根节点是否存在.
        if self.root is None:
            return  # 根节点不存在, 结束遍历即可.

        # 2. 走到这里, 根节点存在, 创建队列, 记录所有的节点.
        queue = []
        queue.append(self.root)

        # 3. 只要队列中有内容, 就说明还有节点, 就继续循环.
        while len(queue) > 0:
            # 4. 获取队列的第1个元素.
            node = queue.pop(0)
            # 5. 打印该节点的内容.
            print(node.item, end='\t')
            # 6. 判断当前节点的左, 右子树是否存在, 存在就添加到队列中.
            if node.lchild is not None:
                queue.append(node.lchild)
            if node.rchild is not None:
                queue.append(node.rchild)

    # 2.4 定义 preorder_travel(), 表示: 深度优先遍历之 先序(根左右)
    def preorder_travel(self, root):
        # 判断 根节点是否存在 存在则获取元素
        if root is not None:
            # 先序的顺序: 根 -> 左 -> 右
            print(root.item, end=' ')   # 根
            # 递归方式, 获取 子左树的所有元素
            self.preorder_travel(root.lchild)
            # 递归方式, 获取 子右树的所有方式
            self.preorder_travel(root.rchild)

    # 2.5 定义 inorder_travel(), 表示: 深度优先遍历之 中序(左根右)
    def inorder_travel(self, root):
        if root is not None:
            self.inorder_travel(root.lchild)
            print(root.item, end=' ')   # 根
            self.inorder_travel(root.rchild)

    # 2.6 定义 postorder_travel(), 表示: 深度优先遍历之 后序(左右根)
    def postorder_travel(self, root):
        if root is not None:
            self.postorder_travel(root.lchild)
            self.postorder_travel(root.rchild)
            print(root.item, end=' ')


# 3. 定义 demo01_测试节点类和二叉树类()
def demo01_测试节点类和二叉树类():
    # 3.1 创建节点对象.
    node1 = Node('乔峰')
    # 3.2 打印节点的 数值域 和 地址域
    print(f'节点的地址: {node1}')
    print(f'节点的内容: {node1.item}')
    print(f'节点的左子树(地址): {node1.lchild}')
    print(f'节点的右子树(地址): {node1.rchild}')

    # 3.3 创建二叉树对象.
    bt = BinaryTree()
    print(f'根节点: {bt.root}')  # None
    print('-' * 21)

    bt2 = BinaryTree(node1)
    print(f'根节点: {bt2.root}')
    print(f'根节点的内容: {bt2.root.item}')
    print(f'根节点的左子树(地址): {bt2.root.lchild}')
    print(f'根节点的右子树(地址): {bt2.root.rchild}')


# 4. 定义 demo02_演示队列的使用()
def demo02_演示队列的使用():
    # 4.1 创建列表对象, "模拟"队列, 即: 先进先出.
    queue = []
    # 4.2 往队列中添加元素
    queue.append('A')
    queue.append('B')
    queue.append('C')
    # 4.3 打印队列的内容.
    print(queue)
    # 4.4 逐个获取队列中的内容, 模拟: 先进先出.
    # pop()函数: 根据索引, 删除(弹出)列表中的元素, 并返回该元素.
    print(queue.pop(0))  # ['A', 'B', 'C'] => ['B', 'C'], 返回: 'A'
    print(queue.pop(0))  # ['B', 'C'] => ['C'], 返回: 'B'
    print(queue.pop(0))  # ['C'] => [], 返回: 'C'


# 5. 定义 demo03_演示广度优先()
def demo03_演示广度优先():
    # 1. 创建二叉树.
    bt = BinaryTree()
    # 2. 添加元素到二叉树中.
    bt.add('A')
    bt.add('B')
    bt.add('C')
    bt.add('D')
    bt.add('E')
    bt.add('F')
    bt.add('G')
    bt.add('H')
    # 3. 广度优先的方式遍历.
    bt.breadth_travel()


# 6. 定义demo04 演示深度优先遍历
def demo04_演示深度优先遍历():
    # 1. 创建二叉树
    bt = BinaryTree()
    # 2. 添加元素到二叉树中
    bt.add(1)
    bt.add(2)
    bt.add(3)
    bt.add(4)
    bt.add(5)
    bt.add(6)
    bt.add(7)
    bt.add(8)
    bt.add(9)
    # 3. 深度优先的方式遍历
    print('先序 遍历结果:')
    bt.preorder_travel(bt.root)

    print('\n中序 遍历结果: ')
    bt.inorder_travel(bt.root)

    print('\n后序 遍历结果: ')
    bt.inorder_travel(bt.root)


# 7. 测试代码.
if __name__ == '__main__':
    # demo01_测试节点类和二叉树类()
    # demo02_演示队列的使用()
    # demo03_演示广度优先()
    demo04_演示深度优先遍历()