数据结构 C语言描述PDF电子书下载

第1章 概论 1

1.1 什么是数据结构 1

1.1.1 基本概念 1

1.1.2 数据的逻辑结构 2

1.1.3 数据的存储结构 3

1.1.4 数据结构的运算 4

1.2 数据抽象和抽象数据类型 5

1.2.1 抽象、数据抽象和过程抽象 5

1.2.2 封装与信息隐蔽 5

1.2.3 数据类型和抽象数据类型 5

1.2.4 数据结构与抽象数据类型 6

1.3 描述数据结构 7

1.3.1 数据结构的规范 7

1.3.2 实现数据结构 7

1.4 算法和算法分析 9

1.4.1 算法及其性能标准 9

1.4.2 算法的时间复杂度 10

1.4.3 渐近时间复杂度 12

1.4.4 最坏、最好和平均情况时间复杂度 13

1.4.5 算法的空间复杂度 13

小结 13

习题1 14

第2章 数组和链表 16

2.1 结构与联合 16

2.1.1 结构 16

2.1.2 联合 17

2.2 数组 18

2.2.1 一维数组 18

2.2.2 二维数组 18

2.2.3 多维数组 20

2.3 链表 20

2.3.1 指针 20

2.3.2 单链表 24

2.3.3 带表头结点的单链表 30

2.3.4 循环链表 31

2.3.5 双向链表 31

小结 33

习题2 33

第3章 堆栈和队列 35

3.1 堆栈 35

3.1.1 堆栈ADT 35

3.1.2 堆栈的顺序表示 36

3.1.3 堆栈的链接表示 38

3.2 队列 39

3.2.1 队列ADT 39

3.2.2 队列的顺序表示 40

3.2.3 队列的链接表示 43

3.3 表达式的计算 43

3.3.1 表达式 43

3.3.2 中缀表达式转换为后缀表达式 44

3.3.3 计算后缀表达式的值 48

3.4 递归和递归过程 50

3.4.1 递归的概念 50

3.4.2 递归的实现 51

3.5 演示和测试 53

小结 55

习题3 55

第4章 线性表和数组ADT 57

4.1 线性表 57

4.1.1 线性表ADT 57

4.1.2 线性表的顺序表示 58

4.1.3 线性表的链接表示 61

4.1.4 两种存储表示的比较 65

4.2 多项式的算术运算 65

4.2.1 多项式ADT 65

4.2.2 多项式的链接表示 66

4.2.3 多项式的输入和输出 67

4.2.4 多项式相加 69

4.3 数组作为抽象数据类型 70

4.4 特殊矩阵 71

4.4.1 对称矩阵 71

4.4.2 带状矩阵 72

4.5 稀疏矩阵 73

4.5.1 稀疏矩阵ADT 73

4.5.2 稀疏矩阵的顺序表示 74

4.5.3 稀疏矩阵转置 75

4.5.4 稀疏矩阵相乘 78

4.5.5 稀疏矩阵的正交链表表示 81

4.5.6 建立正交链表 83

4.5.7 打印正交链表 84

小结 85

习题4 85

第5章 字符串和广义表 87

5.1 字符串 87

5.1.1 字符串ADT 87

5.1.2 字符串的存储表示 88

5.1.3 简单模式匹配算法 89

5.1.4 模式匹配的KMP算法 92

5.2 广义表 96

5.2.1 广义表的概念 96

5.2.2 广义表ADT 97

5.2.3 广义表的存储表示 98

5.2.4 广义表的算法 99

小结 100

习题5 100

第6章 树 101

6.1 树的基本概念 101

6.1.1 树的定义 101

6.1.2 基本术语 102

6.2 二叉树 103

6.2.1 二叉树的定义和性质 103

6.2.2 二叉树ADT 105

6.2.3 二叉树的存储表示 106

6.2.4 二叉树的遍历 109

6.2.5 二叉树遍历的非递归算法 113

6.2.6 二叉树遍历的应用实例 115

6.2.7 线索二叉树 117

6.3 树和森林 121

6.3.1 森林与二叉树的转换 121

6.3.2 树和森林的存储表示 122

6.3.3 树和森林的遍历 124

6.4 堆和优先权队列 125

6.4.1 堆 125

6.4.2 优先权队列 128

6.5 哈夫曼树和哈夫曼编码 131

6.5.1 树的路径长度 131

6.5.2 哈夫曼树和哈夫曼算法 132

6.5.3 哈夫曼编码 134

6.6 并查集和等价关系 136

6.6.1 并查集 136

6.6.2 并查集的实现 136

6.6.3 集合按等价关系分组 139

小结 140

习题6 140

第7章 集合和搜索 142

7.1 集合及其表示 142

7.1.1 集合和搜索 142

7.1.2 集合ADT 143

7.1.3 集合的表示 144

7.2 顺序搜索 144

7.3 二分搜索 146

7.3.1 对半搜索 147

7.3.2 二叉判定树 148

7.3.3 斐波那契搜索 150

7.3.4 插值搜索 151

7.4 分块搜索 152

7.5 搜索算法的时间下界 153

小结 154

习题7 154

第8章 搜索树 155

8.1 二叉搜索树 155

8.1.1 二叉搜索树的定义 155

8.1.2 二叉搜索树的搜索 155

8.1.3 二叉搜索树的插入 156

8.1.4 二叉搜索树的删除 158

8.1.5 二叉搜索树的高度 160

8.2 二叉平衡树 161

8.2.1 二叉平衡树的定义 161

8.2.2 二叉平衡树的平衡旋转 162

8.2.3 二叉平衡树的插入 168

8.2.4 二叉平衡树的删除 171

8.2.5 二叉平衡树的高度 174

8.3 B-树 174

8.3.1 m叉搜索树 174

8.3.2 B-树的定义 176

8.3.3 B-树的高度 176

8.3.4 B-树的搜索 177

8.3.5 B-树的插入 177

8.3.6 B-树的删除 180

8.4 键树 182

8.4.1 键树的定义 182

8.4.2 双链树 183

8.4.3 Trie树 184

8.5 伸展树 185

小结 187

习题8 188

第9章 跳表和散列表 189

9.1 字典 189

9.2 跳表 189

9.2.1 什么是跳表 190

9.2.2 跳表的搜索 193

9.2.3 跳表的插入 194

9.2.4 跳表的删除 195

9.3 散列表 196

9.3.1 散列技术 196

9.3.2 散列函数 197

9.3.3 解决冲突的拉链法 198

9.3.4 解决冲突的线性探查法 199

9.3.5 解决冲突的其他开地址法 203

9.3.6 性能分析 205

小结 206

习题9 206

第10章 图 207

10.1 图的基本概念 207

10.1.1 图的定义与术语 207

10.1.2 图ADT 209

10.2 图的存储结构 210

10.2.1 矩阵表示法 210

10.2.2 邻接表表示法 214

10.2.3 正交链表和多重表表示法 217

10.3 图的遍历 219

10.3.1 深度优先遍历 219

10.3.2 宽度优先遍历 221

10.4 拓扑排序和关键路径 223

10.4.1 拓扑排序 223

10.4.2 关键路径 227

10.5 最小代价生成树 230

10.5.1 普里姆算法 231

10.5.2 克鲁斯卡尔算法 232

10.6 最短路径 234

10.6.1 单源最短路径 235

10.6.2 所有顶点之间的最短路径 238

小结 240

习题10 241

第11章 内排序 243

11.1 排序的基本概念 243

11.2 插入排序 244

11.2.1 直接插入排序 244

11.2.2 希尔排序 248

11.2.3 对半插入排序 249

11.3 交换排序 249

11.3.1 冒泡排序 250

11.3.2 快速排序 251

11.4 合并排序 256

11.4.1 两路合并排序 256

11.4.2 合并排序的迭代算法 256

11.4.3 链表上的合并排序 258

11.5 选择排序 261

11.5.1 简单选择排序 262

11.5.2 堆排序 263

11.6 排序算法的时间下界 264

11.7 基数排序 265

小结 269

习题11 269

第12章 文件和外排序 271

12.1 辅助存储器简介 271

12.1.1 主存储器和辅助存储器 271

12.1.2 磁盘存储器 271

12.2 文件 273

12.2.1 文件的基本概念 273

12.2.2 文件的组织方式 273

12.2.3 C语言文件 277

12.3 文件的索引结构 278

12.3.1 静态索引结构 278

12.3.2 动态索引结构 279

12.4 外排序 280

12.4.1 外排序的基本过程 280

12.4.2 初始游程的生成 280

12.4.3 多路合并 282

12.4.4 最佳合并树 284

小结 285

习题12 286

第13章 实习指导和实习题 287

13.1 实习目的和要求 287

13.1.1 实习目的 287

13.1.2 实习要求 287

13.2 实习步骤 288

13.3 实习报告 288

13.4 实习题 289

实习1 数组操作 289

实习2 链表操作 290

实习3 表达式计算 290

实习4 队列运算和用户界面设计 291

实习5 线性表运算及应用 291

实习6 一元多项式的相加和相乘 291

实习7 对称矩阵的压缩存储 292

实习8 稀疏矩阵的三元组表 292

实习9 稀疏矩阵的正交链表 292

实习10 字符串运算和文本处理 293

实习11 二叉树的基本运算和应用 293

实习12 哈夫曼编码和译码系统 294

实习13 B-树检索 294

实习14 散列表检索 295

实习15 图运算及其应用 295

实习16 内排序算法及其性能比较 296

实习17 外排序 296

13.5 实习报告范例 297

13.5.1 实习题：表达式计算 297

13.5.2 实习报告 297

13.6 上机考核 303

13.6.1 考核目的 303

13.6.2 考核目标 303

13.6.3 考核要求 303

13.6.4 软件环境 303

13.6.5 考核方式 303

13.6.6 试题样例 303

附录A 软件工程概述 305

附录B 考研大纲和教材内容 312

附录C 专用名词中英文对照表 316

参考文献 322