数据结构(C语言版)( 第4版 )(微课版)

第 1 章 概论 ............................................... 1
1.1　数据结构的基本概念与术语 ..................................　1
1.1.1　数据结构的基本概念..................................................1
1.1.2　数据的逻辑结构.........................................................2
1.1.3　数据的存储结构.........................................................3
1.1.4　数据的运算集合.........................................................5
1.2　数据类型和抽象数据类型.....................................　5
1.2.1　数据类型....................................................................6
1.2.2　抽象数据类型.............................................................6
1.2.3　抽象数据类型的描述和实现........................................7
1.3　算法和算法分析 ................................................　8
1.3.1　算法的基本概念和基本特征........................................8
1.3.2　算法的时间复杂度和空间复杂度.................................8
本章小结　................................................................　9
习题.....................................................................10
第　2 章 线性表及其顺序存储..........................　12
2.1　线性表...........................................................12
2.2　顺序表 ..........................................................12
2.2.1　顺序表的基本概念及描述 .........................................12
2.2.2　顺序表的实现...........................................................13
2.3　栈 ................................................................17
2.3.1　栈的基本概念及描述 ................................................17
2.3.2　顺序栈及其实现 .......................................................18
2.3.3　栈的应用之一——括号匹配......................................20
2.3.4　栈的应用之二——算术表达式求值 ...........................22
2.4　队列 .............................................................26
2.4.1　队列的基本概念及描述.............................................26
2.4.2　顺序队列及其实现....................................................27
2.4.3　顺序循环队列及其实现.............................................30
2.4.4　队列的应用..............................................................31
本章小结　...............................................................32
习题.....................................................................32
第　3 章 线性表的链式存储 ............................　34
3.1　链式存储........................................................34
3.2　单链表 ..........................................................35
3.2.1　单链表的基本概念及描述 .........................................35
3.2.2　单链表的实现...........................................................36
3.3　带头节点的单链表 ...........................................　39
3.3.1　带头节点的单链表的基本概念及描述........................39
3.3.2　带头节点的单链表的实现 .........................................40
3.4　循环单链表.....................................................43
3.4.1　循环单链表的基本概念及描述..................................43
3.4.2　循环单链表的实现....................................................44
3.5　双链表 .........................................................　49
3.5.1　双链表的基本概念及描述.........................................49
3.5.2　双链表的实现...........................................................49
3.6　链式栈 .........................................................　54
3.6.1　链式栈的基本概念及描述.........................................54
3.6.2　链式栈的实现...........................................................54
3.7　链式队列........................................................57
3.7.1　链式队列的基本概念及描述......................................57
3.7.2　链式队列的实现 .......................................................57
本章小结　..............................................................　60
习题.....................................................................61
第　4 章 字符串、集合和特殊数组....................　63
4.1　字符串...........................................................63
4.1.1　字符串的基本概念....................................................63
4.1.2　字符串类的定义.......................................................64
4.1.3　字符串的存储结构及其实现......................................65
4.2　字符串的模式匹配 ............................................71
4.2.1　朴素模式匹配算法....................................................71
4.2.2　快速模式匹配算法....................................................72
4.3　集合 .............................................................75
4.3.1　集合的定义和性质....................................................75
4.3.2　集合类的定义...........................................................76
4.3.3　集合的存储结构及其实现.........................................76
4.4　数组 ............................................................　84
4.4.1　数组和数组元素.......................................................84
4.4.2　数组类的定义...........................................................85
4.4.3　数组的顺序存储及其实现.........................................86
4.5　特殊矩阵.......................................................　89
4.5.1　对称矩阵的压缩存储................................................89
2
4.5.2　三角矩阵的压缩存储................................................90
4.5.3　带状矩阵的压缩存储................................................92
4.6　稀疏矩阵.......................................................　93
4.6.1　稀疏矩阵类的定义....................................................93
4.6.2　稀疏矩阵的顺序存储及其实现..................................94
4.6.3　稀疏矩阵的链式存储及其实现..................................96
本章小结　.............................................................100
习题...................................................................100
第　5 章 递归 ...........................................　102
5.1　递归的基本概念与递归程序设计 .........................102
5.2　递归程序执行过程的分析..................................104
5.3　递归程序到非递归程序的转换 ............................106
5.3.1　简单递归程序到非递归程序的转换.........................107
5.3.2　复杂递归程序到非递归程序的转换 .........................109
5.4　递归程序设计的应用实例..................................　114
本章小结　.............................................................　116
习题...................................................................116
第　6 章 树状结构......................................　118
6.1　树的基本概念 ................................................　118
6.2　树类的定义...................................................120
6.3　树的存储结构................................................120
6.3.1　双亲表示法............................................................120
6.3.2　孩子表示法............................................................121
6.3.3　孩子兄弟表示法.....................................................124
6.4　树的遍历......................................................125
6.5　树的线性表示................................................128
6.5.1　树的括号表示.........................................................128
6.5.2　树的层号表示.........................................................130
6.6　并查集 ........................................................　131
6.6.1　并查集的定义.........................................................131
6.6.2　并查集的构建.........................................................132
6.6.3　基于树状结构的并查集实现....................................132
本章小结　.............................................................137
习题...................................................................138
3
第　7 章 二叉树 ........................................　139
7.1　二叉树的基本概念 ..........................................139
7.2　二叉树的基本操作 ..........................................　141
7.3　二叉树的存储结构 ..........................................　141
7.3.1　顺序存储结构.........................................................142
7.3.2　链式存储结构.........................................................143
7.4　二叉树的遍历................................................145
7.4.1　二叉树遍历的定义..................................................145
7.4.2　二叉树遍历的递归实现...........................................145
7.4.3　二叉树遍历的非递归实现.......................................147
7.5　二叉树其他运算的实现.....................................150
7.6　线索二叉树...................................................152
7.6.1　线索二叉树的定义..................................................152
7.6.2　中序线索二叉树的基本操作....................................153
7.6.3　中序线索二叉树的存储结构及其实现......................154
7.7　树、森林和二叉树的转换..................................156
7.7.1　树、森林到二叉树的转换.......................................156
7.7.2　二叉树到树、森林的转换 .......................................157
本章小结　.............................................................158
习题...................................................................158
第　8 章 图 ..............................................　160
8.1　图的基本概念 ................................................160
8.2　图的基本操作................................................163
8.3　图的基本存储结构 ..........................................164
8.3.1　邻接矩阵及其实现..................................................164
8.3.2　邻接表及其实现.....................................................167
8.3.3　邻接多重表............................................................169
8.4　图的遍历......................................................170
8.4.1　深度优先遍历 ........................................................170
8.4.2　广度优先遍历.........................................................172
8.5　生成树与*小生成树 .......................................173
8.5.1　*小生成树的定义 .................................................175
8.5.2　*小生成树的 Prim 算法 ........................................176
8.5.3　*小生成树的 Kruskal 算法 ...................................179
8.6　*短路径......................................................182
8.6.1　单源*短路径 ........................................................182
4
8.6.2　所有顶点对的*短路径...........................................185
8.7　拓扑排序......................................................188
8.8　关键路径......................................................　191
本章小结　.............................................................196
习题...................................................................196
第　9 章 查找 ...........................................　200
9.1　查找的基本概念 .............................................200
9.2　线性表的查找................................................201
9.2.1　顺序查找................................................................201
9.2.2　二分查找................................................................203
9.2.3　分块查找................................................................205
9.3　二叉排序树...................................................207
9.4　丰满树和平衡树 .............................................213
9.4.1　丰满树...................................................................214
9.4.2　平衡二叉排序树.....................................................215
9.4.3　扩充二叉树............................................................222
9.5　红黑树 ........................................................223
9.5.1　红黑树的定义.........................................................224
9.5.2　红黑树的插入.........................................................224
9.5.3　红黑树的删除.........................................................227
9.6　*佳二叉排序树和 Huffman 树 .........................230
9.6.1　*佳二叉排序树.....................................................230
9.6.2　Huffman 树...........................................................235
9.7　B 树 ...........................................................238
9.7.1　B-树的定义 ...........................................................238
9.7.2　B-树的基本操作 ....................................................239
9.7.3　B 树 .....................................................................243
9.8　散列表查找...................................................245
9.8.1　散列存储 ...............................................................245
9.8.2　散列函数的构造.....................................................246
9.8.3　冲突处理 ...............................................................247
本章小结　.............................................................251
习题...................................................................251
第　10 章 排序..........................................　255
10.1　排序的基本概念 ...........................................255
5
10.2　插入排序....................................................256
10.2.1　直接插入排序 ......................................................256
10.2.2　二分法插入排序...................................................259
10.2.3　表插入排序..........................................................260
10.2.4　Shell 插入排序 ....................................................262
10.3　选择排序....................................................263
10.3.1　直接选择排序 ......................................................263
10.3.2　树状选择排序 ......................................................265
10.3.3　堆排序.................................................................267
10.4　交换排序....................................................271
10.4.1　冒泡排序 .............................................................271
10.4.2　快速排序 .............................................................272
10.5　归并排序....................................................274
10.6　基数排序....................................................278
10.6.1　多排序码的排序...................................................278
10.6.2　静态链式基数排序 ...............................................278
10.7　外部排序....................................................281
10.7.1　磁盘排序 .............................................................282
10.7.2　多路平衡归并 ......................................................283
10.7.3　置换-选择排序.....................................................285
10.7.4　*佳归并树..........................................................288
本章小结　.............................................................290
习题...................................................................291
附录　1 基础实验 ......................................　294
实验　1 线性表的顺序存储实现 .................................294
实验　2 不带头节点的单链表....................................297
实验　3 带头节点的单链表.......................................301
实验　4 栈与字符串 ...............................................303
实验　5 递归........................................................306
实验　6 树...........................................................310
实验　7 二叉树.....................................................312
实验　8 图...........................................................315
实验　9 查找........................................................317
实验　10 排序 ......................................................318
附录　2 综合实验