数据结构与程序设计 C语言 第2版PDF电子书下载

目录 1

第1章 编程原则 1

1.1 引言 1

1.2 Life游戏 3

1.2.1 Life游戏规则 3

1.2.2 示例 3

1.2.3 解决方案 5

1.2.4 Life游戏主程序 5

1.3 编程风格 9

1.3.1 命名 9

1.3.2 文档及其格式 10

1.3.3 程序的细化和模块化 11

1.3.4 小节练习 13

1.4.1 占位程序 15

1.4 编码、测试及进一步细化 15

1.4.2 计算相邻元胞的数目 16

1.4.3 输入和输出 17

1.4.4 驱动程序 20

1.4.5 程序的跟踪 21

1.4.6 测试程序的原则 22

1.4.7 小节练习 24

1.4.8 编程项目 24

1.5 注意事项 25

1.6 复习题 26

1.7 参考文献 26

1.7.1 C语言 26

1.7.2 编程原则 27

1.7.3 Life游戏 27

2.1.1 Life程序回顾 28

第2章 软件工程介绍 28

2.1 程序维护 28

2.1.2 关于Life程序的新起点和新方法 30

2.1.3 小节练习 31

2.1.4 编程项目 32

2.2 算法研究：Life程序的第二个版本 32

2.2.1 列表：数据结构的说明 32

2.2.2 主程序 35

2.2.3 信息隐藏 38

2.2.4 细化：子程序的开发 38

2.2.5 算法的验证 41

2.2.6 小节练习 43

2.3 编码 43

2.3.1 列表函数 44

2.3.2 错误处理 45

2.3.3 演示和测试 46

2.3.4 小节练习 49

2.3.5 编程项目 50

2.4 Life函数的编码 50

2.4.1 Vivify函数 50

2.4.2 AddNeighbors函数 51

2.4.3 混合函数 52

2.4.4 初始化 52

2.4.5 编程项目 53

2.5 程序分析与比较 53

2.5.1 语句数 53

2.5.2 比较 54

2.6 总结和展望 55

2.5.5 编程项目 55

2.5.4 小节练习 55

2.5.3 时间和空间的平衡 55

2.6.1 Life游戏 56

2.6.2 程序设计 57

2.6.3 C语言 58

2.6.4 编程项目 59

2.7 注意事项 60

2.8 复习题 61

2.9 参考文献 61

2.9.1 软件工程 61

2.9.2 算法验证 62

2.9.3 问题解决 62

第3章 堆栈和递归 63

3.1 堆栈 63

3.1.1 引言 63

3.1.2 第一个示例：线性颠倒 64

3.1.3 信息隐藏 65

3.1.4 堆栈的说明 65

3.1.5 堆栈的实现 67

3.1.6 链接堆栈 69

3.1.7 小节练习 72

3.1.8 编程项目 73

3.2 递归 74

3.2.1 子程序的堆栈图解 74

3.2.2 子程序调用树 74

3.2.3 阶乘：一个递归定义 76

3.2.4 分而治之：汉诺（HANOI）塔 77

3.2.5 小节练习 82

3.2.6 编程项目 82

3.3.1 解决8 王后难题 83

3.3 回溯：推迟工作 83

3.3.2 示例：4王后 84

3.3.3 回溯 85

3.3.4 细化：选择数据结构 86

3.3.5 回溯分析 88

3.3.6 小节练习 89

3.3.7 编程项目 90

3.4 递归法则 90

3.4.1 设计递归算法 90

3.4.2 递归如何工作 91

3.4.3 尾部递归 94

3.4.4 何时不使用递归 96

3.4.5 指南和总结 100

3.4.6 小节练习 100

3.5 注意事项 101

3.6 复习题 102

3.7 参考文献 103

第4章 队列和链表 104

4.1 定义 104

4.2 队列的实现 107

4.3 C语言中的环形队列 110

4.3.1 小节练习 112

4.3.2 编程项目 113

4.4 队列的应用：模拟 114

4.4.1 引言 114

4.4.2 机场的模拟 114

4.4.3 主程序 116

4.4.4 模拟的步骤 118

4.4.5 伪随机数 121

4.4.6 示例结果 123

4.4.7 编程项目 125

4.5 指针和链表 126

4.5.1 引言和综述 126

4.5.2 指针和C语言中的动态内存 128

4.5.3 链表基础 132

4.5.4 小节练习 133

4.6 链接队列 134

4.6.1 小节练习 136

4.6.2 编程项目 137

4.7 应用：多项式算术 137

4.7.1 项目的目的 137

4.7.2 主程序 138

4.7.3 数据结构及其实现 142

4.7.4 读取和写出多项式 143

4.7.5 多项式加法 145

4.7.6 完成项目 147

4.7.7 小节练习 147

4.7.8 编程项目 148

4.8 抽象数据类型及其实现 149

4.8.1 引言 149

4.8.2 通用定义 150

4.8.3 数据说明的细化 152

4.8.4 小节练习 153

4.9 注意事项 153

4.10 复习题 154

4.11 参考文献 154

第5章通 用列表 156

5.1 列表说明 156

5.2.1 连续实现 158

5.2 列表的实现 158

5.2.2 简单的链接实现 159

5.2.3 变更：保持当前位置 163

5.2.4 双向链表 164

5.2.5 实现的比较 166

5.2.6 小节练习 167

5.2.7 编程项目 168

5.3 字符串 168

5.4 应用：文本编辑器 170

5.4.1 说明 171

5.4.2 实现 171

5.4.3 编程项目 178

5.5 数组中的链表 178

5.5.1 方法 179

5.5.2 操作：空间管理 180

5.5.3 其他操作 183

5.5.4 链表的变化 184

5.5.5 小节练习 184

5.6 排列 186

5.6.1 思想 187

5.6.2 细化 187

5.6.3 通用函数 188

5.6.4 数据结构：优化 188

5.6.5 最终的程序 189

5.6.6 编程项目 191

5.7 注意事项 191

5.8 复习题 192

5.9 参考文献 192

6.1.2 分析 193

6.1.1 键 193

第6章 搜索 193

6.1 搜索：介绍及其表示 193

6.1.3 外部搜索和内部搜索 194

6.1.4 C语言实现 194

6.1.5 参数 194

6.2 顺序搜索 195

6.2.1 算法及函数 195

6.2.2 算法分析 196

6.2.3 测试 197

6.2.4 小节练习 199

6.2.5 编程项目 200

6.3 寄物处：项目 201

6.3.1 介绍和说明 201

6.3.2 演示及测试程序 203

6.3.3 编程项目 205

6.4 二叉搜索 206

6.4.1 算法研究 207

6.4.2 忽略版本 208

6.4.3 识别等式 210

6.4.4 小节练习 211

6.4.5 编程项目 212

6.5 比较树 212

6.5.1 分析n＝10的情况 213

6.5.2 算法推广 215

6.5.3 方法的比较 218

6.5.4 普遍关系 219

6.6.1 优化程序 220

6.6 下限 220

6.5.6 编程项目 220

6.5.5 小节练习 220

6.6.2 任意搜索算法 221

6.6.3 观察2-树 221

6.6.4 搜索下限 223

6.6.5 其他的搜索算法 223

6.6.6 小节练习 224

6.6.7 编程项目 224

6.7 渐近线 224

6.7.1 介绍 224

6.7.2 Big-O表示法 225

6.7.3 Big-O表示法的不精确性 227

6.7.4 通用函数的排序 228

6.8 注意事项 229

6.7.6 编程项目 229

6.7.5 小节练习 229

6.9 复习题 230

6.10 参考文献 230

第7章 排序 232

7.1 介绍和符号 232

7.2 插入排序 233

7.2.1 顺序列表 233

7.2.2 通常的插入排序 234

7.2.3 链接版本 236

7.2.4 分析 237

7.2.5 小节练习 238

7.2.6 编程项目 239

7.3 选择排序 240

7.3.1 算法 240

7.3.2 连续实现 241

7.3.3 分析 242

7.3.4 比较 243

7.3.5 小节练习 243

7.3.6 编程项目 244

7.4 希尔排序 244

7.4.1 小节练习 246

7.4.2 编程项目 246

7.5 下限 246

7.5.1 小节练习 248

7.5.2 编程项目 248

7.6 “分而治之”排序 249

7.6.1 主要思想 249

7.6.2 示例 250

7.6.3 小节练习 253

7.7 链表的归并排序 254

7.7.1 函数 254

7.7.2 合并分析 256

7.7.3 小节练习 258

7.7.4 编程项目 259

7.8 连续列表的快速排序 260

7.8.1 主函数 260

7.8.2 列表的划分 261

7.8.3 快速排序分析 263

7.8.4 快速排序的平均情形分析 265

7.8.5 与归并排序的比较 266

7.8.6 小节练习 267

7.9 堆和堆排序 269

7.9.1 2-树的列表 269

7.8.7 编程项目 269

7.9.2 堆排序 271

7.9.3 堆排序分析 273

7.9.4 优先级队列 274

7.9.5 小节练习 275

7.9.6 编程项目 276

7.10 回顾：方法的比较 276

7.10.1 使用的存储空间 276

7.10.2 计算机时间 276

7.10.3 编程量 276

7.10.4 统计分析 277

7.10.5 实验测试 277

7.10.6 小节练习 277

7.12 复习题 279

7.11 注意事项 279

7.13 参考文献 280

第8章 表和信息检索 282

8.1 引言：突破lgn障碍 282

8.2 矩形数组 283

8.2.1 行优先和列优先顺序 283

8.2.2 下标矩形数组 283

8.2.3 访问表 284

8.2.4 小节练习 284

8.3 各种形状的表 285

8.3.1 三角表 285

8.3.2 不规则表 286

8.3.3 反向表 287

8.3.4 小节练习 288

8.4 表：一种新的抽象数据类型 289

8.4.1 函数 289

8.3.5 编程项目 289

8.4.2 抽象数据类型 290

8.4.3 实现 290

8.4.4 比较 291

8.5 应用：基数排序 291

8.5.1 思想 292

8.5.2 实现 292

8.5.3 分析 295

8.5.4 小节练习 295

8.5.5 编程项目 295

8.6 散列 296

8.6.1 稀疏表 296

8.6.2 选择散列函数 297

8.6.3 利用开放寻址的解决方案 299

8.6.4 冲突的链式解决方案 303

8.6.5 小节练习 305

8.6.6 编程项目 306

8.7 散列分析 307

8.7.1 一个数学娱乐问题的分析 307

8.7.2 计数搜索次数 307

8.7.3 链式方式的分析 308

8.7.4 开放寻址方式的分析 308

8.7.5 理论比较 309

8.7.6 经验比较 310

8.7.7 小节练习 311

8.7.8 编程项目 312

8.8 总结：方法的比较 312

8.9 应用：回顾Life游戏 312

8.9.2 数据结构的声明 313

8.9.1 算法的选择 313

8.9.3 主程序 314

8.9.4 函数 315

8.9.5 编程项目 318

8.10 注意事项 319

8.11 复习题 319

8.12 参考文献 320

第9章 二叉树 321

9.1 二叉树的介绍 321

9.1.1 定义 321

9.1.2 二叉树的遍历 323

9.1.3 二叉树的链接实现 327

9.1.4 小节练习 329

9.2 二叉搜索树 331

9.2.1 顺序列表和实现 332

9.2.2 树搜索 333

9.2.3 二叉搜索树的插入 336

9.2.4 树排序 338

9.2.5 二叉搜索树的删除 339

9.2.6 小节练习 342

9.2.7 编程项目 343

9.3 构建二叉搜索树 346

9.3.1 开始构建 347

9.3.2 声明和主函数 347

9.3.3 插入节点 348

9.3.4 完成任务 349

9.3.5 评估 350

9.3.6 随机搜索树和优化 351

9.3.7 小节练习 352

9.4.1 定义 353

9.4 高度平衡：AVL树 353

9.4.2 节点的插入 354

9.4.3 节点的删除 361

9.4.4 AVL树的高度 363

9.4.5 小节练习 364

9.4.6 编程项目 365

9.5 分裂树：一个自调整数据结构 366

9.5.1 引言 366

9.5.2 分裂步骤 367

9.5.3 分裂算法 369

9.5.4 平摊算法分析：介绍 372

9.5.5 分裂的平摊分析 375

9.5.6 小节练习 379

9.6 注意事项 380

9.5.7 编程项目 380

9.7 复习题 381

9.8 参考文献 382

第10章 多路径树 384

10.1 果园、树和二叉树 384

10.1.1 树的分类 384

10.1.2 顺序树 386

10.1.3 森林和果园 387

10.1.4 形式映射 388

10.1.5 旋转 389

10.1.6 总结 389

10.1.7 小节练习 389

10.2 字典搜索树：trie 391

10.2.1 trie 391

10.2.3 C语言算法 392

10.2.2 键的搜索 392

10.2.4 trie中的插入 393

10.2.5 trie中的删除 394

10.2.6 trie的评论 395

10.2.7 小节练习 395

10.2.8 编程项目 395

10.3 外部搜索：B-树 396

10.3.1 访问时间 396

10.3.2 多路搜索树 396

10.3.3 多路平衡树 397

10.3.4 B-树的插入 397

10.3.5 C语言算法：搜索和插入 399

10.3.6 B-树中的删除 404

10.3.7 小节练习 410

10.3.8 编程项目 411

10.4 红黑树 412

10.4.1 引言 412

10.4.2 定义和分析 412

10.4.3 插入 414

10.4.4 插入的C语言表示 416

10.4.5 小节练习 419

10.4.6 编程项目 419

10.5 树结构程序：游戏中的预测 419

10.5.1 游戏树 419

10.5.2 极大极小方法 420

10.5.3 算法开发 421

10.5.4 细化 422

10.5.5 小节练习 423

10.6 注意事项 424

10.5.6 编程项目 424

10.7 复习题 425

10.8 参考文献 426

第11章 图 427

11.1 数学背景 427

11.1.1 定义和示例 427

11.1.2 无向图 428

11.1.3 有向图 428

11.2 计算机表示 429

11.3 图的遍历 432

11.3.1 方法 432

11.3.2 深度优先算法 433

11.3.3 宽度优先算法 434

11.4.1 问题 435

11.4 拓扑排序 435

11.4.2 深度优先算法 436

11.4.3 宽度优先算法 437

11.5 寻找最短路径的算法 439

11.5.1 问题 439

11.5.2 方法 440

11.5.3 示例 441

11.5.4 实现 442

11.6 作为数据结构的图 443

11.6.1 小节练习 444

11.6.2 编程项目 444

11.7 注意事项 445

11.8 复习题 445

11.9 参考文献 445

12.1 问题 447

第12章 案例分析：波兰表示法 447

12.2 思想 449

12.2.1 表达式树 449

12.2.2 波兰表示法 450

12.2.3 C语言方法 451

12.2.4 小节练习 451

12.3 波兰表达式的求值 452

12.3.1 前缀表达式的求值 452

12.3.2 C语言约定 453

12.3.3 前缀式求值的C函数 453

12.3.4 后缀表达式的求值 454

12.3.5 程序的证明：统计堆栈的入口数 455

12.3.6 后缀表达式的递归求值 458

12.3.7 小节练习 460

12.4 从中缀式转换为波兰式 461

12.4.1 小节练习 466

12.4.2 编程项目 466

12.5 交互式表达式求值程序 467

12.5.1 总体结构 467

12.5.2 数据的表示方法 469

12.5.3 初始化和辅助任务 471

12.5.4 表达式的转换 474

12.5.5 求解表达式的值 482

12.5.6 绘制表达式的图形 483

12.5.7 小节练习 485

12.5.8 编程项目 485

12.6 参考文献 485

附录A 数学方法 487

附录B 递归的消除 505

附录C C语言介绍 528