数据结构

第1章　绪论 1

1.1　什么是数据结构 1

1.1.1　数据的逻辑结构 2

1.1.2　数据的存储结构 3

1.1.3　数据的运算 6

1.2　基本概念 6

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

1.3.1　C/C＋＋语言的基本数据类型 7

1.3.2　C/C＋＋语言的指针类型 7

1.3.3　C/C＋＋语言的数组类型 8

1.3.4　C/C＋＋语言中的结构体类型 8

1.3.5　C/C＋＋语言中的共用体类型 8

1.3.6　C/C＋＋语言中的自定义类型 9

1.4　算法和算法分析 9

1.4.1　算法 10

1.4.2　算法描述 10

1.4.3　算法设计的要求 12

1.4.4　算法效率的度量 13

1.4.5　算法的存储空间需求 14

1.5　上机实验 14

1.5.1 实验内容 14

1.5.2　实验指导 15

1.6　本章小结 16

1.7　练习题 17

第2章　线性表 21

2.1　线性表的类型定义 21

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

2.1　顺序表的定义 22

2.2.2　顺序表的基本运算 23

2.2.3　顺序表实现算法的分析 27

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

2.3.1　线性链表 28

2.3.2　循环链表 36

2.3.3　双向链表 40

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

2.5　上机实验 51

2.5.1　实验内容 51

2.5.2　实验指导 51

2.6　本章小结 53

2.7　练习题 54

第3章　栈和队列 58

3.1 栈 58

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

3.1.2　栈的表示和实现 60

3.2　栈的应用举例 66

3.2.1　数制转换 67

3.2.2　括号匹配的检验 67

3.2.3　行编辑程序 68

3.2.4　迷宫求解 69

3.2.5　表达式求值 71

3.3　栈与递归的实现 72

3.4　队列 76

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

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

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

3.5　离散事件模拟 87

3.6　队列的应用 90

3.7　上机实验 92

3.7.1　实验内容 92

3.7.2　实验指导 92

3.8　本章小结 96

3.9　练习题 96

第4章 串、数组和广义表 100

4.1 串类型的定义 100

4.2　串的表示和实现 102

4.2.1　定长顺序存储表示 102

4.2.2　堆分配存储表示 107

4.2.3 串的链存储表示 110

4.3 串的模式匹配算法 116

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

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

4.4　串操作应用举例 119

4.4.1　文本编辑 119

4.4.2　建立词索引表 121

4.5　数组的定义 121

4.6　数组的顺序表示和实现 122

4.7　矩阵的压缩存储 123

4.7.1　特殊矩阵 124

4.7.2　稀疏矩阵 125

4.8　广义表的定义 132

4.9　广义表的存储表示 134

4.10　广义表的基本运算算法 135

4.11　广义表的递归算法 141

4.12　上机实验 144

4.12.1　实验内容 144

4.12.2　实验指导 144

4.13　本章小结 147

4.14　练习题 147

第5章　树与二叉树 150

5.1　树 150

5.1.1　树的定义 151

5.1.2　树的表示 151

5.1.3　树的基本术语 152

5.1.4　树的存储结构 153

5.2　二叉树及其基本性质 155

5.2.1　什么是二叉树 155

5.2.2　二叉树的基本性质 156

5.2.3　满二叉树与完全二叉树 157

5.3　二叉树基本运算算法 158

5.3.1　二叉树的基本运算 158

5.3.2　二叉树基本运算实现算法 158

5.4　二叉树的遍历 162

5.5　确定唯一的二叉树 166

5.6　二叉树的存储结构 167

5.6.1　顺序存储结构 167

5.6.2　链式存储结构 168

5.7　线索二叉树 169

5.8　二叉树、树以及森林之间的转换 173

5.8.1　树和森林转换为二叉树 173

5.8.2　二叉树还原为树或森林 175

5.9　哈夫曼树及其应用 175

5.9.1　什么是哈夫曼树 175

5.9.2　哈夫曼树的构造 176

5.9.3　哈夫曼编码 178

5.10　上机实验 180

5.10.1　实验内容 180

5.10.2　实验指导 180

5.11　本章小结 182

5.12　练习题 182

第6章　图 186

6.1　图的基本概念 186

6.1.1　图的定义 186

6.1.2　图的基本术语 187

6.2　图的存储结构 189

6.2.1　邻接矩阵 190

6.2.2　邻接表 192

6.3 图的遍历 195

6.3.1　广度优先搜索法 196

6.3.2　深度优先搜索法 198

6.4　最小生成树 201

6.4.1　普里姆算法 201

6.4.2　克鲁斯卡尔算法 203

6.5　最短距离问题 207

6.5.1　单源最短距离 208

6.5.2　每对顶点之间的最短距离 210

6.6　拓扑排序 214

6.7　关键路径 217

6.8　上机实验 220

6.8.1　实验内容 220

6.8.2　实验指导 220

6.9　本章小结 222

6.10　练习题 222

第7章　查找 225

7.1　顺序查找 225

7.2　有序表的对分查找 227

7.3　分块查找 229

7.4　二叉排序树查找 231

7.4.1　二叉排序树的基本概念 231

7.4.2　二叉排序树的插入 232

7.4.3　二叉排序树的删除 233

7.4.4　二叉排序树的查找 235

7.5　二叉平衡树 235

7.6　哈希表查找 240

7.6.1　哈希表查找的基本概念 240

7.6.2　哈希函数的构造方法 241

7.6.3　哈希冲突的解决方法 243

7.7　多层索引树查找 258

7.7.1　B－树 258

7.7.2　B＋树 262

7.8　上机实验 265

7.8.1　实验内容 265

7.8.2　实验指导 265

7.9　本章小结 267

7.10　练习题 267

第8章　排序 270

8.1　互换类排序 270

8.1.1　冒泡排序 271

8.1.2　快速排序 273

8.2　插入类排序 274

8.2.1　简单插入排序 274

8.2.2　希尔排序 276

8.3　选择类排序 278

8.3.1　简单选择排序 278

8.3.2　堆排序 279

8.3.3　树形选择排序 284

8.4　其他排序方法简介 285

8.4.1　归并排序 285

8.4.2　基数排序 288

8.4.3　二叉树排序 291

8.5　各种排序方法的比较和选择 294

8.5.1　各种排序方法的比较 294

8.5.2　各种内排序方法的选择 294

8.6　上机实验 295

8.6.1　实验内容 295

8.6.2　实验指导 295

8.7　本章小结 298

8.8　练习题 299

主要参考文献 302