第 1 章 绪论 ...................... 1
1.1 数据结构基础 .................. 1
1.1.1 基本概念及举例 ............... 1
1.1.2 逻辑结构.......................... 2
1.1.3 存储结构.......................... 3
1.2 算法的概念..................... 4
1.2.1 算法的定义 ...................... 4
1.2.2 算法的特性 ...................... 4
1.2.3 算法设计目标................... 5
1.2.4 算法描述.......................... 5
1.3 算法分析........................ 6
1.3.1 算法的时间复杂度............ 6
1.3.2 算法的空间复杂度............ 9
1.4 绪论学习总结................ 10
1.5 绪论实验.......................11
1.6 练习题 .........................11
第 2 章 线性表 ................. 15
2.1 线性表的基本概念 .......... 15
2.2 顺序表 ........................ 16
2.2.1 顺序表的存储结构..........16
2.2.2 顺序表的基本操作..........16
2.3 单链表 ........................ 20
2.3.1 单链表的存储结构..........20
2.3.2 单链表的基本操作..........21
2.4 双链表 ........................ 29
2.4.1 双链表的存储结构..........29
2.4.2 双链表的基本操作..........29
2.5 循环链表 ..................... 37
2.5.1 循环单链表 ....................38
2.5.2 循环双链表 ....................40
2.6 线性表的应用................ 42
2.6.1 顺序表的应用.................42
2.6.2 单链表的应用.................43
2.6.3 双链表的应用.................44
2.6.4 循环链表的应用 .............45
2.7 线性表学习总结............. 46
2.8 线性表实验................... 47
2.9 练习题 ........................ 48
第 3 章 栈和队列............... 55
3.1 栈的基本概念 ................ 55
3.2 顺序栈 ........................ 56
3.2.1 顺序栈的存储结构..........56
3.2.2 顺序栈的基本操作..........56
3.3 链栈 ........................... 59
3.3.1 链栈的存储结构 .............59
3.3.2 链栈的基本操作 .............59
3.4 栈的应用...................... 62
3.5 队列的基本概念 ............. 64
3.6 顺序队列...................... 65
3.6.1 顺序队列的存储结构 ......65
3.6.2 顺序队列的基本操作 ......65
3.7 链队列 ........................ 68
3.7.1 链队列的存储结构..........68
3.7.2 链队列的基本操作..........68
3.8 循环队列和优先队列 ....... 71
3.8.1 循环队列........................71
3.8.2 优先队列........................73
3.9 队列的应用................... 75
3.10 栈和队列学习总结 ........ 79
3.11 栈和队列实验 .............. 80
3.12 练习题....................... 81
第 4 章 字符串 ................. 88
4.1 字符串的基本概念 .......... 88
4.2 顺序串 ........................ 89
4.2.1 顺序串的存储结构..........89
4.2.2 顺序串的基本操作..........89
4.3 链串 ........................... 95
4.3.1 链串的存储结构 .............95
4.3.2 链串的基本操作 .............96
4.4 字符串的模式匹配 .........101
4.4.1 BF 算法.......................101
4.4.2 KMP 算法 ...................103
4.4.3 改进的 KMP 算法.........106
2
4.5 字符串的应用...............108
4.6 字符串学习总结............111
4.7 字符串实验..................111
4.8 练习题 .......................112
第 5 章 递归 .................. 116
5.1 递归的概念和原理 .........116
5.2 递归模型 ....................118
5.3 递归算法的应用............119
5.4 递归学习总结...............125
5.5 递归实验 ....................125
5.6 练习题 .......................126
第 6 章 数组和特殊矩阵 .... 129
6.1 数组的基本概念 ............129
6.2 数组的存储结构............129
6.3 数组的基本操作............130
6.4 数组的应用..................130
6.5 特殊矩阵的基本概念 ......133
6.6 特殊矩阵压缩存储 .........134
6.6.1 对称矩阵压缩存储........134
6.6.2 三角矩阵压缩存储........135
6.6.3 对角矩阵压缩存储........135
6.6.4 稀疏矩阵压缩存储........136
6.7 特殊矩阵的应用............139
6.8 数组和特殊矩阵学习
总结..........................141
6.9 数组和特殊矩阵实验 ......142
6.10 练习题 .....................142
第 7 章 树和二叉树.......... 146
7.1 树 .............................146
7.1.1 树的基本概念...............146
7.1.2 树的顺序存储和链式
存储.............................150
7.2 二叉树 .......................152
7.2.1 二叉树的性质...............153
7.2.2 二叉树的存储结构........155
7.2.3 二叉树递归算法
设计.............................156
7.2.4 二叉树的基本操作........157
7.3 二叉树遍历..................161
7.3.1 层次遍历......................161
7.3.2 先序遍历......................162
7.3.3 中序遍历......................164
7.3.4 后序遍历......................166
7.4 二叉树构造................. 168
7.5 线索二叉树................. 172
7.5.1 线索二叉树的存储
结构.............................172
7.5.2 构造线索二叉树 ...........172
7.5.3 遍历线索二叉树 ...........174
7.6 哈夫曼树.................... 175
7.6.1 哈夫曼树的定义 ...........175
7.6.2 哈夫曼树构造...............176
7.6.3 哈夫曼编码 ..................178
7.7 二叉树与树、森林之间的
转换 ......................... 179
7.8 树和二叉树的应用 .........181
7.9 树和二叉树学习总结 ..... 185
7.10 树和二叉树实验 ......... 186
7.11 练习题..................... 186
第 8 章 图 ..................... 193
8.1 图的基本概念 .............. 193
8.2 图的存储结构.............. 196
8.2.1 邻接矩阵......................196
8.2.2 邻接表 .........................200
8.3 图的遍历.................... 205
8.3.1 深度优先遍历...............205
8.3.2 广度优先遍历...............207
8.4 生成树和最小生成树 ..... 210
8.4.1 生成树和最小生成树的
基本概念......................210
8.4.2 Prim 算法....................211
8.4.3 Kruskal 算法 ...............214
3
8.5 最短路径 ....................216
8.5.1 最短路径的基本概念 ....217
8.5.2 Dijkstra 算法 ...............217
8.5.3 Floyd 算法...................221
8.6 拓扑排序 ................... 224
8.7 关键路径 ................... 227
8.8 图的应用 ................... 230
8.9 图学习总结................. 235
8.10 图实验 .................... 235
8.11 练习题..................... 236
第 9 章 排序 .................. 243
9.1 排序的定义和分类 ........ 243
9.2 插入排序 ................... 244
9.2.1 直接插入排序...............244
9.2.2 折半插入排序...............246
9.2.3 希尔排序......................247
9.3 交换排序 ................... 248
9.3.1 冒泡排序......................248
9.3.2 快速排序......................250
9.4 选择排序 ................... 252
9.4.1 简单选择排序...............252
9.4.2 堆排序 .........................253
9.5 归并排序 ................... 256
9.6 分配排序 ................... 258
9.6.1 桶排序 .........................258
9.6.2 基数排序......................260
9.7 排序的应用................. 262
9.8 排序学习总结.............. 264
9.9 排序实验 ................... 264
9.10 练习题 .................... 265
第 10 章 查找 ................ 273
10.1 查找的定义、分类和
性能........................ 273
10.2 静态表查找 ............... 274
10.2.1 顺序查找....................274
10.2.2 二分查找....................275
10.2.3 分块查找....................277
10.3 动态表查找 ............... 279
10.3.1 二叉排序树查找.........279
10.3.2 平衡二叉树查找 .........286
10.3.3 B-树 .........................290
10.3.4 B+树 .........................292
10.4 哈希表查找 ............... 293
10.4.1 哈希函数 ...................293
10.4.2 解决冲突方法.............295
10.4.3 哈希表查找性能
分析 ..........................297
10.5 查找的应用 ............... 298
10.6 查找学习总结 ............ 300
10.7 查找实验.................. 300
10.8 练习题..................... 301
附录 A Java 语言中的
数据结构............. 308
附录 B 基础算法
练习题................ 309
附录 C 编程题................ 312
参考文献 ........................ 324

微课视频资源索引
例 2.1 有序顺序表元素逆置 ...................................................................................................... 42
例 2.2 顺序表相邻重复元素删掉 ............................................................................................... 43
例 2.3 有序单链表元素逆置 ...................................................................................................... 43
例 2.4 有序整数单链表 A 和 B 合并为 C .................................................................................. 44
例 2.5 双链表中找到正数第 k 个元素........................................................................................ 44
例 2.6 用循环单链表求解约瑟夫（Joseph）问题.................................................................... 45
例 2.7 用循环双链表判断所有元素是否对称............................................................................. 46
例 3.1 将十进制转换为二进制................................................................................................... 62
例 3.2 利用栈进行括号匹配检查 ............................................................................................... 63
例 3.3 求解汉诺塔问题.............................................................................................................. 64
例 3.4 打印杨辉三角形.............................................................................................................. 75
例 3.5 利用优先队列实现对操作系统进程调度 ......................................................................... 76
例 3.6 利用队列求迷宫问题 ...................................................................................................... 77
例 4.1 病毒检测.......................................................................................................................109
例 4.2 顺序串数字和字母前后排序..........................................................................................109
例 4.3 求字符串最长平台........................................................................................................110
例 5.1 递归算法单链表正向和反向输出其所有节点 ................................................................119
例 5.2 递归算法求解汉诺塔问题 .............................................................................................120
例 5.3 创建一个 n 阶螺旋矩阵并输出......................................................................................121
例 5.4 用递归算法求解迷宫问题 .............................................................................................123
例 6.1 求数组任意两个元素差的绝对值的最小值....................................................................131
例 6.2 二维数组逆置 ...............................................................................................................131
例 6.3 求二维数组两条对角线元素之和 ..................................................................................132
例 6.4 用递归算法求整数数组中的最大值...............................................................................133
例 6.5 将两个 n 阶对称矩阵压缩后求乘积 ..............................................................................139
例 6.6 求三元组表示的稀疏矩阵的转置矩阵的三元组.............................................................141
例 7.1 将一棵二叉链存储结构的树从左到右顺序输出其所有叶子结点 ...................................182
例 7.2 求二叉链结构的二叉树的宽度......................................................................................183
例 7.3 输出二叉树中值为 x 节点的所有祖先...........................................................................184
例 7.4 求二叉树中两个结点的最近公共祖先结点....................................................................184
算法 8.13 求单源最短路径 Dijkstra 算法................................................................................219
算法 8.14 求多源最短路径的 Floyd 算法................................................................................223
例 8.1 判断从顶点 u 到顶点 v 之间是否有路径.......................................................................230
例 8.2 求从顶点 u 到顶点 v 之间的所有简单路径 ...................................................................232
例 8.3 求从顶点 u 到顶点 v 的一条最短路径 ..........................................................................233
例 9.1 排序求刷题数量............................................................................................................262
例 9.2 分数按等级由高到低顺序输出......................................................................................263
例 10.1 统计整数序列中每个整数出现的次数.........................................................................298
例 10.2 按学号递增顺序输出学生的学号和姓名信息..............................................................299