计算思维与算法入门

目录
前言
第1章 程序设计与计算思维1
1.1 认识计算思维4
1.1.1 分解6
1.1.2 模式识别9
1.1.3 模式概括与抽象11
1.1.4 算法13
1.2 算法的条件15
1.3 课后习题21
第2章 常用数据结构与算法22
2.1 认识数据结构24
2.2 常见的数据结构27
2.3 矩阵与深度学习29
2.3.1 稀疏矩阵33
2.3.2 矩阵相加算法34
2.3.3 矩阵相乘算法34
2.3.4 转置矩阵35
2.4 链表35
2.4.1 单向链表的串接算法37
2.4.2 单向链表节点的删除算法37
2.4.3 在单向链表中添加新节点38
2.4.4 单向链表的反转39
2.5 堆栈40
2.6 队列42
2.6.1 双向队列44
2.6.2 优先队列44
2.7 树结构45
2.7.1 树的基本概念46
2.7.2 二叉树48
2.7.3 树转化为二叉树的算法51
2.7.4 二叉树转化为树的算法53
2.8 图简介54
2.9 哈希表57
2.10 课后习题59
第3章 分治法60
3.1 分治法简介61
3.2 递归法62
3.3 汉诺塔算法63
3.4 快速排序法68
3.5 合并排序法70
3.6 二分查找法71
3.7 课后习题72
第4章 贪心法74
4.1 贪心法简介75
4.2 最小生成树76
4.2.1 Prim算法77
4.2.2 Kruskal算法79
4.3 图的最短路径法81
4.3.1 Dijkstra算法81
4.3.2 A* 算法83
4.3.3 Floyd算法86
4.4 课后习题88
第5章 动态规划法90
5.1 动态规划法简介91
5.2 字符串对比功能93
5.3 AOV网络与拓扑排序94
5.4 AOE网络97
5.5 青蛙跳台阶算法99
5.6 课后习题101
第6章 安全性算法102
6.1 数据加密104
6.1.1 对称密钥加密系统105
6.1.2 非对称密钥加密系统与RSA算法106
6.1.3 认证107
6.1.4 数字签名107
6.2 哈希算法109
6.2.1 除留余数法109
6.2.2 平方取中法111
6.2.3 折叠法112
6.2.4 数字分析法113
6.3 碰撞与溢出处理113
6.3.1 线性探测法114
6.3.2 平方探测法114
6.3.3 再哈希法115
6.4 课后习题116
第7章 树结构的算法118
7.1 二叉树的遍历119
7.2 二叉查找树122
7.3 优化二叉查找树126
7.3.1 扩充二叉树126
7.3.2 哈夫曼树128
7.4 平衡树（AVL树）129
7.5 博弈树——八枚金币问题132
7.6 堆积排序法134
7.7 斐波那契查找法136
7.8 课后习题139
第8章 改变程序功力的经典算法141
8.1 迭代法142
8.1.1 帕斯卡三角算法143
8.1.2 插入排序法145
8.1.3 希尔排序法146
8.1.4 基数排序法147
8.2 枚举法148
8.2.1 3个小球放入盒子150
8.2.2 质数求解算法152
8.2.3 顺序查找法154
8.2.4 冒泡排序法154
8.2.5 选择排序法156
8.3 回溯法158
8.3.1 老鼠走迷宫158
8.3.2 八皇后算法160
8.4 课后习题161
第9章 游戏设计中的算法163
9.1 游戏中的数学与物理算法164
9.1.1 两点距离的算法164
9.1.2 匀速运动166
9.1.3 加速运动167
9.2 图的遍历算法168
9.2.1 路径算法168
9.2.2 深度优先查找算法170
9.2.3 广度优先查找算法172
9.3 碰撞处理算法173
9.3.1 以行进路线来检测174
9.3.2 范围检测176
9.3.3 颜色检测179
9.4 遗传算法182
9.5 课后习题184
附录 课后习题与参考答案185