目录第1章绪论1

1.1概述2

1.1.1数据结构的研究内容2

1.1.2数据结构的发展过程4

1.2基本概念和术语4

1.2.1数据、数据元素、数据项和数据对象4

1.2.2逻辑结构和存储结构4

1.2.3数据类型和抽象数据类型8

1.3算法和算法分析12

1.3.1算法的定义及特性12

1.3.2算法与数据结构、程序的关系13

1.3.3评价算法的基本标准13

1.3.4算法时间的度量13

1.3.5算法的空间复杂度17

小结19

习题19

第2章线性表23

2.1线性表的概念24

2.1.1线性表的定义和特点24

2.1.2线性表的类型定义24

2.2线性表的顺序表示和实现28

2.2.1线性表的顺序存储表示28

2.2.2顺序表的结构定义29

2.2.3顺序表基本操作的实现30数据结构（C语言描述）目录2.3线性表的链式表示和实现36

2.3.1单链表的定义和表示36

2.3.2单链表基本操作的实现39

2.3.3循环链表48

2.3.4双向链表49

2.3.5静态链表52

2.4线性表的应用53

2.5线性表典型算法的实现57

小结60

习题61

第3章栈和队列63

3.1栈64

3.1.1栈的定义和特点64

3.1.2栈的类型定义64

3.1.3顺序栈的表示和实现65

3.1.4链栈的表示和实现69

3.2栈与递归71

3.2.1采用递归算法解决的问题71

3.2.2递归过程与递归工作栈74

3.3队列75

3.3.1队列及其特点75

3.3.2队列的类型定义76

3.3.3队列的顺序表示和实现77

3.3.4队列的链式表示和实现80

3.4栈和队列的应用84

3.4.1数制的转换84

3.4.2括号匹配的检验85

3.4.3表达式求值86

3.4.4队列的应用89

小结90

习题90

第4章串、数组和广义表93

4.1串的定义与操作94

4.1.1串的定义与相关概念94

4.1.2串的抽象类型定义95

4.2串的表示和实现96

4.2.1定长顺序存储表示96

4.2.2堆分配存储表示99

4.2.3串的链式存储表示100

4.3串的模式匹配102

4.3.1简单的模式匹配算法102

4.3.2KMP算法104

4.4数组107

4.4.1数组的类型定义107

4.4.2数组的顺序存储109

4.4.3特殊矩阵的压缩存储111

4.5广义表118

4.5.1广义表的定义118

4.5.2广义表的存储结构119

小结121

习题122

第5章树和二叉树125

5.1树的基本概念126

5.1.1树的定义126

5.1.2树的基本术语127

5.1.3树的抽象类型定义129

5.2二叉树基本概念130

5.2.1二叉树的定义130

5.2.2二叉树的抽象数据类型定义131

5.3二叉树的性质和存储结构133

5.3.1二叉树的性质133

5.3.2二叉树的存储结构135

5.4遍历二叉树和线索二叉树137

5.4.1遍历二叉树138

5.4.2线索二叉树147

5.5树和森林152

5.5.1树的存储结构152

5.5.2森林(树)与二叉树的转换155

5.5.3树和森林的遍历157

5.6哈夫曼树与哈夫曼编码159

5.6.1哈夫曼树的基本概念159

5.6.2哈夫曼树的构造算法160

5.6.3哈夫曼编码164

小结168

习题169

第6章图173

6.1图的概述174

6.1.1图的定义及基本术语174

6.1.2图的类型定义177

6.2图的存储结构178

6.2.1邻接矩阵179

6.2.2邻接表182

6.3图的遍历185

6.3.1深度优先遍历186

6.3.2广度优先遍历188

6.4最小生成树190

6.4.1生成树和最小生成树的概念190

6.4.2Prim算法191

6.4.3Kruskal算法194

6.5最短路径195

6.5.1单源最短路径195

6.5.2任意一对顶点间的最短路径200

6.6拓扑排序与关键路径204

6.6.1拓扑排序204

6.6.2关键路径207

小结212

习题214

第7章查找217

7.1查找的基本概念218

7.2静态查找表219

7.2.1顺序查找219

7.2.2折半查找221

7.2.3分块查找225

7.3动态查找表227

7.3.1二叉排序树227

7.3.2平衡二叉树234

7.3.3B树237

7.3.4B+树238

7.4哈希表239

7.4.1哈希表概述240

7.4.2哈希函数的构造方法240

7.4.3处理冲突的方法243

7.4.4哈希表的查找246

小结251

习题251

第8章排序255

8.1概述256

8.1.1排序的基本概念256

8.1.2内部排序方法的分类257

8.1.3排序记录的存储结构257

8.1.4排序算法效率的评价指标258

8.2插入排序259

8.2.1直接插入排序259

8.2.2折半插入排序261

8.2.3希尔排序263

8.3交换排序265

8.3.1冒泡排序265

8.3.2快速排序268

8.4选择排序271

8.4.1简单选择排序271

8.4.2堆排序273

8.5归并排序278

8.6基数排序280

8.6.1多关键字的排序280

8.6.2链式基数排序281

8.7内部排序方法比较285

小结286

习题286

参考文献289