教学目的

数据结构是计算机科学与技术、人工智能、信息安全及相关本科专业的核心专业基础课，在学科课程体系中起到承上启下的作用，是多个毕业要求指标点的关键支撑课程。主要讲授数据结构基本原理和方法，软件设计中常用的各种数据结构如线性表、栈、队列、串、数组和稀疏矩阵、树和二叉树以及图的实现，查找和排序算法设计技术。本课程的主要任务是培养学生解决数据组织和数据处理问题，提高数据抽象能力和高效算法设计能力，为后续专业课程学习和计算机复杂算法设计及分析打下坚实的基础。

本课程的主要教学环节有理论教学和实验教学，具体教学目标如下：

1. 掌握数据结构的基本原理，深刻理解数据逻辑结构、存储结构和运算算法设计之间的关系，能够从求解问题中提炼出数据模型并准确地采用抽象数据类型进行描述。

2. 掌握常用数据结构的实现过程，针对逻辑结构特点设计相应的存储结构，继而高效地设计数据结构基本运算算法，能够对算法进行时间和空间复杂度分析。

3. 掌握常用数据结构的特点及其应用，能够在综合性求解问题中选择合适数据结构并设计出高效算法，具备基本的数据组织和数据处理能力。

4. 掌握数据结构的实验方法，能够根据需要开展实验研究，正确地描述数据和组织数据，并应用数据处理方法，编写程序，分析实验结果以获得合理有效的结论，具备解决复杂工程问题的能力。

通过对该课程的学习，应达到以下课程目标：

课程目标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设计复杂算法。

课程目标对毕业要求的支撑

课程教学内容与课程目标关系

实验内容与学时分配

说明：所以实验题的题目、目的和内容见《教材》，所有在线编程实验题目见LeetCode网站（www.leetcode-cn.com）。实验1：线性表

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序表各种基本运算的算法。

（2）实现单链表各种基本运算的算法。

（3）实现双链表各种基本运算的算法。

（4）实现循环单链表各种基本运算的算法。

（5）实现循环双链表各种基本运算的算法。

2. 设计性实验

（1）将单链表按基准划分。

（2）将两个单链表合并为一个单链表。

（3）求集合（用单链表表示）的并、交和差运算。

（4）求两个多项式相加运算。

3. 综合性实验

（1）求两个多项式相乘运算。

（2）职工信息的综合运算。

（3）用单链表实现两个大整数相加运算。

4. 在线编程实验（LeetCode平台）

（1）LeetCode4—寻找两个正序数组的中位数。

（2）LeetCode26 —删除排序数组中的重复项。

（3）LeetCode27—移除元素。

（4）LeetCode80—删除排序数组中的重复项II。

（5）LeetCode24—两两交换链表中的结点。

（6）LeetCode86—分隔链表。

（7）LeetCode92—翻转链表II。

（8）LeetCode143—重排链表。

（9）LeetCode203—移除链表元素。

（10）LeetCode328—奇偶链表。

（11）LeetCode707—设计链表。

实验2：栈和队列

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序栈各种基本运算的算法。

（2）实现链栈各种基本运算的算法。

（3）实现环形队列各种基本运算的算法。

（4）实现链队各种基本运算的算法。

2. 设计性实验

（1）用栈求解迷宫问题的所有路径及最短路径。

（2）编写病人看病模拟程序。

（3）求解栈元素排序问题。

3. 综合性实验

（1）用栈求解n皇后问题

（2）编写停车场管理程序

4. 在线编程实验（LeetCode平台）

（1）LeetCode150—逆波兰表达式求值。

（2）LeetCode155—最小栈。

（3）LeetCode224—基本计算器。

（4）LeetCode227—基本计算器II。

（5）LeetCode622—设计循环队列。

（6）LeetCode641—设计循环双端队列。

（7）LeetCode946—验证栈序列。

（8）LeetCode1249—移除无效的括号。

实验3：串

学时数：2。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序串各种基本运算的算法

（2）实现链串各种基本运算的算法

（3）实现顺序串的各种模式匹配算法

2. 设计性实验

（1）文本串加密和解密程序。

（2）求一个串中出现的第一个最长重复子串。

3. 综合性实验

（1）利用KMP算法求子串在主串中出现的次数。

4. 在线编程实验（LeetCode平台）

（1）LeetCode14—最长公共前缀。

（2）LeetCode443—压缩字符串。

（3）LeetCode459—重复的子字符串。

（4）LeetCode1408—数组中的字符串匹配。

实验4：递归

学时数：2。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）采用递归和非递归方法求解Hanoi问题。

（2）求路径和路径条数问题。

2. 设计性实验

（1）恢复IP地址。

（2）高效求解xn。

（3）用递归方法逆置带头结点的单链表。

（4）用递归方法求单链表中倒数第k个结点。

3. 综合性实验

（1）用递归方法求解n皇后问题。

（2）用递归方法求解0/1背包问题。

4. 在线编程实验（LeetCode平台）

（1）LeetCode24—两两交换链表中的结点。

（2）LeetCode50—Pow(x,n)。

（3）LeetCode51—N皇后。

（4）LeetCode59—螺旋矩阵II。

（5）LeetCode206—反转链表。

实验5：树和二叉树

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现二叉树各种基本运算的算法。

（2）实现二叉树各种遍历算法。

（3）由遍历序列构造二叉树。

（4）实现中序线索化二叉树。

（5）构造哈夫曼树和生成哈夫曼编码。

2. 设计性实验

（1）求二叉树中的结点个数、叶子结点个数、某结点层次和二叉树宽度。

（2）求二叉树中从根结点到叶子结点的路径。

（3）简单算术表达式二叉树的构建和求值。

3. 综合性实验

（1）用二叉树表示家谱关系并实现各种查找功能。

（2）大学的数据统计。

（3）二叉树的序列化和反序列化。

（4）判断二叉树b1中是否有与b2相同的子树。

（5）判断二叉树b1中是否有与b2树形结构相同的子树。

4. 在线编程实验（LeetCode平台）

（1）LeetCode102—二叉树的层序遍历。

（2）LeetCode114—二叉树展开为链表。

（3）LeetCode222—完全二叉树的结点个数。

（4）LeetCode226—翻转二叉树。

（5）LeetCode589—N叉树的前序遍历。

（6）LeetCode617—合并二叉树。

（7）LeetCode662—二叉树最大宽度。

（8）LeetCode872—叶子相似的树。

实验6：图

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现图的邻接矩阵和邻接表存储。

（2）实现图的遍历算法。

（3）求连通图的所有深度优先遍历序列。

（4）求连通图的深度优先生成树和广度优先生成树。

（5）采用普里姆算法求最小生成树。

（6）采用克鲁斯卡尔算法求最小生成树。

（7）采用狄克斯特拉算法求带权有向图的最短路径。

（8）采用弗洛伊德算法求带权有向图的最短路径。

（9）求AOE网中的所有关键活动。

2. 设计性实验

（1）求有向图的简单路径。

（2）求无向图中满足约束条件的路径。

（3）求解两个动物之间通信最少翻译问题。

（4）求带权有向图中的最小环。

3. 综合性实验

（1）求解建公路问题。

（2）求解最小费用问题。

（3）求解最短路径问题。

4. 在线编程实验（LeetCode平台）

（1）LeetCode130—被围绕的区域。

（2）LeetCode200—岛屿数量。

（3）LeetCode207—课程表。

（4）LeetCode210—课程表II。

（5）LeetCode310—最小高度树。

（6）LeetCode684—冗余连接。

（7）LeetCode743—网络延迟时间。

（8）LeetCode785—判断二分图。

（9）LeetCode797—所有可能的路径。

（10）LeetCode994—腐烂的橘子。

（11）LeetCode1462—课程安排IV。

（12）LeetCode1615—最大网络秩。

实验7：查找

学时数：4。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序查找的算法。

（2）实现折半查找的算法。

（3）实现分块查找的算法。

（4）实现二叉排序树的基本运算算法。

（5）实现哈希表的相关运算算法。

2. 设计性实验

（1）在有序序列中查找某关键字的区间。

（2）求两个等长有序序列的中位数。

（3）由有序序列创建一颗高度最小的二叉排序树。

（4）统计一个字符串中出现的字符及其次数。

（5）求一颗二叉排序树查找成功和失败情况下的平均查找长度。

（6）判断一个序列是否是二叉排序中的一个合法的查找序列。

（7）求二叉排序树中两个结点的最近公共祖先。

3. 综合性实验

（1）改进折半查找算法设计和分析。

（2）求折半查找成功时的平均查找长度。

4. 在线编程实验（LeetCode平台）

（1）LeetCode240—搜索二维矩阵II。

（2）LeetCode704—二分查找。

（3）LeetCode35—搜索插入位置。

（4）LeetCode34—在排序数组中查找元素的第一个和最后一个位置。

（5）LeetCode162—寻找峰值。

（6）LeetCode4—寻找两个正序数组的中位数。

（7）LeetCode96—不同的二叉排序树。

（8）LeetCode700—二叉排序树中的搜索。

（9）LeetCode450—删除二叉排序树中的结点。

（10）LeetCode380—常数时间插入、删除和获取随机元素。

实验8：内排序

学时数：4。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现直接插入排序算法。

（2）实现折半插入排序算法。

（3）实现希尔排序算法。

（4）实现冒泡排序算法。

（5）实现快速排序算法。

（6）实现简单选择排序算法。

（7）实现堆排序算法。

（8）实现二路归并排序算法。

（9）实现基数排序算法。

2. 设计性实验

（1）实现可变长度的字符串序列快速排序算法。

（2）实现英文单词按字典序排列的基数排序算法。

3. 综合性实验

（1）实现学生信息的多关键字排序。

（2）求各种排序算法的绝对执行时间。

4. 在线编程实验（LeetCode平台）

（1）LeetCode1528—重新排列字符串。

（2）LeetCode912—排序数组。

（3）LeetCode148—排序链表。

（4）LeetCode922—按奇偶排序数组II。

（5）LeetCode973—最接近原点的k个点。

（6）LeetCode295—数据流的中位数。

（7）LeetCode215—数组中的第k个最大元素。

（8）LeetCode75—颜色分类。

说明：所以实验题的题目、目的和内容见《教材》，所有在线编程实验题目见LeetCode网站（www.leetcode-cn.com）。实验1：线性表

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序表各种基本运算的算法。

（2）实现单链表各种基本运算的算法。

（3）实现双链表各种基本运算的算法。

（4）实现循环单链表各种基本运算的算法。

（5）实现循环双链表各种基本运算的算法。

2. 设计性实验

（1）将单链表按基准划分。

（2）将两个单链表合并为一个单链表。

（3）求集合（用单链表表示）的并、交和差运算。

（4）求两个多项式相加运算。

3. 综合性实验

（1）求两个多项式相乘运算。

（2）职工信息的综合运算。

（3）用单链表实现两个大整数相加运算。

4. 在线编程实验（LeetCode平台）

（1）LeetCode4—寻找两个正序数组的中位数。

（2）LeetCode26 —删除排序数组中的重复项。

（3）LeetCode27—移除元素。

（4）LeetCode80—删除排序数组中的重复项II。

（5）LeetCode24—两两交换链表中的结点。

（6）LeetCode86—分隔链表。

（7）LeetCode92—翻转链表II。

（8）LeetCode143—重排链表。

（9）LeetCode203—移除链表元素。

（10）LeetCode328—奇偶链表。

（11）LeetCode707—设计链表。

实验2：栈和队列

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序栈各种基本运算的算法。

（2）实现链栈各种基本运算的算法。

（3）实现环形队列各种基本运算的算法。

（4）实现链队各种基本运算的算法。

2. 设计性实验

（1）用栈求解迷宫问题的所有路径及最短路径。

（2）编写病人看病模拟程序。

（3）求解栈元素排序问题。

3. 综合性实验

（1）用栈求解n皇后问题

（2）编写停车场管理程序

4. 在线编程实验（LeetCode平台）

（1）LeetCode150—逆波兰表达式求值。

（2）LeetCode155—最小栈。

（3）LeetCode224—基本计算器。

（4）LeetCode227—基本计算器II。

（5）LeetCode622—设计循环队列。

（6）LeetCode641—设计循环双端队列。

（7）LeetCode946—验证栈序列。

（8）LeetCode1249—移除无效的括号。

实验3：串

学时数：2。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序串各种基本运算的算法

（2）实现链串各种基本运算的算法

（3）实现顺序串的各种模式匹配算法

2. 设计性实验

（1）文本串加密和解密程序。

（2）求一个串中出现的第一个最长重复子串。

3. 综合性实验

（1）利用KMP算法求子串在主串中出现的次数。

4. 在线编程实验（LeetCode平台）

（1）LeetCode14—最长公共前缀。

（2）LeetCode443—压缩字符串。

（3）LeetCode459—重复的子字符串。

（4）LeetCode1408—数组中的字符串匹配。

实验4：递归

学时数：2。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）采用递归和非递归方法求解Hanoi问题。

（2）求路径和路径条数问题。

2. 设计性实验

（1）恢复IP地址。

（2）高效求解xn。

（3）用递归方法逆置带头结点的单链表。

（4）用递归方法求单链表中倒数第k个结点。

3. 综合性实验

（1）用递归方法求解n皇后问题。

（2）用递归方法求解0/1背包问题。

4. 在线编程实验（LeetCode平台）

（1）LeetCode24—两两交换链表中的结点。

（2）LeetCode50—Pow(x,n)。

（3）LeetCode51—N皇后。

（4）LeetCode59—螺旋矩阵II。

（5）LeetCode206—反转链表。

实验5：树和二叉树

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现二叉树各种基本运算的算法。

（2）实现二叉树各种遍历算法。

（3）由遍历序列构造二叉树。

（4）实现中序线索化二叉树。

（5）构造哈夫曼树和生成哈夫曼编码。

2. 设计性实验

（1）求二叉树中的结点个数、叶子结点个数、某结点层次和二叉树宽度。

（2）求二叉树中从根结点到叶子结点的路径。

（3）简单算术表达式二叉树的构建和求值。

3. 综合性实验

（1）用二叉树表示家谱关系并实现各种查找功能。

（2）大学的数据统计。

（3）二叉树的序列化和反序列化。

（4）判断二叉树b1中是否有与b2相同的子树。

（5）判断二叉树b1中是否有与b2树形结构相同的子树。

4. 在线编程实验（LeetCode平台）

（1）LeetCode102—二叉树的层序遍历。

（2）LeetCode114—二叉树展开为链表。

（3）LeetCode222—完全二叉树的结点个数。

（4）LeetCode226—翻转二叉树。

（5）LeetCode589—N叉树的前序遍历。

（6）LeetCode617—合并二叉树。

（7）LeetCode662—二叉树最大宽度。

（8）LeetCode872—叶子相似的树。

实验6：图

学时数：6。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现图的邻接矩阵和邻接表存储。

（2）实现图的遍历算法。

（3）求连通图的所有深度优先遍历序列。

（4）求连通图的深度优先生成树和广度优先生成树。

（5）采用普里姆算法求最小生成树。

（6）采用克鲁斯卡尔算法求最小生成树。

（7）采用狄克斯特拉算法求带权有向图的最短路径。

（8）采用弗洛伊德算法求带权有向图的最短路径。

（9）求AOE网中的所有关键活动。

2. 设计性实验

（1）求有向图的简单路径。

（2）求无向图中满足约束条件的路径。

（3）求解两个动物之间通信最少翻译问题。

（4）求带权有向图中的最小环。

3. 综合性实验

（1）求解建公路问题。

（2）求解最小费用问题。

（3）求解最短路径问题。

4. 在线编程实验（LeetCode平台）

（1）LeetCode130—被围绕的区域。

（2）LeetCode200—岛屿数量。

（3）LeetCode207—课程表。

（4）LeetCode210—课程表II。

（5）LeetCode310—最小高度树。

（6）LeetCode684—冗余连接。

（7）LeetCode743—网络延迟时间。

（8）LeetCode785—判断二分图。

（9）LeetCode797—所有可能的路径。

（10）LeetCode994—腐烂的橘子。

（11）LeetCode1462—课程安排IV。

（12）LeetCode1615—最大网络秩。

实验7：查找

学时数：4。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现顺序查找的算法。

（2）实现折半查找的算法。

（3）实现分块查找的算法。

（4）实现二叉排序树的基本运算算法。

（5）实现哈希表的相关运算算法。

2. 设计性实验

（1）在有序序列中查找某关键字的区间。

（2）求两个等长有序序列的中位数。

（3）由有序序列创建一颗高度最小的二叉排序树。

（4）统计一个字符串中出现的字符及其次数。

（5）求一颗二叉排序树查找成功和失败情况下的平均查找长度。

（6）判断一个序列是否是二叉排序中的一个合法的查找序列。

（7）求二叉排序树中两个结点的最近公共祖先。

3. 综合性实验

（1）改进折半查找算法设计和分析。

（2）求折半查找成功时的平均查找长度。

4. 在线编程实验（LeetCode平台）

（1）LeetCode240—搜索二维矩阵II。

（2）LeetCode704—二分查找。

（3）LeetCode35—搜索插入位置。

（4）LeetCode34—在排序数组中查找元素的第一个和最后一个位置。

（5）LeetCode162—寻找峰值。

（6）LeetCode4—寻找两个正序数组的中位数。

（7）LeetCode96—不同的二叉排序树。

（8）LeetCode700—二叉排序树中的搜索。

（9）LeetCode450—删除二叉排序树中的结点。

（10）LeetCode380—常数时间插入、删除和获取随机元素。

实验8：内排序

学时数：4。任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。

1. 验证性实验

（1）实现直接插入排序算法。

（2）实现折半插入排序算法。

（3）实现希尔排序算法。

（4）实现冒泡排序算法。

（5）实现快速排序算法。

（6）实现简单选择排序算法。

（7）实现堆排序算法。

（8）实现二路归并排序算法。

（9）实现基数排序算法。

2. 设计性实验

（1）实现可变长度的字符串序列快速排序算法。

（2）实现英文单词按字典序排列的基数排序算法。

3. 综合性实验

（1）实现学生信息的多关键字排序。

（2）求各种排序算法的绝对执行时间。

4. 在线编程实验（LeetCode平台）

（1）LeetCode1528—重新排列字符串。

（2）LeetCode912—排序数组。

（3）LeetCode148—排序链表。

（4）LeetCode922—按奇偶排序数组II。

（5）LeetCode973—最接近原点的k个点。

（6）LeetCode295—数据流的中位数。

（7）LeetCode215—数组中的第k个最大元素。

（8）LeetCode75—颜色分类。

配套教材

扫码优惠购书

书名：数据结构教程（微课视频·题库·AI赋能版）（第7版）

ISBN：9787302718420

作者：李春葆

定价：65元

版本：C语言版本

“十四五”普通高等教育国家级规划教材，提供课件，大纲，教案，教学计划，源码，视频，题库，习题册，上机指导书，AI助教和智能体等

图书推荐

（1） 紧扣考纲，备考无忧： 依据教育部最新考研大纲修订，收录2018—2026年考研真题详解，配套完整考试大纲，精准覆盖考点，是考研复习的实用资料。

（2） 内容全面，讲解透彻： 全书系统覆盖数据结构核心知识点，条理清晰、实例丰富，从基础概念到复杂算法层层拆解，兼顾理论深度与实践应用。

（3） 资源丰富，学练结合： 配备50小时以上微课视频、AI学习资源、完整源码与在线题库，搭配分级实验题与LeetCode编程题，边学边练提升编程能力。

（4） 教学配套，适配教学： 提供教学大纲、教学课件、电子教案等全套教学资源，程序均通过主流编译环境调试，适合高校教学与自主学习使用。

（5）适合C语言编程。

本书内容

本书在前6版的基础上针对教育部新的考研大纲进行了修订。本书共12章，内容包括绪论、线性表、栈和队列、串、递归、数组和广义表、树和二叉树、图、查找、内排序、外排序、采用面向对象的方法描述算法等，书中给出了大量练习题和各类上机实验题。本书是全视频教程，提供了涵盖绝大部分知识点的微课视频（总时长超过50小时），部分视频提供了更多示例的讲解，附录E中还包括2018—2025年全国计算机专业研究生入学联考数据结构部分试题的讲解视频。本书内容全面、知识点翔实、条理清晰、讲解透彻、实例丰富、实用性强，适合高等院校计算机和相关专业学生使用。

目录

第1章绪论/

1.1什么是数据结构/

1.1.1数据结构的定义/

1.1.2逻辑结构/

1.1.3存储结构/

1.1.4数据运算/

1.1.5数据类型和抽象数据类型/

1.2算法及其描述/

1.2.1算法的定义/

1.2.2算法设计的目标/

1.2.3算法的描述/

1.3算法分析/

1.3.1算法分析概述/

1.3.2算法的时间性能分析/

1.3.3算法的空间性能分析/

1.4算法+数据结构=程序/

1.4.1程序和数据结构/

1.4.2算法和程序/

1.4.3算法和数据结构/

1.4.4数据结构的发展/

本章小结/

第2章线性表/

2.1线性表及其逻辑结构/

2.1.1线性表的定义/

2.1.2线性表的抽象数据类型描述/

2.2线性表的顺序存储结构/

2.2.1线性表的顺序存储结构——顺序表/

2.2.2顺序表基本运算的实现/

2.3线性表的链式存储结构/

2.3.1线性表的链式存储结构——链表/

2.3.2单链表/

2.3.3双链表/

2.3.4循环链表/

2.4线性表的应用/

2.5有序表/

2.5.1有序表的抽象数据类型描述/

2.5.2有序表的存储结构及其基本运算算法/

2.5.3有序表的归并算法/

2.5.4有序表的应用/

本章小结/

第3章栈和队列/

3.1栈/

3.1.1栈的定义/

3.1.2栈的顺序存储结构及其基本运算的实现/

3.1.3栈的链式存储结构及其基本运算的实现/

3.1.4栈的应用/

3.2队列/

3.2.1队列的定义/

3.2.2队列的顺序存储结构及其基本运算的实现/

3.2.3队列的链式存储结构及其基本运算的实现/

3.2.4队列的应用/

3.2.5双端队列/

本章小结/

第4章串/

4.1串的基本概念/

4.2串的存储结构/

4.2.1串的顺序存储结构——顺序串/

4.2.2串的链式存储结构——链串/

4.3串的模式匹配/

4.3.1BF算法/

4.3.2KMP算法/

本章小结/

第5章递归/

5.1什么是递归/

5.1.1递归的定义/

5.1.2何时使用递归/

5.1.3递归模型/

5.1.4递归与数学归纳法/

5.2栈和递归/

5.2.1函数调用栈/

5.2.2递归调用的实现/

5.2.3递归算法的时空性能分析/

5.2.4递归到非递归的转换*/

5.3递归算法的设计/

5.3.1递归算法的设计步骤/

5.3.2基于递归数据结构的递归算法设计/

5.3.3基于递归求解方法的递归算法设计/

本章小结/

第6章数组和广义表/

6.1数组/

6.1.1数组的基本概念/

6.1.2数组的存储结构/

6.1.3特殊矩阵的压缩存储/

6.2稀疏矩阵/

6.2.1稀疏矩阵的三元组表示/

6.2.2稀疏矩阵的十字链表表示/

6.3广义表/

6.3.1广义表的定义/

6.3.2广义表的存储结构/

6.3.3广义表的运算*/

本章小结/

第7章树和二叉树/

7.1树的基本概念/

7.1.1树的定义/

7.1.2树的逻辑表示方法/

7.1.3树的基本术语/

7.1.4树的性质/

7.1.5树的基本运算/

7.1.6树的存储结构/

7.2二叉树的概念和性质/

7.2.1二叉树的定义/

7.2.2二叉树的性质/

7.2.3二叉树与树、森林之间的转换/

7.3二叉树的存储结构/

7.3.1二叉树的顺序存储结构/

7.3.2二叉树的链式存储结构/

7.4二叉树的基本运算及其实现/

7.4.1二叉树的基本运算的概述/

7.4.2二叉树的基本运算算法的实现/

7.5二叉树的遍历/

7.5.1二叉树遍历的概念/

7.5.2先序、中序和后序遍历递归算法/

7.5.3先序、中序和后序遍历非递归算法*/

7.5.4层次遍历算法/

7.6二叉树的构造/

7.7线索二叉树/

7.7.1线索二叉树的概念/

7.7.2线索化二叉树/

7.7.3遍历线索化二叉树/

7.8哈夫曼树/

7.8.1哈夫曼树概述/

7.8.2哈夫曼树的构造算法/

7.8.3哈夫曼编码/

7.9用并查集求解等价问题/

7.9.1并查集的定义/

7.9.2并查集的算法实现/

本章小结/

第8章图/

8.1图的基本概念/

8.1.1图的定义/

8.1.2图的基本术语/

8.2图的存储结构和基本运算算法/

8.2.1邻接矩阵存储方法/

8.2.2邻接表存储方法/

8.2.3图的基本运算算法设计/

8.2.4其他存储方法/

8.3图的遍历/

8.3.1图的遍历的概念/

8.3.2深度优先遍历/

8.3.3广度优先遍历/

8.3.4非连通图的遍历/

8.3.5图遍历算法的应用/

8.4生成树和最小生成树/

8.4.1生成树的概念/

8.4.2非连通图和生成树/

8.4.3Prim算法/

8.4.4Kruskal算法/

8.5最短路径/

8.5.1路径的概念/

8.5.2Dijkstra算法/

8.5.3Floyd算法/

8.6拓扑排序/

8.7AOE网与关键路径/

8.7.1相关概念/

8.7.2求AOE网的关键活动/

本章小结/

第9章查找/

9.1查找的基本概念/

9.2线性表的查找/

9.2.1顺序查找/

9.2.2折半查找/

9.2.3索引存储结构和分块查找/

9.3树表的查找/

9.3.1二叉排序树/

9.3.2平衡二叉树/

9.3.3红黑树/

9.3.4B树/

9.3.5B+树/

9.4哈希表的查找/

9.4.1哈希表的基本概念/

9.4.2哈希函数的构造方法/

9.4.3哈希冲突的解决方法/

9.4.4哈希表的运算算法/

本章小结/

第10章内排序/

10.1排序的基本概念/

10.2插入排序/

10.2.1直接插入排序/

10.2.2折半插入排序/

10.2.3希尔排序/

10.3交换排序/

10.3.1冒泡排序/

10.3.2快速排序/

10.4选择排序/

10.4.1简单选择排序/

10.4.2堆排序/

10.5归并排序/

10.6基数排序/

10.7各种内排序方法的比较和选择/

本章小结/

第11章外排序/

11.1外排序的概述/

11.2磁盘排序/

11.2.1磁盘排序概述/

11.2.2生成初始归并段/

11.2.3多路平衡归并/

11.2.4最佳归并树/

本章小结/

第12章采用面向对象的方法描述算法/

12.1面向对象的概念/

12.2用C++设计面向对象的程序/

12.2.1类/

12.2.2类对象/

12.2.3构造函数和析构函数/

12.2.4模板类/

12.3用C++描述数据结构/

12.3.1顺序表类模板/

12.3.2链栈类模板/

12.4使用STL设计数据结构和算法/

附录A实验报告格式/

附录B引用型参数和指针引用型参数的说明/

附录C算法索引/

附录D名词索引/

附录E2026年全国硕士研究生招生考试计算机学科专业

基础（408）数据结构部分联考大纲/

参考文献/

视频样例

AI辅助样例

课程思政案例样例

考研试题解析样例

免费赠送习题册

在线题库www.qingline.net

考核及成绩评定方式

PPT样例

教案和教学计划样例

面试视频

相关教材（不同语言版本）