一、课程概述
《北京大学 数据结构与算法 Python 版》是一门旨在系统教授数据结构与算法知识，并使用 Python 语言实现的高级课程。该课程涵盖了多种重要的数据结构和经典算法，结合 Python 简洁强大的特性，帮助学员理解数据组织、存储和操作的原理，以及如何运用算法解决实际问题，为计算机科学相关专业的学习和实际开发工作打下坚实的基础。
二、课程目标
知识掌握目标：
使学员深入理解各种基本数据结构的概念、特点和操作，包括数组、链表、栈、队列、树（二叉树、二叉搜索树、平衡二叉树等）、图等。
让学员掌握常用算法的原理和实现，如排序算法（冒泡排序、插入排序、快速排序、归并排序等）、查找算法（顺序查找、二分查找等）、递归算法、动态规划算法、贪心算法等。
技能提升目标：
培养学员使用 Python 语言实现数据结构和算法的编程能力，能够将理论知识转化为可运行的代码。
提升学员对算法性能分析的能力，包括时间复杂度和空间复杂度的计算，使学员能根据实际问题选择合适的数据结构和算法。
问题解决目标：
引导学员运用所学的数据结构和算法解决实际问题，提高学员的逻辑思维和问题解决能力。
培养学员将算法思想应用于大规模数据处理、优化程序性能、解决计算机系统设计和软件工程问题的能力。
三、课程内容
数据结构基础：
数组和列表：
讲解数组和 Python 中的列表的基本概念、存储方式和基本操作（如插入、删除、查找等）。
分析数组和列表的优缺点，以及在不同场景下的应用，如数据存储和元素访问的效率。
链表：
深入介绍单向链表、双向链表和循环链表的结构和操作。
实现链表的基本操作，包括节点的创建、插入、删除和遍历，理解指针操作的细节。
栈和队列：
阐述栈的后进先出（LIFO）和队列的先进先出（FIFO）原则。
使用 Python 实现栈和队列的基本操作，如入栈、出栈、入队、出队，并分析其应用场景，如函数调用栈、任务调度队列。
树结构：
二叉树：
讲解二叉树的定义、性质和基本操作，包括创建、遍历（前序、中序、后序、层次遍历）。
实现二叉树的存储和操作，如二叉树的构建、节点插入、删除和查找。
二叉搜索树：
阐述二叉搜索树的特性，即左子节点值小于父节点，右子节点值大于父节点。
实现二叉搜索树的插入、删除、查找操作，以及如何保持树的平衡性，理解其在查找操作中的高效性。
平衡二叉树（如 AVL 树、红黑树）：
深入分析平衡二叉树的平衡机制，如 AVL 树的旋转操作、红黑树的颜色标记和调整规则。
实现平衡二叉树的操作，确保学员理解如何通过平衡操作保持树的高度平衡，提高查找效率。
图结构：
图的表示：
介绍图的基本概念和表示方法，如邻接矩阵和邻接表。
分析不同表示方法的优缺点，以及在不同图算法中的应用场景。
图的遍历算法：
讲解深度优先搜索（DFS）和广度优先搜索（BFS）算法在图中的实现和应用。
运用 DFS 和 BFS 解决图的连通性、路径查找等问题，如寻找最短路径、拓扑排序等。
排序算法：
基本排序算法：
实现并分析冒泡排序、选择排序和插入排序，理解其基本原理和比较交换操作。
比较不同基本排序算法的时间复杂度和空间复杂度，分析它们在不同数据规模下的性能表现。
高级排序算法：
讲解快速排序和归并排序的分治思想和实现细节。
对比高级排序算法和基本排序算法的性能，掌握如何选择合适的排序算法应对不同的排序需求。
查找算法：
顺序查找和二分查找：
实现顺序查找和二分查找算法，分析其时间复杂度和适用范围。
比较两种查找算法的性能差异，强调二分查找在有序数据集中的高效性。
哈希查找：
讲解哈希表的概念、哈希函数和冲突解决方法（如开放定址法、链地址法）。
实现哈希表的插入、查找和删除操作，理解哈希表在快速查找和存储键值对中的应用。
高级算法设计：
递归算法：
深入理解递归的概念和基本原理，包括递归函数的定义和调用过程。
运用递归解决经典问题，如汉诺塔问题、斐波那契数列等，分析递归算法的优缺点。
动态规划算法：
讲解动态规划的基本思想，如最优子结构和重叠子问题的概念。
运用动态规划解决经典问题，如背包问题、最长公共子序列问题，掌握状态转移方程的推导和存储优化。
贪心算法：
阐述贪心算法的思想和应用场景，如最小生成树（Prim 算法、Kruskal 算法）和最短路径（Dijkstra 算法）。
实现贪心算法解决实际问题，分析贪心算法的局部最优选择如何导致全局最优解。