《数据结构》课程教学大纲（含课程思政）
课程代码：
课程负责人：
课程中文名称：数据结构
课程英文名称：Data Structures
课程类别：必修
课程学分数：5
课程学时数：72+36
授课对象：计算机科学与技术、人工智能、信息安全及相关专业本科
本课程的前导课程：高级语言程序设计、离散数学
本课程的后续课程：编译原理、操作系统
一、教学介绍
数据结构是计算机科学与技术、人工智能、信息安全及相关本科专业的核心专业基础课，在学科课程体系中起到承上启下的作用，是多个毕业要求指标点的关键支撑课程。主要讲授数据结构基本原理和方法，软件设计中常用的各种数据结构如线性表、栈、队列、串、数组和稀疏矩阵、树和二叉树以及图的实现，查和排序算法设计技术。本课程的主要任务是培养学生解决数据组织和数据处理问题，提高数据抽象能力和高效算法设计能力，为后续专业课程学习和计算机复杂算法设计及分析打下坚实的基础。
二、教学目的
本课程的主要教学环节有理论教学和实验教学，具体教学目标如下：
二叉树中序遍历非递归算法
1. 掌握数据结构的基本原理，深刻理解数据逻辑结构、存储结构和运算算法设计之间的关系，能够从求解问题中提炼出数据模型并准确地采用抽象数据类型进行描述。
2. 掌握常用数据结构的实现过程，针对逻辑结构特点设计相应的存储结构，继而高效地设计数据结构基本运算算法，能够对算法进行时间和空间复杂度分析。
3. 掌握常用数据结构的特点及其应用，能够在综合性求解问题中选择合适数据结构并设计出高效算法，具备基本的数据组织和数据处理能力。
4. 掌握数据结构的实验方法，能够根据需要开展实验研究，正确地描述数据和组织数据，并应用数据处理方法，编写程序，分析实验结果以获得合理有效的结论，具备解决复杂工程问题的能力。
三、课程内容与学时分配
说明：所有课程思政内容见本书配套的课程思政PPT，可以扫描各章开头的二维
码观看。
课程思政总论：分为国家战略、教师职责、我的理解和数据结构课程思政4部分。主要在数据结构课程教学中突出科学方法和工匠精神（科技报国）。
主要内容：
1. 绪论：数据结构相关概念、算法及算法分析。
教学重点：数据结构的3个方面（逻辑结构，存储结构和运算）。算法的特性和算法时间与空间复杂度分析，数据结构的目标。
教学难点：抽象数据类型ADT的作用，数据类型和抽象数据类型的区别。算法的最好、最坏和平均时间复杂度分析方法。
课程思政：从设计数据结构的方法引入共和国科技发展的重大事例—核武器研制的艰辛历程，简要介绍中国之父—邓稼先。[工匠精神（科技报国）]
2. 线性表：线性表及其逻辑结构、线性表的顺序存储结构、线性表的链式存储结构、线性表的应用和有序表。
教学重点：顺序表存储结构，线性表基本运算算法设计和顺序表应用算法设计。链式存储结构，线性表基本运算算法设计和链表应用算法设计。线性表两类存储结构的比较。
教学难点：基于整体建表和二路归并的高效算法设计方法。
课程思政：科学方法论—知识结构化，以数据结构和关系数据库为例介绍知识结构化和系统结构化。[科学方法]
3. 栈与队列：栈的定义、栈的顺序存储结构及其基本运算实现、栈的链式存储结构及其基本运算的实现、栈的综合应用；队列的定义、队列的顺序存储结构及其基本运算实现、队列的链式存储结构及其基本运算的实现、队列的综合应用；双端队列的定义。
教学重点：栈和队列的存储结构及其基本运算算法设计，利用栈求简单表达式值和求解迷宫问题，利用队列求解迷宫问题的算法设计，用栈和队列求解迷宫问题的差别。
教学难点：栈和队列的综合应用。
课程思政：从每种数据结构的实现有多种方式引出专利，简要介绍中国企业的专利发展。[工匠精神（科技报国）]
4. 串：串的基本概念、串的存储结构、串的模式匹配。
教学重点：串模式匹配的BF和KMP算法。
教学难点：KMP算法。
课程思政：模式匹配的应用—搜索引擎，简介百度和360搜索引擎的应用。[工匠精神（科技报国）]
5. 递归：递归的概念、递归调用的实现原理、递归模型，递归算法设计方法、递归算法到非递归算法的转换。
教学重点：递归调用的实现原理，递归模型，基于递归数据结构的递归算法设计方法和基于归纳的递归算法设计方法。
教学难点：递归算法设计方法。
课程思政：介绍归纳法和演绎法，解决问题的思维方式，运用归纳和演绎法高效学习，获得能力的途径和教育的目的。[科学方法：]
6. 数组和广义表：数组的基本概念、数组的存储结构、特殊矩阵的压缩存储；稀疏矩阵的三元组表示、稀疏矩阵的十字链表表示；广义表的定义和基本算法设计。
教学重点：特殊矩阵和稀疏矩阵的压缩存储，广义表的基本算法设计。
教学难点：广义表的基本算法设计。
课程思政：从矩阵压缩引入大数据压缩与存储，展示华为数据压缩国际专利。[工匠精神（科技报国）]
7. 树和二叉树：树的基本概念、二叉树概念和性质、二叉树存储结构、二叉树的基本运算及其实现、二叉树的遍历、二叉树的构造、线索二叉树、哈夫曼树和并查集。
教学重点：树和二叉树的性质，二叉树存储结构，二叉树遍历算法设计及其应用。
教学难点：二叉树的递归算法设计方法。
课程思政：科学方法—社会结构，从树和二叉树引入国家组织结构，以武汉防疫胜利为例说明中国行政管理的高效性，社会主义制度的优越性。[科学方法]
8. 图：图的基本概念、图的存储结构、图的遍历、生成树和最小生成树、最短路径、拓扑排序、AOE网与关键路径。
教学重点：图的存储结构，图的遍历及其应用，求最小生成树的Prim和Kruskal算法，求最短路径的Dijkstra和Floyd算法。
教学难点：图遍历应用算法设计，求最小生成树的Prim和Kruskal算法，求最短路径的Dijkstra和Floyd算法。
课程思政：简要介绍图的应用，如机器人路径规划问题，GIS求最短路径问题，城市规划的管网设计和生产进度的调度。[科学方法]
9. 查：查的基本概念、线性表的查、树表的查和哈希表查。
教学重点：线性表查的顺序查、折半查和分块查算法，二叉排序树算法设计，平衡二叉树，B树的插入和删除操作。哈希函数设计，开放定地法和拉链法解决冲突方法。
教学难点：折半查算法设计及其分析，二叉排序树的插入、生成、查和删除算法设计。哈希表查的性能分析。
课程思政：从查引入北斗卫星导航系统，介绍关键部件原子钟的攻关历程。[工匠精神（科技报国）：]
10. 内排序：排序的基本概念、插入排序、交换排序、选择排序、归并排序、基数排序和各种内排序方法比较。
教学重点：各种内排序算法设计，各种内排序方法的比较和选择。
教学难点：希尔排序、快速排序、堆排序、二路归并排序和基数排序算法设计。
课程思政：简要介绍各种高效排序的启示点，展示人类十大算法闪烁着人类智慧的光芒。[科学方法]
11. 外排序：外排序步骤和磁盘排序过程。
教学重点：多路平衡归并，最佳归并树。
教学难点：败者树在多路归并中的应用。
课程思政：从二路归并扩展到k路归并，简要说明利用堆或者败者树提高k路归并性能，引出选择合适的数据结构可以提供算法的性能。[科学方法]
12. 采用面向对象的方法描述算法：C++语言面向对象编程方法，采用面向对象方式设计数据结构，STL及其应用。
教学重点：用C++面向对象方式设计数据结构，STL应用。
教学难点：应用STL设计复杂算法。
四、课程内容与学时分配表：
四、教材与参考书
教材：数据结构教程（第6版），李春葆等，清华大学出版社，2022。
参考书：
[1] 算法导论. Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein 著. 潘金贵，顾铁成，李成法、叶懋译. 北京：机械工业出版社，2009
[2] 数据结构、算法与应用（C++语言描述）. Sartag Sahni著. 王立柱，刘志红译. 北京：机械工业出版社，2015。
[3] 数据结构（C语言），严蔚敏，清华大学出版社，1999。
[4] 数据结构教程（第6版）学习指导，清华大学出版社，李春葆等，2022。
五、考核方式
期末考试（60%），作业（10%），上机实验（20%），其他（10%）。
指标点与支撑课程（数据结构及其实验）的对应关系

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。