目录

第1章绪论1

1.1什么是数据结构1

1.2基本概念和术语4

1.3抽象数据类型的表示与实现10

1.3.1描述语言概要10

1.3.2数据存储结构的C语言描述12

1.4算法和算法分析16

1.4.1算法16

1.4.2算法设计的要求17

1.4.3算法效率的度量17

1.4.4算法的存储空间需求20

第2章线性表22

2.1线性表的类型定义22

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

2.3线性表的链式表示和实现34

2.3.1线性链表34

2.3.2循环链表39

2.3.3双向链表40

2.3.4线性链表新的实现42

2.4一元多项式的表示及相加43

第3章栈和队列48

3.1栈48

3.1.1抽象数据类型栈的定义48

3.1.2栈的表示和实现49

3.2栈的应用举例51

3.2.1数制转换51

3.2.2括号匹配的检验52

3.2.3行编辑程序53

3.2.4迷宫求解54

3.2.5表达式求值57

3.3栈与递归的实现60

3.4队列66

3.4.1抽象数据类型队列的定义66

3.4.2链队列——队列的链式表示和实现68

3.4.3循环队列——队列的顺序表示和实现70

3.5离散事件模拟72

第4章串78

4.1串类型的定义78

4.2串的表示和实现81

4.2.1C语言串的存储表示81

4.2.2短串的存储表示83

4.2.3长串的存储表示86

4.2.4块链串的存储表示89

4.3串的模式匹配算法90

4.3.1求子串位置的定位函数 Index(S,T,pos)90

4.3.2模式匹配的一种改进算法91

4.4串操作应用举例96

4.4.1文本编辑96

4.4.2建立词索引表97

第5章数组和广义表104

5.1数组的定义104

5.2数组的顺序表示和实现105

5.3矩阵的压缩存储109

5.3.1特殊矩阵109

5.3.2稀疏矩阵110

5.4广义表的定义121

5.5广义表的存储结构123

5.6广义表的递归算法125

5.6.1求广义表的深度126

5.6.2复制广义表127

5.6.3建立广义表的存储结构128

5.7m元多项式的表示130

第6章树和二叉树134

6.1树的定义和基本术语134

6.2二叉树137

6.2.1二叉树的定义137

6.2.2二叉树的性质138

6.2.3二叉树的存储结构141

6.3遍历二叉树和线索二叉树144

6.3.1遍历二叉树144

6.3.2线索二叉树148

6.4堆和优先队列152

6.4.1优先队列152

6.4.2堆的定义153

6.4.3堆的基本操作的实现154

6.5赫夫曼树及其应用157

6.5.1最优二叉树(赫夫曼树)157

6.5.2赫夫曼编码和译码160

6.6树和森林164

6.6.1树的存储结构164

6.6.2森林与二叉树的转换168

6.6.3树和森林的遍历169

6.7并查集与等价问题170

6.7.1等价关系和等价类170

6.7.2并查集的定义和实现171

6.7.3对“并”算法的改进——加权合并法173

6.7.4对“查”算法的改进——路径压缩法175

6.8回溯法与树的遍历176

6.9树的计数178

第7章图182

7.1图的定义和术语182

7.2图的存储结构186

7.2.1数组表示法186

7.2.2邻接表189

7.2.3十字链表192

7.2.4邻接多重表194

7.3图的遍历195

7.3.1深度优先搜索195

7.3.2广度优先搜索197

7.4图的连通性问题198

7.4.1无向图的连通分量和生成树198

7.4.2有向图的强连通分量200

7.4.3最小生成树202

7.4.4关节点和重连通分量208

7.5最短路径211

7.5.1单个源点到其余各顶点的最短路径212

7.5.2每一对顶点之间的最短路径215

7.6有向无环图及其应用217

7.6.1有向无环图217

7.6.2拓扑排序218

7.6.3关键路径221

7.7二部图与图匹配226

第8章动态存储管理233

8.1概述233

8.2可利用空间表及分配方法234

8.3边界标识法238

8.4伙伴系统243

8.5无用单元收集246

8.6存储紧缩251

第9章查找254

9.1静态查找表256

9.1.1顺序表的查找256

9.1.2有序表的查找259

9.1.3静态树表的查找262

9.1.4索引顺序表的查找265

9.2动态查找表266

9.2.1二叉排序树267

9.2.2平衡二叉树273

9.2.3红黑树279

9.2.4B树和B+树288

9.2.5跳跃表300

9.2.6键树304

9.3散列表312

9.3.1散列和散列表定义312

9.3.2散列函数及其构造方法313

9.3.3冲突处理方法和散列表构造319

9.3.4散列表的查找及其分析330

9.3.5散列表和其他动态查找表字典操作的效率比较333

9.4布隆过滤器334

9.4.1位向量334

9.4.2布隆过滤器工作原理336

9.4.3布隆过滤器基本型的实现337

9.4.4布隆过滤器的应用和性能分析341

9.4.5布隆过滤器的改进343

第10章内部排序345

10.1概述345

10.2插入排序347

10.2.1直接插入排序347

10.2.2其他插入排序348

10.2.3希尔排序352

10.3快速排序354

10.4选择排序358

10.4.1简单选择排序358

10.4.2树状选择排序360

10.4.3堆排序361

10.5归并排序362

10.6基数排序364

10.6.1多关键字的排序364

10.6.2链式基数排序365

10.7各种内部排序方法的比较讨论368

第11章外部排序372

11.1外存信息的存取372

11.1.1存储器层次结构372

11.1.2磁盘信息的存取373

11.1.3高速缓存策略374

11.2外部排序的方法375

11.3多路平衡归并376

11.4置换选择排序380

11.5最佳归并树385

第12章文件和索引结构387

12.1文件基础387

12.1.1文件的基本概念387

12.1.2顺序文件389

12.1.3索引文件391

12.1.4二叉排序树索引非顺序文件示例393

12.2索引顺序文件394

12.2.1索引顺序文件概述394

12.2.2ISAM文件395

12.3B+树索引文件398

12.3.1VSAM文件398

12.3.2现代B+树索引存储方式对VSAM的改进400

12.3.3B+树的实现401

12.3.4B+树及数据存储组织与管理的新发展406

12.4直接存取文件(散列文件)407

12.5多关键字文件409

12.5.1多重表文件409

12.5.2倒排文件409

12.5.3全文检索的散列倒排索引示例411

附录A名词索引414

附录B函数索引421

附录CAnyviewC使用说明428

参考文献437