《零基础学算法(第4版)》从日常生活中常见的实例入手,引领读者进入算法和数据结构的抽象世界。由于数据结构、算法的知识比较抽象,使许多读者望而却步。本书在编写过程中,尽量使用读者容易理解的、简单的语言来描述算法和数据结构,对于一些复杂的内容,采用图文并茂的方式介绍其原理,使读者能很快理解相关知识。第1~5章介绍了常用算法和数据结构的相应代码,第6~8章介绍了使用数据结构和算法解决一些经典问题的程序,第9章介绍了信息学奥赛部分试题的解题代码,第10章给出了与算法和数据结构相关的常见面试题。书中的所有程序都是在Dev-C++开发环境中编写而成的,本书附录简单介绍了该开发环境的使用。
封面图
目录
- 前言
- 上篇算法与数据结构基础
- 第1章基础算法思想1
- 1.1编程的灵魂:数据结构+算法1
- 1.2算法的作用:猜价格游戏2
- 1.2.1算法的作用2
- 1.2.2实例:看商品猜价格2
- 1.3枚举(穷举)算法思想6
- 1.3.1算法思路6
- 1.3.2实例:填数游戏6
- 1.3.3实例:填运算符8
- 1.4递推算法思想11
- 1.4.1算法思路11
- 1.4.2顺推实例:斐波那契数列11
- 1.4.3逆推实例:该存多少钱13
- 1.5递归算法思想14
- 1.5.1算法思路14
- 1.5.2实例:求阶乘15
- 1.5.3实例:数制转换17
- 1.6分治算法思想19
- 1.6.1算法思路19
- 1.6.2实例:乒乓球比赛日程安排20
- 1.7贪婪算法思想23
- 1.7.1算法思路24
- 1.7.2实例:找零钱24
- 1.8试探算法思想26
- 1.8.1算法思路26
- 1.8.2实例:生成彩票号码组合27
- 1.9模拟算法30
- 1.9.1算法思路30
- 1.9.2实例:猜数游戏30
- 1.9.3实例:掷骰子游戏31
- 1.10算法的评价32
- 1.10.1算法评价原则32
- 1.10.2算法的效率33
- 1.11上机实践34
- 第2章简单数据结构36
- 2.1最简单的结构:线性表36
- 2.1.1线性表的概念36
- 2.1.2操作顺序表37
- 2.1.3操作链表44
- 2.1.4实例:用链表制作通讯录53
- 2.2后进先出结构:栈56
- 2.2.1栈的概念56
- 2.2.2操作栈57
- 2.2.3实例:算术表达式求值62
- 2.3先进先出结构:队列68
- 2.3.1什么是队列68
- 2.3.2操作队列69
- 2.3.3循环队列的操作72
- 2.3.4实例:银行排号程序74
- 2.4上机实践77
- 第3章 复杂数据结构79
- 3.1层次关系结构:树79
- 3.1.1树的概念79
- 3.1.2二叉树的概念80
- 3.1.3二叉树的存储82
- 3.1.4操作二叉树84
- 3.1.5遍历二叉树88
- 3.1.6测试二叉树92
- 3.1.7线索二叉树95
- 3.1.8最优二叉树(赫夫曼树)102
- 3.2网状关系:图111
- 3.2.1图的定义和基本术语111
- 3.2.2图的存储115
- 3.2.3图的创建117
- 3.2.4图的遍历123
- 3.2.5最小生成树128
- 3.2.6最短路径132
- 3.3上机实践136
- 第4章常用算法——排序137
- 4.1排序概述137
- 4.1.1排序算法分类137
- 4.1.2数据准备138
- 4.2冒泡排序法139
- 4.2.1冒泡排序法概述139
- 4.2.2改进的冒泡排序法142
- 4.3快速排序法143
- 4.3.1算法描述143
- 4.3.2算法实现144
- 4.4简单选择排序法146
- 4.5堆排序法148
- 4.5.1算法描述148
- 4.5.2算法实现150
- 4.6直接插入排序法152
- 4.6.1算法描述152
- 4.6.2算法实现153
- 4.7希尔(Shell)排序法154
- 4.7.1算法描述154
- 4.7.2算法实现155
- 4.8合并排序法157
- 4.8.1算法描述157
- 4.8.2算法实现158
- 4.9排序算法的选择161
- 4.9.1选择基准161
- 4.9.2各种排序算法的优缺点162
- 4.10上机实践163
- 第5章常用算法——查找164
- 5.1查找的基本概念164
- 5.2简单查找165
- 5.2.1顺序查找165
- 5.2.2折半查找167
- 5.3二叉排序树170
- 5.3.1二叉排序树的定义170
- 5.3.2插入节点170
- 5.3.3查找节点173
- 5.3.4删除节点174
- 5.4索引查找178
- 5.4.1索引的概念178
- 5.4.2索引查找算法180
- 5.5散列表184
- 5.5.1散列表概述184
- 5.5.2构造散列函数185
- 5.5.3处理冲突187
- 5.5.4创建和查找散列表188
- 5.6上机实践190
- 下篇用算法与数据结构解决实际问题
- 第6章数学问题191
- 6.1有趣的整数191
- 6.1.1完数191
- 6.1.2亲密数193
- 6.1.3水仙花数195
- 6.1.4自守数196
- 6.1.5最大公约数和最小公倍数197
- 6.2素数200
- 6.2.1求素数200
- 6.2.2回文数203
- 6.2.3哥德巴赫猜想206
- 6.3阶乘209
- 6.3.1用递归计算阶乘210
- 6.3.2大数阶乘211
- 6.4求π的近似值214
- 6.4.1概率法214
- 6.4.2割圆法216
- 6.4.3公式法217
- 6.4.4计算任意位数的π218
- 6.5方程求解222
- 6.5.1高斯消元法解线性方程组222
- 6.5.2二分法解非线性方程227
- 6.5.3牛顿迭代法解非线性方程228
- 6.6矩阵的运算230
- 6.6.1矩阵的加法和乘法运算230
- 6.6.2多维矩阵转一维矩阵233
- 6.6.3逆矩阵235
- 6.6.4稀疏矩阵238
- 6.7一元多项式的运算240
- 6.7.1多项式加法241
- 6.7.2多项式减法245
- 6.8上机实践248
- 第7章数据结构问题250
- 7.1约瑟夫环250
- 7.2大整数四则运算252
- 7.2.1使用数组进行大整数运算252
- 7.2.2使用链表进行大整数运算264
- 7.3进制转换271
- 7.3.1进制转换的分析272
- 7.3.2进制转换实现代码272
- 7.4括号匹配277
- 7.5中序式转后序式280
- 7.5.1后序表达式280
- 7.5.2算法实现281
- 7.5.3后序表达式求值284
- 7.6停车场管理286
- 7.6.1问题分析287
- 7.6.2算法实现287
- 7.7迷宫求解297
- 7.7.1迷宫问题297
- 7.7.2算法实现297
- 7.7.3求迷宫的所有路径304
- 7.8LZW压缩307
- 7.8.1LZW的相关概念308
- 7.8.2LZW压缩过程308
- 7.8.3LZW压缩的实现310
- 7.8.4LZW解压缩过程314
- 7.8.5解压缩函数315
- 7.8.6集成压缩和解压缩功能318
- 7.9上机实践320
- 第8章经典算法问题321
- 8.1不定方程问题321
- 8.1.1百钱买百鸡321
- 8.1.2存钱利息最大化323
- 8.1.3求阶梯数326
- 8.1.4五家共井327
- 8.1.5鸡兔同笼328
- 8.2推算问题329
- 8.2.1猴子吃桃329
- 8.2.2舍罕王的赏赐330
- 8.3魔术方阵332
- 8.3.1简捷连续填数法332
- 8.3.2双向翻转法335
- 8.3.3井字调整法337
- 8.4智力趣题340
- 8.4.1汉诺塔341
- 8.4.2背包问题345
- 8.4.3马踏棋盘352
- 8.4.4八皇后问题361
- 8.4.5青蛙过河366
- 8.4.6三色旗369
- 8.5趣味游戏371
- 8.5.1取石子游戏372
- 8.5.2生命游戏375
- 8.5.3洗扑克牌379
- 8.5.4黑白棋381
- 8.5.5凑24点游戏391
- 8.5.610点半游戏396
- 8.6上机实践401
- 第9章 信息学奥赛试题精解403
- 9.1NOIP普及组试题精解403
- 9.1.1求级数之和403
- 9.1.2求素数组合406
- 9.1.3计算卒的路线409
- 9.1.4检查校验码411
- 9.1.5排座位413
- 9.1.6击鼓传花416
- 9.1.7绘制模拟立体图418
- 9.1.8公路上的树422
- 9.1.9采药423
- 9.1.10求等价表达式425
- 9.1.11不开心的龙龙429
- 9.1.12孙悟空摘桃431
- 9.1.13FBI树433
- 9.1.14外星人的语言435
- 9.2NOIP提高组试题精解440
- 9.2.1砝码称重440
- 9.2.2阿明的零花钱442
- 9.2.3购买年货445
- 9.2.4调整队形448
- 9.2.5均分纸牌450
- 9.2.6最小矩形面积452
- 9.2.7低价买股票460
- 9.2.8数字金字塔463
- 9.2.9方格取数465
- 9.2.10导弹防御系统468
- 9.3上机实践471
- 第10章 常见面试题及解答473
- 10.1数据结构类面试题473
- 10.1.1选择题473
- 10.1.2编程题475
- 10.2经典算法类面试题482
- 附录Dev-C++开发环境的使用489