PYTHON语言程序设计（进阶篇）（原书第3版）

本书旨在采用以基础为先的教学方法，帮助学生在更广泛的情境中学习问题解决思路和程序设计方法，从而创建高效、优雅的代码，适用于Python程序设计和数据结构入门课程。书中首先介绍选择、循环和函数等基本编程概念和技巧，然后才引入自定义类。本书还配有不同难度的问题和练习，涵盖有趣的应用领域，以激发灵感，激励学生学习。第3版新增了数据结构主题，内容、示例和练习均与主流趋势保持同步。
本书中文版分为基础篇和进阶篇，基础篇对应原书的第1~14章，进阶篇对应原书的第15~23章，便于教师按需选择教材。
本书特色
以问题驱动、基础为先的方法进行介绍，侧重于问题解决思路，而非语法。
从基础开始，循序渐进地讲解，先教授基本概念和技巧，再引入自定义类。
涵盖从基础到面向对象程序设计，从简单函数到STL，再到简单数据类型和经典结构的广泛主题。
编程练习按难度分组，为学生提供大量实践和应用技能的机会。
书中有丰富的来自各个领域的例子和问题，为学习概念提供了有趣的背景。
采用灵活的章节顺序，允许教师跳过或稍后处理图形内容。

本书首先介绍Python基础知识，在带领读者编写自定义类之前，先介绍关于选择结构、循环结构和函数的基本编程概念和技术。然后介绍如何使用Python解决问题。不同难度的练习和问题涵盖了多个有趣的应用领域。本书包含大量练习题，指导读者创建高效、优雅的代码，在实践中掌握编程技巧。第3版新增了关于数据结构的内容，并更新了大量示例和练习。

Y. Daniel Liang:普度大学终身教授，阿姆斯特朗亚特兰大州立大学计算机科学系教授。他所编写的Java教程在美国大学Java课程中采用率最高，同时他还兼任Prentice Hall Java系列丛书的编辑。梁勇（Y. Daniel Liang），阿姆斯特朗亚特兰大州立大学计算机科学系Yamacraw教授。之前曾是普渡大学计算机科学系副教授，并曾两次获得普渡大学大学杰出研究奖。他所编写的Java教程在美国大学Java课程中采用率最高。

目　　录<br />Introduction to Python Programming and Data Structures, Third Edition<br />译者序<br />前言<br />作者简介<br />第15章　递归　　1<br />15.1　概述　　1<br />15.2　案例研究：计算阶乘　　2<br />15.3　案例研究：计算斐波那契数　　4<br />15.4?使用递归求解问题　　6<br />15.5?递归辅助函数　　7<br />15.5.1?选择排序算法　　8<br />15.5.2?二分查找算法　　9<br />15.6?案例研究：获取目录的大小　　11<br />15.7?案例研究：汉诺塔　　12<br />15.8?案例研究：分形图形　　15<br />15.9?案例研究：八皇后问题　　18<br />15.10?递归和迭代的比较　　20<br />15.11?尾递归　　21<br />关键术语　　22<br />本章总结　　22<br />编程练习　　22<br />第16章　开发高效的算法　　 34<br />16.1?概述　　34<br />16.2?使用大O表示法衡量算法的<br />效率　　35<br />16.3?示例：确定大O表示法　　36<br />16.4?分析算法的时间复杂度　　39<br />16.4.1?二分查找算法　　39<br />16.4.2?选择排序算法　　39<br />16.4.3?汉诺塔问题算法　　40<br />16.4.4?常见的递推关系　　41<br />16.4.5?比较常见的增长函数　　41<br />16.5?使用动态规划求解斐波那契数　　42<br />16.6?使用欧几里得算法计算最大公<br />约数　　44<br />16.7?案例研究：寻找素数的高效算法　　47<br />16.8?使用分而治之方法寻找距离最近的点对　　53<br />16.9?使用回溯法求解八皇后问题　　56<br />16.10?计算几何：寻找一个凸包　　59<br />16.10.1?礼品包装算法　　59<br />16.10.2?Graham算法　　60<br />16.11?字符串匹配　　62<br />16.11.1?穷举算法　　62<br />16.11.2?Boyer-Moore算法　　63<br />16.11.3?Knuth-Morris-Pratt算法　　67<br />关键术语　　71<br />本章总结　　71<br />编程练习　　71<br />第17章　排序算法　　76<br />17.1?概述　　76<br />17.2?插入排序算法　　76<br />17.3?冒泡排序算法　　79<br />17.4?归并排序算法　　81<br />17.5?快速排序算法　　84<br />17.6?堆排序算法　　88<br />17.6.1?对堆进行排序　　89<br />17.6.2?添加一个新的节点　　89<br />17.6.3?移除根节点　　90<br />17.6.4?Heap类　　92<br />17.6.5?使用Heap类执行排序　　94<br />17.6.6?堆排序算法的时间复杂度　　94<br />17.7?桶排序算法和基数排序算法　　95<br />关键术语　　97<br />本章总结　　97<br />编程练习　　97<br />第18章　链表、栈、队列和优先级<br />队列　　101<br />18.1?概述　　101<br />18.2?链表　　101<br />18.3?LinkedList类　　104<br />18.4?实现LinkedList类　　105<br />18.4.1?实现addFirst(e)　　106<br />18.4.2?实现addLast(e)　　107<br />18.4.3?实现insert(index,e)　　108<br />18.4.4?实现removeFirst()　　109<br />18.4.5?实现removeLast()　　109<br />18.4.6?实现removeAt(index)　　111<br />18.4.7?LinkedList的源代码　　112<br />18.5?列表和链表的比较　　115<br />18.6?链表的变体　　116<br />18.7?迭代器　　117<br />18.8?生成器　　120<br />18.9?栈　　121<br />18.10?队列　　123<br />18.11?优先级队列　　125<br />18.12?案例研究：表达式求值　　126<br />关键术语　　129<br />本章总结　　130<br />编程练习　　130<br />第19章　二叉搜索树　　133<br />19.1　概述　　133<br />19.2　二叉搜索树基础　　133<br />19.3?二叉搜索树的表示　　134<br />19.4　在二叉搜索树中搜索元素　　135<br />19.5　在二叉搜索树中插入一个元素　　136<br />19.6　树的遍历　　137<br />19.7　BST类　　138<br />19.8　删除二叉搜索树中的元素　　143<br />19.9　树的可视化　　148<br />19.10　案例研究：数据压缩　　152<br />关键术语　　156<br />本章总结　　156<br />编程练习　　156<br />第20章　AVL树　　160<br />20.1　概述　　160<br />20.2　重新平衡树　　160<br />20.3　为AVL树设计类　　163<br />20.4　重写insert方法　　164<br />20.5　实现旋转操作　　165<br />20.6　实现delete方法　　165<br />20.7　AVLTree类　　166<br />20.8　测试AVLTree类　　169<br />20.9　AVL树的最大高度　　172<br />关键术语　　173<br />本章总结　　173<br />编程练习　　173<br />第21章　哈希算法　　175<br />21.1　概述　　175<br />21.2　什么是哈希　　175<br />21.3　哈希函数和哈希码　　176<br />21.4　使用开放寻址处理冲突　　177<br />21.4.1　线性探测　　177<br />21.4.2　二次型探测　　178<br />21.4.3　双重哈希　　179<br />21.5　使用分离链接处理冲突　　181<br />21.6　负载因子和重新哈希　　182<br />21.7　使用哈希算法实现映射　　182<br />21.8　使用哈希算法实现集合　　188<br />关键术语　　192<br />本章总结　　192<br />编程练习　　192<br />第22章　图及其应用　　194<br />22.1　概述　　194<br />22.2　基本的图术语　　195<br />22.3?图的表示　　197<br />22.3.1?顶点的表示　　197<br />22.3.2　边的表示：边列表　　198<br />22.3.3　边的表示：Edge对象　　198<br />22.3.4　边的表示：邻接矩阵　　198<br />22.3.5　边的表示：邻接列表　　199<br />22.4　图的建模　　201<br />22.5　图的可视化　　206<br />22.6　图的遍历　　209<br />22.7　深度优先搜索　　209<br />22.7.1　深度优先搜索算法　　210<br />22.7.2　深度优先搜索算法的实现　　211<br />22.7.3　深度优先搜索的应用　　212<br />22.8　案例研究：连通圆问题　　213<br />22.9　广度优先搜索　　215<br />22.9.1　广度优先搜索算法　　215<br />22.9.2?广度优先搜索算法的实现　　216<br />22.9.3　广度优先搜索的应用　　217<br />22.10　案例研究：九枚硬币反面朝上的<br />问题　　218<br />关键术语　　223<br />本章总结　　223<br />编程练习　　224<br />第23章　加权图及其应用　　228<br />23.1　概述　　228<br />23.2　加权图的表示　　229<br />23.2.1?边列表　　230<br />23.2.2　加权的邻接列表　　230<br />23.3　WeightedGraph类　　231<br />23.4　最小生成树　　235<br />23.4.1　最小生成树算法　　236<br />23.4.2　改进Prim最小生成树算法　　237<br />23.4.3　最小生成树算法的实现　　238<br />23.5　寻找最短路径　　241<br />23.6　案例研究：加权的九枚硬币反面<br />朝上问题　　245<br />关键术语　　248<br />本章总结　　248<br />编程练习　　249<br />附录A　Python关键字　　254<br />附录B　ASCII字符集　　255<br />附录C　数制系统　　256<br />附录D　命令行参数　　261<br />附录E　正则表达式　　264<br />附录F　位运算操作　　270<br />附录G　大O表示法、大Ω表示法和<br />大Θ表示法　　271<br />附录H　运算符的优先顺序表　　272