数据结构 从概念到C实现PDF电子书下载

第1章 绪论 1

1.1问题求解与程序设计 2

1.1.1程序设计的一般过程 2

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

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

1.1.4本书讨论的主要内容 7

1.2数据结构的基本概念 8

1.2.1数据结构 8

1.2.2抽象数据类型 11

1.3算法的基本概念 12

1.3.1算法及算法的特性 12

1.3.2算法的描述方法 14

1.4算法分析 15

1.4.1算法的时间复杂度 16

1.4.2算法的空间复杂度 17

1.4.3算法分析举例 18

1.5扩展与提高 20

1.5.1从数据到大数据 20

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

习题1 23

第2章 线性表 25

2.1引言 26

2.2线性表的逻辑结构 27

2.2.1线性表的定义 27

2.2.2线性表的抽象数据类型定义 27

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单链表的使用 44

2.4.4双链表 45

2.4.5循环链表 47

2.5顺序表和链表的比较 48

2.6扩展与提高 48

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

2.6.2顺序表的动态分配方式 51

2.7应用实例 52

2.7.1约瑟夫环问题 52

2.7.2一元多项式求和 55

习题2 59

第3章 栈和队列 63

3.1引言 64

3.2栈 65

3.2.1栈的逻辑结构 65

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

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

3.2.4顺序栈和链栈的比较 71

3.3队列 72

3.3.1队列的逻辑结构 72

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

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

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

3.4扩展与提高 81

3.4.1两栈共享空间 81

3.4.2双端队列 82

3.5应用举例 83

3.5.1括号匹配问题 83

3.5.2表达式求值 85

习题3 88

第4章 字符串和多维数组 91

4.1引言 92

4.2字符串 92

4.2.1字符串的逻辑结构 92

4.2.2字符串的存储结构 94

4.2.3模式匹配 94

4.3多维数组 98

4.3.1数组的逻辑结构 98

4.3.2数组的存储结构与寻址 99

4.4矩阵的压缩存储 100

4.4.1特殊矩阵的压缩存储 100

4.4.2稀疏矩阵的压缩存储 102

4.5扩展与提高 105

4.5.1稀疏矩阵的转置运算 105

4.5.2广义表 107

4.6应用实例 111

4.6.1发纸牌 111

4.6.2八皇后问题 112

习题4 115

第5章 树和二叉树 119

5.1引言 120

5.2树的逻辑结构 121

5.2.1树的定义和基本术语 121

5.2.2树的抽象数据类型定义 123

5.2.3树的遍历操作 123

5.3树的存储结构 124

5.3.1双亲表示法 124

5.3.2孩子表示法 125

5.3.3孩子兄弟表示法 126

5.4二叉树的逻辑结构 127

5.4.1二叉树的定义 127

5.4.2二叉树的基本性质 129

5.4.3二叉树的抽象数据类型定义 130

5.4.4二叉树的遍历操作 131

5.5二叉树的存储结构 133

5.5.1顺序存储结构 133

5.5.2二叉链表 134

5.5.3三叉链表 138

5.6森林 138

5.6.1森林的逻辑结构 138

5.6.2树、森林与二叉树的转换 139

5.7最优二叉树 141

5.7.1哈夫曼算法 141

5.7.2哈夫曼编码 143

5.8扩展与提高 145

5.8.1二叉树遍历的非递归算法 145

5.8.2线索二叉树 148

5.9应用实例 151

5.9.1堆与优先队列 151

5.9.2并查集 154

习题5 155

第6章图 159

6.1引言 160

6.2图的逻辑结构 161

6.2.1图的定义和基本术语 161

6.2.2图的抽象数据类型定义 163

6.2.3图的遍历操作 164

6.3图的存储结构及实现 167

6.3.1邻接矩阵 167

6.3.2邻接表 170

6.3.3邻接矩阵和邻接表的比较 174

6.4最小生成树 175

6.4.1Prim算法 176

6.4.2 Kruskal算法 178

6.5最短路径 182

6.5.1 Dijkstra算法 183

6.5.2 Floyd算法 185

6.6有向无环图及其应用 187

6.6.1 AOV网与拓扑排序 187

6.6.2 AOE网与关键路径 190

6.7扩展与提高 193

6.7.1图的其他存储方法 193

6.7.2图的连通性 194

6.8应用实例 196

6.8.1七巧板涂色问题 196

6.8.2医院选址问题 198

习题6 200

第7章 查找技术 205

7.1概述 206

7.1.1查找的基本概念 206

7.1.2查找算法的性能 207

7.2线性表的查找技术 207

7.2.1顺序查找 207

7.2.2折半查找 208

7.3树表的查找技术 211

7.3.1二叉排序树 211

7.3.2平衡二叉树 217

7.3.3 B树 220

7.4散列表的查找技术 225

7.4.1散列查找的基本思想 225

7.4.2散列函数的设计 226

7.4.3处理冲突的方法 227

7.4.4散列查找的性能分析 231

7.4.5开散列表与闭散列表的比较 232

7.5各种查找方法的比较 232

7.6扩展与提高 233

7.6.1顺序查找的改进——分块查找 233

7.6.2折半查找的改进——插值查找 234

7.6.3 B树的改进——B＋树 235

习题7 236

第8章 排序技术 239

8.1概述 240

8.1.1排序的基本概念 240

8.1.2排序算法的性能 241

8.2插入排序 241

8.2.1直接插入排序 241

8.2.2希尔排序 243

8.3交换排序 245

8.3.1起泡排序 245

8.3.2快速排序 247

8.4选择排序 250

8.4.1简单选择排序 250

8.4.2堆排序 252

8.5归并排序 256

8.5.1二路归并排序的递归实现 256

8.5.2二路归并排序的非递归实现 257

8.6各种排序方法的比较 259

8.7扩展与提高 261

8.7.1排序问题的时间下界 261

8.7.2基数排序 262

习题8 264

附录A预备知识 269

A.1数学术语 269

A.2级数求和 269

A.3集合 270

A.4关系 271

附录B C语言基本语法 273

B.1程序结构 273

B.2数据的基本表现形式——常量和变量 274

B.3数据类型 275

B.4控制语句 277

B.5函数 278

B.6动态存储分配 281

附录C词汇索引 283

参考文献 287