本书图文并茂、示例丰富,结合136段代码和213幅图表,直观易懂地介绍了算法与数据结构的基础知识,包括数组、查找、栈和队列、递归算法、排序、字符串查找、线性列表、树结构和二分查找树等。本书并非单纯地对算法与数据结构进行介绍,而是致力于让读者掌握编写实用程序的技术。为此,本书提供的示例代码都是实际可运行的程序,理解这些示例程序之后,相信读者的Python编程能力也会有很大的提升。本书各章节末设置有练习题,并在书末给出了答案,据此读者可检测自己对知识的掌握情况,加深理解。
1.136段代码+213幅图表,透彻讲解算法与数据结构基础知识,比课本更生动、更易懂!
2.原版系列累计销量超120万册,荣获日本工学教育协会作品奖。
3.日本编程教育界人才,热销书《明解C语言》作者倾力打造!算法与数据结构入门!
4.双色印刷,版式优美,技术书也能赏心悦目。
柴田望洋(作者)
日本福冈工业大学信息工程学院副教授。在IT界家喻户晓,编写了一系列富有影响力的计算机教材和参考书,如《明解C语言》《明解C语言:中级篇》《明解C++》等。本书荣获日本工学教育协会作品奖。
第 1章 基本算法 1
1-1 算法 2
求三个值中的最大值 2
条件判断和分支 9
流程图符号 11
1-2 循环 14
求1和n之间所有整数之和 14
二值排序和二值交换 16
循环过程中的条件判断(其一) 18
循环过程中的条件判断(其二) 20
循环过程中的条件判断(其三) 21
读取正数 23
边长和面积均为整数的矩形 25
跳过循环和遍历多个范围 27
结构化程序设计 29
多重循环 29
章末问题 35
第 2章 数据结构和数组 37
2-1 数据结构和数组 38
数组的必要性 38
列表和元组 39
通过索引表达式访问 41
通过切片表达式访问 42
数据结构 45
2-2 数组 48
求数组中元素的最大值 48
求数组中元素最大值的函数的实现 49
注释和类型提示 50
构建可复用模块 51
模块测试 51
反转数组中元素的顺序 55
进制转换 58
质数枚举 64
章末问题 72
第3章 查找 75
3-1 查找算法 76
查找和关键字 76
数组查找 76
3-2 线性查找 78
线性查找 78
哨兵法 82
3-3 二分查找 84
二分查找 84
复杂度 88
3-4 散列法 92
对有序数组进行操作 92
散列法 92
散列冲突 93
拉链法 93
开放地址法 102
章末问题 109
第4章 栈和队列 113
4-1 栈 114
栈 114
栈的实现 114
4-2 队列 125
队列 125
使用数组实现简单队列 125
使用环形缓冲区实现队列 126
章末问题 138
第5章 递归算法 141
5-1 递归的基础知识 142
递归 142
阶乘值 142
辗转相除法 145
5-2 递归算法的分析 147
递归算法的分析 147
递归算法的非递归写法 149
5-3 汉诺塔问题 152
汉诺塔问题 152
5-4 八皇后问题 156
八皇后问题 156
摆放皇后 156
分支操作 162
定界操作和分支定界法 163
解决八皇后问题的程序 165
章末问题 167
第 6章 排序 169
6-1 排序 170
排序 170
6-2 直接交换排序 172
直接交换排序(冒泡排序) 172
鸡尾酒排序(双向冒泡排序) 179
6-3 直接选择排序 182
直接选择排序 182
6-4 直接插入排序 184
直接插入排序 184
6-5 希尔排序 188
直接插入排序的特点 188
希尔排序 188
6-6 快速排序 194
快速排序简介 194
分组过程 195
快速排序 197
非递归快速排序 200
枢轴的选择 205
时间复杂度 207
6-7 归并排序 210
有序数组的归并 210
归并排序 212
6-8 堆排序 216
堆 216
堆排序 217
删除根节点后重建堆 217
堆排序的扩展 219
数组堆化 221
堆排序的时间复杂度 224
6-9 计数排序 225
计数排序 225
章末问题 231
第 7章 字符串查找 235
7-1 暴力匹配算法 236
字符串查找 236
暴力匹配算法(直接匹配算法) 236
7-2 KMP算法 241
KMP 算法 241
7-3 Boyer-Moore算法 245
Boyer-Moore 算法 245
章末问题 249
第 8章 线性表 251
8-1 什么是线性表 252
线性表 252
线性表的实现 252
8-2 单链表 254
通过指针实现单链表 254
在程序中使用单链表 266
8-3 通过游标实现单链表 269
通过游标实现单链表 269
数组中的空元素 273
自由列表 274
在程序中使用数组游标版的单链表 276
8-4 双向循环链表 279
循环链表 279
双链表 279
双向循环链表 280
双向循环链表的实现 280
在程序中使用双向循环链表 291
章末问题 294
第 9章 树结构和二叉查找树 297
9-1 树结构 298
树 298
有序树和无序树 299
有序树的查找 299
9-2 二叉树和二叉查找树 302
二叉树 302
完全二叉树 302
二叉查找树 303
二叉查找树的实现 304
在程序中使用二叉查找树 314
章末问题 317
章末问题答案 322
参考文献 324
致谢 325