第 2 章 数据结构与算法基础
2.1 数据结构基础
2.1.1 什么是数据结构
数据结构是为了高效访问数据而设计出的一种数据的组织和存储方式。更具体的说，一个数据结构包含一个数据元素的集合、数据元素之间的关系以及访问和操作数据的方法。
像前面我们接触到的list、set、dict、tuple其实已经是一种python封装的高级数据结构了，里面封装了对基本数据类型数据的存储以及组织方式。
2.1.2 数据结构的分类
1）逻辑结构
数据的逻辑结构反映了数据元素之间的逻辑关系。逻辑结构可分为线性和非线性两大类。
线性数据结构中的元素之间是一对一的顺序关系，在一对一的顺序关系中，除了第一个元素没有前驱元素，最后一个元素没有后继元素外，其余每个元素都有且仅有一个直接前驱元素和一个直接后继元素。这种关系使得数据元素可以按照一个线性的顺序依次排列，就像排成一列的队伍，每个成员前后都有明确的相邻成员（队首和队尾除外）如数组、链表、栈、队列等。
非线性数据结构中的元素之间具有多个对应关系，如树、图等。
2）物理结构
数据的物理结构反映了数据在计算机内存中的存储结构。一般而言，数据结构针对的是内存中的数据。内存由许多存储单元组成，每个存储单元可以存储一个固定大小的数据块，通常以字节（Byte）为单位。每个存储单元都有一个唯一的地址，操作系统正是根据这一地址去访问内存中的数据的。我们讨论的数据结构中的数据元素就保存在这一个个的内存单元中。数据在内存中的存储结构可分为连续存储（数组）与分散存储（链表）。
连续存储借助数据之间的相对位置来表示数据元素之间的逻辑关系。
分散存储借助指示数据位置的指针来表示数据元素之间的逻辑关系。
所有数据结构都是基于数组、链表或二者的组合实现的。例如，栈和队列既可以使用数组实现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。
2.2 算法基础
2.2.1 什么是算法
算法是一个用于解决特定问题的有限指令序列（计算机可以执行的操作）。通俗的理解就是可以解决特定问题的方法。
算法的五大特性：
输入：算法具有0个或多个输入。
输出：算法至少有1个输出。
有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成。
确定性：算法中的每一步都有确定的含义，不会出现二义性。
可行性：算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案。
2.2.2 算法的分类
按照应用目的分类：搜索算法（深度优先搜索、广度优先搜索等）、排序算法（冒泡排序、插入排序、选择排序、快速排序、归并排序等）、最优化算法等。
按照实现策略分类：暴力法、增量法、分治算法、动态规划算法、贪心算法等。
2.2.3 时间复杂度
1）时间复杂度定义
时间复杂度用来描述运行一个算法所需时间资源的多少。为了屏蔽计算机硬件差异对评估结果的影响，我们不使用算法运行的绝对运行时间，而是使用运行算法时执行的基本指令数量来衡量其所需的时间资源。
常见的计算机基本指令有：
赋值指令：用于为变量赋值。
算术运算指令：包括加法、减法、乘法和除法等基本的数值运算。
逻辑运算指令：包括与、或、非等逻辑操作。
比较指令：用于比较两个值的大小或相等性。
我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的。那么一个算法的所需时间 T 就可以表达为一个与输入规模 n 相关的函数：T(n)。
例如下面这个求和的算法，其所需时间 T(n) = 5n+5。其中 n 表示算法的输入规模，这里代表数组长度。
def sum(nums):
sum_num = 0 # 1次赋值操作
i = -1 # 1次赋值操作
while (i := i + 1) < len(nums): # n+1次加法运算 + n+1次赋值操作 + n+1次比较运算
sum_num += nums[i] # n次加法运算 + n次赋值操作
return sum_num
而下面这个寻找最大值的算法，其所需时间由于条件判断而变得不确定，若输入数组中的最大值位于首位，那么 T(n) = 4n+1；如果最大值位于末位，那么 T(n) = 5n。
def find_max(nums):
max_num = nums[0] # 1次赋值操作
i = 0 # 1次赋值操作
while (i := i + 1) < len(nums): # n次加法运算 + n次赋值操作 + n次比较运算
if nums[i] > max_num: # n-1次比较运算
max_num = nums[i] # 0~(n-1)次赋值操作
return max_num
我们注意到上述算法的运行时间还取决于具体数据，而不仅仅是问题规模。对于这种算法，我们把它们的执行情况分为：
最优时间复杂度，即算法完成工作最少需要多少基本操作。
最坏时间复杂度，即算法完成工作最多需要多少基本操作。
平均时间复杂度，即算法完成工作平均需要多少基本操作。
对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值；对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作；对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。此外，“平均”还依赖于所选的实例，以及这些实例出现的概率。因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。因此，上述寻找最大值的算法所需时间为 T(n) = 5n。
一般情况下，我们并不关心输入规模较小时算法的用时多少，并且其实上述的T(n)函数也并不是绝对的精确。所以我们通常只关注输入规模无限增大时，算法用时的增长趋势。也就是比较 T(n) 函数在 n 趋近于无穷大时的增长速度。
到目前为止，我们就已经能够对时间复杂度下一个准确的定义了：
时间复杂度统计的是算法运行时执行的基本指令数，而非绝对运行时间。
时间复杂度体现的是算法基本指令数随输入规模 n 增大时的变化趋势。
2）时间复杂度的大O表示法
由于时间复杂度只需要关注输入规模增大时，算法用时的增长趋势。而输入规模无限增大时，T(n) 函数中的低阶项和常数项，以及高阶项的常数系数，对于增长趋势的影响就会变得微乎其微，因此我们可以将其忽略掉，然后用最高阶项来表示 T(n) 函数的增长趋势。
例如我们现在有两个算法，分别是算法A：T(n) = 5n+5，算法B：T(n) = 2n2+2n-2，按照上述思路，算法A的时间复杂度可以表示为O(n)，算法B的时间复杂度可以表示为O(n2)。
3）常见的时间复杂度
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!) < O(nn)
注意：表示时间复杂度时经常将log2n简写为logn。
下面给出几个常见的时间复杂度案例：
（1）O(1)
两数求和：
def add(a, b):
return a + b
如果算法的执行时间不随着问题规模 n 的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是 O(1)。
（2）O(logn)
二分查找：
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
对数阶反映了“每轮缩减到一半”的情况。
（3）O(n)
求数组中所有元素的和：
def sum(nums):
sum_num = 0
for num in nums:
sum_num += num
return sum_num
（4）O(nlogn)
归并排序：
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
（5）O(n2)
冒泡排序：
def bubble_sort(nums):
for i in range(len(nums) - 1):
for j in range(len(nums) - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
（6）O(2n)
枚举全部子集：
def subsets(nums):
“”“使用位运算来生成所有子集”“”
n = len(nums)
result = []
for i in range(1 << n):
subset = []
for j in range(n):
if i & (1 << j):
subset.append(nums[j])
result.append(subset)
return result
（7）O(n!)
全排列：
def permute(nums):
result = []
if len(nums) == 1:
return [nums]
for i in range(len(nums)):
remaining = nums[:i] + nums[i + 1 :]
for perm in permute(remaining):
result.append([nums[i]] + perm)
return result
2.2.4 空间复杂度
1）空间复杂度定义
空间复杂度用来描述一个算法运行所需内存空间的多少。同时间复杂度类似，空间复杂度并不代表算法运行时所使用的绝对内存空间，它描述的是算法使用的内存空间随输入规模变大时的变化趋势。
程序运行时占用内存空间的主要有以下内容：
指令：程序编译后的二进制指令。
数据：程序声明的变量、常量、对象等内容。
我们在计算空间复杂度时，一般只需关注数据所占用的内存空间即可。
2）常见的空间复杂度
（1）O(1)
常数阶常见于数量与输入数据大小无关的常量、变量、对象。
需要注意的是，在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为O(1)。
原地反转数组：
def reverse_array(arr):
left, right = -1, len(arr)
while (left := left + 1) < (right := right - 1):
arr[left], arr[right] = arr[right], arr[left]
（2）O(n)
判断数组中是否有重复元素：
def has_duplicates(arr):
seen = set()
for num in arr:
if num in seen:
return True
seen.add(num)
return False
（3）O(n2)
矩阵转置：
def transpose(matrix):
n = len(matrix)
result = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
result[j][i] = matrix[i][j]
return result
第 3 章 常用数据结构
抽象数据类型（Abstract Data Type，简称 ADT）是计算机科学中一个重要的概念，它是对数据的一种抽象描述，关注数据的逻辑特性和操作，而不涉及具体的实现细节。
抽象数据类型通常由以下两部分组成：
数据对象：描述了该数据类型所包含的数据元素以及它们之间的逻辑关系。例如，在一个栈的抽象数据类型中，数据对象是一系列按后进先出（LIFO）原则组织的元素。
操作集合：定义了对数据对象可以执行的操作。对于栈来说，常见的操作包括入栈（push）、出栈（pop）、查看栈顶元素（peek）等。
抽象数据类型与数据结构的关系
抽象数据类型：强调的是数据的逻辑特性和操作的功能，是一种抽象的概念，不涉及具体的实现细节。它是从用户的角度来描述数据和操作的。
数据结构：是抽象数据类型的具体实现，它关注的是数据在计算机内存中的存储方式和操作的具体实现算法。例如，栈这种抽象数据类型可以用数组或链表等数据结构来实现。
3.1 数组
3.1.1 数组的概述
数组是一种线性数据结构，将相同类型的元素顺序地存储在连续的内存空间中，每个元素都有一个索引。
由于数组元素在内存中是连续存储的，所以只要知道数组的起始位置，以及数组元素的类型（单个元素的长度），就可以根据索引计算出任意元素的位置。
数组在创建时需要指定长度，并且数组一旦创建，长度就无法改变，如果需要扩容，只能创建一个更大的数组，再将原数据拷贝到新数组。并且由于数组的连续性，插入和删除数据可能需要移动其他元素。
在 Python 中，并没有像其他一些编程语言（如 C、Java）那样严格意义上的 “数组” 概念，但有多种数据结构可以用来模拟数组的功能，最常用的是列表（list），另外还有 array 模块的数组和 numpy 库的 ndarray。
通过Python 的list列表实现一个动态数组，它内部存储的实际上是对象的引用（指针），而不是对象本身。每个引用指向内存中存储实际对象的位置。
3.1.2 数组的功能定义
方法 说明
size() 返回数组中元素个数
is_empty() 判断数组是否为空
insert(index, item) 在指定位置插入元素
append(item) 在末尾插入元素
remove(index) 删除指定位置的元素
set(index, item) 修改指定位置的元素
get(index) 获取指定位置的元素
find(item) 查找数组中某个元素的位置
for_each(func) 遍历数组
3.1.3 数组的创建
实现一个动态数组。
class Array:
def init(self):
“”“初始化数组”“”
self.__capacity = 8
self.__size = 0
self.__items = [0] * 8
def __str__(self):
"""打印数组"""
arr_str = "["
for i in range(self.__size):
arr_str += str(self.__items[i])
if i < self.__size - 1:
arr_str += ", "
arr_str += "]"
return arr_str
@property
def size(self):
"""获取数组元素个数"""
return self.__size
def is_empty(self):
"""判断数组是否为空"""
return self.__size == 0
3.1.4 数组扩容
当数组容量占满后，我们可以创建一个新的数组，容量为之前数组的2倍，并将之前数组的元素拷贝到新数组中。
def __grow(self):
“”“数组扩容”“”
self.new___items = [0] * self.__capacity * 2
for i in range(self.__size):
self.new___items[i] = self.__items[i]
self.__items = self.new___items
self.__capacity *= 2
3.1.5 插入元素
在中间插入元素时，将指定位置及其之后的元素全部向后移动一个位置，并将指定位置改为新的元素。
def insert(self, index, item):
"""插入元素"""
if index < 0 or index > self.__size:
raise IndexError
if self.__size == self.__capacity:
self.__grow()
for i in range(self.__size, index, -1):
self.__items[i] = self.__items[i - 1]
self.__items[index] = item
self.__size += 1
在末尾插入元素时，使用insert()并将index设置为数组长度。
def append(self, item):
“”“末尾插入元素”“”
self.insert(self.__size, item)
3.1.6 删除元素
删除数组中指定位置的元素时，将该位置之后的所有元素向前移动一个位置。
def remove(self, index):
"""删除元素"""
if index < 0 or index >= self.__size:
raise IndexError
for i in range(index, self.__size - 1):
self.__items[i] = self.__items[i + 1]
self.__size -= 1
3.1.7 修改元素
def set(self, index, item):
“”“修改元素”“”
if index < 0 or index >= self.__size:
raise IndexError
self.__items[index] = item
3.1.8 访问元素
def get(self, index):
“”“访问元素”“”
if index < 0 or index >= self.__size:
raise IndexError
return self.__items[index]
3.1.9 查找元素
def find(self, item):
“”“查找元素”“”
for i in range(self.__size):
if self.__items[i] == item:
return i
return -1
3.1.10 遍历数组
def for_each(self, func):
“”“遍历数组”“”
for i in range(self.__size):
func(self.__items[i])
3.1.11 完整代码
class Array:
def init(self):
“”“初始化数组”“”
self.__capacity = 8
self.__size = 0
self.__items = [0] * 8
def __str__(self):
"""打印数组"""
arr_str = "["
for i in range(self.__size):
arr_str += str(self.__items[i])
if i < self.__size - 1:
arr_str += ", "
arr_str += "]"
return arr_str
@property
def size(self):
"""获取数组元素个数"""
return self.__size
def is_empty(self):
"""判断数组是否为空"""
return self.__size == 0
def __grow(self):
"""数组扩容"""
self.new___items = [0] * self.__capacity * 2
for i in range(self.__size):
self.new___items[i] = self.__items[i]
self.__items = self.new___items
self.__capacity *= 2
def insert(self, index, item):
"""插入元素"""
if index < 0 or index > self.__size:
raise IndexError
if self.__size == self.__capacity:
self.__grow()
for i in range(self.__size, index, -1):
self.__items[i] = self.__items[i - 1]
self.__items[index] = item
self.__size += 1
def append(self, item):
"""末尾插入元素"""
self.insert(self.__size, item)
def remove(self, index):
"""删除元素"""
if index < 0 or index >= self.__size:
raise IndexError
for i in range(index, self.__size - 1):
self.__items[i] = self.__items[i + 1]
self.__size -= 1
def set(self, index, item):
"""修改元素"""
if index < 0 or index >= self.__size:
raise IndexError
self.__items[index] = item
def get(self, index):
"""访问元素"""
if index < 0 or index >= self.__size:
raise IndexError
return self.__items[index]
def find(self, item):
"""查找元素"""
for i in range(self.__size):
if self.__items[i] == item:
return i
return -1
def for_each(self, func):
"""遍历数组"""
for i in range(self.__size):
func(self.__items[i])
3.2 链表
3.2.1 链表的概述
链表（Linked List）是一个线性结构，由一系列节点（Node）组成，每个节点包含一个数据元素和一个指向下一节点的指针（Pointer）。所有节点通过指针相连，形成一个链式结构。通常我们将链表中的第一个节点称为头结点，并将头结点的位置作为整个链表的位置标识。与数组不同，链表中每个节点分散的存储在内存中，每个节点都保存了当前节点的数据和下一节点的地址（指针）。
由于链表中节点通过指针相连，插入和删除节点只需要修改指针的指向即可，而不需要像数组那样移动数据。且链表不需要像数组那样预先指定大小，而是可以随时动态的增长或缩小。由于链表使用分散存储的方式，因而无需使用大段连续的内存空间。
由于链表中的节点不是连续存储的，无法像数组一样根据索引直接计算出每个节点的地址。必须从头节点开始遍历链表，直到找到目标节点，这导致了链表的随机访问效率较低。链表的每个节点都需要存储指向下一个节点的指针，这会占用额外的存储空间。相比于数组，链表需要更多的内存空间来存储相同数量的数据元素。
常见的链表包括三种：
单向链表：单向链表的节点包含值和指向下一节点的引用。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
环形链表：将单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
双向链表：双向链表记录了两个方向的引用，同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用。
3.2.2 链表的功能定义
方法 说明
size() 返回链表中元素个数
is_empty() 判断链表是否为空
insert(index, item) 在指定位置插入元素
append(item) 在末尾插入元素
remove(index) 删除指定位置的元素
set(index, item) 修改指定位置的元素
get(index) 获取指定位置的元素
find(item) 查找链表中某个元素的位置
for_each(func) 遍历链表
3.2.3 链表的创建
实现一个单向链表。
class Node:
def init(self, data, next=None):
self.data = data
self.next = next
class LinkedList:
def init(self):
“”“初始化链表”“”
self.__head = None
self.__size = 0
def __str__(self):
"""打印链表"""
result = []
current = self.__head
while current:
result.append(str(current.data))
current = current.next
return " -> ".join(result)
@property
def size(self):
"""获取链表元素个数"""
return self.__size
def is_empty(self):
"""判断链表是否为空"""
return self.__size == 0
3.2.4 插入元素
def insert(self, index, item):
"""插入元素"""
if index < 0 or index > self.__size:
raise IndexError
if index == 0:
# 插入到头部，需要新建一个节点，然后让新节点的next指向原来的head，然后让head指向新节点
self.__head = Node(item, self.__head)
else:
# 插入到中间，先找到index-1位置的节点
node = self.__head
for i in range(index - 1):
node = node.next
# 新节点的next指向index位置的节点，然后让index-1位置的节点的next指向新节点
node.next = Node(item, node.next)
self.__size += 1
在末尾插入元素时，使用insert()并将index设置为链表长度。
def append(self, item):
“”“末尾插入元素”“”
self.insert(self.__size, item)
3.2.5 删除元素
def remove(self, index):
"""删除元素"""
if index < 0 or index >= self.__size:
raise IndexError
if index == 0:
self.__head = self.__head.next
else:
# 找到index-1位置的节点，然后让index-1位置的节点的next指向index位置的节点的next
node = self.__head
for i in range(index - 1):
node = node.next
node.next = node.next.next
self.__size -= 1
3.2.6 修改元素
def set(self, index, item):
“”“修改元素”“”
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
node = node.next
node.data = item
3.2.7 访问元素
def get(self, index):
“”“访问元素”“”
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
node = node.next
return node.data
3.2.8 查找元素
def find(self, item):
“”“查找元素”“”
node = self.__head
while node:
if node.data == item:
return True
node = node.next
return False
3.2.9 遍历链表
def for_each(self, func):
“”“遍历链表”“”
node = self.__head
while node:
func(node)
node = node.next
3.2.10 完整代码
class Node:
def init(self, data, next=None):
self.data = data
self.next = next
class LinkedList:
def init(self):
“”“初始化链表”“”
self.__head = None
self.__size = 0
def __str__(self):
"""打印链表"""
result = []
current = self.__head
while current:
result.append(str(current.data))
current = current.next
return " -> ".join(result)
@property
def size(self):
"""获取链表元素个数"""
return self.__size
def is_empty(self):
"""判断链表是否为空"""
return self.__size == 0
def insert(self, index, item):
"""插入元素"""
if index < 0 or index > self.__size:
raise IndexError
if index == 0:
# 插入到头部，需要新建一个节点，然后让新节点的next指向原来的head，然后让head指向新节点
self.__head = Node(item, self.__head)
else:
# 插入到中间，先找到index-1位置的节点
node = self.__head
for i in range(index - 1):
node = node.next
# 新节点的next指向index位置的节点，然后让index-1位置的节点的next指向新节点
node.next = Node(item, node.next)
self.__size += 1
def append(self, item):
"""末尾插入元素"""
self.insert(self.__size, item)
def remove(self, index):
"""删除元素"""
if index < 0 or index >= self.__size:
raise IndexError
if index == 0:
self.__head = self.__head.next
else:
# 找到index-1位置的节点，然后让index-1位置的节点的next指向index位置的节点的next
node = self.__head
for i in range(index - 1):
node = node.next
node.next = node.next.next
self.__size -= 1
def set(self, index, item):
"""修改元素"""
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
node = node.next
node.data = item
def get(self, index):
"""访问元素"""
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
node = node.next
return node.data
def find(self, item):
"""查找元素"""
node = self.__head
while node:
if node.data == item:
return True
node = node.next
return False
def for_each(self, func):
"""遍历链表"""
node = self.__head
while node:
func(node)
node = node.next