第六章 算法思维与调试能力
6.1 经典算法实现
排序算法
# 冒泡排序（Bubble Sort）- O(n²)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 优化：标记是否发生交换
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
# 快速排序（Quick Sort）- 分治法
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 归并排序（Merge Sort）
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
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
查找算法
# 线性查找 - O(n)
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
# 二分查找（要求有序）- O(log n)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 二分查找递归版本
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
6.2 调试技巧与工具
打印调试法
# 策略性打印
def complex_calculation(x, y):
print(f"[DEBUG] 输入: x={x}, y={y}")
result1 = x * y
print(f"[DEBUG] result1 (x*y) = {result1}")
result2 = result1 + x
print(f"[DEBUG] result2 (result1+x) = {result2}")
if x > y:
print(f"[DEBUG] 进入分支 x>y")
final = result2 / (x - y)
else:
print(f"[DEBUG] 进入分支 x<=y")
final = result2 / (x + y)
print(f"[DEBUG] 最终结果: {final}")
return final
# 使用断言进行调试
def divide(a, b):
assert b != 0, "除数不能为零" # 条件为False时抛出AssertionError
return a / b
使用IDE断点调试
// Java调试示例 - 在IDE中设置断点
public class DebugDemo {
public static int fibonacci(int n) {
// 在此行设置断点，查看n的值
if (n <= 1) {
return n;
}
// 逐步执行，观察递归调用
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
// 设置条件断点：当i == 5时中断
for (int i = 0; i < 10; i++) {
int result = fibonacci(i);
System.out.println("fib(" + i + ") = " + result);
}
}
}
常见错误与解决方案
# 1. 空指针/None访问
obj = None
# if obj.value: # AttributeError!
if obj is not None and hasattr(obj, 'value'):
print(obj.value)
# 2. 索引越界
arr = [1, 2, 3]
# print(arr[3]) # IndexError
if len(arr) > 3:
print(arr[3])
# 3. 可变默认参数（已介绍过）
# 4. 浮点数精度（已介绍过）
# 5. 循环中修改被迭代的集合
colors = ['red', 'blue', 'green', 'yellow']
# 危险：在遍历时删除元素
for color in colors:
if color == 'blue':
colors.remove(color) # 可能导致跳过元素
# 正确做法：遍历副本
for color in colors[:]: # 使用切片副本
if color == 'blue':
colors.remove(color)
# 或使用列表推导式
colors = [c for c in colors if c != 'blue']
# 6. 引用传递的误解
def update_list(lst):
lst = [1, 2, 3] # 重新绑定，不影响外部
my_list = [4, 5, 6]
update_list(my_list)
print(my_list) # [4,5,6] - 没变！
# 正确修改
def update_list_correct(lst):
lst.clear()
lst.extend([1, 2, 3])
第七章 综合实战项目
项目：学生成绩管理系统
"""
学生成绩管理系统
功能：
1. 添加学生信息
2. 删除学生
3. 修改成绩
4. 查询学生
5. 统计信息（平均分、最高分、最低分）
6. 排序显示
"""
class Student:
def __init__(self, student_id, name, scores):
self.student_id = student_id
self.name = name
self.scores = scores # 字典：{"语文": 85, "数学": 92}
def average(self):
"""计算平均分"""
if not self.scores:
return 0
return sum(self.scores.values()) / len(self.scores)
def total(self):
"""计算总分"""
return sum(self.scores.values())
def __str__(self):
return f"{self.student_id}\t{self.name}\t{self.scores}\t平均: {self.average():.2f}"
class StudentManager:
def __init__(self):
self.students = {} # id -> Student对象
def add_student(self, student_id, name, scores):
"""添加学生"""
if student_id in self.students:
print(f"学生ID {student_id} 已存在！")
return False
self.students[student_id] = Student(student_id, name, scores)
print(f"学生 {name} 添加成功！")
return True
def remove_student(self, student_id):
"""删除学生"""
if student_id not in self.students:
print(f"学生ID {student_id} 不存在！")
return False
removed = self.students.pop(student_id)
print(f"学生 {removed.name} 已删除")
return True
def update_score(self, student_id, subject, score):
"""修改成绩"""
if student_id not in self.students:
print(f"学生ID {student_id} 不存在！")
return False
if subject not in self.students[student_id].scores:
print(f"科目 {subject} 不存在！")
return False
self.students[student_id].scores[subject] = score
print(f"更新成功：{self.students[student_id].name} 的 {subject} 成绩为 {score}")
return True
def search_student(self, keyword):
"""搜索学生（支持ID或姓名）"""
results = []
for student in self.students.values():
if keyword == student.student_id or keyword in student.name:
results.append(student)
return results
def get_statistics(self):
"""获取统计信息"""
if not self.students:
return None
averages = [s.average() for s in self.students.values()]
totals = [s.total() for s in self.students.values()]
return {
"student_count": len(self.students),
"avg_average": sum(averages) / len(averages),
"max_average": max(averages),
"min_average": min(averages),
"max_total": max(totals),
"min_total": min(totals)
}
def sort_students(self, key="average", reverse=False):
"""排序学生"""
if key == "average":
return sorted(self.students.values(), key=lambda s: s.average(), reverse=reverse)
elif key == "total":
return sorted(self.students.values(), key=lambda s: s.total(), reverse=reverse)
elif key == "id":
return sorted(self.students.values(), key=lambda s: s.student_id, reverse=reverse)
else:
return list(self.students.values())
def display_all(self):
"""显示所有学生"""
if not self.students:
print("暂无学生数据")
return
print("\n" + "="*60)
print("ID\t姓名\t成绩\t\t\t平均分")
print("-"*60)
for student in self.students.values():
print(student)
print("="*60)
# 主程序
def main():
manager = StudentManager()
# 添加示例数据
manager.add_student("001", "张三", {"语文": 85, "数学": 92, "英语": 78})
manager.add_student("002", "李四", {"语文": 90, "数学": 88, "英语": 95})
manager.add_student("003", "王五", {"语文": 76, "数学": 85, "英语": 82})
while True:
print("\n" + "="*40)
print("学生成绩管理系统")
print("1. 添加学生")
print("2. 删除学生")
print("3. 修改成绩")
print("4. 搜索学生")
print("5. 统计信息")
print("6. 排序显示")
print("7. 显示所有")
print("0. 退出")
print("="*40)
choice = input("请选择操作: ")
if choice == "0":
print("感谢使用！")
break
elif choice == "1":
student_id = input("学号: ")
name = input("姓名: ")
scores = {}
while True:
subject = input("科目（输入空结束）: ")
if not subject:
break
score = float(input(f"{subject}成绩: "))
scores[subject] = score
manager.add_student(student_id, name, scores)
elif choice == "2":
student_id = input("要删除的学号: ")
manager.remove_student(student_id)
elif choice == "3":
student_id = input("学号: ")
subject = input("科目: ")
score = float(input("新成绩: "))
manager.update_score(student_id, subject, score)
elif choice == "4":
keyword = input("输入学号或姓名关键字: ")
results = manager.search_student(keyword)
if results:
print(f"找到 {len(results)} 名学生：")
for s in results:
print(s)
else:
print("未找到")
elif choice == "5":
stats = manager.get_statistics()
if stats:
print("\n统计信息：")
print(f"学生总数: {stats['student_count']}")
print(f"平均分平均: {stats['avg_average']:.2f}")
print(f"最高平均分: {stats['max_average']:.2f}")
print(f"最低平均分: {stats['min_average']:.2f}")
print(f"最高总分: {stats['max_total']}")
print(f"最低总分: {stats['min_total']}")
else:
print("暂无数据")
elif choice == "6":
key = input("排序依据（average/total/id）: ")
reverse = input("降序？(y/n): ").lower() == 'y'
sorted_students = manager.sort_students(key, reverse)
for s in sorted_students:
print(s)
elif choice == "7":
manager.display_all()
else:
print("无效选择，请重试")
if __name__ == "__main__":
main()
