第1章 数据结构与算法概述
1.1 引言
计算机科学的核心是“解决问题”，而解决问题的本质是“数据的组织”与“步骤的设计”。数据结构（Data Structure）研究如何在计算机中高效地组织和存储数据，算法（Algorithm）则研究如何设计解决问题的清晰步骤。两者共同构成了计算机科学的基石——无论是操作系统、数据库，还是人工智能、分布式系统，其底层逻辑都依赖于对数据结构的选择和算法的优化。
Python作为一门简洁、高效且功能丰富的编程语言，为数据结构与算法的学习和实现提供了理想的工具。其语法贴近自然语言，内置了列表、字典等高级数据结构，同时支持面向对象编程，既能帮助初学者快速理解概念，也能满足工程实践中对灵活性和可读性的需求。本章将从基本概念出发，建立数据结构与算法的理论框架，并阐述Python在这一领域的独特优势。
1.2 数据结构的定义与分类
1.2.1 数据结构的定义
定义1.1 数据结构：是计算机中组织和存储数据的特定方式，它包含数据元素之间的逻辑关系（数据的组织形式）、数据的存储方式（数据在计算机中的物理表示），以及对数据的基本操作（如插入、删除、查找等）。
简言之，数据结构的核心是“关系”与“操作”。例如，通讯录中“联系人按姓名首字母排序”是逻辑关系，“存储在手机内存的数组中”是存储方式，“添加联系人”“搜索联系人”是基本操作。
1.2.2 数据结构的分类
根据数据元素之间关系的不同，数据结构可分为线性结构和非线性结构两大类。

1. 线性结构
   数据元素之间存在一对一的“线性”关系，除首尾元素外，每个元素有唯一的前驱和后继。
   数组（Array）：元素按顺序存储在连续内存空间，支持随机访问（通过索引直接定位）。
   例：Python列表（List）本质是动态数组，可通过list[i]快速访问第i个元素。
   链表（Linked List）：元素（节点）通过指针/引用连接，内存空间不连续，插入/删除无需移动元素。
   栈（Stack）：遵循“后进先出”（LIFO）原则，仅允许在一端（栈顶）操作。
   队列（Queue）：遵循“先进先出”（FIFO）原则，允许在一端（队尾）插入、另一端（队头）删除。
2. 非线性结构
   数据元素之间存在一对多或多对多的“非线性”关系，结构更复杂，适用于表达层级、网络等关系。
   树（Tree）：元素间呈层次关系，有唯一根节点，每个节点有零个或多个子节点（如二叉树、B+树）。
   例：文件系统的目录结构、数据库索引。
   图（Graph）：由顶点和边组成，顶点间通过边连接，可表示任意复杂关系（如社交网络、地图路径）。
   集合（Set）：元素无序且唯一，支持交集、并集等操作（Python内置set基于哈希表实现）。
   哈希表（Hash Table）：通过哈希函数将键映射到值，支持O(1)平均时间复杂度的插入和查找（Python字典dict是典型实现）。
   1.3 算法的基本概念
   1.3.1 算法的定义与特性
   定义1.2 算法：是解决特定问题的有限步骤集合，它接收输入（可能为空），经过一系列明确、可行的操作，在有限时间内输出结果。
   算法需满足以下基本特性：
   有穷性：步骤有限，不会无限循环；
   确定性：每个步骤有唯一含义，无歧义；
   可行性：步骤可通过基本操作实现；
   输入/输出：有零个或多个输入，至少一个输出。
   1.3.2 算法效率的度量：复杂度分析
   评价算法优劣的核心是效率——即时间消耗（时间复杂度）和空间消耗（空间复杂度）。由于硬件环境（如CPU速度、内存大小）影响实际运行时间，我们需通过渐近复杂度（大O符号）描述效率与输入规模的关系，忽略常数因子和低阶项。
3. 时间复杂度（Time Complexity）
   定义1.3 时间复杂度：表示算法执行时间随输入规模n增长的趋势，记为T(n) = O(f(n))，其中f(n)是n的函数。
   分析方法：统计算法中“基本操作”的执行次数（如赋值、比较、算术运算），取最高阶项并忽略系数。
   常见时间复杂度（按效率从高到低排序）：
   O(1)：常数时间，操作次数与n无关。
   例：通过索引访问数组元素（list[i]）、哈希表查找。
   O(log n)：对数时间，操作次数随n增长但增速缓慢（如二分查找）。
   例：在有序数组中查找目标，每次排除一半元素。
   O(n)：线性时间，操作次数与n成正比（如遍历数组）。
   python

	def sum_array(arr): 
	total = 0 
	for num in arr: # 循环n次，n为数组长度 
	total += num 
	return total

O(n log n)：线性对数时间，常见于高效排序算法（如归并排序、快速排序）。
O(n²)：平方时间，常见于嵌套循环（如冒泡排序、矩阵乘法）。
python

	def print_pairs(arr): 
	for i in range(len(arr)): # 外层循环n次 
	for j in range(len(arr)): # 内层循环n次 
	print(arr[i], arr[j]) # 总操作次数n²

O(2ⁿ)：指数时间，效率极低，常见于递归未优化的问题（如未剪枝的斐波那契递归）。
2. 空间复杂度（Space Complexity）
定义1.4 空间复杂度：表示算法额外空间消耗随输入规模n增长的趋势，记为S(n) = O(g(n))。
注意：空间复杂度通常不包含输入数据本身的空间，仅统计算法运行时的额外空间（如临时变量、数据结构）。
常见空间复杂度：
O(1)：常数空间，额外空间与n无关（如变量交换）。
python

	def swap(a, b): 
	temp = a # 仅用1个临时变量 
	a = b 
	b = temp

O(n)：线性空间，额外空间与n成正比（如复制数组）。
python

	def copy_array(arr): 
	new_arr = [0] * len(arr) # 新数组大小为n 
	for i in range(len(arr)): 
	new_arr[i] = arr[i] 
	return new_arr

O(log n)：对数空间，常见于递归（递归栈深度为log n，如二分查找递归实现）。
1.3.3 复杂度分析实例
例1.1 分析以下Python函数的时间复杂度：
python

	def find_max(arr): 
	max_val = arr[0] # 1次操作 
	for num in arr: # 循环n次 
	if num > max_val: # n次比较 
	max_val = num # 最多n次赋值 
	return max_val

分析：循环内基本操作次数为O(n)，总时间复杂度T(n) = O(n)。
例1.2 分析以下函数的空间复杂度：
python

	def fibonacci(n): 
	if n <= 1: 
	return n 
	dp = [0] * (n + 1) # 数组大小为n+1 
	dp[0], dp[1] = 0, 1 
	for i in range(2, n + 1): 
	dp[i] = dp[i-1] + dp[i-2] 
	return dp[n]

分析：额外空间为数组dp（大小n+1），空间复杂度S(n) = O(n)（可优化为O(1)，仅存储前两个值）。
1.4 数据结构与算法的关系
数据结构与算法是“形”与“神”的关系：数据结构是算法的载体，算法是数据结构的灵魂。
1.4.1 数据结构决定算法的可行性
不同数据结构支持的操作不同，直接影响算法能否实现。例如：
实现“最近使用的元素优先保留”（LRU缓存），需用哈希表+双向链表（哈希表支持O(1)查找，双向链表支持O(1)插入/删除）；
实现“高效范围查询”（如数据库的BETWEEN查询），需用B+树（叶子节点有序链表，支持快速范围扫描）。
1.4.2 算法优化依赖数据结构选择
同一问题，选择不同数据结构会导致算法效率差异。例如“查找元素是否存在”：
用数组存储，需遍历比较，时间复杂度O(n)；
用哈希表存储，平均时间复杂度O(1)。
1.4.3 典型案例：排序算法与数据结构
冒泡排序：基于数组，通过相邻元素交换实现，时间复杂度O(n²)；
归并排序：基于数组分治，需额外空间存储子数组，时间复杂度O(n log n)；
堆排序：基于堆（完全二叉树的数组实现），时间复杂度O(n log n)，空间复杂度O(1)。
1.5 为什么选择Python实现数据结构
Python虽非性能最优的语言（解释型、动态类型导致执行速度慢于C++/Java），但在数据结构学习和中等规模应用中优势显著：
1.5.1 语法简洁，聚焦逻辑而非实现细节
Python代码接近自然语言，无需关注内存管理（如C++的指针、Java的垃圾回收），可快速实现数据结构核心逻辑。例如，实现一个简单链表：
python

	class ListNode: 
	def __init__(self, val=0, next=None): 
	self.val = val 
	self.next = next 
	
	# 创建链表：1 -> 2 -> 3 
	head = ListNode(1, ListNode(2, ListNode(3)))

相比C++的指针操作，Python代码更易读，适合初学者理解“节点”和“引用”的概念。
1.5.2 内置数据结构丰富，开箱即用
Python提供列表（动态数组）、字典（哈希表）、集合（哈希集合）等高效内置结构，可直接作为实现复杂数据结构的基础组件。例如：
用列表实现栈：stack = []; stack.append(1); stack.pop()（时间复杂度O(1)）；
用字典实现图的邻接表：graph = {1: [2,3], 2: [4]}（快速访问邻居节点）。
1.5.3 动态类型与面向对象支持
Python的动态类型允许灵活处理不同数据，面向对象特性支持封装数据结构（如定义TreeNode类实现二叉树）。例如，实现二叉搜索树的插入方法：
python

	class TreeNode: 
	def __init__(self, val=0): 
	self.val = val 
	self.left = None 
	self.right = None 
	
	class BST: 
	def insert(self, root, val): 
	if not root: 
	return TreeNode(val) 
	if val < root.val: 
	root.left = self.insert(root.left, val) 
	else: 
	root.right = self.insert(root.right, val) 
	return root

1.5.4 生态丰富，便于扩展与验证
Python拥有collections（提供deque、OrderedDict等高级结构）、heapq（堆操作）、bisect（二分查找）等标准库，可直接验证自定义数据结构的正确性。例如，用heapq验证手写堆的实现：
python

	import heapq 
	
	# 内置堆（小顶堆） 
	heap = [] 
	heapq.heappush(heap, 3) 
	heapq.heappush(heap, 1) 
	print(heapq.heappop(heap)) # 输出1（与自定义堆对比结果）

1.5.5 局限性与应对
Python的主要局限是性能：对于超大规模数据（如n>10⁸），解释执行效率不足。此时可通过以下方式优化：
优先使用内置函数（如sum()、sorted()，底层用C实现）；
关键模块用Cython或C扩展（如numpy的数组操作）；
算法层面优化（如用哈希表替代线性扫描）。
1.6 本章总结
数据结构是组织数据的方式，分为线性结构（数组、链表等）和非线性结构（树、图等），核心是“关系”与“操作”；
算法是解决问题的步骤集合，效率通过时间复杂度（O(f(n))）和空间复杂度（O(g(n))）度量，关注随输入规模增长的趋势；
数据结构与算法相辅相成：数据结构为算法提供载体，算法通过数据结构实现高效操作；
Python优势在于语法简洁、内置结构丰富、生态完善，适合学习和中等规模应用，性能问题可通过优化缓解。
后续章节将从线性结构开始，逐步深入各类数据结构的Python实现、核心算法及工程实践，注重“定义→实现→应用→优化”的闭环学习。
思考题

分析以下代码的时间复杂度：

python

	def func(n): 
	res = 0 
	for i in range(n): 
	for j in range(i, n): 
	res += 1 
	return res

设计一个数据结构，支持在O(1)时间内实现“插入”“删除”和“获取随机元素”操作（提示：结合哈希表与数组）。

为什么说“数组查找的时间复杂度是O(1)，而链表是O(n)”？这一结论在什么情况下可能不成立？

用Python实现一个简单的栈，要求支持push、pop和get_min（获取最小值）操作，且每个操作的时间复杂度为O(1)。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49283.html