交通问题
使用图结构，利用节点和边表示道路同时同行的问题
使用贪心法
1.2 抽象数据类型- 类型：一组值或对象的集合
- 数据类型：计算机语言中的类型，既包括这个类型的值的集合，也包括定义在这个类型上的操作
- 抽象数据类型：有一定行为（操作）的抽象（数学）类型
- 抽象出数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来
- 支持数据类型的实现和使用分离的原则，是对问题进行抽象和分解的有效工具
- 允许独立地考虑数据类型的外部接口和内部实现
- 对于系统的分解、设计、维护和修改十分有利，是面向对象技术与方法的主要理论基础
- 传统概念：数据结构是计算机中表示（存储）的、具有一定逻辑关系和行为特征的一组数据
- 面向对象的观点：数据结构是抽象数据类型的物理实现
- 如何具体表示抽象数据类型中的数学模型
- 如何给出抽象数据类型中需要操作的实现
- 数据结构的三方面：
- 逻辑结构：数学模型
- 指数学模型（集合、表、数、图）中的基本元素（节点）之间的相互关系
- 描述方式：
B
=
<
K
,
R
>
B=
- 存储结构：物理结构
- 指数学模型的具体表示方式，包括结点的表示和关系的表示
- 数据的逻辑结构在计算机存储器中的映射（或表示）
- 操作：逻辑结构
- 给定
B
=
<
K
,
R
>
B=
- 给定
B
=
<
K
,
R
>
B=
- 逻辑结构：数学模型
算法是由有穷规则构成（为解决某一类问题）的运算序列
- 算法可以有若干输入和若干输出
- 算法有穷
- 算法每一步有明确定义
- 算法有可行性
算 法 + 数 据 结 构 = 程 序 算法+数据结构=程序 算法+数据结构=程序
1.4.1 算法设计的方法：- 贪心法
- 把问题分解成若干步骤，每一步骤取局部最优以达到整体较优
- 分治法
- 把大问题不断分解成小问题，然后分而治之
- 回溯法
- 一旦失败则返回上一步重新选择，重点在于判断点与回溯技巧
- 动态规划法
- 与分治法相似，把一个大问题分解成若干小问题，但是子问题较多且有可能相互包含
- 分支限界法
- 与回溯法相似，回溯法使用深度优先策略，而分支限界搜索使用广度优先
-
常用的算法度量特性：
- 空间复杂度
- 时间复杂度
-
算法分析的三个重要概念 ：
- 问题规模
- 空间单位
- 时间单位
-
代价的表示与计算：大O表示法
-
加法规则（顺序复合）：
- 算法分为两部分时，复杂性是两部分复杂性之和
- T ( n ) = T 1 ( n ) + T 2 ( n ) = O ( f 1 ( n ) ) + ( f 2 ( n ) ) = O ( max ( f 1 ( n ) , f 2 ( n ) ) ) T(n)=T_1(n)+T_2(n)=O(f_1(n))+(f_2(n))=O(max(f_1(n),f_2(n))) T(n)=T1(n)+T2(n)=O(f1(n))+(f2(n))=O(max(f1(n),f2(n)))
-
乘法规则（循环）：
-
循环 T 1 ( n ) T_1(n) T1(n)，每次 T 2 ( n ) T_2(n) T2(n)时间，则
-
T ( n ) = O ( f 1 ( n ) × f 2 ( n ) ) T(n)=O(f_1(n)times f_2(n)) T(n)=O(f1(n)×f2(n))
-
def matrix_mul(a, b): # 矩阵乘法，O(n^3) res = [[0] * len(b[0]) for i in range(len(a))] for i in range(len(a)): for j in range(len(b[0])): for k in range(len(b)): res[i][j] += a[i][k] * b[k][j] return res -
T ( n ) = O ( n 3 ) T(n)=O(n^3) T(n)=O(n3)
-
-
线性表是零个或多个元素的有穷序列， L = ( k 0 , k 1 , . . . , k n − 1 ) L=(k_0,k_1,...,k_{n-1}) L=(k0,k1,...,kn−1)
- 线性表的逻辑结构：
L
=
<
K
,
R
>
L=
- 表的长度：表中所含元素个数
- 长度为0的表称为空表
- 前驱： k i ki ki是 k i + 1 k_{i+1} ki+1的前驱
- 后继： k i + 1 k_{i+1} ki+1是 k i k_i ki的后继
- 表的长度：表中所含元素个数
- 数据结构通常需要提供“标准”操作
- 创建和销毁实例
- 判断是否为空；如果有容量限制，还需要判断是否为满
- 向结构中加入或删除元素
- 访问结构中的元素
- 编程语言影响需要实现的操作
- 例如Python的自动回收机制，在Python中可以不编写销毁结构的操作
- 具体数据结构需要提供特性操作
- 集合：集合运算
- 图：判断边是否存在
- 从作用角度，数据结构的操作可以分为三类：
- 构造
- 访问
- 变更
- 从支持的操作类型角度，数据结构可以分为两类：
- 不变数据结构：仅支持构造和访问，tuple、frozenset
- 变动数据结构：支持变更，list，dict、set
假设为表数据结构取⼀个类型名 List。为简洁严格地表示操作的对象和结果，下⾯介绍⼀种数学表达形式，形式如下⾯描述：
O p e r a t i o n N a m e : T 1 ∗ T 2 → R e s u l t T OperationName:T1 * T2 to Result T OperationName:T1∗T2→ResultT
其中 O p e r a t i o n N a m e OperationName OperationName是操作名， T 1 ∗ T 2 T1*T2 T1∗T2表示有两个参数，类型分别为 T 1 T1 T1和 T 2 T2 T2， R e s u l t T ResultT ResultT表示操作的结果类型，用 ( ) () ()表示不返回任何结果
-
表数据结构的创建和销毁、判断空和满
-
new_list : ( ) -> List # 创建⼀个空表 del_list : List -> ( ) # 销毁表 is_empty : List -> bool # 表空？ is_full : List -> bool # 表满？
-
-
加入元素
-
prepend : List * Data -> List # ⾸端加⼊ append : List * Data -> List # 尾端加⼊ insert : List * int * Data -> List # 定位加⼊ # 要求将元素加⼊表中特定位置，原处该位及其后的元素后移
-
-
删除元素
-
del_front : List -> List # 删除⾸元素 del_end : List -> List # 删除末元素 delete : List * int -> List # 定位删除 del_elem : List * Data -> List # 删除⼀个 Data del_all_elem : List * Data -> List # 删除所有 Data
-
-
访问元素
-
get_elem : List * int -> Data
-
-
其他操作
-
length : List -> integer # 表元素的个数 locate : List * Data -> integer # 查找元素在表中第⼀个出现的位置，没有时返回特殊值（如-1） sort_list : List -> List # 将表中元素按上升序重新排列（sorting，排序）
-
牵涉到表内容（或结构）变化的操作有两种可能考虑：
- 构造一个新表作为结果
- 按需直接修改表
- 线性表的实现主要考虑两⽅⾯的情况
- 计算机内存的特点，以及保存元素和元素顺序信息的需要
- 重要操作的效率。其中使⽤最频繁的操作通常是：（定位）元素访问，元素加⼊，元素删除，元素遍历
- 两种实现模型：
- 顺序表：将表元素顺序存放在的⼀⼤块连续的存储区⾥
- 链接表：将表元素存放在通过链接构造起来的⼀系列存储块⾥
采⽤顺序存储是表示线性表最简单的⽅法；元素之间逻辑上的相邻关系通过元素在计算机内物理位置上的相邻关系来表示；顺序表示的线性表称为顺序表
存储结构：
-
顺序表中任意元素的位置可以简单计算得出，存取操作可以在 O ( 1 ) O(1) O(1)时间内完成
-
线性表的首地址或基地址
- 顺序表中 k 0 k_0 k0的存储位置 l o c ( k 0 ) loc(k_0) loc(k0)
-
假定顺序表中每个元素占用 c c c个存储单元
- 下标为 i i i的元素 k i k_i ki的存储位置为： l o c ( k i ) = l o c ( k 0 ) + i × c loc(k_i)=loc(k_0)+itimes c loc(ki)=loc(k0)+i×c
-
如果表中要保存的元素的情况复杂，⼤⼩不⼀，或者还有复杂的内部结构，可以采⽤链接⽅式，在表中保存元素链接
操作：
- 访问给定下标
i
i
i的元素
- 需判断 i i i值是否在表当时的合法元素范围内 ( 0 ≤ i ≤ n － 1 ) (0 ≤ i ≤ n－1) (0≤i≤n－1)
- 不在范围内是⾮法访问，合法时从给定位置取得元素的值
- 查找给定元素
d
d
d 的（第⼀次出现的）位置
- 循环，将 d d d与表中元素逐个比较
- 通过下标变量控制循环，从0开始直到大于表中元素个数时结束
- 找到元素时返回下标，找不到时返回特殊值，如-1
- 查找给定元素 d 在位置 k 之后的第⼀次出现的位置
- 与上文类似
- 从 k + 1 k+1 k+1位置开始比较
- 表尾加入元素
O
(
1
)
O(1)
O(1):
- 检查表是否满，表满时操作失败
- 把新数据存⼊元素存储区的第 n n n个单元
- 元素计数变量 n n n+1
- 首端加入元素和定位加入元素
- 需要移动已有元素，腾出要求存入元素的位置
操作复杂性：
- 在
n
n
n个元素的顺序表的下标
i
i
i处加入元素，需要移动
n
−
i
n-i
n−i个元素；删除下标为
i
i
i的元素需要移动
n
−
i
−
1
n-i-1
n−i−1个元素
- 设在位置 i i i加入和删除元素的概率分别为 p i p_i pi和 p i ′ p'_i pi′
- 加入和删除操作平均移动次数分别为 ∑ n i = 0 ( n − i ) p i underset{i=0}{overset{n}{sum}}(n-i)p_i i=0∑n(n−i)pi和 ∑ n i = 0 ( n − i − 1 ) p i ′ underset{i=0}{overset{n}{sum}}(n-i-1)p'_i i=0∑n(n−i−1)pi′
- 如果各种情况平均分布，维持顺序的时间复杂度是 O ( n ) O(n) O(n)
- 访问操作：
- 不需要扫描表的操作， O ( 1 ) O(1) O(1)
- 需要扫描表的操作， O ( n ) O(n) O(n)
总结：
- 优点：
- O ( 1 ) O(1) O(1)时间按位置存取元素
- 元素存储紧凑，除表元素存储外只需要 O ( 1 ) O(1) O(1)空间存放辅助信息
- 缺点：
- 需要连续的大块存储区存放表中元素，可能有大量空闲单元
- 加入删除操作需要移动许多元素
- 需要考虑元素存储区的大小
- 顺序表的模型包括两部分内容
- 元素存储区：存放表中的实际元素
- 若干单元：存放表的全局信息（容量；表元素个数
- 两种组织方式：
- list是一种线性结构，可以看作是线性表的一种实现：
- 基于下标访问元素/更新元素，复杂度为 O ( 1 ) O(1) O(1)
- 允许任意扩充元素，并且在不断加入元素的过程中，表对象标识不变
- list实现的基本约束和解决方案：
- O ( 1 ) O(1) O(1)时间访问并维持顺序，必须是顺序表
- 容纳任意元素，必须采用分离式实现
- 采用上述办法的自然结果：
- 加入、删除元素需要移动许多元素， O ( n ) O(n) O(n)
- 如果加入元素时存储区已满，需要更换储存，把原有元素拷贝（优化：可以在拷贝过程中完成元素加入）
- list的逐步建立：
- 加入一个元素通常需要 O ( n ) O(n) O(n)，建立n个元素的表则需要 O ( n 2 ) O(n^2) O(n2)
- 最好的情况是尾端加入
- 尾端加入可能出现存储区满，需要 O ( n ) O(n) O(n)
- 表中元素越多，换一次存储区的代价越高
- 考虑随着表长度增加，换存储区的频率降低
- 可以考虑每次换存储区时容量加倍
- Python list 的实际实现策略
- 建⽴空 list 时分配可以容纳 8 个元素的存储区
- 元素区满时加⼊：换⼀块 4 倍⼤的存储区；但在表已经⽐较⼤时就会改变策略，换存储区时规模加倍
- 效果：通过尾端加⼊元素，操作的平均复杂性是 O ( 1 ) O(1) O(1)
- 其他操作的性质由连续表的实现⽅式确定
- 所有序列的共性操作，复杂性由操作中需要考察的元素个数确定，其中len是 O ( 1 ) O(1) O(1)操作
- 元素访问和赋值，尾端加⼊和尾端（切⽚）删除是 O ( 1 ) O(1) O(1)操作
- ⼀般元素加⼊，切⽚替换，切⽚删除，表拼接（extend）等都是
O
(
n
)
O(n)
O(n)操
作。 pop 操作默认情况是尾端删除返回，为 O ( 1 ) O(1) O(1)，⼀般情况（指定⾮尾端
位置）为 O ( n ) O(n) O(n)
- Python 没提供检查⼀个 list 的当前存储块容量的操作
- clear为
O
(
1
)
O(1)
O(1)，可能做法：
- 元素计数设置为0
- 换一块空表默认大小的存储区
- reverse修改列表，将元素倒置
- sort，将列表元素排序，最好的复杂性是 O ( n log n ) O(nlog n) O(nlogn)
- 理解从问题到程序的主要过程
- 体会抽象数据类型、数据结构和算法在问题求解过程中的作⽤
- 了解数据结构的主要概念和分类
- 了解算法的概念和主要设计、分析⽅法
- 线性表的顺序表示⽅法。
