目录

第1章概论1

1.1什么是数据结构1

1.2数据结构的基本概念和术语3

1.3抽象数据类型及其表示与实现6

1.4算法和算法分析8

1.4.1什么是算法8

1.4.2算法的设计要求9

1.4.3算法时间性能分析9

1.4.4算法空间性能分析14

1.5类C语言描述15

小结17

习题18

实验题20第2章线性表23

2.1线性表的类型定义23

2.1.1线性表的定义23

2.1.2线性表的抽象数据类型24

2.2线性表的顺序存储结构及实现25

2.2.1线性表的顺序表示25

2.2.2顺序表上基本运算的实现26

2.2.3顺序表的算法举例31

2.3线性表的链式存储结构及实现31

2.3.1单链表的表示31

2.3.2单链表操作的实现33

2.3.3链表的算法举例39

2.3.4循环链表402.3.5双向链表41

2.3.6静态链表43

2.4线性表实现方法的比较46

2.5线性表的应用举例47

2.5.1一元多项式的表示47

2.5.2一元多项式的存储47

2.5.3一元多项式的运算48

2.6算法举例50

小结53

习题53

实验题57数据结构与算法目录第3章栈和队列61

3.1栈61

3.1.1栈的定义61

3.1.2栈的顺序存储结构和实现62

3.1.3栈的链式存储结构和实现65

3.2栈的典型应用67

3.3栈与递归71

3.3.1递归的实现71

3.3.2递归算法举例72

3.4队列74

3.4.1队列的定义74

3.4.2队列的顺序存储结构及实现74

3.4.3队列的链式存储结构及实现77

3.5栈和队列的应用举例79

3.6算法举例84

小结87

习题88

实验题92第4章串和数组95

4.1串的定义95

4.2串的存储结构96

4.2.1串的顺序存储结构96

4.2.2串的链式存储结构96

4.3串的模式匹配97

4.3.1简单模式匹配算法97

4.3.2KMP算法99

4.4串的应用举例102

4.5数组的定义103

4.6数组的顺序存储结构104

4.7矩阵的压缩存储106

4.7.1特殊矩阵106

4.7.2稀疏矩阵107

4.8算法举例113

小结115

习题115

实验题118第5章树和二叉树121

5.1树的逻辑结构121

5.1.1树的定义和术语121

5.1.2树的逻辑表示方法123

5.2树的存储结构124

5.3二叉树的逻辑结构127

5.3.1二叉树的定义127

5.3.2二叉树的性质128

5.4二叉树的存储结构130

5.4.1二叉树的顺序存储结构130

5.4.2二叉树的链式存储结构131

5.4.3基于二叉链表的二叉树遍历131

5.4.4线索链表和线索二叉树139

5.5树、森林与二叉树的相互转换143

5.5.1树与二叉树的相互转换143

5.5.2森林与二叉树的相互转换144

5.5.3树和森林的遍历146

5.6哈夫曼树及其应用147

5.6.1哈夫曼树（最优二叉树）147

5.6.2哈夫曼编码150

5.7二叉树的应用举例153

5.8算法举例156

小结159

习题159

实验题164第6章图169

6.1图的定义和术语169

6.2图的存储结构173

6.2.1邻接矩阵173

6.2.2邻接表175

6.2.3十字链表177

6.2.4邻接多重表178

6.3图的遍历179

6.3.1深度优先遍历180

6.3.2广度优先遍历181

6.3.3图的遍历与图的连通性183

6.4生成树和最小生成树183

6.4.1生成树183

6.4.2最小生成树184

6.5最短路径189

6.5.1单源点最短路径189

6.5.2任意两顶点之间的最短路径192

6.6有向无环图及其应用194

6.6.1拓扑排序194

6.6.2关键路径197

6.7图的应用举例202

6.8算法举例205

小结208

习题209

实验题212第7章查找217

7.1集合和查找217

7.2静态查找表上的查找218

7.2.1顺序查找218

7.2.2折半查找220

7.2.3分块查找223

7.3动态查找表上的查找225

7.3.1二叉排序树225

7.3.2平衡二叉树230

7.3.3B树239

7.4哈希表上的查找244

7.4.1哈希表的定义244

7.4.2构造哈希函数的方法245

7.4.3解决冲突的方法246

7.4.4哈希表的查找性能分析250

7.4.5开放定址法与链地址法的比较251

7.5算法举例252

小结255

习题255

实验题258第8章排序263

8.1概述263

8.2插入排序265

8.2.1直接插入排序265

8.2.2折半插入排序267

8.2.3希尔排序268

8.3交换排序269

8.3.1起泡排序269

8.3.2快速排序271

8.4选择排序274

8.4.1直接选择排序274

8.4.2堆排序275

8.5归并排序279

8.6分配排序281

8.7各种内部排序方法的比较285

8.8外部排序286

8.8.1文件管理286

8.8.2外部排序的方法287

8.8.3多路平衡归并排序288

8.8.4最佳归并树290

8.9算法举例292

小结294

习题294

实验题297参考文献300