目

录第1章绪论1

1.1数据结构的基本概念1

1.1.1数据与数据元素1

1.1.2数据的逻辑结构2

1.1.3数据的存储结构4

1.2抽象数据类型5

1.3算法与算法分析7

1.3.1算法定义及描述7

1.3.2算法评价8

1.3.3算法性能分析与度量9

习题13

第2章线性表16

2.1线性表的基本概念17

2.1.1逻辑结构及基本操作17

2.1.2抽象数据类型18

2.2线性表的顺序存储实现19

2.2.1存储结构19

2.2.2基本操作的实现21

2.3线性表的链式存储实现24

2.3.1单链表24

2.3.2双链表30

2.3.3循环链表32

2.4应用33

2.4.1学生队列合并33

2.4.2一元多项式求导问题34

习题36

第3章栈38

3.1栈的基本概念39

3.1.1逻辑结构及基本操作393.1.2抽象数据类型39

3.2栈的顺序存储实现40

3.2.1存储结构40

3.2.2基本操作的实现42

3.2.3共享栈的介绍和基本操作43

3.3栈的链式存储实现45

3.3.1存储结构45

3.3.2基本操作的实现47

3.4栈和递归49

3.4.1函数调用栈49

3.4.2递归调用过程50

3.5应用51

3.5.1马踏棋盘51

3.5.2开关盒布线54

习题56

第4章队列58

4.1队列的基本概念59

4.1.1逻辑结构及基本操作59

4.1.2抽象数据类型60

4.2队列的顺序存储实现60

4.2.1存储结构60

4.2.2基本操作的实现61

4.2.3循环队列62

4.3队列的链式存储实现65

4.3.1存储结构65

4.3.2基本操作的实现66

4.4应用68

4.4.1滑动窗口最大值68

4.4.2图元识别71

习题74

第5章字符串76

5.1字符串的基本概念77

5.1.1逻辑结构及基本操作77

5.1.2抽象数据类型78

5.2字符串的存储结构及实现78

5.2.1定长串78

5.2.2堆串81

5.2.3块链串83

5.3字符串的模式匹配84

5.3.1朴素的模式匹配84

5.3.2无回溯的模式匹配86

5.4应用89

5.4.1最长公共子串89

5.4.2字符串全排列91

习题92

第6章数组94

6.1多维数组95

6.1.1数组的定义95

6.1.2数组的存储95

6.2矩阵的压缩存储96

6.2.1对称矩阵的压缩存储96

6.2.2三角矩阵的压缩存储97

6.2.3对角矩阵的压缩存储98

6.3稀疏矩阵98

6.3.1稀疏矩阵的压缩存储98

6.3.2稀疏矩阵的转置运算101

6.4应用103

6.4.1九宫格103

6.4.2三子棋105

习题106

第7章树与二叉树109

7.1树110

7.1.1树的定义110

7.1.2树的基本术语110

7.1.3树的存储结构111

7.2二叉树113

7.2.1二叉树的定义113

7.2.2二叉树的性质115

7.2.3二叉树的存储结构116

7.3二叉树的遍历118

7.3.1二叉树遍历的定义118

7.3.2二叉树的递归遍历119

7.3.3二叉树的非递归遍历121

7.4线索二叉树125

7.4.1线索二叉树的定义125

7.4.2线索二叉树的建立126

7.4.3线索二叉树的遍历127

7.5树与森林130

7.5.1树与森林的遍历130

7.5.2森林与二叉树的关系130

7.6哈夫曼(Huffman)树与编码132

7.6.1Huffman树132

7.6.2Huffman编码133

7.7应用137

7.7.1二叉排序树137

7.7.2中缀表达式138

习题140

第8章图142

8.1图的基本概念143

8.1.1图的定义143

8.1.2图的连通性145

8.1.3图的抽象数据类型147

8.2图的存储结构149

8.2.1邻接矩阵149

8.2.2邻接表151

8.2.3邻接多重表154

8.2.4十字链表155

8.3图的遍历算法156

8.3.1深度优先遍历157

8.3.2广度优先遍历159

8.4最小生成树161

8.4.1最小生成树问题161

8.4.2普里姆（Prim）算法162

8.4.3克鲁斯卡尔(Kruskal)算法165

8.5最短路径166

8.5.1最短路径问题166

8.5.2迪杰斯特拉（Dijkstra）算法166

8.5.3弗洛伊德（Floyd）算法169

8.6拓扑排序和关键路径171

8.6.1AOV网与拓扑排序171

8.6.2拓扑排序算法173

8.6.3AOE网与关键路径175

8.6.4关键路径算法176

8.7应用179

8.7.1扩大朋友圈179

8.7.2市内交通导航问题180

习题183

第9章查找186

9.1查找的基本概念187

9.2线性表的查找188

9.2.1顺序查找188

9.2.2二分查找189

9.2.3索引顺序查找192

9.3二叉查找树193

9.3.1二叉查找树的定义193

9.3.2二叉查找树的基本操作194

9.3.3查找性能分析198

9.4平衡二叉树198

9.4.1平衡二叉树的定义199

9.4.2平衡二叉树的建立199

9.5哈希表205

9.5.1哈希表的基本概念205

9.5.2哈希函数的构造206

9.5.3处理冲突的方法207

9.5.4查找性能分析208

9.6B树与B+树210

9.6.1B树210

9.6.2B+树216

9.7应用217

9.7.1直方图的计算217

9.7.2键树219

习题220

第10章排序223

10.1排序的基本概念223

10.1.1排序算法的分类224

10.1.2排序算法性能评价225

10.2插入排序226

10.2.1直接插入排序226

10.2.2折半插入排序228

10.2.3希尔（Shell）排序229

10.3选择排序230

10.3.1直接选择排序231

10.3.2堆排序232

10.4交换排序237

10.4.1冒泡排序237

10.4.2快速排序239

10.5归并排序242

10.6基数排序244

10.6.1多排序码排序244

10.6.2链式基数排序245

10.7各种内部排序算法的比较248

10.8外部排序250

10.8.1外部排序的基本过程250

10.8.2多路平衡归并252

10.8.3置换—选择排序254

10.8.4最佳归并树258

10.9应用260

10.9.1按文件名排序260

10.9.2数据库数据排序261

习题263

第11章算法进阶265

11.1分治算法265

11.1.1折半查找算法中的分治策略269

11.1.2归并排序中的分治策略270

11.2贪心算法271

11.2.1钱币找零问题中的贪心策略272

11.2.2背包问题中的贪心策略274

11.2.3最小生成树问题中的贪心策略275

11.3动态规划算法276

11.3.1最大子序列和问题的动态规划算法278

11.3.20/1背包问题的动态规划算法280

11.4搜索算法282

11.4.1回溯法282

11.4.2分支限界法285

习题287