课程标准-《数据结构教程（C++语言描述）》

《数据结构教程（C++语言描述）》课程标准教材：李春葆主编《数据结构教程（C++语言描述）》（第3版·微课视频版），清华大学出版社

教材编号：106540-01ISBN：978-7-302-68534-0一、课程基本信息项目内容课程名称数据结构（DataStructures）课程编号（由学院填写）课程类别学科基础课/专业核心课适用专业计算机科学与技术、软件工程、人工智能、数据科学、信息安全等先修课程C/C++程序设计、离散数学、高等数学（线性代数）后续课程算法设计与分析、操作系统、编译原理、数据库原理总学时64学时（理论48+实验16）学分4学分开课学期第3学期（大二上）或第4学期（大二下）授课语言中文，编程语言：C++二、课程性质与定位"数据结构"是计算机及相关专业的核心专业基础课，处于程序设计语言与高级专业课之间的承上启下位置。本课程以线性结构、树形结构、图形结构三大逻辑结构为主线，系统讲授数据的逻辑结构、存储结构和基本运算，配合查找与排序两大算法主题，培养学生选择合适数据组织方式、设计高效算法、用C++实现并分析算法性能的综合能力，是后续算法、数据库、操作系统、人工智能等课程的基础。三、课程目标3.1知识目标K1：掌握数据结构三要素（逻辑结构、存储结构、运算）及其相互关系；K2：熟练掌握线性表、栈、队列、串、数组、树、二叉树、图等典型数据结构的定义、性质、存储结构与基本运算；K3：掌握递归算法设计方法及递归与非递归的转换；K4：掌握折半查找、二叉排序树、AVL树、B树、哈希表等查找方法；K5：掌握插入、交换、选择、归并、基数等内排序算法及外排序的基本步骤；K6：掌握算法的时间复杂度和空间复杂度分析方法。3.2能力目标A1：能够根据问题特点选择合适的数据结构并用C++实现；A2：能够独立设计、编码、调试中等规模的数据结构与算法程序；A3：能够运用STL（vector、list、stack、queue、map、unordered_map等）解决工程问题；A4：能够分析算法的正确性与效率，并比较不同算法的优劣；A5：能够运用数据结构思想抽象与建模实际问题（如导航、推荐、检索、调度）。3.3素质目标S1：培养严谨的计算思维与"自顶向下、逐步求精"的工程素养；S2：培养代码规范、单元测试、性能调优的良好工程习惯；S3：通过经典算法（如哈夫曼、Dijkstra、KMP）培养追溯科学史与方法论的能力。3.4课程目标与毕业要求的对应关系（示例）课程目标毕业要求指标点支撑强度K1–K6工程知识1.3：能够将专业知识用于复杂工程问题的建模与求解HA1–A2问题分析2.2：能识别和表达复杂工程问题HA3使用现代工具5.2：能选择并使用恰当的开发工具MA4–A5设计/开发解决方案3.2：能设计满足特定需求的算法与模块HS1–S3终身学习12.1：自主获取知识、跟踪前沿M四、教学内容与学时分配周次章节教学内容理论学时实验学时第1周第1章绪论数据结构定义、逻辑/存储结构、抽象数据类型、算法及复杂度分析40第2–4周第2章线性表

第3章栈和队列顺序表、单链表、双链表、循环链表；顺序栈、链栈、顺序队、链队、STL容器；单调栈/队列124第5–7周第4章串

第5章数组和稀疏矩阵顺序串、链串、STLstring、BF/KMP算法；数组地址映射、特殊矩阵压缩、稀疏矩阵的三元组与十字链表102第8周第6章递归递归定义、递归模型、递归算法设计、递归转非递归42第9–10周第7章树和二叉树树的定义、二叉树性质、存储、遍历、线索二叉树、哈夫曼树、并查集82第11–12周第8章图图的概念与存储、遍历、最小生成树（Prim/Kruskal）、最短路径（Dijkstra/Floyd）、拓扑排序、关键路径84第13–15周第9章查找

第10章排序顺序/折半/分块查找、二叉排序树、AVL/红黑/B/B+树、哈希表；插入、交换、选择、归并、基数排序、外排序102第16周综合复习与考试章节串讲、典型题型分析、综合实验答辩40合计6016备注：理论与实验合计76学时，若采用64学时方案，可压缩第5章为自学+实验、第10章合并到第9章后部。五、各章重点与难点一览章节重点难点第1章三要素关系、时间/空间复杂度计算复杂度的渐近分析、递推方程展开第2章顺序表/链表算法设计、有序合并链表指针操作、空表/边界情况处理第3章栈/队的应用、单调栈/队栈/队选择、循环队列假溢出、单调性维护第4章BF与KMP算法next数组的求解原理与实现第5章数组地址映射、稀疏矩阵压缩特殊矩阵下标转换、十字链表操作第6章递归模型、回溯框架递归到非递归的等价转换第7章二叉树遍历、哈夫曼、并查集线索化算法、按权构造哈夫曼、路径压缩第8章邻接矩阵/表、DFS/BFS、Dijkstra、Floyd、拓扑、关键路径算法正确性证明、关键路径事件最早/最晚时间第9章折半查找、BST、AVL、哈希AVL旋转、平均查找长度推导、哈希冲突第10章各类内排序、快速排序、堆排序快排基准选择、堆调整、稳定性分析六、实验/上机教学6.1实验目标通过16学时上机实验，掌握使用C++与STL实现典型数据结构与算法，并能对算法性能进行实测分析。6.2实验项目列表序号实验名称学时类型对应章节实验1线性表的顺序表与链表实现与对比2验证+设计第2章实验2栈/队列应用（表达式求值、迷宫求解、约瑟夫环）2设计第3章实验3KMP串匹配算法实现2设计第4章实验4递归算法设计（汉诺塔、子集、八皇后）2设计第6章实验5二叉树遍历与哈夫曼编码2综合第7章实验6图的遍历与最短路径（Dijkstra/Floyd）4综合第8章实验7查找与排序综合（哈希表+快排/堆排性能比较）2综合第9–10章6.3实验环境操作系统：Windows10/11或macOS/Linux编译器：GCC11+/Clang14+/MSVC2022（支持C++17）IDE：VisualStudio、VSCode、CLion、Dev-C++均可在线评测：可选用LeetCode、洛谷、HDUOJ提交对应题目七、教学方法与手段多元教学法：讲授+演示+板书推导+上机+微课视频+翻转课堂；微课资源：每节配套微课视频（教材已提供二维码），课前预习、课中精讲、课后复习；可视化辅助：使用VisuAlgo、AlgorithmVisualizer等工具演示链表、树、图、排序的动态过程；案例驱动：以"导航、检索、调度、压缩"等真实场景导入；代码即讲义：所有关键算法均给出可运行的C++代码，并在课堂上演示运行与单步调试；互动设计：提问、随堂练习、白板演算、小组讨论；思政融入：通过哈夫曼编码、KMP、华罗庚、姚期智等讲述科学家事迹，培养创新精神。八、考核方式项目比例说明期末闭卷考试50%涵盖全部章节，重点为算法设计与复杂度分析期中考试10%第1–6章实验报告与代码25%7次实验，每次按代码正确性、报告质量、答辩表现评分平时作业10%每章3–5题，覆盖概念、推导、编程课堂表现与考勤5%出勤、提问、随堂练习期末考试题型与分值（示例）单项选择题：20分（基本概念、复杂度判别）简答题：20分（结构对比、算法思想阐述）应用计算题：30分（推导遍历序列、构造哈夫曼/AVL、Dijkstra执行过程）算法设计题：30分（用C++编写算法，含正确性与复杂度说明）九、推荐教材与参考书目主教材李春葆等.数据结构教程（C++语言描述）（第3版·微课视频版）.清华大学出版社,2024.配套李春葆.数据结构教程（C++语言描述）学习指导（第3版）.清华大学出版社.李春葆.数据结构教程上机实验指导（第3版）.清华大学出版社.参考书严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社.MarkAllenWeiss.DataStructuresandAlgorithmAnalysisinC++(4thed).Pearson.ThomasH.Cormen,etal.IntroductiontoAlgorithms(CLRS,4thed).MITPress.RobertSedgewick.Algorithms(4thed).Addison-Wesley.DonaldE.Knuth.TheArtofComputerProgrammingVol.1–3.Addison-Wesley.在线资源教材微课视频（书内二维码/清华大学出版社平台）VisuAlgo：LeetCode中国：洛谷OJ：十、教学进度与建议（学期周历）周次主题课堂任务学生任务1第1章绪论引入数据结构课程意义、讲解三要素与复杂度预习第2章、复习C++类与指针2第2章线性表（上）顺序表与单链表完成顺序表/链表算法练习3第2章线性表（下）双链表、循环链表、STLvector/list实验14第3章栈和队列顺序栈、链栈、顺序队、链队、STL完成栈/队列习题5第3章综合+第4章串（上）单调栈/队列应用、串定义、BF实验26第4章串（下）KMP算法、next数组完成KMP推导习题7第5章数组和稀疏矩阵地址映射、特殊矩阵、三元组实验38第6章递归递归模型、典型递归、消递归实验4；期中复习9第7章树和二叉树（上）树/二叉树概念、性质、存储完成遍历练习10第7章树和二叉树（下）遍历、线索化、哈夫曼、并查集实验511第8章图（上）图定义、存储、遍历完成图遍历练习12第8章图（下）MST、最短路径、拓扑、关键路径实验613第9章查找（上）顺序/折半/分块、BST完成查找推导14第9章查找（下）+第10章排序（上）AVL/B树/哈希；插入、交换排序实验715第10章排序（下）选择、归并、基数、外排序完成排序比较实验1