栈

栈是限制在一端进行插入操作和删除操作的线性表俗称堆栈，允许进行操作的一端称为栈顶，另一固定端称为栈底，当栈中没有元素时称为空栈

  1. 栈只能在一端进行数据操作
  2. 栈模型具有先进后出或者叫做后进先出的规律

data5.png

  • 入栈(push)
  • 出栈(pop)
  • 判断栈是否为空(empty)
  • 查看栈顶元素值(top)

顺序存储代码实现

#顺序存储实现栈

class Stack:
    def __init__(self):
        self.__top = 0
        self.__data = [None] * 30

    def push(self,value):
        '''入栈 压入元素'''
        if self.__top >= len(self.__data):
            raise ValueError('error')
        self.__data[self.__top] = value
        self.__top += 1

    def pop(self):
        '''出栈 弹出元素'''
        if self.__top == 0:
            raise ValueError('error')
        self.__top -= 1
        return self.__data[self.__top]

    def is_empty(self):
        '''判断是否为空'''
        return self.__top == 0

    def top(self):
        '''返回栈顶元素'''
        return self.__data[self.__top-1]


sta = Stack()
print(sta.is_empty())


sta.push(1)
sta.push(2)
print(sta.top())
sta.push(2)
sta.push(3)
print(sta.top())
print(sta.is_empty())

链式存储代码实现

# 链式存储实现栈

class Node:
    def __init__(self,value,next):
        self.value = value
        self.next = next

class Stack:
    def __init__(self):
        self.__top = None

    def push(self,value):
        '''入栈 压入元素'''
        # new = Node(value,self.__top)
        # new.next = self.__top
        # self.__top = new

        # 简化为1行代码
        self.__top = Node(value,self.__top)

    def pop(self):
        '''出栈 弹出元素'''
        if self.__top == None:
            raise ValueError('error')
        p = self.__top
        self.__top = p.next
        return p.value

    def is_empty(self):
        '''判断是否为空'''
        return self.__top == None

    def top(self):
        '''返回栈顶元素'''
        if self.is_empty():
            raise ValueError('error')
        return self.__top.value

sta = Stack()
print(sta.is_empty())

sta.push(1)
sta.push(2)
print(sta.top())
sta.push(2)
sta.push(3)
print(sta.top())
print(sta.is_empty())
print(sta.pop())
print(sta.pop())
print(sta.pop())
print(sta.pop())
print(sta.pop())
print(sta.pop())

队列

队列FIFO(first in first out)是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为队尾，允许进行删除操作的一端称为队头

  1. 队列只能在队头和队尾进行数据操作
  2. 队列模型具有先进先出或者叫做后进后出的规律

data6.png

顺序存储队列

#顺序存储队列

class Queue:
    def __init__(self,len):
        '''初始化队列'''
        self.head = 0
        self.tail = 0
        self.len = len
        self.data = [None] * self.len

    def enqueue(self,value):
        '''入队'''
        if self.is_full():
            raise ValueError('full')
        self.data[self.tail] = value
        self.tail = (self.tail+1)%self.len

    def dequeue(self):
        '''出队'''
        if self.is_empty():
            raise ValueError('empty')
        data = self.data[self.head]
        self.head = (self.head+1)%self.len
        return data

    def is_full(self):
        '''判断队列是否满 满返回true'''
        return (self.tail+1)%self.len == self.head

    def is_empty(self):
        '''判断队列是否空 空返回teue'''
        return self.tail == self.head

q = Queue(5)
q.enqueue(1)
print(q.dequeue())
q.enqueue(2)
print(q.dequeue())
q.enqueue(3)
print(q.dequeue())
q.enqueue(4)
print(q.dequeue())
q.enqueue(5)
print(q.dequeue())

链式存储队列

# 链式存储队列

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

class Queue:
    def __init__(self):
        '''初始化队列'''
        self.head = None
        self.tail = None

    def enqueue(self,value):
        '''入队'''
        new = Node(value)
        if self.head == None:
            self.head = new
            self.tail = new
            return
        self.tail.next = new
        self.tail = new

    def dequeue(self):
        '''出队'''
        if self.is_empty():
            raise ValueError('error')
        p = self.head
        self.head = self.head.next
        if self.head == None:
            self.tail = None
        return p.value

    def is_full(self):
        '''判断队列是否满 满返回true'''

    def is_empty(self):
        '''判断队列是否空 空返回teue'''
        # return self.head == None
        return self.tail == None

q = Queue()
q.enqueue(1)
print(q.dequeue())
q.enqueue(2)
print(q.dequeue())
q.enqueue(3)
print(q.dequeue())
q.enqueue(4)
print(q.dequeue())
q.enqueue(5)
print(q.dequeue())
print(q.is_empty())

递归

所谓递归函数是指一个函数的函数体中直接调用或间接调用了该函数自身的函数。这里的直接调用是指一个函数的函数体中含有调用自身的语句，间接调用是指一个函数在函数体里有调用了其它函数，而其它函数又反过来调用了该函数的情况

# 求等差数列值和
# n = 4 1+2+3+4=10
def sum(n):
    return 1 if n == 1 else n + sum(n - 1)

# 求阶乘 n = 5 1*2*3*4*5=120
def jie(n):
    return 1 if n == 1 else n * jie(n - 1)

# 斐波那契数列
def fei(n):
    return n if n <= 2 else fei(n-2) + fei(n-1)

print(sum(100)) # 5050
print(jie(5)) # 120
print(fei(7)) # 21

树形结构

树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件：有且仅有一个特定的称为根（Root）的节点；其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）

data7.png

基本概念

  • 一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树中节点的最大度数。
  • 度数为零的节点称为树叶或终端节点，度数不为零的节点称为分支节点，除根节点外的分支节点称为内部节点。
  • 一个节点的子树之根节点称为该节点的子节点，该节点称为它们的父节点，同一节点的各个子节点之间称为兄弟节点。一棵树的根节点没有父节点，叶节点没有子节点。
  • 一个节点系列k1,k2, ……,ki,ki+1, ……,kj,并满足ki是ki+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1,即路径中的边数。路径中前面的节点是后面节点的祖先，后面节点是前面节点的子孙。
  • 节点的层数等于父节点的层数加一，根节点的层数定义为一。树中节点层数的最大值称为该树的高度或深度。
  • m（m≥0）棵互不相交的树的集合称为森林。树去掉根节点就成为森林，森林加上一个新的根节点就成为树。

data8.png

二叉树

度为2的树称为二叉树

  • 二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右

data9.png

二叉树的特征

  • 二叉树第i（i≥1）层上的节点最多为\(2^{i-1}\)个。
  • 深度为k（k≥1）的二叉树最多有\(2^k－1\)个节点。
  • 满二叉树 ：深度为k（k≥1）时有\(2^k－1\)个节点的二叉树。
  • 完全二叉树 ：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。

二叉树的遍历

QQ截图20230515161250.jpg

  • 先序遍历： 先访问树根，再访问左子树，最后访问右子树
  • 结果:[5,3,1,4,7,6,9]
  • 中序遍历： 先访问左子树，再访问树根，最后访问右子树
  • 结果:[1,3,4,5,6,7,9]
  • 后序遍历： 先访问左子树，再访问右子树，最后访问树根
  • 结果:[1,4,3,6,9,7,5]
  • 层次遍历: 从根节点开始，逐层从左向右进行遍历
  • 结果:[5,3,7,1,4,6,9]

二叉树的存储结构

二叉树顺序存储

二叉树本身是一种递归结构，可以使用Python list进行存储。但是如果二叉树的结构比较稀疏的话浪费的空间是比较多的

  • 空结点用None表示
  • 非空二叉树用包含三个元素的列表[d,l,r]表示，其中d表示根结点，l，r左子树和右子树
['A',['B',None,None
     ],
     ['C',['D',['F',None,None],
               ['G',None,None],
          ],     
          ['E',['H',None,None],
               ['I',None,None],
          ],
     ]
]

bitree1.png

二叉树链式存储

二叉树每个节点中除了存储数据的元素本身外，还需要两个变量来记录当前节点的左子树和右子树

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

二叉排序树（二叉查找树）- Binary Search Tree

在二叉树中，任何一个子树都满足左子树中所有节点的值都小于它的根节点，所有的右节点的值都大于它的根节点的值的二叉树称为二叉排序树

  • 链式队列
class Node:
    def __init__(self, value,next=None):
        self.value = value
        self.next = next

class Queue:
    def __init__(self):
        '''初始化队列'''
        self.head = None
        self.tail = None

    def enqueue(self,value):
        '''入队'''
        new = Node(value)
        if self.head == None:
            self.head = new
            self.tail = new
            return
        self.tail.next = new
        self.tail = new

    def dequeue(self):
        '''出队'''
        if self.is_empty():
            raise ValueError('error')
        p = self.head
        self.head = self.head.next
        if self.head == None:
            self.tail = None
        return p.value

    def is_full(self):
        '''判断队列是否满 满返回true'''

    def is_empty(self):
        '''判断队列是否空 空返回teue'''
        # return self.head == None
        return self.tail == None
  • 二叉树遍历
from link_list_queue import Queue


class Node:
    def __init__(self,value,left = None,right = None):
        self.value = value
        self.left = left
        self.right = right


class BinanySearchTree:
    def __init__(self,root = None):
        '''初始化树'''
        self.root = root

    def insert(self,value):
        '''向树中插入数据'''
        if self.root == None:
            self.root = Node(value)
            return
        # 通过递归插入数据
        self.insert_tree(self.root,Node(value))

    def insert_tree(self,root_node,value_node):
        '''向树中插入数据'''
        # 判断插入值和当前节点的关系
        if root_node.value <= value_node.value:
            # right
            if root_node.right == None:
                root_node.right = value_node
            else:
                self.insert_tree(root_node.right,value_node)
        else:
            #left
            if root_node.left == None:
                root_node.left = value_node
            else:
                self.insert_tree(root_node.left,value_node)


    def __contains__(self, item):
        '''查看item是否存在与树中，如果存在返回true,否则返回false'''
        if self.root == None:
            return False
        root = self.root
        while root:
            # 判断当前值
            if root.value == item:
                return True
            elif root.value <= item:
                #right
                root = root.right
            else:
                #left
                root = root.left
        return False

    def preorder_traversal(self):
        '''先序遍历'''
        data = []
        self.preorder(self.root,data)
        return data

    def preorder(self,root,data):
        '''递归先序'''
        if root == None:
            return
        data.append(root.value) # 1.根
        self.preorder(root.left,data) # 2.左
        self.preorder(root.right,data) # 3.右

    def middleorder_traversal(self):
        '''中序遍历'''
        data = []
        self.middleorder(self.root,data)
        return data

    def middleorder(self,root,data):
        '''递归中序'''
        if root == None:
            return
        self.middleorder(root.left,data) # 1.左
        data.append(root.value) # 2.根
        self.middleorder(root.right,data) # 3.右

    def lastorder_traversal(self):
        '''后序遍历'''
        data = []
        self.lastorder(self.root,data)
        return data

    def lastorder(self,root,data):
        '''递归后序'''
        if root == None:
            return
        self.lastorder(root.left,data) # 1.左
        self.lastorder(root.right,data) # 2.右
        data.append(root.value) # 3.根

    def level_traversal(self):
        '''层次遍历'''
        # 判断是否为空
        if self.root == None:
            return
        # 创建队列
        q = Queue()
        q.enqueue(self.root)
        data = []
        # 只要队列里有参数 就一直运行
        while q.is_empty() != True:
            res = q.dequeue()
            if res.left != None:
                q.enqueue(res.left)
            if res.right != None:
                q.enqueue(res.right)
            data.append(res.value)
        return data

tree = BinanySearchTree()
tree.insert(5)
tree.insert(3)
tree.insert(1)
tree.insert(4)
tree.insert(7)
tree.insert(6)
tree.insert(9)

print(tree.preorder_traversal())
print(tree.middleorder_traversal())
print(tree.lastorder_traversal())
print(tree.level_traversal())

算法

是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出

  • 算法五大特性
  1. 输入 -- 具有0个或多个输入
  2. 输出 -- 至少由1个或者多个输出
  3. 有穷性 -- 算法执行的步骤是有限的
  4. 确定性 -- 每个计算步骤无二义性
  5. 可行性 -- 每个计算步骤能够在有限的时间内完成
  • 若\(n1 + n2 + n3=1000\), 且\(n1^2 + n2^2 = n3^2\) (n1,n2,n3为自然数),求出所有n1、n2、n3可能的组合
import time

start_time = time.time()
for n1 in range(0,1001):
    for n2 in range(0,1001):
        for n3 in range(0,1001):
            if n1 + n2 + n3 == 1000 and n1**2 + n2**2 == n3**2:
                    print('[%d,%d,%d]' % (n1,n2,n3))
end_time = time.time()
print('执行时间:%.2f' % (end_time-start_time))  # 此处大约运行180秒
  • 如果在此代码基础上减少一层循环,会大大提高效率
import time

start_time = time.time()
for n1 in range(0,1001):
    for n2 in range(0,1001):
        n3 = 1000 - n2 - n1
        if n3 >= 0 and n1**2 + n2**2 == n3**2:
            print('[%d,%d,%d]' % (n1,n2,n3))
end_time = time.time()
print('执行时间:%.2f' % (end_time-start_time))  # 此处大约运行0.72秒

时间复杂度概述

同一个算法，由于机器配置差异,每台机器执行的总时间不同,但是执行基本运算的数量大体相同，所以把算法执行步骤的数量称为时间复杂度

  • 时间复杂度衡量标准: 运算步骤来衡量,n代表解决问题的规模问题,对于同一类问题所花费的步骤有一个统一的表示,这个T(n)为时间复杂度,n**3为它的大O表示法,即\(O(n^3)\)时间复杂度是指程序执行步骤的数量
################################################################
for n1 in range(0,1001):
    for n2 in range(0,1001):
    for n3 in range(0,1001):
        if n1 + n2 + n3 == 1000 and n1**2 + n2**2 == n3**2:
            print('[%d,%d,%d]' % (n1,n2,n3))
################################################################

# 计算时间复杂度 - 执行计算步骤的次数
T = 1000 * 1000 * 1000 * 2
T = n * n * n * 2
T(n) = n ** 3 * 2  --> 则时间复杂度为T(n) 及 n**3 * 2
  1. 假定计算机执行算法每个基本操作的时间是固定的一个时间单位，则有多少个基本操作就代表会花费多少时间单位。虽然对于不同机器环境切确的时间单位不同，但对于算法进行的基本操作数量在规模数量级上相同，因此可以忽略机器环境影响而客观反映算法的时间效率，用大O记法表示
  2. 时间复杂度：假设存在函数g，使得算法A处理规模为n的问题所用时间为\(T(n)=O(g(n))\)，则称\(O(g(n))\)为算法A的渐近时间复杂度，简称时间复杂度，记为\(T(n)\)
  3. 对算法进行特别具体细致分析虽然好，但实践中实际价值有限。对我们来说算法的时间性质和空间性质最重要的是数量级和趋势，这些是分析算法效率的主要部分。 所以忽略系数，忽略常数，比如\(5n^2\)和\(100n^2\)属于一个量级，时间复杂度为\(O(n^2)\)

时间复杂度分类

  1. 最优时间复杂度 - 最少需要多少个步骤
  2. 最坏时间复杂度 - 最多需要多少个步骤
  3. 平均时间复杂度 - 平均需要多少个步骤
  4. 我们平时所说的时间复杂度,指的是最坏时间复杂度
# 示例 - 列表元素排序
[3,1,4,1,5,9,2,6]   --> 时间复杂度:O(n^2)
[1,2,3,4,5,6,7,8]   --> 时间复杂度:O(n)
for i in L:
    先扫描一遍,若有序直接退出
    时间复杂度变为 n

时间复杂度计算规则

# 1. 基本操作,只有常系数，认为其时间复杂度为O(1)
顺序/条件/循环 - 所有语言都包括
顺序 - 基本步骤之间的累加
print('abc') -> O(1)
print('abc') -> O(1)
# 2. 循环: 时间复杂度按乘法进行计算
# 3. 分支: 时间复杂度取最大值(哪个分支执行次数多算哪个)

# 练习:请计算如下代码的时间复杂度
for n1 in range(0,1001):
    for n2 in range(0,1001):
    n3 = 1000 - n1 - n2
    if n1**2 + n2**2 == n3**2:
        print('[%d,%d,%d]'%(n1,n2,n3))

T(n) = n * n * (1+max(1,0))
T(n) = n**2 * 2
T(n) = n**2
T(n) = O(n**2)
用大O表示法表示为 O(n^2)
  • 常见时间复杂度
执行次数 时间复杂度 阶
20（20个基本步骤） O(1) 常数阶
8n+6 O(n) 线性阶
2n^2 + 4n + 2 O(n^2) 平方阶
8logn + 16 O(logn) 对数阶
4n + 3nlogn + 22 O(nlog(n)) nlog阶
2n^3 + 2n^2 + 4 O(n^3) 立方阶
2 ^ n O(2^n) 指数阶 
# 所消耗的时间从小到大
O(1)<O(logn)<O(n)<O(nlogn)<O(n**2)<O(n**3)<O(2**n)<O(n!)<O(n**n)

# 练习: 写出如下的时间复杂度
O(5)          --> O(1)
O(2n+1)       --> O(n)
O(n**2+n+1)   --> O(n**2)
O(3n**3+1)    --> O(n**3)
  • 时间复杂度计算
  1. 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量。O表示一个数量级的概念。根据算法中语句执行的最大次数（频度）来估算一个算法执行时间的数量级
  2. 写出程序中所有运算语句执行的次数，进行加和
  3. 如果得到的结果是常量则时间复杂度为1
  4. 如果得到的结果中存在变量n则取n的最高次幂作为时间复杂度

data11.png

算法基础概念

算法（Algorithm）是一个有穷规则（或语句、指令）的有序集合。它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出

  1. 定义
  • 算法设计 : 取决于选定的逻辑结构
  • 算法实现 : 依赖于采用的存储结构
  1. 算法的特性
  • 有穷性 : 算法执行的步骤（或规则）是有限的
  • 确定性 : 每个计算步骤无二义性
  • 可行性 : 每个计算步骤能够在有限的时间内完成
  • 输入输出 : 存在数据的输入和出输出
  1. 评价算法好坏的方法
  • 正确性 : 运行正确是一个算法的前提
  • 可读性 : 容易理解、容易编程和调试、容易维护
  • 健壮性 : 考虑情况全面，不容以出现运行错误
  • 时间效率高 : 算法消耗的时间少
  • 储存量低 : 占用较少的存储空间
  • 参考网站 : https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

排序

排序(Sort)是将无序的记录序列（或称文件）调整成有序的序列

冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

冒泡排序.gif

选择排序(Selection Sort)

选择排序(Selection sort)是一种简单直观的排序算法。其基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

选择排序.gif

插入排序

  1. 直接插入排序（Insertion Sort)
  2. 希尔排序(Shell Sort)

直接插入排序是将无序序列中的数据插入到有序的序列中，在遍历无序序列时，首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置，一直到无序序列中的所有元素插完为止

快速排序

从数列中挑出一个元素，称为"基准"（pivot），重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

快速排序.gif

八种排序算法的复杂度

sort_complexity.jpeg

  • 快速排序
data = [5,9,12,4,2,14,8,5,5,3,1]
print(data)

# 快速排序
def quick_sort(data, start = 0, end = None):
    if end == None:
        # 获取结束索引
        end = len(data) - 1
    # 判断执行条件
    # 指针重叠 直接返回
    # 递归退出条件
    if start >= end:
        return data

    # 设定随机数
    x = data[start]
    old_start = start
    old_end = end

    # 外层循环执行条件
    # 当左右两侧索引重叠或越过时 停止循环
    while start < end:
        # 确定随机数
        # 先移动右侧索引
        while start < end:
            if x >= data[end]:
                data[start] = data[end]
                start += 1
                break
            end -= 1
        # 在移动左侧索引
        while start < end:
            if x <= data[start]:
                data[end] = data[start]
                end -= 1
                break
            start += 1
    # 移动结束后 将默认的数放到指定索引
    data[start] = x

    # 递归
    quick_sort(data, old_start, start - 1)
    quick_sort(data, end + 1, old_end)

quick_sort(data)
print(data)

查找

查找(或检索)是在给定信息集上寻找特定信息元素的过程

二分法查找

当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的

binraysearch1.jpg

binarysearch2.gif