python中的数据结构与算法(上)

相关概述

数据结构:存储和组织数据的方式方法

算法:解决问题的思路\方式

数据结构与算法的关系:算法是解决实际业务问题的思路,数据结构是算法的载体,高效的程序需要在数据结构的基础上设计和选择算法

终极意义:大大提高程序的性能和执行效率

程序 = 数据结构 + 算法

人工智能 = 算法 + 算力 + 数据 

数据结构

数据结构是存储和组织数据的方式方法,合适的数据结构往往能带来比较大的性能提升

数据结构的分类:

        线性结构(一个前驱父节点,一个后继子节点 --例如:栈\队列 )

        线性结构的分类:

                顺序表:存储空间是连续的,存储方式分为一体式存储和分离式存储

                        一体式存储:数据区和信息区在一起  arr = [1,2,3]

                        分离式存储:数据区和信息区分开存储 arr = ['a',1,False,'asdf']

                链表:存储空间是不连续的

                        单向链表,双向链表,单向循环链表,双向循环链表

                

        非线性结构(多个前驱父节点,多个后继子节点 -- ;例如:树\图)

        

线性结构存储数据的方式

线性结构根据存储方式可分为顺序表和链表
顺序表:开10间房必须得是连续的
链表:开10间房可以是非连续的
顺序表更适合查和改,内存地址都在一起,空间连续,查找修改快,增删慢

链表更适合增和删,内存地址分开存储,空间不连续,增删快,查找修改慢

链表失去了顺序表随机读取的优点(索引),链表增加了节点的连接域,空间开销比较大,但对存储空间的使用相对灵活


顺序表的存储方式:
    一站式存储,元素占的字节数一样,通过偏移固定字节数就可以找到相应的元素
    分离式存储,元素占的字节数不一样,通过存储地址值,来管理元素
   

顺序表和链表的复杂度比较:

访问元素:链表O(n)   顺序表O(1)--索引

头部插入/删除:链表O(1) 顺序表:考虑到后面所有的元素O(n)

尾部插入/删除:链表O(n) 顺序表O(1)

在中间插入删除,均为O(n)



内存中存储数据的方式是字节,内存以字节为基本存储单位,每个基本存储空间都有自己的地址,整形int 4个字节,字符char 1个字节

顺序表有 数据区 和 信息区两部分组成.

数据区 和 信息区在一起的 -> 一体式存储(扩容时只能整体搬迁)

数据取货 和 信息区分开存储的 -> 分离式存储(可以直接让信息区指向新的 数据区即可, 不用整体搬迁).



顺序表扩容策略思路1: 每次增加固定的容量. 时空转换之拿时间换空间

my_list = (i for i in range(10000000))     生成器思路2: 每次扩容, 容量翻倍. 时空转换之拿空间换时间

my_list = [i for i in range(10000000)]     列表一次生成

大多数情况都是考虑拿空间换时间

线性结构之链表介绍

链表属于 线性结构, 在存储时 不要求连续的内存空间, 只要有地儿就行.

可以简单理解为, 它是用来解决顺序表的弊端的(必须要有足够的连续空间, 否则扩容失败.)

链表 由 节点 组成. 节点又分为 数值域(元素域) 和 地址域(链接域), 根据节点不同, 链表可以分为 四大类.

自定义代码模拟链表

链表介绍:
    概述:
        它属于数据结构之 线性结构的一种, 每个节点都只能有 1个前驱 和 1个后继节点.
    作用:
        用于优化顺序表的弊端(如果没有足够的连续的内存空间, 会导致扩容失败)
        链表扩容时, 有地儿就行, 连不连续无所谓.
    组成:
        由 节点 组成, 其中节点由 元素域(数值域) 和 链接域(地址域)组成.
    分类:
        根据 节点类型不同, 链表主要分为:
        单向链表: 节点由1个数值域 和 1个地址域组成, 前边节点的地址域存储的是后续节点的地址, 最后1个节点的地址域为 None
        单向循环链表:
        双向链表:
        双向循环链表:

自定义代码模拟链表, 思路分析:
    1. 自定义SingleNode类, 表示 节点类.
        属性:
            item   数值域(元素域)
            next   地址域(链接域)

    2. 自定义SingleLinkedList类, 表示: 链表
        属性:
            head  表示头结点, 指向第1个节点.
        行为:
            is_empty(self) 链表是否为空
            length(self) 链表长度
            travel(self. ) 遍历整个链表
            add(self, item) 链表头部添加元素
            append(self, item) 链表尾部添加元素
            insert(self, pos, item) 指定位置添加元素
            remove(self, item) 删除节点
            search(self, item) 查找节点是否存在

    3. 测试.

""" 案例: 自定义代码模拟链表 链表介绍: 概述: 它属于数据结构之 线性结构的一种, 每个节点都只能有 1个前驱 和 1个后继节点. 作用: 用于优化顺序表的弊端(如果没有足够的连续的内存空间, 会导致扩容失败) 链表扩容时, 有地儿就行, 连不连续无所谓. 组成: 由 节点 组成, 其中节点由 元素域(数值域) 和 链接域(地址域)组成. 分类: 根据 节点类型不同, 链表主要分为: 单向链表: 节点由1个数值域 和 1个地址域组成, 前边节点的地址域存储的是后续节点的地址, 最后1个节点的地址域为 None 单向循环链表: 双向链表: 双向循环链表: 自定义代码模拟链表, 思路分析: 1. 自定义SingleNode类, 表示 节点类. 属性: item 数值域(元素域) next 地址域(链接域) 2. 自定义SingleLinkedList类, 表示: 链表 属性: head 表示头结点, 指向第1个节点. 行为: is_empty(self) 链表是否为空 length(self) 链表长度 travel(self. ) 遍历整个链表 add(self, item) 链表头部添加元素 append(self, item) 链表尾部添加元素 insert(self, pos, item) 指定位置添加元素 remove(self, item) 删除节点 search(self, item) 查找节点是否存在 3. 测试. """ # 1. 自定义SingleNode类, 表示 节点类. class SingleNode: # 初始化属性 def __init__(self, item): self.item = item # 元素域(数值域) self.next = None # 链接域(地址域) # 2. 自定义SingleLinkedList类, 表示: 链表 class SingleLinkedList: # 1. 初始化属性. def __init__(self, node=None): self.head = node # 链表的 头结点, 指向第1个节点. # 2. is_empty(self) 链表是否为空 def is_empty(self): # 思路: 判断头结点是否为None, 如果为None, 则链表为空. # 写法1: if else # if self.head is None: # return True # else: # return False # 写法2: 三元表达式 # return True if self.head is None else False # 写法3: 最终版. return self.head is None # return self.head == None # 能用, 但是不推荐 # 3. length(self) 链表长度 def length(self): # 3.1 创建游标(表示当前节点), 默认从头结点开始. cur = self.head # 3.2 定义计数器. count = 0 # 3.3 开始遍历, 只要当前节点不为空, 就一直循环. while cur is not None: # 3.4 计数器 + 1, 然后 cur指向下个节点. count += 1 cur = cur.next # 3.5 循环结束, 列表长度已经获取了, 返回即可. return count # 4. travel(self. ) 遍历整个链表 def travel(self): # 4.1 创建游标(表示当前节点), 默认从头结点开始. cur = self.head # 4.2 只要当前节点不为空, 就一直循环. while cur is not None: # 4.3 打印当前节点的数值域. print(f'数值域: {cur.item}') # 4.4 修改当前节点, 然后 cur指向下个节点. cur = cur.next # 5. add(self, item) 链表头部添加元素 def add(self, item): # 5.1 创建新节点 new_node = SingleNode(item) # 5.2 设置新节点的地址域 指向 头结点 new_node.next = self.head # 5.3 设置头结点指向新节点. self.head = new_node # 6. append(self, item) 链表尾部添加元素 def append(self, item): # 6.1 封装新节点. new_node = SingleNode(item) # 6.2 判断列表如果为空, 直接设置当前节点为头结点即可. if self.is_empty(): self.head = new_node else: # 6.3 走到这里, 说明链表不为空, 需要找到尾结点. # 6.4 创建游标(表示当前节点), 默认从头结点开始. cur = self.head # 6.4 开始遍历, 只要当前节点不为空, 就一直循环. while cur.next is not None: # 6.5 游标后移. cur = cur.next # 6.6 走到这里 cur就是最后1个节点, 设置它的地址域指向新节点即可 cur.next = new_node # 7. insert(self, pos, item) 指定位置添加元素 def insert(self, pos, item): # 7.1 判断索引是否越界, 如果 <= 0 往前加. if pos <= 0: self.add(item) # 7.2 如果索引是 >= 长度的, 就往后加. elif pos >= self.length(): self.append(item) else: # 7.3 走这里, 说明索引合法, 即: 中间的值. 需找到插入位置前的哪个元素. # 7,4 创建游标(表示当前节点), 默认从头结点开始. cur = self.head # 7.5 定义变量, 记录当前节点的位置(可以理解为索引, 但是不是, 因为链表没有索引) count = 0 # 7.6 开始遍历, 只要 当前节点的位置 < pos , 就一直循环. while count < pos - 1: # 7.7 走这里, 说明还没有找到插入前的哪个节点, 就: 节点后移, 计数器+1 cur = cur.next count += 1 # 7.8 走到这里, cur就是插入位置前的那个节点. 先封装内容为新节点. new_node = SingleNode(item) # 7.9 设置 新节点的地址域 指向 插入位置前那个节点的 地址域 new_node.next = cur.next # 7.10 设置 插入位置前的那个节点的地址域 指向 新节点 cur.next = new_node # 8. remove(self, item) 删除节点 def remove(self, item): # 8.1 创建游标(表示当前节点), 默认从头结点开始. cur = self.head # 8.2 定义变量, 记录要删除节点的 前驱节点. pre = None # 8.3 开始遍历, 只要 当前节点不为空, 就一直循环. while cur is not None: # 8.4 判断当前节点是否是要删除的节点. if cur.item == item: # 8.5 判断要删除的节点是否是头结点. if cur == self.head: # 8.6 直接设置头结点为 当前节点的下个节点即可. self.head = cur.next else: # 8.7 走到这里,说明要删除的节点不是头结点. 直接设置 前驱节点的地址域 指向 当前节点的地址域即可. pre.next = cur.next cur.next = None # 删除节点, 断开链接. # 8.8 走这里, 说明删除成功, 直接返回即可, 即: 结束程序. return else: # 8.9 走这里, 说明当前节点不是要删除的节点, 就: 游标后移, 前驱节点后移. pre = cur cur = cur.next # 9. search(self, item) 查找节点是否存在 def search(self, item): # 9.1 创建游标(表示当前节点), 默认从头结点开始. cur = self.head # 9.2 只要当前节点不为空, 就一直循环. while cur is not None: # 9.3 判断当前节点是否是要找的节点, 如果是就返回True if cur.item == item: return True # 9.4 如果当前节点不是要找的节点, 就: 游标后移. cur = cur.next # 9.5 走到这里, 所以节点都找完了, 还没找到, return False return False # 3. 在main中测试 if __name__ == '__main__': # # 3.1 测试节点类. # node1 = SingleNode(10) # # 3.2 打印当前节点的 元素域(数值域) 和 链接域(地址域) # print(f'元素域(数值域): {node1.item}') # 10 # print(f'链接域(地址域): {node1.next}') # None # print(f'node1对象: {node1}') # 地址值, 可以重写 str魔法方法改为打印属性值. # print(f'node1的类型: {type(node1)}') # print('-' * 23) # # # 3.2 测试链表类. # # my_linkedlist = SingleLinkedList() # my_linkedlist = SingleLinkedList(node1) # print(f'头结点为: {my_linkedlist.head}') # print(f'头结点的元素域: {my_linkedlist.head.item}') # 10 # print(f'头结点的地址域: {my_linkedlist.head.next}') # None # 4. 完整测试. # 4.1 创建节点类. node1 = SingleNode('乔峰') # 4.2 将上述的节点作为头结点, 创建链表. my_linkdlist = SingleLinkedList(node1) # my_linkdlist = SingleLinkedList() # 4.3 打印头结点. # print(f'头结点为: {my_linkdlist.head}') # print(f'头结点的数值域为: {my_linkdlist.head.item}') print('-' * 23) # 4.4 测试链表是否为空. print(my_linkdlist.is_empty()) print('-' * 23) # 4.7 测试(往头部)添加元素. my_linkdlist.add('虚竹') my_linkdlist.add('段誉') print('-' * 23) # 4.8 测试(往尾部)添加元素. my_linkdlist.append('王语嫣') my_linkdlist.append('穆婉清') print('-' * 23) # 4.9 测试(指定位置)添加元素. my_linkdlist.insert(-3, '小龙女') my_linkdlist.insert(10, '尹志平') my_linkdlist.insert(2, '阿朱') print('-' * 23) # 4.10 测试删除元素. my_linkdlist.remove('小龙女') my_linkdlist.remove('尹志平') my_linkdlist.remove('乔峰') print('-' * 23) # 4.11 测试查找元素. print(my_linkdlist.search('段誉')) # True print(my_linkdlist.search('乔峰')) # False print('-' * 23) # 4.5 测试链表长度. print(f'链表长度为: {my_linkdlist.length()}') print('-' * 23) # 4.6 测试遍历链表. my_linkdlist.travel() print('-' * 23) 

算法

算法是解决实际业务问题的思路方式

主要分类:增删改查\排序

如何衡量算法的优劣:时间复杂度和空间复杂度

        空间复杂度:算法在执行过程中,临时占用内存空间的大小

                常见的空间复杂度:O(1)<O(logn)<O(n)<O(n²)<O(n³)

        时间复杂度:表示一个算法随问题规模不断变化的最主要趋势,用来衡量一个算法的优劣

               常见的时间复杂度由从最优到最坏排列:

                        O(1)          常数阶

                        O(logn)     对数阶

                        O(n)          线性阶

                        O(nlogn)   线性对数阶

                        O(n²)        平方阶

                        O(n³)        立方阶

        如非特殊说明.我们考虑的都是最坏的时间复杂度,因为它是算法的一种保证.

        算法的特点:独立性(算法是独立存在的一种解决问题的方法和思想,不因编程语言的不同而有所不同)

        算法的特征:有输入\有输出\有穷性\确定性\可行性

算法时间复杂度案例

需求是:a+b+c=1000,a²+b²=c²,求出满足条件的a,b,c的值

上图中可见:     

思路①总步骤=1001 * 1001 * 1001 * 10

思路②总步骤 = 1001 * 1001 * 10

我们不能单纯的用上述的公式来衡量算法的优劣,因为问题规模是可能发生改变的,

问题规模可能由1000变为2000,3000,5000

于是我们采用了大O标记法(将次要条件都省略掉,最终形成一个表达式),即只考虑主要条件,而忽略次要条件

主要条件:随着问题规模变化而直接改变的内容

次要条件:随着问题规模变化而不变的内容

于是上述思路①的时间复杂度为O(n³)   思路②的时间复杂度为O(n²)

如非必要,,我们说的时间复杂度指的都是最坏的时间复杂度,且只参考最高次项

也就是说:判断一个算法的效率时,往往只需要关注操作数量的最高次项,其他次要项和常数项可以忽略,在没有特殊说明时,我们分析的算法的时间复杂度都是指最坏的时间复杂度
不随问题规模变化而变化的因素都可以忽略

        

递归简介

递归介绍: 概述: 方法自己调用自己的情况就叫递归. 经典案例: 1.求阶乘 2.斐波那契数列. 核心要点: 1. 递归必须要有出口, 否则容易造成死递归. 2. 递归调用次数不能过多, 否则容易造成死递归. 3. 递归必须有规律. 要搞定递归,掌握两点: 1. 分析出口. 2. 找规律.

""" 案例: 求阶乘 公式: n! = n * (n - 1)! 大白话: 5! = 5 * 4 * 3 * 2 * 1 = 120 出口: 1! = 1 分析流程: 5! = 5 * 4! ----- 4! = 4 * 3! 3! = 3 * 2! 规律 2! = 2 * 1! ----- 1! = 1 出口 """ def factorial(n): # 出口 if n == 1: return 1 # 规律 return n * factorial(n - 1) print(factorial(5))

求阶乘的入栈图解

递归之斐波那契数列

 """ 斐波那契数列（Fibonacci Sequence）是一个经典的数学数列，定义如下： 一个由0和1开始的数列，后续每一项都是前两项之和，其数列为：0、1、1、2、3、5、8、13、21、34…… """ def fibonacci(n): # 出口（base case） if n == 0: return 0 elif n == 1: return 1 # 规律（recursive case） return fibonacci(n - 1) + fibonacci(n - 2)