数据结构-从概念到C实现(第2版)

目录

第1章绪论1

1.1问题求解与程序设计2

1.1.1程序设计的一般过程2

1.1.2数据结构在程序设计中的作用4

1.1.3算法在程序设计中的作用5

1.1.4本书讨论的主要内容6

1.2数据结构的基本概念8

1.2.1数据结构8

1.2.2抽象数据类型11

1.3算法的基本概念12

1.3.1算法及算法的特性12

1.3.2算法的描述方法13

1.4算法分析15

1.4.1算法的时间复杂度15

1.4.2算法的空间复杂度17

1.4.3算法分析举例17

1.5扩展与提高20

1.5.1从数据到大数据20

1.5.2算法分析的其他渐近符号22

1.6考研加油站23第2章线性表25

2.1引言26

2.2线性表的逻辑结构27

2.2.1线性表的定义27

2.2.2线性表的抽象数据类型定义27数据结构——从概念到C实现（第2版）目录2.3线性表的顺序存储结构及实现29

2.3.1顺序表的存储结构定义29

2.3.2顺序表的实现30

2.3.3顺序表的使用34

2.4线性表的链接存储结构及实现35

2.4.1单链表的存储结构定义35

2.4.2单链表的实现37

2.4.3单链表的使用45

2.4.4双链表46

2.4.5循环链表47

2.5扩展与提高48

2.5.1线性表的静态链表存储48

2.5.2顺序表的动态分配方式50

2.5.3顺序表和链表的比较52

2.6应用实例53

2.6.1约瑟夫环问题53

2.6.2一元多项式求和55

2.7考研加油站60第3章栈、队列和数组63

3.1引言64

3.2栈65

3.2.1栈的逻辑结构65

3.2.2栈的顺序存储结构及实现66

3.2.3栈的链接存储结构及实现69

3.2.4顺序栈和链栈的比较72

3.3队列72

3.3.1队列的逻辑结构72

3.3.2队列的顺序存储结构及实现73

3.3.3队列的链接存储结构及实现77

3.3.4循环队列和链队列的比较81

3.4多维数组81

3.4.1数组的逻辑结构81

3.4.2数组的存储结构与寻址82

3.5矩阵的压缩存储83

3.5.1特殊矩阵的压缩存储83

3.5.2稀疏矩阵的压缩存储86

3.6扩展与提高88

3.6.1两栈共享空间88

3.6.2双端队列89

3.6.3广义表91

3.7应用实例94

3.7.1括号匹配问题94

3.7.2表达式求值95

3.7.3八皇后问题99

3.8考研加油站102第4章树和二叉树105

4.1引言106

4.2树的逻辑结构107

4.2.1树的定义和基本术语107

4.2.2树的抽象数据类型定义109

4.2.3树的遍历操作109

4.3树的存储结构110

4.3.1双亲表示法110

4.3.2孩子表示法111

4.3.3孩子兄弟表示法112

4.4二叉树的逻辑结构113

4.4.1二叉树的定义113

4.4.2二叉树的基本性质115

4.4.3二叉树的抽象数据类型定义116

4.4.4二叉树的遍历操作117

4.5二叉树的存储结构119

4.5.1顺序存储结构119

4.5.2二叉链表120

4.5.3三叉链表124

4.6森林124

4.6.1森林的逻辑结构124

4.6.2树、森林与二叉树的转换125

4.7*优二叉树127

4.7.1哈夫曼算法127

4.7.2哈夫曼编码129

4.8扩展与提高131

4.8.1二叉树遍历的非递归算法131

4.8.2线索二叉树134

4.9应用实例138

4.9.1堆与优先队列138

4.9.2并查集140

4.10考研加油站141第5章图145

5.1引言146

5.2图的逻辑结构147

5.2.1图的定义和基本术语147

5.2.2图的抽象数据类型定义149

5.2.3图的遍历操作150

5.3图的存储结构及实现153

5.3.1邻接矩阵153

5.3.2邻接表156

5.3.3邻接矩阵和邻接表的比较161

5.4*小生成树161

5.4.1Prim算法162

5.4.2Kruskal算法165

5.5*短路径169

5.5.1Dijkstra算法169

5.5.2Floyd算法172

5.6有向无环图及其应用174

5.6.1AOV网与拓扑排序174

5.6.2AOE网与关键路径177

5.7扩展与提高179

5.7.1图的其他存储方法179

5.7.2图的连通性181

5.8应用实例183

5.8.1七巧板涂色问题183

5.8.2医院选址问题184

5.9考研加油站187第6章查找技术189

6.1概述190

6.1.1查找的基本概念190

6.1.2查找算法的性能191

6.2线性表的查找技术191

6.2.1顺序查找191

6.2.2折半查找192

6.3树表的查找技术195

6.3.1二叉查找树195

6.3.2平衡二叉树201

6.3.3B树204

6.4散列表的查找技术208

6.4.1散列查找的基本思想208

6.4.2散列函数的设计210

6.4.3处理冲突的方法211

6.4.4散列查找的性能分析215

6.5字符串模式匹配216

6.5.1BF算法216

6.5.2KMP算法218

6.6扩展与提高220

6.6.1顺序查找的改进——分块查找220

6.6.2折半查找的改进——插值查找220

6.6.3平衡二叉树的改进——红黑树221

6.6.4B树的改进——B+树227

6.6.5各种查找方法的比较228

6.7考研加油站228第7章排序技术231

7.1概述232

7.1.1排序的基本概念232

7.1.2排序算法的性能233

7.2插入排序233

7.2.1直接插入排序233

7.2.2希尔排序235

7.3交换排序237

7.3.1起泡排序237

7.3.2快速排序239

7.4选择排序242

7.4.1简单选择排序242

7.4.2堆排序244

7.5归并排序248

7.5.1二路归并排序的递归实现248

7.5.2二路归并排序的非递归实现249

7.6外部排序251

7.6.1外部排序的基本思想251

7.6.2置换—选择排序252

7.6.3败者树254

7.7扩展与提高255

7.7.1排序问题的时间下界255

7.7.2基数排序256

7.7.3各种排序方法的比较258

7.8考研加油站260参考文献263第1章绪论1

1.1问题求解与程序设计2

1.1.1程序设计的一般过程2

1.1.2数据结构在程序设计中的作用4

1.1.3算法在程序设计中的作用5

1.1.4本书讨论的主要内容6

1.2数据结构的基本概念8

1.2.1数据结构8

1.2.2抽象数据类型11

1.3算法的基本概念12

1.3.1算法及算法的特性12

1.3.2算法的描述方法13

1.4算法分析15

1.4.1算法的时间复杂度15

1.4.2算法的空间复杂度17

1.4.3算法分析举例17

1.5扩展与提高20

1.5.1从数据到大数据20

1.5.2算法分析的其他渐进符号22

1.6考研加油站23第2章线性表24

2.1引言25

2.2线性表的逻辑结构26

2.2.1线性表的定义26

2.2.2线性表的抽象数据类型定义26数据结构——从概念到C实现（第2版）目录2.3线性表的顺序存储结构及实现28

2.3.1顺序表的存储结构定义28

2.3.2顺序表的实现29

2.3.3顺序表的使用33

2.4线性表的链接存储结构及实现34

2.4.1单链表的存储结构定义34

2.4.2单链表的实现36

2.4.3单链表的使用44

2.4.4双链表45

2.4.5循环链表46

2.5扩展与提高47

2.5.1线性表的静态链表存储47

2.5.2顺序表的动态分配方式49

2.5.3顺序表和链表的比较51

2.6应用实例52

2.6.1约瑟夫环问题52

2.6.2一元多项式求和54

2.7考研加油站59第3章栈、队列和数组61

3.1引言62

3.2栈63

3.2.1栈的逻辑结构63

3.2.2栈的顺序存储结构及实现64

3.2.3栈的链接存储结构及实现67

3.2.4顺序栈和链栈的比较70

3.3队列70

3.3.1队列的逻辑结构70

3.3.2队列的顺序存储结构及实现71

3.3.3队列的链接存储结构及实现75

3.3.4循环队列和链队列的比较79

3.4多维数组79

3.4.1数组的逻辑结构79

3.4.2数组的存储结构与寻址80

3.5矩阵的压缩存储81

3.5.1特殊矩阵的压缩存储81

3.5.2稀疏矩阵的压缩存储84

3.6扩展与提高86

3.6.1两栈共享空间86

3.6.2双端队列87

3.6.3广义表89

3.7应用举例92

3.7.1括号匹配问题92

3.7.2表达式求值93

3.7.3八皇后问题97

3.8考研加油站100第4章树和二叉树102

4.1引言103

4.2树的逻辑结构104

4.2.1树的定义和基本术语104

4.2.2树的抽象数据类型定义106

4.2.3树的遍历操作106

4.3树的存储结构107

4.3.1双亲表示法107

4.3.2孩子表示法108

4.3.3孩子兄弟表示法109

4.4二叉树的逻辑结构110

4.4.1二叉树的定义110

4.4.2二叉树的基本性质112

4.4.3二叉树的抽象数据类型定义113

4.4.4二叉树的遍历操作114

4.5二叉树的存储结构116

4.5.1顺序存储结构116

4.5.2二叉链表117

4.5.3三叉链表121

4.6森林121

4.6.1森林的逻辑结构121

4.6.2树、森林与二叉树的转换122

4.7*优二叉树124

4.7.1哈夫曼算法124

4.7.2哈夫曼编码126

4.8扩展与提高128

4.8.1二叉树遍历的非递归算法128

4.8.2线索二叉树131

4.9应用实例135

4.9.1堆与优先队列135

4.9.2并查集137

4.10考研加油站138第5章图141

5.1引言142

5.2图的逻辑结构143

5.2.1图的定义和基本术语143

5.2.2图的抽象数据类型定义145

5.2.3图的遍历操作146

5.3图的存储结构及实现149

5.3.1邻接矩阵149

5.3.2邻接表152

5.3.3邻接矩阵和邻接表的比较157

5.4*小生成树157

5.4.1Prim算法158

5.4.3Kruskal算法161

5.5*短路径165

5.5.1Dijkstra算法165

5.5.2Floyd算法168

5.6有向无环图及其应用170

5.6.1AOV网与拓扑排序170

5.6.2AOE网与关键路径173

5.7扩展与提高175

5.7.1图的其他存储方法175

5.7.2图的连通性177

5.8应用实例179

5.8.1七巧板涂色问题179

5.8.2医院选址问题180

5.9考研加油站183第6章查找技术185

6.1概述186

6.1.1查找的基本概念186

6.1.2查找算法的性能187

6.2线性表的查找技术187

6.2.1顺序查找187

6.2.2折半查找188

6.3树表的查找技术191

6.3.1二叉查找树191

6.3.2平衡二叉树197

6.3.3B树200

6.4散列表的查找技术204

6.4.1散列查找的基本思想204

6.4.2散列函数的设计206

6.4.3处理冲突的方法207

6.4.4散列查找的性能分析211

6.5字符串模式匹配212

6.5.1BF算法212

6.5.2KMP算法214

6.6扩展与提高216

6.6.1顺序查找的改进——分块查找216

6.6.2折半查找的改进——插值查找216

6.6.3平衡二叉树的改进——红黑树217

6.6.4B树的改进——B+树223

6.6.5各种查找方法的比较224

6.7考研加油站224第7章排序技术227

7.1概述228

7.1.1排序的基本概念228

7.1.2排序算法的性能229

7.2插入排序229

7.2.1直接插入排序229

7.2.2希尔排序231

7.3交换排序233

7.3.1起泡排序233

7.3.2快速排序235

7.4选择排序238

7.4.1简单选择排序238

7.4.2堆排序240

7.5归并排序244

7.5.1二路归并排序的递归实现244

7.5.2二路归并排序的非递归实现245

7.6外部排序247

7.6.1外部排序的基本思想247

7.6.2置换选择排序248

7.6.3败者树250

7.7扩展与提高251

7.7.1排序问题的时间下界251

7.7.2基数排序252

7.7.3各种排序方法的比较254

7.8考研加油站256参考文献258