数据结构教程（Python语言描述）（第2版·微课视频版）教学大纲（参考版）

《数据结构教程（Python语言描述）》教学大纲一、课程基本信息项目内容课程名称数据结构教程（Python语言描述）课程英文名DataStructures(PythonDescription)课程性质专业基础课/专业核心课课程类别理论+实验总学时48学时（理论32+实验16）学分3学分开课学期大学二年级第一学期（建议）先修课程Python程序设计、离散数学、计算机导论后续课程算法分析与设计、操作系统、数据库系统、编译原理、人工智能适用专业计算机科学与技术、软件工程、人工智能、数据科学与大数据技术、网络工程、物联网工程教材《数据结构教程（Python语言描述）（第2版·微课视频版）》李春葆二、课程性质与定位"数据结构"是计算机类专业的核心基础课，承前启后地连接了程序设计语言（Python）与算法分析、操作系统、数据库等后续专业课程。本课程系统讲授线性表、栈、队列、串、数组、树、图等典型数据结构的逻辑结构、存储结构与基本运算，并结合Python语言特性，让学生在掌握经典数据结构原理的同时，具备使用Python高效实现各类数据结构与算法的能力。通过本课程学习，学生能够建立起"面向问题选择数据结构、面向数据结构选择算法、面向时空效率评估算法"的工程化思维，为后续高阶课程及实际软件开发奠定坚实基础。三、课程目标1.知识目标理解数据结构的基本概念，掌握逻辑结构、存储结构与运算三者的关系掌握线性表、栈、队列、串、数组、树、二叉树、图等经典数据结构的特性与实现掌握查找（顺序、折半、分块、二叉排序树、平衡二叉树、B树、哈希表）的原理与性能掌握插入、交换、选择、归并、基数等内排序算法及外排序的基本思路理解算法的时间复杂度与空间复杂度分析方法掌握递归算法的设计步骤与典型应用2.能力目标能够针对实际问题分析其数据特征，选择合适的数据结构进行抽象建模能够使用Python语言正确、高效地实现各类经典数据结构及其基本运算能够运用所学数据结构与算法求解综合性问题（如约瑟夫问题、表达式求值、迷宫路径、Huffman编码、最短路径等）能够使用大O记号分析算法时空复杂度并比较优劣能够编写规范的实验报告，独立完成LeetCode等在线编程平台的相关题目3.素质目标培养抽象思维与逻辑推理能力培养算法设计与工程实现相结合的工程素养培养自主学习与终身学习的能力培养良好的编码规范与测试调试习惯四、课程内容与学时分配章次章节名称理论实验周次主要内容1绪论20第1周数据结构概念、逻辑/存储结构、算法基础、复杂度分析、Python复习2线性表42第2-3周ADT、顺序表、单/双/循环链表、综合应用3栈和队列42第4-5周顺序栈/链栈、循环队列/链队、双端队列、优先队列4串和数组32第6周串的存储与模式匹配（BF/KMP）、特殊矩阵压缩、稀疏矩阵5递归32第7周递归模型、归纳法、执行过程、递归算法设计6树和二叉树52第8-10周树的存储、二叉树遍历、线索化、Huffman树、并查集7图42第11-12周邻接矩阵/表、DFS/BFS、最小生成树、最短路径、拓扑排序8查找32第13-14周折半查找、BST、AVL、B/B+树、哈希表9排序42第15-16周插入/交换/选择/归并/基数排序、内/外排序合计3216五、各章教学要求第1章绪论（2学时）教学目标：理解数据、数据元素、数据项、数据结构等基本概念区分数据的逻辑结构、存储结构与运算的关系复习Python的核心数据类型与程序设计技巧掌握算法时间复杂度与空间复杂度的分析方法教学重点：数据的逻辑结构（线性、树形、图状、集合）与四种基本存储结构（顺序、链式、索引、哈希）算法的五大特性与设计目标大O记号、T(n教学难点：数据结构与抽象数据类型（ADT）的关系时间复杂度的最坏/最好/平均分析实验内容：本章不安排独立实验，结合后续章节进行算法复杂度分析第2章线性表（6学时：理论4+实验2）教学目标：掌握线性表的定义与抽象数据类型描述掌握顺序表与链表的存储结构、基本运算实现能够针对实际问题选择合适的存储结构教学重点：顺序表的插入、删除、查找算法及时间复杂度分析单链表的头插法、尾插法建表双链表与循环链表的特性顺序表与链表的对比教学难点：链表节点的指针操作与边界处理（头节点、尾节点）双链表的对称性插入与删除综合应用题的算法设计（如有序合并、约瑟夫问题）实验内容：实验1：顺序表的实现及综合应用实验2：单链表与双链表的实现及综合应用第3章栈和队列（6学时：理论4+实验2）教学目标：掌握栈和队列的定义与"后进先出"、"先进先出"特性掌握顺序栈、链栈、循环队列、链队的实现能够使用栈/队列解决综合性问题（表达式求值、迷宫求解、报数游戏等）教学重点：顺序栈的入栈/出栈算法循环队列的"队空/队满"判断与下标计算Python中collections.deque与heapq优先队列的应用教学难点：循环队列下标的取模运算与"少用一个空间"的判满方案链栈与链队的动态空间管理双端队列与优先队列的典型应用场景实验内容：实验3：顺序栈与链栈实现及表达式求值实验4：循环队列与链队实现及综合应用第4章串和数组（5学时：理论3+实验2）教学目标：掌握串的存储结构与模式匹配算法掌握特殊矩阵的压缩存储与稀疏矩阵的三元组/十字链表表示理解多维数组的地址映射教学重点：BF算法与KMP算法的核心思想与next数组构造对称矩阵、三角矩阵、对角矩阵的压缩稀疏矩阵的三元组表示与转置算法教学难点：KMP算法next数组的推导与改进nextval稀疏矩阵的快速转置算法实验内容：实验5：BF与KMP算法实现与对比实验6：稀疏矩阵的三元组表示与基本运算第5章递归（5学时：理论3+实验2）教学目标：理解递归的定义、模型与执行过程掌握递归算法的设计步骤能够使用递归求解经典问题（阶乘、Fibonacci、Hanoi、全排列等）教学重点：递归模型（递归出口+递归体）基于递归数据结构（链表、二叉树）的递归设计基于归纳方法（数学归纳）的递归设计教学难点：递归的执行过程与栈帧分析递归到非递归（尾递归优化、显式栈）的转换递归算法的时空复杂度分析（递推方程、Master定理初步）实验内容：实验7：经典递归问题求解（汉诺塔、全排列）实验8：递归与非递归算法转换实验第6章树和二叉树（7学时：理论5+实验2）教学目标：掌握树与二叉树的概念、性质与存储结构熟练使用先序、中序、后序、层次四种遍历掌握线索二叉树、Huffman树、并查集的构造与应用教学重点：二叉树的五个重要性质二叉树的递归遍历算法（先/中/后序）及非递归实现由"先+中"或"后+中"序列构造二叉树Huffman树的构造与Huffman编码并查集的"按秩合并"与"路径压缩"教学难点：线索二叉树的中序前驱/后继查找序列化与反序列化树/森林与二叉树之间的相互转换并查集时间复杂度的近似分析（O(实验内容：实验9：二叉树四种遍历的递归与非递归实现实验10：Huffman编码或并查集实现第7章图（6学时：理论4+实验2）教学目标：掌握图的基本概念与两种存储结构（邻接矩阵、邻接表）熟练使用DFS与BFS遍历算法掌握最小生成树与最短路径的经典算法教学重点：邻接矩阵与邻接表的对比与适用场景DFS（递归+显式栈）与BFS（队列）实现Prim算法、Kruskal算法的执行流程Dijkstra算法、Floyd算法的差异与适用条件拓扑排序（Kahn算法）教学难点：图遍历的非连通图处理Prim/Kruskal与并查集的结合Dijkstra不能处理负权边的原因拓扑排序与AOV网/AOE网的关系实验内容：实验11：DFS/BFS遍历及连通分量实验12：最小生成树或最短路径求解第8章查找（5学时：理论3+实验2）教学目标：理解查找的基本概念（ASL、静态/动态查找表）掌握线性表查找、树表查找、哈希查找三大类方法能够根据数据特征选择合适的查找结构教学重点：折半查找的判定树与ASL计算二叉排序树（BST）的插入、删除与查找平衡二叉树（AVL）的四种旋转哈希函数构造与冲突解决（开放定址法、链地址法）教学难点：AVL树的LR、RL双旋转B树与B+树的插入分裂与删除合并哈希表的ASL分析与装填因子实验内容：实验13：折半查找与二叉排序树实验14：哈希表的构造与冲突处理第9章排序（6学时：理论4+实验2）教学目标：掌握插入、交换、选择、归并、基数五类内排序算法理解外排序的基本思路（多路归并）能够分析各排序算法的时间复杂度与稳定性教学重点：直接插入、希尔、冒泡、快速、简单选择、堆、归并排序的算法实现各排序算法的时间复杂度、空间复杂度、稳定性对比堆数据结构与堆调整算法教学难点：快速排序的递归划分与最坏O(n堆排序的"自底向上"建堆归并排序的递归与迭代实现外排序的归并段生成与多路败者树实验内容：实验15：常用内排序算法的实现与性能比较实验16：归并排序或堆排序的综合应用六、实验项目一览实验序号实验名称学时类型1顺序表的实现及综合应用1验证性2单链表与双链表的实现及综合应用1设计性3顺序栈与链栈实现及表达式求值1设计性4循环队列与链队实现及综合应用1设计性5BF与KMP算法实现与对比1验证性6稀疏矩阵的三元组表示与基本运算1设计性7经典递归问题求解1验证性8递归与非递归算法转换实验1设计性9二叉树遍历的递归与非递归实现1设计性10Huffman编码或并查集实现1综合性11图的DFS/BFS遍历及连通分量1设计性12最小生成树或最短路径求解1综合性13折半查找与二叉排序树1设计性14哈希表的构造与冲突处理1设计性15常用内排序算法的实现与性能比较1综合性16归并排序或堆排序的综合应用1综合性实验环境：Python3.9+、PyCharm/VSCode，建议提供LeetCode在线编程平台账号。七、考核方式考核项目比例说明平时成绩20%出勤、课堂表现、随堂练习、课后作业实验成绩30%实验报告、代码质量、实验答辩期末考试50%闭卷笔试，考查基本概念、算法分析与设计期末考试题型建议选择题（20%）：基本概念、复杂度分析填空题（10%）：术语、性质、关键公式简答题（15%）：算法思想、对比题算法分析题（25%）：手工模拟、复杂度推导算法设计题（30%）：编写算法（伪代码或Python）八、教材与参考资料主教材《数据结构教程（Python语言描述）（第2版·微课视频版）》李春葆主编在线资源清览题库：LeetCode中文站：/牛客网算法专题：/数据结构可视化：/Python官方文档：/zh-cn/3/中国大学MOOC："数据结构"系列课程九、教学建议理论与实践并重：每个核心算法都应配合Python代码演示与手工模拟，巩固理解图示辅助教学：充分利用动画、思维导图、判定树、状态变化图，帮助学生建立空间想象典型案例驱动：以约瑟夫问题、迷宫求解、表达式求值、Huffman编码、最短路径等经典问题贯穿课程复杂度分析贯穿全程：每讲解一个算法，都要分析其时间/空间复杂度并与已学算法对比结合LeetCode训练：每章结束后布置3-5道相关