第1章绪论1

1.1数据结构研究的内容和方法1

1.1.1数据结构的含义1

1.1.2数据结构研究的内容2

1.1.3研究数据结构的方法6

1.2抽象数据类型的表示与实现7

1.3学习数据结构的目的8

1.3.1数据结构的发展简史及在计算机科学中的地位8

1.3.2学习数据结构的目的9

1.4算法和算法分析9

1.4.1算法的定义9

1.4.2算法的性质9

1.4.3算法的设计目标11

1.4.4算法效率的度量11

习题114

第2章线性表16

2.1线性表的定义及其基本操作16

2.1.1线性表的定义16

2.1.2线性表的逻辑结构和特征16

2.1.3线性表的抽象数据类型表示17

2.2线性表的顺序存储结构19

2.2.1顺序表20

2.2.2顺序表上的基本操作20

2.2.3顺序存储结构的基本特点23

2.3线性表的链式存储结构24

2.3.1单链表24

2.3.2单链表中的基本操作262.3.3单向循环链表31

2.3.4双向链表32

2.3.5静态链表34

2.3.6链式存储结构的特点37

2.4线性表应用举例38

2.4.1Josephu问题38

2.4.2一元多项式的表示与相加41

本章小结45

习题245

第3章栈与队列47

3.1栈47

3.1.1栈的定义及其操作47

3.1.2栈的顺序存储结构49

3.1.3栈的链式存储结构51

3.2栈应用举例52

3.2.1数制转换53

3.2.2行编辑处理54

3.2.3表达式求值56

3.3栈与递归函数61

3.3.1递归定义与递归函数61

3.3.2递归函数到非递归函数的转化64

3.4队列66

3.4.1队列的定义及其操作66

3.4.2队列的顺序存储结构67

3.4.3队列的链式存储结构70

3.5队列应用实例72

3.5.1迷宫问题72

3.5.2离散事件模拟75

3.5.3有序事件模拟80

本章小结82

习题383

第4章串84

4.1串的定义及其操作84

4.1.1串的定义84

4.1.2串的抽象数据类型85

4.2串的存储结构87

4.2.1串的静态存储结构87

4.2.2串的动态存储结构93

4.3串模式匹配98

4.4串应用举例101

4.4.1文本编辑101

4.4.2建立词索引表104

本章小结106

习题4106

第5章数组和广义表107

5.1数组的定义及其操作107

5.1.1数组的定义107

5.1.2数组的抽象数据类型108

5.2数组的存储结构109

5.2.1数组的静态存储方式109

5.2.2数组的动态存储方式112

5.3矩阵的压缩存储113

5.3.1特殊矩阵的压缩存储113

5.3.2稀疏矩阵的压缩存储116

5.4广义表的定义及其操作120

5.4.1广义表的定义120

5.4.2广义表的抽象数据类型121

5.5广义表的存储结构122

5.5.1广义表的链式存储122

5.5.2广义表基本操作的递归算法124

本章小结127

习题5127

第6章树129

6.1树的基本概念129

6.1.1树的定义及基本操作130

6.1.2树的性质133

6.2二叉树135

6.2.1二叉树的定义及基本操作135

6.2.2二叉树的性质137

6.2.3二叉树的存储结构139

6.3二叉树的遍历142

6.3.1二叉树的遍历算法142

6.3.2二叉树遍历算法的非递归形式144

6.3.3二叉树遍历的应用148

6.4线索二叉树151

6.4.1线索二叉树的概念151

6.4.2建立线索二叉树153

6.4.3线索二叉树的遍历154

6.4.4线索二叉树的更新155

6.5树和森林156

6.5.1树的存储结构156

6.5.2森林和二叉树的转换160

6.5.3树和森林的遍历161

6.6二叉树应用举例162

6.6.1Huffman树及其构造算法162

6.6.2Huffman编码及译码166

本章小结169

习题6169

第7章图171

7.1图的定义及操作171

7.1.1图的定义171

7.1.2图的抽象数据类型175

7.2图的存储结构177

7.2.1数组表示法177

7.2.2邻接表表示法179

7.2.3十字链表表示法181

7.2.4邻接多重表表示法183

7.3图的遍历184

7.3.1深度优先搜索算法184

7.3.2广度优先搜索算法186

7.3.3求连通分量的算法187

7.4最小生成树188

7.4.1Prim算法189

7.4.2Kruskal算法191

7.5最短路径问题193

7.5.1Dijkstra算法193

7.5.2Floyd算法197

7.6图的应用实例199

7.6.1拓扑排序200

7.6.2关键路径204

本章小结208

习题7209

第8章查找211

8.1查找概述211

8.2顺序表的静态查找212

8.2.1顺序查找算法213

8.2.2折半查找算法214

8.2.3分块查找算法216

8.3树表的动态查找219

8.3.1二叉排序树和平衡二叉排序树219

8.3.2B-树232

8.3.3B+树和B树240

8.4Hash表的查找241

8.4.1Hash表的含义241

8.4.2Hash函数的构造方法243

8.4.3处理冲突的方法246

8.4.4Hash表的查找及分析248

本章小结251

习题8252

第9章排序253

9.1排序概述253

9.2插入排序255

9.2.1直接插入排序255

9.2.2折半插入排序258

9.2.3链表插入排序259

9.2.4Shell排序261

9.3交换排序262

9.3.1起泡排序262

9.3.2快速排序264

9.4选择排序266

9.4.1直接选择排序267

9.4.2堆选择排序268

9.5归并排序274

9.6基数排序276

9.7各种内排序方法的比较讨论280

9.8外排序概述281

习题9283

第10章算法设计基础284

10.1穷举法284

10.1.1算法概述284

10.1.2穷举法解决背包问题285

10.2贪心法287

10.2.1算法概述287

10.2.2贪心法解决背包问题288

10.3分治法289

10.3.1分治策略289

10.3.2应用实例： 大整数乘法291

10.4动态规划法292

10.4.1算法概述292

10.4.2动态规划法解决背包问题293

10.5回溯法294

10.5.1算法概述294

10.5.2回溯法解决背包问题295

本章小结296

习题10296

参考文献298