第2章 Python编程基础回顾
2.1 引言
数据结构的实现依赖于编程语言对数据的组织与操作能力。Python作为一门支持多范式的编程语言，其动态类型系统、丰富的内置数据结构及面向对象特性，为数据结构与算法的实现提供了灵活且高效的工具。本章聚焦Python编程中与数据结构密切相关的核心基础，包括基本数据类型的操作逻辑、函数与递归的工程应用、面向对象编程的封装思想，以及内置数据结构的性能特性。通过本章的回顾，将为后续线性结构、树形结构等复杂数据结构的实现与优化奠定基础。
2.2 基本数据类型与操作
Python的数据类型可分为标量类型（存储单个值）和容器类型（存储多个值的集合）。容器类型是实现复杂数据结构的基石，其操作特性直接影响数据结构的设计与效率。
2.2.1 标量类型
标量类型是构成容器的基本单元，包括整数、浮点数、布尔值和字符串，其核心特性如下：
整数（int）：支持任意精度运算，无位数限制（仅受内存约束）。例如，2 ** 1000可直接计算超大整数，无需担心溢出。
浮点数（float）：采用64位双精度存储，存在二进制浮点表示固有的精度误差（如0.1 + 0.2 = 0.30000000000000004）。工程中需通过round()或decimal模块控制精度。
布尔值（bool）：仅包含True（1）和False（0），支持逻辑运算（and/or/not）及算术运算（如True + 2 = 3）。
字符串（str）：不可变字符序列，支持索引（s[i]）、切片（s[i:j]）和迭代，但修改需通过创建新字符串实现（如s = "H" + s[1:]）。
2.2.2 容器类型
容器类型用于组织多个元素，根据元素间关系可分为序列型（有序）和映射型（键值对），以下是数据结构实现中最常用的三种：

1. 列表（List）：动态数组
   定义：有序、可变、元素可重复的序列，底层基于动态数组实现，支持随机访问。
   核心操作与时间复杂度：

动态数组特性：列表初始化时会预分配一定容量（capacity），当元素数量超过容量时，会触发扩容（通常为原容量的1.5~2倍），通过复制元素到新内存空间实现。例如，初始容量为4的列表，添加第5个元素时会扩容至8，此时耗时O(n)，但平均到每次添加操作仍为O(1)。
代码实例：列表作为动态数组的基本操作
python

	# 创建与访问 
	lst = [10, 20, 30] 
	print(lst[1]) # 输出20（索引访问，O(1)） 
	
	# 尾部增删（高效） 
	lst.append(40) # 列表变为[10,20,30,40]，O(1) 
	lst.pop() # 列表变回[10,20,30]，O(1) 
	
	# 中间插入（低效） 
	lst.insert(1, 15) # 列表变为[10,15,20,30]，需移动索引1及之后元素，O(n)

2. 字典（Dict）：哈希表
   定义：无序（Python 3.7+起保留插入顺序）、键唯一的键值对集合，底层基于哈希表实现，支持平均O(1)时间复杂度的查找、插入和删除。
   核心操作与时间复杂度：

哈希表原理：字典通过哈希函数将键映射到哈希表的索引位置（桶），若多个键映射到同一桶（哈希冲突），则通过链表或开放定址法解决。Python采用“开放定址法+链表”的混合策略，确保冲突时仍能高效访问。
键的约束：字典的键必须是可哈希对象（即不可变类型），如整数、字符串、元组等；列表、字典等可变类型不可作为键（因其哈希值会随内容变化）。
代码实例：字典的键值对操作
python

	# 创建与访问 
	d = {"name": "Alice", "age": 20} 
	print(d["name"]) # 输出Alice（O(1)访问） 
	print(d.get("gender")) # 输出None（键不存在，安全访问） 
	
	# 修改与新增 
	d["age"] = 21 # 修改键"age"的值为21，O(1) 
	d["gender"] = "female" # 新增键值对，字典变为{"name":"Alice", "age":21, "gender":"female"} 
	
	# 遍历 
	for k, v in d.items(): 
	print(f"{k}: {v}") # 输出name:Alice, age:21, gender:female（顺序与插入一致）

3. 集合（Set）：基于哈希表的无序集合
   定义：元素唯一、无序的集合，底层基于哈希表实现，支持集合运算（交集、并集等）和平均O(1)时间复杂度的元素操作。
   核心操作：

工程应用：集合常用于元素去重和快速查找（如判断元素是否存在），其查找效率（O(1)）远高于列表（O(n)）。
代码实例：集合的去重与查找
python

	# 去重 
	lst = [1, 2, 2, 3, 3, 3] 
	s = set(lst) # 集合自动去重，s = {1, 2, 3} 
	
	# 快速查找 
	print(2 in s) # 输出True（O(1)查找） 
	print(4 in s) # 输出False

2.2.3 不可变容器：元组与字符串
元组（Tuple）：不可变序列，元素创建后无法修改，支持索引和切片，常用于存储固定值（如坐标、配置参数）。语法：t = (1, 2, 3)，因不可变特性，可作为字典的键。
字符串（String）：不可变字符序列，操作与元组类似，支持切片但不支持修改单个字符（需通过拼接创建新字符串）。
2.3 函数与递归
函数是代码复用的基本单元，递归则是解决分治问题的核心思想。数据结构中的链表遍历、树的操作等高频依赖函数与递归实现。
2.3.1 函数定义与参数传递
函数定义语法：
python

	def 函数名(参数列表): 
	"""文档字符串：描述函数功能、参数及返回值""" 
	函数体 
	return 返回值 # 可选，无return时返回None

参数类型：
位置参数：按参数列表顺序传递，必须传值且数量匹配。
python

	def add(a, b): 
	return a + b 
	add(1, 2) # 正确：a=1, b=2，返回3

关键字参数：传递时指定参数名，顺序可灵活调整，常用于可选参数。

python
add(b=2, a=1) # 正确：等价于add(1, 2)

默认参数：定义时指定默认值，调用时可省略。默认参数必须位于位置参数之后。
11.
python

def power(x, n=2): # n的默认值为2 
return x ** n 
power(3) # 等价于power(3, 2)，返回9 
power(3, 3) # 返回27

可变参数：接收任意数量的位置参数（*args，元组类型）或关键字参数（**kwargs，字典类型）。

python

	def sum_args(*args): # args接收所有位置参数，为元组 
	return sum(args) 
	sum_args(1, 2, 3) # 返回6 
	
	def print_kwargs(**kwargs): # kwargs接收所有关键字参数，为字典 
	for k, v in kwargs.items(): 
	print(f"{k}: {v}") 
	print_kwargs(name="Alice", age=20) # 输出name:Alice, age:20

2.3.2 递归的原理与应用
递归定义：函数直接或间接调用自身的过程，需满足两个核心条件：
终止条件：递归调用的停止点（避免无限递归）；
递归方程：将原问题分解为规模更小的子问题，且子问题与原问题结构一致。
典型递归实例
例2.1 阶乘计算
阶乘定义：n!=n×(n−1)×⋯×1n! = n imes (n-1) imes cdots imes 1n!=n×(n−1)×⋯×1，且0!=10! = 10!=1。
python

	def factorial(n): 
	if n == 0: # 终止条件：0! = 1 
	return 1 
	return n * factorial(n-1) # 递归方程：n! = n × (n-1)! 
	
	print(factorial(5)) # 输出120（5! = 5×4×3×2×1）

例2.2 斐波那契数列
斐波那契数列定义：F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)（n≥2n geq 2n≥2）。
python

	def fib(n): 
	if n <= 1: # 终止条件：F(0)=0, F(1)=1 
	return n 
	return fib(n-1) + fib(n-2) # 递归方程 
	
	print(fib(5)) # 输出5（F(5)=5，序列：0,1,1,2,3,5）

2.3.3 递归的局限性与优化

1. 栈溢出风险
   Python默认递归深度限制约为1000（可通过sys.setrecursionlimit()调整，但受系统栈大小限制）。深度过大会触发RecursionError。
   解决：将递归改写为迭代（循环），通过栈手动模拟递归过程。
   例2.3 阶乘的迭代实现
   python

	def factorial_iter(n): 
	result = 1 
	for i in range(1, n+1): 
	result *= i 
	return result

2. 重复计算
   递归调用中可能重复计算相同子问题，如斐波那契数列的fib(5)需计算fib(4)和fib(3)，而fib(4)又需计算fib(3)，导致子问题fib(3)被重复计算。
   解决：记忆化（Memoization）——存储已计算的子问题结果，避免重复计算。
   例2.4 斐波那契数列的记忆化优化
   python

	def fib_memo(n, memo=None): 
	if memo is None: 
	memo = {0: 0, 1: 1} # 初始化记忆字典，存储已知子问题结果 
	if n not in memo: 
	memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo) # 计算并缓存子问题 
	return memo[n] 
	
	print(fib_memo(5)) # 输出5，子问题fib(3)仅计算1次

2.4 面向对象编程
面向对象编程（OOP）通过“类”封装数据与操作，是实现复杂数据结构（如链表、树、图）的核心范式。数据结构中的“节点”（如链表节点、树节点）本质是对象，其属性（值、指针）和方法（插入、删除）通过类定义。
2.4.1 类与对象
类（Class）：定义对象的属性（数据）和方法（操作）的模板。
对象（Object）：类的实例，具体的实体。
类的定义与实例化
语法：
python

	class 类名: 
	def __init__(self, 参数列表): # 构造方法：初始化对象属性 
	self.属性名 = 参数 # self表示对象自身 
	def 方法名(self, 参数列表): # 实例方法：第一个参数必须为self 

方法体

例2.5 定义链表节点类
链表节点包含“值”（val）和“指针”（next，指向下一节点），通过类封装：
python

	class ListNode: 
	def __init__(self, val=0, next=None): 
	self.val = val # 节点值 
	self.next = next # 指向下一节点的指针（默认为None） 
	
	# 实例化节点并构建链表：1 -> 2 -> 3 
	node3 = ListNode(3) 
	node2 = ListNode(2, node3) # node2的next指向node3 
	node1 = ListNode(1, node2) # node1的next指向node2

2.4.2 继承与多态
继承：子类（派生类）继承父类（基类）的属性和方法，实现代码复用。
多态：子类重写父类方法，使相同方法调用呈现不同行为。
例2.6 继承与方法重写
python

	class Animal: # 父类 
	def __init__(self, name): 
	self.name = name 
	def speak(self): # 父类方法 
	raise NotImplementedError("子类需重写speak方法") 
	
	class Dog(Animal): # 子类，继承Animal 
	def speak(self): # 重写父类方法（多态） 
	return f"{self.name} says 'Woof!'" 
	
	class Cat(Animal): # 子类，继承Animal 
	def speak(self): # 重写父类方法（多态） 
	return f"{self.name} says 'Meow!'" 
	
	# 多态体现：相同方法调用，不同子类对象返回不同结果 
	dog = Dog("Buddy") 
	cat = Cat("Luna") 
	print(dog.speak()) # 输出"Buddy says 'Woof!'" 
	print(cat.speak()) # 输出"Luna says 'Meow!'"

2.4.3 封装与访问控制
封装通过限制属性的直接访问，确保数据安全性。Python通过命名约定实现封装：
公有属性/方法：默认，可被外部访问（如self.val）；
私有属性/方法：以双下划线__开头，仅类内部可访问（通过名称修饰实现，并非严格私有）。
例2.7 私有属性的封装
python

	class BankAccount: 
	def __init__(self, balance): 
	self.__balance = balance # 私有属性：余额，外部不可直接访问 
	
	def deposit(self, amount): # 公有方法：存款 
	if amount > 0: 
	self.__balance += amount 
	
	def get_balance(self): # 公有方法：查询余额（控制访问） 
	return self.__balance 
	
	account = BankAccount(1000) 
	account.deposit(500) 
	print(account.get_balance()) # 输出1500（通过公有方法访问私有属性） 
	print(account.__balance) # 报错：AttributeError（无法直接访问私有属性）

2.5 内置数据结构的性能分析与工程选择
选择数据结构的核心依据是操作的性能需求。本节通过对比列表、字典、集合的关键操作效率，提供工程实践中的选择指南。
2.5.1 关键操作性能对比

2.5.2 性能对比实例：列表vs集合的查找效率
场景：在包含100万个元素的容器中查找指定值，对比列表和集合的耗时。
python

	import time 
	
	n = 10**6 
	lst = list(range(n)) # 列表：[0, 1, 2, ..., 999999] 
	s = set(lst) # 集合：{0, 1, 2, ..., 999999} 
	
	# 列表查找（O(n)） 
	start = time.time() 
	999999 in lst # 查找最后一个元素 
	print(f"列表查找耗时：{time.time() - start:.4f}秒") 
	
	# 集合查找（O(1)） 
	start = time.time() 
	999999 in s 
	print(f"集合查找耗时：{time.time() - start:.4f}秒")

输出（典型环境）：

	列表查找耗时：0.0482秒 
	集合查找耗时：0.0000秒

结论：数据量越大，集合的查找优势越显著。工程中需频繁查找时，应优先使用集合或字典。
2.5.3 工程选择原则
1.优先使用内置数据结构：Python内置数据结构（列表、字典、集合）底层由C实现，性能优于手动实现的简单结构（如链表）。
2.避免“列表滥用”：列表适合顺序存储和索引访问，但不适合频繁查找、去重或头部/中间增删，此类场景应选字典/集合。
3.权衡空间与时间：字典/集合通过哈希表实现，空间开销略高于列表（需存储哈希值和指针），但时间效率更高，属于“空间换时间”的典型权衡。
2.6 本章总结
基本数据类型中，容器类型（列表、字典、集合）是数据结构实现的基础，需掌握其操作特性与时间复杂度；
函数与递归是代码组织的核心，递归需注意终止条件和重复计算问题，可通过记忆化优化；
面向对象编程通过类封装数据与操作，继承和多态提升代码复用性，是实现复杂数据结构（如链表、树）的关键；
性能分析表明：列表适合索引访问，字典/集合适合快速查找，工程选择需基于操作频率和效率需求。
本章内容为后续数据结构的实现提供了Python语法基础，下一章将基于这些知识，深入探讨线性数据结构的设计与实现。
思考题

分析以下代码的输出结果，并解释原因：

python

	def func(a, lst=[]): 
	lst.append(a) 
	return lst 
	print(func(1)) # 输出？ 
	print(func(2)) # 输出？

（提示：默认参数在函数定义时初始化，且只初始化一次）

设计一个函数，判断字符串是否为回文（正读反读相同，如“abcba”），要求时间复杂度O(n)，空间复杂度O(1)。

为什么字典的键必须是可哈希对象？举例说明不可哈希对象作为键会导致什么问题。
用Python实现一个基于字典的缓存工具，支持add(key, value)和get(key)方法，要求get(key)时返回对应值（键不存在时返回None），并统计每个键的访问次数（提示：用嵌套字典存储值和访问次数）。

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