这是我们Python进阶的第一个系列, 主要介绍Python中的数据结构.
什么是数据结构？
数据结构的定义
数据是描述客观事物的数值, 字符和所有能被计算机识别的符号的集合.
数据元素是数值的基本单位, 它可以是单个的数值, 也可以是一组数值.
数据项是具有独立含义的数据最小单位, 也叫域.
数据对象是性质相同的有限个数据元素的集合, 它是数据的一个子集.
数据结构是指所涉及的数据元素的集合以及数据元素之间的关系, 由数据元素之间的关系构成结构.因此可以把数据结构看成带结构的数据元素的集合.
数据结构包含以下几个方面:
- 数据逻辑结构: 数据元素之间的逻辑关系, 如集合、线性结构、树形结构、图形结构等.
- 数据存储结构: 数据元素在计算机中的存储方式, 如顺序存储、链接存储、散列存储等.
- 数据运算: 数据元素之间的运算, 如查找、插入、删除、排序等.
数据的逻辑结构主要是从逻辑关系上描述数据的, 与数据的存储无关.
数据的存储结构是指数据元素在计算机中的存储方式, 他是依赖于计算机语言的.
数据的运算是指对数据元素进行各种操作, 如查找、插入、删除、排序等.
数据的逻辑结构
数据的逻辑结构是面向用户的, 它描述数据元素之间的逻辑关系, 可以看成是从具体问题抽象出来的数据模型.
逻辑结构的表示
逻辑结构的表示可以用图形、表格、树形、集合等方式表示.
为了更通用, 通常采用二元组表示数据的逻辑结构, 即一个二元组如下:
$$
B=(D, R)
$$
- $B$是一种数据逻辑结构;
- $D$是数据元素的集合, 在$D$上数据元素至今可能存在多种关系;
- $R$是所有关系的集合.
即:
$$
D={d_i|0\leq i\leq n-1}\
R={r_j|1\leq j\leq m}
$$
$d_i$表示集合$D$中的第$i$个数据元素(或节点),$n$为数据元素的个数. 若$n=0$, 则$D$是一个空集, 此时$B$也是一个空集.
$r_j$表示集合$R$中的第$j$个关系, $m$为关系的个数. 若$m=0$, 则$R$是一个空集, 表示$D$中没有关系, 彼此是独立的.
若不做特别说明, 数据结构中元素的序号或索引均从0开始.
$R$中的某个关系$r_j$是序偶的集合, 对于$r_j$中任一序偶$(x,y\in D)$, 把$x$称为序偶的第一元素, 把$y$称为序偶的第二元素. 又称序偶的第一元素是第二元素的前驱元素, 称第二元素是第一元素的后继元素.
如果某个元素没有前驱元素, 则称它为开始元素(或者首节点), 如果某个元素没有后继元素, 则称它为终端元素.
对称序偶满足若$<x,y>$和$<y,x>$同时存在于$R$, 则$x=y$. 可用圆括号代替尖括号, 即$(x,y)\in R$.
逻辑结构的类型
逻辑结构与元素本身的内容无关, 也与数据元素的个数无关.
归纳起来, 数据的逻辑结构主要有以下类型:
- 集合结构: 与数学中的集合概念相似, 即数据元素之间没有任何关系, 只有一个元素.
- 线性结构: 数据元素之间存在一对一的关系, 即每个元素只有一个前驱元素和一个后继元素.
- 树形结构: 数据元素之间存在一对多的关系, 即每个元素有零个或多个前驱元素和一个或多个后继元素.
- 图形结构: 数据元素之间存在多对多的关系, 即每个元素有零个或多个前驱元素和零个或多个后继元素.
数据的存储结构
数据存储结构是指数据元素在计算机中的存储方式, 它是依赖于计算机语言的.
逻辑结构是存储结构的本质. 数据的存储结构称为从逻辑结构到存储器的映射.
归纳起来有四种常用的存储结构类型:
- 顺序存储: 数据元素按顺序存储在一块连续的存储区中.在Python中, 列表是顺序存储的一种实现. 主要优点是节省存储空间, 可以实现对元素的随机存取, 即每个元素对应一个序号. 主要缺点是初始空间大小难以确定, 且插入和删除操作效率低.
- 链式存储: 数据元素以链表的形式存储在一块连续的存储区中, 每个元素包含一个指针, 指向下一个元素. 主要优点是插入和删除操作效率高, 且可以实现动态大小的存储区. 主要缺点是需要额外的指针空间, 且指针需要额外的维护, 增加了存储开销.
- 索引存储: 数据元素以索引表的形式存储在一块连续的存储区中, 索引表包含每个元素的存储位置. 索引表中的每一项称为索引项, 一般形式为(关键字, 地址), 关键字唯一标识一个元素, 索引表按关键字有序排列, 地址作为指向元素的指针. 主要优点是可以实现快速查找, 且可以实现动态大小的存储区. 主要缺点是需要额外的索引表空间, 且索引表需要额外的维护, 增加了存储开销.
- 哈希(散列)存储: 数据元素以哈希表的形式存储在一块连续的存储区中, 哈希表包含每个元素的存储位置. 哈希存储结构只存储元素的数据, 不存储元素之间的逻辑关系, 一般只适用于要求对数据进行快速查找和插入的场合.
数据的运算
运算包括功能描述(或运算功能)和功能实现(或运算实现)
对于同一数据结构其逻辑结构是相同的, 但存储结构和运算实现可能不同.
数据结构和数据类型
数据结构是数据元素的集合, 它描述数据元素之间的关系, 而数据类型是数据元素的性质, 它描述数据元素的性质.
数据类型是数据结构的子集, 它描述数据元素的性质, 如整数、浮点数、字符串、日期等. 数据类型是数据结构的抽象, 它是数据结构的具体实现.
抽象数据类型是从数据模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算. 一个具体问题的抽象数据类型的定义一般包括数据对象, 数据关系和基本运算三个方面的内容. 用三元组$(DSP)$表示, 基本格式如下
ADT抽象数据类型名
{
数据对象
数据关系
基本运算
}ADT抽象数据类型名算法及其描述
算法的定义
数据元素之间的关系有逻辑关系和物理关系, 对应的运算有逻辑结构上的运算和具体存储结构上的运算. 算法是在具体存储结构上实现某个抽象的运算
确切来讲, 算法是指用来解决特定问题的指令集, 它是一系列操作, 用来对数据进行处理, 并产生结果.
算法有五个重要的特性:
- 有穷性: 算法必须在有限的步骤内完成, 否则就无法完成.
- 确定性: 算法必须产生确定的结果, 否则就无法确定.
- 输入性: 算法必须有零个或多个输入, 否则就无法运行.
- 输出性: 算法必须有一个或多个输出, 否则就无法运行.
- 可行性: 算法的每个指令都是可执行的, 即使借助纸和笔也能完成.
算法的描述
算法描述可以用程序流程图, 自然语言或者伪代码表示.
程序流程图是一种图形化的算法描述方法, 它以流程图的形式描述算法的步骤, 并标注输入、输出、中间变量等信息.
自然语言描述算法时, 一般采用英文, 并用动词、名词、形容词等来描述算法的步骤. 但是, 由于自然语言的复杂性, 并不能完全准确地描述算法的步骤.
伪代码是自然语言和编程语言的混合结构, 其比自然语言更加精确.
本系列采用伪代码描述算法, 并用Python实现相应的算法.
同时Python中assert语句可以用来验证算法的正确性, 我们将在后面进行使用.
Python简介
Python是一种高级编程语言, 它具有简洁、高效、可读性强、可移植性强、支持多种编程范式、支持面向对象、支持动态数据类型等特点.
Python的标准数据类型
Python中有六种标准数据类型:
- 数值类型: int、float、complex
- 字符串类型: str
- 列表类型: list
- 元组类型: tuple
- 字典类型: dict
- 布尔类型: bool
由于Python基础系列中已经对这些数据类型进行了详细介绍, 这里不再重复介绍.
如有需要, 请参阅Python基础系列的相关章节.
列表的复制
列表是常用的数据类型, 列表之间的复制是一种常见的操作.
- 非复制方法——直接赋值: 这种方法是将一个列表赋给另一个列表, 实际上是将两个变量指向同一个列表, 因此修改其中一个变量, 另一个变量也会受到影响.
- 列表的深复制——copy模块: copy模块提供了深复制的deepcopy()方法, 它可以将一个列表完全复制到另一个新的列表中, 两个列表之间互不影响.
- 列表的浅复制——copy模块: copy模块提供了浅复制的copy()方法, 对列表的第一层实现了深复制, 但是对列表的嵌套列表实现了浅复制, 因此, 嵌套列表中的元素不会被复制.
#非复制方法
a = [1, 2, 3]
b = a
b[0] = 4
print(a) # [4, 2, 3]
print(b) # [4, 2, 3]
#列表的深复制
import copy
a = [1, 2, 3]
b = copy.deepcopy(a)
b[0] = 4
print(a) # [1, 2, 3]
print(b) # [4, 2, 3]
#列表的浅复制
a = [1, 2, 3]
b = a.copy()
b[0] = 4
print(a) # [4, 2, 3]
print(b) # [4, 2, 3]
aa=[1,2,[3,4]]
bb=aa.copy()
bb[2][0]=5
bb[1][0]=3
print(aa) # [1, 2, [5, 4]]
print(bb) # [1, 3, [5, 4]]输入输出和文件操作
不再重复介绍, 请参阅Python基础系列的相关章节.
Python程序设计
本系列主要采用面向对象的方法进行设计, 不再重复介绍, 请参阅Python面向对象系列的相关章节.
Python中变量的作用域和垃圾回收机制
变量作用域是指变量的有效范围, 它决定了变量的生命周期, 以及变量的可见性.
在Python中, 并不是所有的语句块都会产生作用域, 只有变量在Module(模块), Class(类), def(函数/方法)中才会产生作用域.
Python中变量的作用域是静态的, 即在编译时就确定了变量的作用域, 而非运行时.
Python中变量的作用域有以下四种:
- L(Local, 局部作用域): 包含在def关键字定义的语句块中, 即在函数中定义的变量, 每当函数被调用时都会产生一个新的局部作用域.
- E(Enclosing, 嵌套作用域): 包含在一个函数内部, 但位于该函数外部的变量, 即在函数内部定义的变量, 该变量的值会在函数返回后被销毁. E相对与更上层的函数而言也是L.
- G(Global, 全局作用域): 包含在模块(模块)中定义的变量, 全局变量可以被所有函数共享, 它是所有函数的默认作用域.
- B(Built-in, 内建作用域): 包含在Python解释器中定义的变量, 如None, True, False等.
搜索变量名的优先级是LEGB法则, 即Local -> Enclosing -> Global -> Built-in.
Python中垃圾回收机制是指自动管理内存, 它是Python的重要特点之一.
Python中垃圾回收机制是引用计数法和标记清除法的混合实现, 它通过引用计数法来跟踪对象是否被引用, 并回收没有引用的对象, 而通过标记清除法来回收没有引用的对象.
Python会自动垃圾回收, 因此在使用Python设计算法时不需要关心内存空间的释放问题.
算法分析
算法的设计目标
算法设计应满足以下目标:
- 正确性: 算法必须能够正确地解决问题.
- 可读性: 算法的设计应该易于理解和使用.
- 效率: 算法的运行时间应该尽可能短.
- 健壮性: 算法应能够应对各种输入数据, 并产生正确的输出.
- 适应性: 算法应能够适应变化的需求.
算法的时间性能分析
算法的时间性能分析是指分析算法的运行时间, 它包括算法的运行时间的度量、时间复杂度分析、算法的最坏情况分析、算法的平均情况分析、算法的空间复杂度分析等.
分析算法的时间复杂度
一个算法是由控制结构(顺序,分支和循环)和原操作(固有数据类型的操作等), 算法的执行时间取决于二者的综合效果.
问题规模$n$是指算法输入数据量的大小, 算法频度$T(n)$是问题规模$n$的函数.
算法的执行时间大致等于 $原操作所需的时间\times T(n)$, 可以通过比较不同算法的$T(n)$来分析算法的优劣.
例如求两个$n$阶方阵的相加($\bf{C}=\bf{A}+\bf{B}$)的算法的$T(n)$:
def add_matrix(A, B):
for i in range(n): #语句1
for j in range(n): #语句2
C[i][j] = A[i][j] + B[i][j] #语句3
return C在该算法中语句1的频度为$n+1$, 其循环体的执行次数为$n$; 语句2作为语句1循环体内的语句只执行$n$次, 但是语句2本身也要执行$n+1$次, 因此语句2的频度为$n(n+1)$; 语句3的频度为$n^2$, 它执行了$n^2$次.
则该算法中所有语句的频度之和为$T(n)=n+1+n(n+1)+n^2=n^2+2n+1$.
由于算法的执行时间不是绝对时间的统计, 所以求出$T(n)$后通常进一步采用时间复杂度来表示, 算法的时间复杂度用$T(n)$的数量级来表示, 即$T(n)=O(f(n))$.
其中$O$读作“大O”, 其含义是为$T(n)$找到一个上界, $T(n)$的数量级表示为$O(f(n))$, 是指存在一个常数$c$和$n_0$使得$\lim_{n\to n_0}T(n)\leq cf(n)$, 其中$n\geq n_0$, 其中$n_0$是最小的可能值, 因此时间复杂度也称为渐进时间复杂度.
当然我们只需要求出$T(n)$的最高阶即可, 忽略其低阶项和常数项, 这样既可以简化, 又可以反映当$n$比较大的时候的算法性能.
在一个没有循环的算法中的每个简单语句其执行时间都可以用$O(1)$表示, 称为常数阶.
在一个只有一重循环的算法中算法频度与问题规模$n$成正比, 因此算法的时间复杂度为$O(n)$, 为线性阶.
其余常用的时间复杂度有$O(n^2)$, $O(n^3)$, $O(2^n)$, $O(n!)$等.
不同阶的时间复杂度存在如下关系:
$$
O(1)<O(\log n)<O(\sqrt{n})<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
$$
我们在进行时间复杂度分析时, 仅需考虑基本操作的执行次数即可, 即简化算法时间复杂度分析.
例如分析以下算法的时间复杂度:
def factorial(n):
s=0
for i in range(n+1):
for j in range(i+1):
for k in range(j):
s+=1
return s该算法的基本操作为s+=1, 则计算算法频度如下:
$$
T(n)=\sum_{i=0}^{n}\sum_{j=0}^{i}\sum_{k=0}^{j-1}1=\sum_{i=0}^{n}\sum_{j=0}^{i}(j-1-0+1)\\=\sum_{i=0}^{n}\sum_{j=0}^{i}j=\sum_{i=0}^{n}\frac{i(i+1)}{2}=\frac{1}{2}(\sum_{i=0}^{n}i^2+\sum_{i=0}^{n}i)\\=\frac{2n^3+6n^2+4n}{12}=O(n^3)
$$
算法的最好最坏和平均时间复杂度
设一个算法的输入规模为$n$, $D_n$是所有输入实例的集合, 任一输入$I\in D_n$, $P(I)$是$I$出现的频率, 我们有:
$$
\sum_{I\in D_n}P(I)=1
$$
$T(I)$是算法在输入$I$下的基本操作次数, 则该算法的平均时间复杂度为:
$$
T(n)=\sum_{I\in D_n}P(I)\times T(I)
$$
算法的最好时间复杂度是指算法在最好情况下的执行时间, 即
$$
B(n)=\min_{I\in D_n}T(I)
$$
算法的最坏时间复杂度是指算法在最坏情况下的执行时间, 即
$$
W(n)=\max_{I\in D_n}T(I)
$$
在计算时间复杂度时, 我们通常只考虑最坏情况和平均情况.
渐进符号
常用的渐近符号来计算算法的运行时间复杂度:
- $O$符号
- $\Omega$符号
- $\Theta$符号
符号 $Ο(n)$ 是表示算法运行时间上限的正式方式, 它衡量最坏情况下的时间复杂度或算法可能需要完成的最长时间
$$
Ο(f(n)) = { g(n) : there\ exists\ c > 0\ and\ n_0\ such\ that\ f(n)\ \leq\ c\cdot g(n)\ for\ all\ n > n_0.}
$$
符号 $\Omega(n)$ 是表示算法运行时间下限的正式方式, 它衡量最好情况下的时间复杂度或算法的最短时间
$$
\Omega(f(n)) = { g(n) : there\ exists\ c > 0\ and\ n_0\ such\ that\ f(n)\ \geq\ c\cdot g(n)\ for\ all\ n > n_0.}
$$
符号 $\Theta(n)$ 是表示算法运行时间下限和上限的正式方式.
$$
\Theta(f(n)) = { g(n) : there\ exists\ c_1, c_2 > 0\ and\ n_0\ such\ that\ f(n)\ \leq\ c_1\cdot g(n)\\ \leq\ f(n)\ \leq\ c_2\cdot g(n)\ for\ all n > n_0.}
$$
算法的空间复杂度分析
算法的空间复杂度是指算法运行所需的内存空间, 它反映了算法的存储需求, 即算法运行时所需的内存空间大小.
算法的空间复杂度分析是指分析算法运行时所需的内存空间大小, 它包括算法的存储需求、辅助存储需求、栈空间需求、堆空间需求等.
一般空间复杂度也是问题规模$n$的函数, 即$S(n)=O(g(n))$
常用数据结构
通用数据结构
计算机科学中的各种数据结构大致分为如下所示的两类. 我们将在后续章节中详细讨论以下每种数据结构:
- 线性数据结构
- 数组 − 它是与数据元素的索引配对的数据元素的顺序排列.
- 链表 − 每个数据元素都包含指向另一个元素的链接以及其中存在的数据.
- 堆栈 − 它是一种仅遵循特定操作顺序的数据结构. LIFO(后进先出)或 FILO(先进后出).
- 队列 − 它类似于堆栈, 但操作顺序只是 FIFO(先进先出).
- 矩阵 − 它是二维数据结构, 其中数据元素由一对索引引用.
- 非线性数据结构
- 树 − 它是一种数据结构, 其中数据元素以某种方式组织成树状结构.
- 图 − 它是一种数据结构, 其中数据元素以某种方式组织成图状结构.
- 散列表 − 它是一种数据结构, 其中数据元素以键-值对的形式存储, 并通过哈希函数进行索引.
Python特定的数据结构
Python中有以下特定的数据结构:
- 列表(list)
- 字典(dict)
- 元组(tuple)
