第1章绪论1

1.1什么是数据结构2

1.2抽象数据类型及面向对象概念4

1.2.1数据类型4

1.2.2数据抽象与抽象数据类型(ADTs: Abstract Data Types)4

1.2.3面向对象的概念5

1.2.4用于描述数据结构的语言7

1.3数据结构的抽象层次7

*1.4用C++描述面向对象程序9

1.4.1C++的函数特征9

1.4.2C++的数据声明10

1.4.3C++的作用域11

1.4.4C++的类11

1.4.5C++中的对象13

1.4.6C++的输入输出13

1.4.7C++中的函数15

1.4.8C++中的参数传递15

1.4.9C++中的函数名重载和操作符重载16

1.4.10C++中的动态存储分配17

1.4.11友元(friend)函数18

1.4.12内联(inline)函数18

1.4.13结构(struct)与类18

1.4.14联合(Union)与类19

1.5算法定义19

1.6模板(template)20

1.7性能分析与度量23

1.7.1算法的性能标准23

*1.7.2算法的后期测试24

1.7.3算法的事前估计26

1.7.4空间复杂度度量26

1.7.5时间复杂度度量27

1.7.6时间复杂度的渐进表示法31

1.7.7渐进的空间复杂度34

习题34

第2章数组37

2.1作为抽象数据类型的数组37

2.1.1在C++中数组的定义和初始化37

2.1.2作为抽象数据类型的数组38

2.1.3数组的顺序存储方式40

2.2顺序表42

2.2.1顺序表的定义和特点43

2.2.2顺序表的类定义43

2.2.3顺序表的查找、插入和删除45

2.2.4作为抽象数据类型，使用顺序表的事例47

*2.3多项式抽象数据类型47

2.3.1多项式抽象数据类型48

2.3.2多项式的表示49

2.3.3多项式的相加51

2.4稀疏矩阵53

2.4.1稀疏矩阵的抽象数据类型53

2.4.2稀疏矩阵的压缩表示53

*2.4.3稀疏矩阵的转置54

*2.4.4稀疏矩阵相乘57

2.5字符串59

2.5.1字符串抽象数据类型和类定义59

2.5.2字符串操作的实现61

2.5.3字符串的模式匹配63

*2.5.4模式匹配的改进算法——KMP(D.E.Knuth—J.H.Morris—V.R.Pratt)

算法64

习题68

第3章链表71

3.1单链表(Singly Linked List)71

3.1.1单链表的结构71

3.1.2单链表的类定义72

3.1.3单链表中的插入与删除73

3.1.4带表头结点的单链表75

3.1.5用模板定义的单链表类76

3.1.6单链表的游标(Iterator)类79

3.1.7静态链表81

3.2循环链表82

3.2.1循环链表的类定义82

3.2.2用循环链表求解约瑟夫问题83

*3.3多项式及其相加84

3.3.1多项式的类定义84

3.3.2多项式的加法85

3.4双向链表87

3.5稀疏矩阵92

3.5.1稀疏矩阵的类定义92

3.5.2稀疏矩阵的建立94

3.5.3删除稀疏矩阵95

3.6C++中的虚函数和动态联编96

3.6.1C++中的继承(inheritance)96

3.6.2基类与派生类对象指针的转换97

3.6.3虚函数(virtual function)99

3.6.4纯虚函数和抽象基类99

3.6.5多态性(polymorphism)和动态联编99

习题101

第4章栈和队列103

4.1栈103

4.1.1栈的抽象数据类型103

4.1.2栈抽象数据类型的顺序存储表示与实现——顺序栈104

4.1.3栈抽象数据类型的链接存储表示——链式栈106

*4.2表达式的计算(Expression Evaluation)107

4.2.1表达式107

4.2.2应用后缀表示计算表达式的值108

4.2.3中缀表达式转换为后缀表达式111

4.3队列113

4.3.1队列的抽象数据类型113

4.3.2队列的顺序存储表示——循环队列114

4.3.3队列的链接存储表示——链式队列116

4.3.4队列的应用举例——打印二项展开式(a+b)j的系数118

4.4优先级队列(Priority Queue)119

4.4.1优先级队列的定义119

4.4.2优先级队列的存储表示和实现120

*4.5事件驱动模拟(Event\|Driven Simulation)121

习题130

第5章递归(RECURVE)132

5.1递归的概念132

5.2迷宫问题135

5.3递归过程与递归工作栈138

*5.4利用栈实现的迷宫问题非递归解法142

5.5广义表(General Lists)145

5.5.1广义表的概念146

5.5.2广义表的表示及操作147

5.5.3广义表存储结构的实现149

5.5.4广义表的访问算法151

5.5.5广义表的递归算法153

*5.5.6三元多项式的表示159

习题161

第6章树与森林163

6.1树和森林的概念163

6.1.1树的定义163

6.1.2树的术语163

6.1.3树的抽象数据类型164

6.2二叉树(Binary Tree)165

6.2.1二叉树的定义165

6.2.2二叉树的性质166

6.2.3二叉树的抽象数据类型167

6.3二叉树的表示168

6.3.1数组表示168

6.3.2链表存储表示169

6.4二叉树遍历(Binary Tree Traversal)172

6.4.1中序遍历(Inorder Traversal)173

6.4.2前序遍历(preorder Traversal)173

6.4.3后序遍历(Postorder Traversal)174

6.4.4应用二叉树遍历的事例175

*6.4.5二叉树遍历的游标类(Tree Iterator)177

*6.4.6不用栈的二叉树中序遍历算法182

*6.5线索化二叉树(Threaded Binary Tree)182

6.5.1线索(Thread)182

6.5.2中序线索化二叉树183

6.5.3前序与后序的线索化二叉树188

6.6堆(Heap)189

6.6.1堆的定义190

6.6.2堆的建立191

6.6.3堆的插入与删除192

6.7树与森林194

6.7.1树的存储表示194

6.7.2森林与二叉树的转换199

6.7.3树的遍历200

6.7.4森林的遍历202

*6.8二叉树的计数203

6.9霍夫曼树(Huffman Tree)206

6.9.1路径长度(Path Length)206

6.9.2霍夫曼树207

6.9.3霍夫曼编码209

习题210

第7章集合与搜索212

7.1集合及其表示212

7.1.1集合基本概念212

7.1.2以集合为基础的抽象数据类型213

7.1.3用位向量实现集合抽象数据类型213

7.1.4用有序链表实现集合的抽象数据类型215

7.2等价类和并查集219

7.2.1等价关系与等价类219

7.2.2确定等价类的链表方法220

7.2.3并查集222

7.3静态搜索结构227

7.3.1搜索的概念227

7.3.2静态搜索结构228

7.3.3顺序搜索229

7.3.4基于有序顺序表的折半搜索231

*7.3.5基于有序顺序表的斐波那契搜索和插值搜索234

7.4二叉搜索树235

7.4.1定义235

7.4.2二叉搜索树上的搜索237

7.4.3二叉搜索树的插入238

7.4.4二叉搜索树的删除239

*7.4.5与二叉搜索树相关的中序游标类240

*7.5最优二叉搜索树242

7.5.1扩充二叉搜索树242

7.5.2最优二叉搜索树243

7.6AVL树247

7.6.1AVL树的定义247

7.6.2平衡化旋转248

7.6.3AVL树的插入和删除252

7.6.4AVL树的高度255

习题256

第8章图259

8.1图的基本概念259

8.1.1图的基本概念259

8.1.2图的抽象数据类型261

8.2图的存储表示262

8.2.1邻接矩阵262

8.2.2邻接表265

8.2.3邻接多重表269

8.3图的遍历与连通性270

8.3.1深度优先搜索271

8.3.2广度优先搜索272

8.3.3连通分量273

8.3.4重连通分量274

8.4最小生成树277

8.4.1克鲁斯卡尔(Kruskal)算法278

8.4.2普里姆(Prim)算法280

8.5最短路径283

8.5.1边上权值非负情形的单源最短路径问题283

*8.5.2边上权值为任意值的单源最短路径问题286

8.5.3所有顶点之间的最短路径288

8.6活动网络290

8.6.1用顶点表示活动的网络290

8.6.2用边表示活动的网络294

习题298

第9章排序301

9.1概述301

9.2插入排序303

9.2.1直接插入排序303

9.2.2折半插入排序304

9.2.3链表插入排序305

9.2.4希尔排序307

9.3交换排序309

9.3.1起泡排序309

9.3.2快速排序310

9.4选择排序312

9.4.1直接选择排序313

9.4.2锦标赛排序313

9.4.3堆排序317

9.5归并排序318

9.5.1归并318

9.5.2迭代的归并排序算法319

9.5.3递归的表归并排序321

*9.6基数排序323

9.6.1多关键码排序323

9.6.2链式基数排序324

9.7外排序326

9.7.1外排序的基本过程326

9.7.2k路平衡归并329

9.7.3初始归并段的生成333

*9.7.4并行操作的缓冲区处理337

9.7.5最佳归并树339

习题341

第10章索引结构与散列344

10.1静态索引结构344

10.1.1线性索引344

10.1.2倒排表346

10.1.3m路静态搜索树347

10.2动态索引结构348

10.2.1动态的m路搜索树348

10.2.2B-树350

10.2.3B-树的插入352

10.2.4B-树的删除354

10.2.5B+树358

*10.3Trie树361

10.3.1Trie树的定义361

10.3.2Trie树的搜索362

10.3.3在Trie树上的插入和删除363

10.4散列(Hashing)364

10.4.1词典(Dictionary)的抽象数据类型364

10.4.2散列表与散列方法365

10.4.3散列函数365

10.4.4处理溢出的闭散列方法369

10.4.5处理溢出的开散列方法——链地址法376

10.4.6散列表分析378

*10.5可扩充散列379

10.5.1二叉Trie树379

10.5.2将二叉Trie树转换为目录380

10.5.3插入与目录扩充383

10.5.4删除与目录收缩385

10.5.5性能分析386

习题388

附录实习要求与实习报告391

实习1栈和队列396

实习2串(内容： 全屏幕文本编辑器)396

实习3树(内容： 作业调度)398

实习4图(内容： 某公园导游图)399

实习5查找、排序(内容： 简单的职工管理系统)399

参考文献401