数据结构
“”"
基础概念:
程序 = 数据结构 + 算法
数据结构 = 存储和组织数据的方式.
算法 = 解决问题的思维, 思路, 方式.
算法的特性:独立性: 算法 = 思维, 是解决问题的思路和方式, 不依赖语言.5大特性: 有输入, 有输出, 有穷性, 确定性, 可行性.问: 如何衡量算法的优劣?
答: 时间复杂度.
例如: 下述的两个代码, 执行时长为: 代码的总步骤 * 每步的基本时间方式1: 1001³ * 9 * 每步的基本时间方式2: 1001² * 9 * 每步的基本时间虽然上述的方式可以计算代码执行时间, 但是我们在考虑算法的时间复杂度的时候, 只考虑 主要条件, 而会忽略次要条件.时间复杂度介绍:它适用于衡量算法的优劣的, 一般采用大O标记法, 把次要条件都忽略, 最终形成的表达式就叫: 大O标记法.名词解释:问题规模: 程序(算法)的计算量, 计算范围...主要条件: 随着问题规模变化而变化的代码.次要条件: 随着问题规模变化而不变的代码.计算方式:常数项: O(1)顺序结构: 加法分支结构: 最高次项循环结构: 乘法分析的时候, 只参考 主要条件, 忽略 次要条件 和 常数项.如果没有特殊说明的情况下, 我们分析时间复杂度, 指的都是: 最坏时间复杂度.最优时间复杂度: 最理想, 最乐观的状态, 算法需要的最少步骤.最坏时间复杂度: 算法的保证, 最多需要多少步能计算出结果.常用的时间复杂度介绍:从低到高分别是:常数阶 < 对数阶 < 线性阶 < 常数对数阶 < 平方阶 < 立方阶O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³)空间复杂度(了解):概述: 算法执行过程中, 临时占用的内存空间大小.分类:O(1) < O(logn) < O(n) < O(n²) < O(n³)细节:内存是通过 字节 的形式来存储数据的, 每块空间都有自己的地址值.
“”"
import time# 需求: 演示算法 -> 穷举法. 已知: a² + b² = c², 且 a + b + c = 1000, 问: a,b,c可以是哪些组合.
start = time.time()
# 方式1: 穷举法, 3层循环嵌套.
for a in range(0, 1001):for b in range(0, 1001):for c in range(0, 1001):# if a + b + c == 1000 and a ** 2 + b ** 2 == c ** 2: # 122秒if a ** 2 + b ** 2 == c ** 2 and a + b + c == 1000: # 235秒print(a, b, c)
end = time.time()
print(f'程序共执行了: {(end - start):.2f} 秒') # 122.01秒# 方式2: 穷举法 + 代入法, 2层循环嵌套.
start = time.time()
# 方式1: 穷举法, 3层循环嵌套.
for a in range(0, 1001):for b in range(0, 1001):c = 1000 - a - bif a ** 2 + b ** 2 == c ** 2:print(a, b, c)
end = time.time()
print(f'程序共执行了: {(end - start):.2f} 秒') # 0.34s
“”"
数据结构介绍:
概述:
数据结构 = 存储,组织属于的方式, 也是算法解决问题时的载体.
分类:
线性结构
非线性结构
线性结构:特点:每个节点有且只能有1个前驱节点(父节点) 和 1个后继节点(子节点)举例:栈, 队列, 链表...分类:顺序表:概述:采用 连续 的内存空间来存储.根据存储方式不同, 又分为:一体式存储: 信息区 和 数据区在一起.分离式存储: 信息区 和 数据区分开存储.扩容策略:一体式: 扩容时, 信息区和数据区整体搬迁.分离式: 只搬迁数据区, 然后用信息区重新关联即可.思路:方式1: 每次增加固定的容量, 假设: 每次扩容增加100个字节. 拿时间换空间.方式2: 每次扩容容量翻倍. 拿空间换时间(推荐做法).链表:概述:采用 非连续 的内存空间来存储.非线性结构:特点:每个节点都可以有多个前驱节点(父节点) 和 多个后继节点(子节点)举例:树图...
“”"
"""
链表介绍:概述:它属于数据结构的一种, 属于: 线性结构(每个节点都只能有1个前驱节点 和 1个后继节点)回顾: 顺序表的弊端扩容时要求有足够的连续的内存空间, 否则扩容失败.链表扩容:比较简单, 有地儿就行, 可以不连续, 最后通过"链条"连接起来.链表 = 通过 一条线把各个节点链接起来, 形成一个 链条就叫: 链表.组成:元素域(数值域) + 链接域(地址域)分类:单向链表:每个节点由 元素域(数值域) + 链接域(地址域), 前边节点的链接域指向后1个节点的地址, 最后1个节点的链接域为: None.单向循环链表:每个节点由 元素域(数值域) + 链接域(地址域), 前边节点的链接域指向后1个节点的地址, 最后1个节点的链接域为: 第1个节点的地址.双向链表:每个节点由 链接域(地址域) + 元素域(数值域) + 链接域(地址域),每个节点的链接域会分别指向: 前, 后节点的地址.第1个节点的: 前链接域(地址域) 和 最后1个节点的 后链接域(地址域)为 None双向循环链表:每个节点由 链接域(地址域) + 元素域(数值域) + 链接域(地址域),每个节点的链接域会分别指向: 前, 后节点的地址.第1个节点的: 前链接域(地址域) 指向最后1个节点的 地址.最后1个节点的 后链接域(地址域)指向第1个节点的 地址.需求:自定义代码, 采用面向对象思维, 模拟链表.
"""
“”"
案例: 自定义代码, 采用面向对象思维, 模拟: (单向)链表.
回顾:
链表 由节点组成, 节点 = 数值域(元素域) + 地址域(链接域)
分析:
节点类: SingleNode
属性:
item: 数值域(元素域)
next: 地址域(链接域)
链表类: SingleLinkedList属性:head: 指向头结点
“”"
# 定义节点类
class SingleNode(object):def __init__(self, item):self.item = itemself.next = None#定义链表类
class SingleLinkedList(object):def __init__(self, head=None):self.head = head# 判断链表为空def is_Empty(self):return self.head == None# 返回链表长度def length(self):cur = self.headcount = 0while cur is not None:count += 1cur = cur.nextreturn count# 遍历打印链表def travel(self):cur = self.headcount = 0while cur is not None:print(cur.item)cur = cur.next# 链表头部增加元素def add(self, item):new_node = SingleNode(item)new_node.next = self.headself.head = new_node# 链表尾部添加元素def append(self, item):new_node = SingleNode(item)if self.is_Empty():self.head = new_nodeelse:cur = self.headwhile cur.next is not None:cur = cur.nextcur.next = new_nodeif __name__ == '__main__':# 创建对象s1 = SingleLinkedList()# 测试判空函数print(s1.is_Empty())# 测试添加元素s1.add('坤坤')# 测试遍历元素s1.travel()# 测试在尾部添加数据s1.append('鸡叫')# 测试遍历元素s1.travel()