Python数据结构与算法分析（第2版） (Bradley N. Miller, David L. Ranum) (Z-Library)

📄 File Format: PDF

💾 File Size: 10.3 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

(This page has no text content)

📄 Page 3

图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。

📄 Page 4

Problem Solving with Algorithms and Data Structures Using Python, Second Edition Python数据结构与算法分析 （第 2 版） 人 民 邮 电 出 版 社 北　　京 [美] 布拉德利·米勒 戴维·拉努姆　著 吕　能 刁寿钧　译 图 灵 程 序 设 计 丛 书

📄 Page 5

内 容 提 要 了解数据结构与算法是透彻理解计算机科学的前提。随着 Python 日益广泛的应用，Python 程序员需要 实现与传统的面向对象编程语言相似的数据结构与算法。本书是用 Python 描述数据结构与算法的开山之作， 汇聚了作者多年的实战经验，向读者透彻讲解在 Python 环境下，如何通过一系列存储机制高效地实现各类 算法。通过本书，读者将深刻理解 Python 数据结构、递归、搜索、排序、树与图的应用，等等。 本书适合所有 Python 程序员阅读。 定价：79.00元 读者服务热线：(010)51095183转600　印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广登字 20170147 号 著　　　　[美] 布拉德利 • 米勒 戴维 • 拉努姆 译　　　　吕　能　刁寿钧 责任编辑　谢婷婷 责任印制　周昇亮 人民邮电出版社出版发行　　北京市丰台区成寿寺路11号 邮编　100164　　电子邮件　315@ptpress.com.cn 网址　http://www.ptpress.com.cn 北京　　　　　　印刷 开本：800×1000　1/16 印张：19.25 字数：466千字 2019年 9 月第 1 版 印数：1 — 3 000册 2019年 9 月北京第 1 次印刷 著作权合同登记号　图字：01-2018-0949 号 ◆ ◆ ◆ 图灵社区会员 Aidenlazz() 专享 尊重版权

📄 Page 6

前 言 3 1 2 3 4 5 8 10 13 9 6 7 12 11 版 权 声 明 Authorized translation from the English language edition, titled Problem Solving with Algorithms and Data Structures Using Python, Second Edition by Bradley N. Miller and David L. Ranum, Copyright © 2011. All rights reserved. This book or any portion thereof may not be reproduced, transmitted or used in any manner whatsoever without the express written permission of the authors. Simplified Chinese language edition published by Posts & Telecom Press, Copyright © 2019. 本书中文简体字版由 Franklin, Beedle & Associates 授权人民邮电出版社独家出版。未经出版 者书面许可，不得以任何方式复制或抄袭本书内容。 版权所有，侵权必究。

📄 Page 7

4 前 言

📄 Page 8

前 言 1 1 2 3 4 5 10 6 7 8 9 前 言 致学生 既然你已经开始阅读本书，那么必定对计算机科学感兴趣。你可能也对 Python 这门编程语 言感兴趣，并且已经通过之前的课程或自学有了一些编程经验。不论是何种情况，你肯定都希望 学习更多知识。 本书将介绍计算机科学，也会介绍 Python。然而，书中的内容并不仅仅局限于这两个方面。 学习数据结构与算法对理解计算机科学的本质非常关键。 学习计算机科学与掌握其他高难度学科没什么不同。成功的唯一途径便是循序渐进地学习其 中的核心思想。刚开始接触计算机科学的人，需要多多练习来加深理解，从而为学习更复杂的内 容做好准备。此外，初学者需要建立起自信心。 本书用作数据结构与算法的入门课的教材。数据结构与算法通常是计算机科学专业的第二门 课程，比第一门课程更深入。但是本书的读者对象仍然是初学者，很可能还在第一门课程所教的 基本思想和方法中挣扎，但已经准备好进一步探索这一领域并且进一步练习如何解决问题。 如前所述，本书将介绍计算机科学。它既会介绍抽象数据类型及数据结构，也会介绍如何编 写算法和解决问题。你会学习一系列的数据结构，并且解决各种经典问题。随着学习的深入，你 将反复应用在各章中掌握的工具与技术。 致教师 许多学生在学到这个阶段时会发现，计算机科学除了编程以外还有很多内容。数据结构与算 法可以独立于编程来学习和理解。 本书假定学生已经学过计算机科学的入门课程，但入门课程不一定是用 Python 讲解的。他 们理解基本的结构体，比如分支、迭代以及函数定义，也接触过面向对象编程，并且能够创建和 使用简单的类。同时，学生也能够理解 Python 的基础数据结构，比如序列（列表和字符串）以 及字典。 图灵社区会员 Aidenlazz() 专享 尊重版权

📄 Page 9

2 前 言 本书有三大特点：  通过简单易读的文字而不引入太多编程语法，重点关注如何解决问题，从而向学生介绍 基本的数据结构与算法；  较早介绍基于大 O 记法的算法分析，并且通篇运用；  使用 Python 讲解，以促使初学者能够使用和掌握数据结构与算法。 学生将首先学习线性数据结构，包括栈、队列、双端队列以及列表。我们用 Python 列表以 及链表实现这些数据结构。然后学习与树有关的非线性数据结构，了解连接节点和引用结构（链 表）等一系列技术。最后，学生将通过运用链式结构、链表以及 Python 字典的实现，学习图的 相关知识。对于每一种结构，本书都尽力在使用 Python 提供的內建数据类型的同时展现众多的 实现技巧。这种讲法在向学生揭示各种主要实现方法的同时，也强调 Python 的易用性。 Python 是一门非常适合于讲解算法的语言，语法干净简洁，用户环境直观，基本的数据类型 十分强大和易用。其交互性在不需要额外编写驱动函数的情况下为测试数据结构单元提供了直观 环境。而且，Python 为算法提供了教科书式的表示法，基本上不需要再用伪代码。这一特性有助 于通过数据结构与算法来描述众多与之有关、相当有趣的现代问题。 我们相信，对于初学者来说，投入时间学习与算法和数据结构相关的基本思想是非常有益的。 我们也相信，Python 是一门教授初学者入门的优秀语言。其他许多语言要求学生学习非常高级的 编程概念，这会阻碍他们掌握真正需要的基础知识，从而可能导致失败，而这样的失败并不是 计算机科学本身造成的，而是由于所使用的语言不当。我们的目标是提供一本教科书，量体裁衣 般地聚焦于他们需要掌握的内容，以他们能理解的方式编写，创造和发展一个有助于他们成功的 环境。 本书结构 本书紧紧地围绕着运用经典数据结构和技术来解决问题。下面的组织结构图展示了充分利用 本书的不同方式。

📄 Page 10

前 言 3 1 2 3 4 5 10 6 7 8 9 第 1 章做一些背景知识的准备，我们来复习一下计算机科学、问题解决、面向对象编程以及 Python。基础扎实的学生可以跳过第 1 章，直接学习第 2 章。不过，正所谓温故而知新，适当的 复习和回顾必然是值得的。 第 2 章介绍算法分析的内在思想，重点讲解大 O 记法，还将分析本书一直使用的重要 Python 数据结构。这可以帮助学生理解如何权衡各种抽象数据类型的不同实现。第 2 章也包含了在运行 时使用的 Python 原生类型的实验测量例子。 第 3~7 章全面介绍在经典计算机科学问题中出现的数据结构与算法。尽管在阅读顺序上并无 严格要求，但是许多话题之间都存在一定的依赖关系，所以应该按照本书的顺序学习。比如，第 3 章介绍栈，第 4 章利用栈解释递归，第 5 章利用递归实现二分搜索。 第 8 章是选学内容，包含彼此独立的几节。每一节都与之前的某一章有关。正如前面的组织 结构图所示，你既可以在学习完第 7 章以后再一起学习第 8章中的各节内容，也可以把它们与对应 的那一章放在一起学习。例如，希望更早介绍数组的教师，可以在讲完第 3章以后直接跳到 8.2节。 新版改进  所有的代码都用 Python 3.2 写成。  第 1 章介绍 Python 的集合以及异常处理。  不再使用第三方绘图包。新版中的所有图形都通过原生的 turtle 模块绘制。  新加的第 2 章着重讲解算法分析。此外，这一章还包括对全书出现的关键 Python 数据结 构的分析。  第 3 章新增了关于链表实现的一节。  将“动态规划”一节移到了第 4 章的最后。  更关注图递归算法，包括递归树绘制以及递归迷宫搜索程序。  所有的数据结构源代码都被放在一个 Python 包中，方便学生在完成作业时使用。  新版包含各章例子的完整源代码，从而避免了从各处复制代码的麻烦。  第 6 章改进了二叉搜索树。  第 6 章新增了关于平衡二叉树的一节。  第 8 章介绍 C 风格的数组和数组管理。 致谢 在完成本书的过程中，我们得到了众多朋友的帮助。感谢我们的同事 Steve Hubbard 为本书 的第 1 版提供了大量的反馈，并为新版提供了众多新素材。感谢各地的同事给我们发邮件指出第

📄 Page 11

4 前 言 1 版存在的错误，并且为新版内容提供意见。 感谢迪科拉市 Java John’s 咖啡馆的朋友 Mary 和 Bob，以及其他服务员，他们允许我俩在 Brad 休假期间成为店里的“常驻作者”。David 在常驻咖啡馆写书的那几个月中竟然没有成为咖啡爱好 者。对了，在一间店名带 Java 的咖啡馆里写一本 Python 的书，确实有点讽刺。 感谢 Franklin, Beedle & Associates 出版公司的各位员工，特别是 Jim Leisy 和 Tom Sumner。 与他们的合作非常愉快。最后，还要特别感谢我们两人的妻子 Jane Miller 和 Brenda Ranum。她 们的爱与支持使得本书终成现实。 电子书 扫描如下二维码，即可购买本书电子版。 布拉德利·米勒（Bradley N. Miller） 戴维·拉努姆（David L. Ranum）

📄 Page 12

目 录 i 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 目 录 第 1 章 导论 ..................................................... 1 1.1 本章目标 ................................................... 1 1.2 入门 .......................................................... 1 1.3 何谓计算机科学 ....................................... 1 1.3.1 何谓编程 ....................................... 3 1.3.2 为何学习数据结构及抽象数据 类型 ............................................... 4 1.3.3 为何学习算法 ............................... 4 1.4 Python 基础 ............................................... 5 1.4.1 数据 ............................................... 5 1.4.2 输入与输出 .................................. 16 1.4.3 控制结构 ...................................... 18 1.4.4 异常处理 ...................................... 21 1.4.5 定义函数 ...................................... 23 1.4.6 Python 面向对象编程： 定义类 .......................................... 24 1.5 小结 ......................................................... 37 1.6 关键术语 .................................................. 38 1.7 讨论题 ...................................................... 38 1.8 编程练习 .................................................. 38 第 2 章 算法分析 ............................................ 40 2.1 本章目标 .................................................. 40 2.2 何谓算法分析 .......................................... 40 2.2.1 大 O 记法 ..................................... 43 2.2.2 异序词检测示例 ........................... 46 2.3 Python 数据结构的性能........................... 49 2.3.1 列表 .............................................. 49 2.3.2 字典.............................................. 53 2.4 小结 ......................................................... 55 2.5 关键术语 .................................................. 55 2.6 讨论题 ..................................................... 56 2.7 编程练习 .................................................. 56 第 3 章 基本数据结构 ................................... 57 3.1 本章目标 .................................................. 57 3.2 何谓线性数据结构 .................................. 57 3.3 栈 ............................................................. 58 3.3.1 何谓栈 .......................................... 58 3.3.2 栈抽象数据类型 .......................... 59 3.3.3 用 Python 实现栈 ......................... 60 3.3.4 匹配括号 ...................................... 62 3.3.5 普通情况：匹配符号 ................... 64 3.3.6 将十进制数转换成二进制数 ....... 65 3.3.7 前序、中序和后序表达式 ........... 67 3.4 队列 ......................................................... 75 3.4.1 何谓队列 ...................................... 75 3.4.2 队列抽象数据类型 ....................... 75 3.4.3 用 Python 实现队列 ..................... 76 3.4.4 模拟：传土豆 .............................. 77 3.4.5 模拟：打印任务 .......................... 79 3.5 双端队列 .................................................. 84 3.5.1 何谓双端队列 .............................. 84 3.5.2 双端队列抽象数据类型 ............... 84 3.5.3 用 Python 实现双端队列 .............. 85 3.5.4 回文检测器 .................................. 86

📄 Page 13

2 目 录 3.6 列表 ......................................................... 88 3.6.1 无序列表抽象数据类型 ............... 88 3.6.2 实现无序列表：链表 ................... 89 3.6.3 有序列表抽象数据类型 ............... 97 3.6.4 实现有序列表 .............................. 97 3.7 小结 ....................................................... 100 3.8 关键术语 ............................................... 101 3.9 讨论题 ................................................... 101 3.10 编程练习 .............................................. 102 第 4 章 递归 .................................................. 105 4.1 本章目标 ............................................... 105 4.2 何谓递归 ............................................... 105 4.2.1 计算一列数之和 ........................ 105 4.2.2 递归三原则 ................................ 107 4.2.3 将整数转换成任意进制的 字符串 ........................................ 108 4.3 栈帧：实现递归 .................................... 110 4.4 递归可视化 ............................................ 111 4.5 复杂的递归问题 .................................... 116 4.6 探索迷宫 ............................................... 118 4.7 动态规划 ............................................... 123 4.8 小结 ....................................................... 128 4.9 关键术语 ............................................... 129 4.10 讨论题 ................................................. 129 4.11 编程练习 .............................................. 129 第 5 章 搜索和排序 ..................................... 131 5.1 本章目标 ............................................... 131 5.2 搜索 ....................................................... 131 5.2.1 顺序搜索 .................................... 131 5.2.2 二分搜索 .................................... 134 5.2.3 散列 ........................................... 136 5.3 排序 ....................................................... 145 5.3.1 冒泡排序 .................................... 145 5.3.2 选择排序 .................................... 147 5.3.3 插入排序 .................................... 149 5.3.4 希尔排序 .................................... 151 5.3.5 归并排序 .................................... 153 5.3.6 快速排序 .................................... 156 5.4 小结 ....................................................... 159 5.5 关键术语 ............................................... 160 5.6 讨论题 ................................................... 160 5.7 编程练习 ............................................... 161 第 6 章 树 ...................................................... 163 6.1 本章目标 ............................................... 163 6.2 示例 ....................................................... 163 6.3 术语及定义 ........................................... 166 6.4 实现 ....................................................... 168 6.4.1 列表之列表 ................................ 168 6.4.2 节点与引用 ................................ 171 6.5 二叉树的应用 ........................................ 173 6.5.1 解析树 ....................................... 173 6.5.2 树的遍历 .................................... 179 6.6 利用二叉堆实现优先级队列 ................. 182 6.6.1 二叉堆的操作 ............................ 182 6.6.2 二叉堆的实现 ............................ 183 6.7 二叉搜索树 ........................................... 189 6.7.1 搜索树的操作 ............................ 190 6.7.2 搜索树的实现 ............................ 190 6.7.3 搜索树的分析 ............................ 201 6.8 平衡二叉搜索树 .................................... 202 6.8.1 AVL 树的性能 ........................... 203 6.8.2 AVL 树的实现 ........................... 204 6.8.3 映射实现总结 ............................ 210 6.9 小结 ....................................................... 211 6.10 关键术语 ............................................. 211 6.11 讨论题 ................................................. 211 6.12 编程练习 ............................................. 213 图灵社区会员 Aidenlazz() 专享 尊重版权

📄 Page 14

目 录 3 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 第 7 章 图及其算法 ...................................... 214 7.1 本章目标 ................................................ 214 7.2 术语及定义 ............................................ 215 7.3 图的抽象数据类型 ................................ 216 7.3.1 邻接矩阵 .................................... 216 7.3.2 邻接表 ........................................ 217 7.3.3 实现 ............................................ 218 7.4 宽度优先搜索 ........................................ 220 7.4.1 词梯问题 .................................... 220 7.4.2 构建词梯图 ................................ 221 7.4.3 实现宽度优先搜索 ..................... 223 7.4.4 分析宽度优先搜索 ..................... 226 7.5 深度优先搜索 ........................................ 226 7.5.1 骑士周游问题 ............................ 226 7.5.2 构建骑士周游图 ......................... 227 7.5.3 实现骑士周游 ............................ 229 7.5.4 分析骑士周游 ............................ 231 7.5.5 通用深度优先搜索 ..................... 233 7.5.6 分析深度优先搜索 ..................... 236 7.6 拓扑排序 ................................................ 236 7.7 强连通单元 ............................................ 238 7.8 最短路径问题 ........................................ 241 7.8.1 Dijkstra 算法 .............................. 243 7.8.2 分析 Dijkstra 算法 ...................... 245 7.8.3 Prim 算法 ................................... 245 7.9 小结 ....................................................... 248 7.10 关键术语 .............................................. 249 7.11 讨论题 .................................................. 249 7.12 编程练习 .............................................. 250 第 8 章 附加内容 .......................................... 251 8.1 本章目标 ................................................ 251 8.2 复习 Python 列表 ................................... 251 8.3 复习递归 ................................................ 256 8.3.1 同余定理 .................................... 257 8.3.2 幂剩余 ........................................ 257 8.3.3 最大公因数与逆元 ..................... 258 8.3.4 RSA 算法 ................................... 261 8.4 复习字典：跳表 .................................... 264 8.4.1 映射抽象数据类型 ..................... 265 8.4.2 用 Python 实现字典 ................... 265 8.5 复习树：量化图片 ................................ 274 8.5.1 数字图像概述 ............................ 274 8.5.2 量化图片 .................................... 275 8.5.3 使用八叉树改进量化算法 ......... 277 8.6 复习图：模式匹配 ................................ 284 8.6.1 生物学字符串 ............................ 285 8.6.2 简单比较 .................................... 285 8.6.3 使用图：DFA ............................ 287 8.6.4 使用图：KMP ............................ 288 8.7 小结 ....................................................... 291 8.8 关键术语 ................................................ 291 8.9 讨论题 ................................................... 291 8.10 编程练习 .............................................. 292 附录 A Python 图形包 ................................ 293 附录 B Python 资源 .................................... 294 参考资料 ........................................................... 295

📄 Page 15

4 目 录

📄 Page 16

1.3 何谓计算机科学 1 1 2 3 4 5 8 6 7 导 论 1.1 本章目标  复习计算机科学、编程以及解决问题方面的知识。  理解抽象这一概念及其在解决问题的过程中所发挥的作用。  理解并建立抽象数据类型的概念。  复习 Python。 1.2 入门 自从第一台利用转接线和开关来传递计算指令的电子计算机诞生以来，人们对编程的认识历 经了多次变化。与社会生活的其他许多方面一样，计算机技术的变革为计算机科学家提供了越来 越多的工具和平台去施展他们的才能。高效的处理器、高速网络以及大容量内存等一系列新技术， 要求计算机科学家掌握更多复杂的知识。然而，在这一系列快速的变革之中，仍有一些基本原则 始终保持不变。计算机科学被认为是一门利用计算机来解决问题的学科。 你肯定在学习解决问题的基本方法上投入过大量的时间，并且相信自己拥有根据问题描述构 建解决方案的能力。你肯定也体会到了编写计算机程序的困难之处。大型难题及其解决方案的复 杂性往往会掩盖问题解决过程的核心思想。 本章将为后续各章重点解释两个重要的话题。首先，本章会复习计算机科学以及数据结构与 算法的研究必须符合的框架，尤其是学习这些内容的原因以及为什么说理解它们有助于更好地解 决问题。其次，本章会复习 Python。尽管不会提供完整、详尽的 Python 参考资料，但是会针对 阅读后续各章所需的基础知识及基本思想，给出示例以及相应的解释。 1.3 何谓计算机科学 要定义计算机科学，通常十分困难，这也许是因为其中的“计算机”一词。你可能已经意识 到，计算机科学并不仅是研究计算机本身。尽管计算机在这一学科中是非常重要的工具，但也仅 第 1 章

📄 Page 17

2 第 1 章 导论 仅只是工具而已。 计算机科学的研究对象是问题、解决问题的过程，以及通过该过程得到的解决方案。给定一 个问题，计算机科学家的目标是开发一个能够逐步解决该问题的算法。算法是具有有限步骤的过 程，依照这个过程便能解决问题。因此，算法就是解决方案。 可以认为计算机科学就是研究算法的学科。但是必须注意，某些问题并没有解决方案。尽管 这一话题已经超出了本书讨论的范畴，但是对于学习计算机科学的人来说，认清这一事实非常重 要。结合上述两类问题，可以将计算机科学更完善地定义为：研究问题及其解决方案，以及研究 目前无解的问题的学科。 在描述问题及其解决方案时，经常用到“可计算”一词。若存在能够解决某个问题的算法， 那么该问题便是可计算的。因此，计算机科学也可以被定义为：研究可计算以及不可计算的问题， 即研究算法的存在性以及不存在性。在上述任意一种定义中，“计算机”一词都没有出现。解决 方案本身是独立于计算机的。 在研究问题解决过程的同时，计算机科学也研究抽象。抽象思维使得我们能分别从逻辑视角 和物理视角来看待问题及其解决方案。举一个常见的例子。 试想你每天开车去上学或上班。作为车的使用者，你在驾驶时会与它有一系列的交互：坐进 车里，插入钥匙，启动发动机，换挡，刹车，加速以及操作方向盘。从抽象的角度来看，这是从 逻辑视角来看待这辆车，你在使用由汽车设计者提供的功能来将自己从某个地方运送到另一个地 方。这些功能有时候也被称作接口。 另一方面，修车工看待车辆的角度与司机截然不同。他不仅需要知道如何驾驶，而且更需要 知道实现汽车功能的所有细节：发动机如何工作，变速器如何换挡，如何控制温度，等等。这就 是所谓的物理视角，即看到表面之下的实现细节。 使用计算机也是如此。大多数人用计算机来写文档、收发邮件、浏览网页、听音乐、存储图 像以及打游戏，但他们并不需要了解这些功能的实现细节。大家都是从逻辑视角或者使用者的角 度来看待计算机。计算机科学家、程序员、技术支持人员以及系统管理员则从另一个角度来看待 计算机。他们必须知道操作系统的原理、网络协议的配置，以及如何编写各种脚本来控制计算机。 他们必须能够控制用户不需要了解的底层细节。 上面两个例子的共同点在于，抽象的用户（或称客户）只需要知道接口是如何工作的，而并 不需要知道实现细节。这些接口是用户用于与底层复杂的实现进行交互的方式。下面是抽象的另 一个例子，来看看 Python 的 math 模块。一旦导入这一模块，便可以进行如下的计算。 >>> import math >>> math.sqrt(16) 4.0 >>> 这是一个过程抽象的例子。我们并不需要知道平方根究竟是如何计算出来的，而只需要知道

📄 Page 18

1.3 何谓计算机科学 3 1 2 3 4 5 8 6 7 计算平方根的函数名是什么以及如何使用它。只要正确地导入模块，便可以认为这个函数会返回 正确的结果。由于其他人已经实现了平方根问题的解决方案，因此我们只需要知道如何使用该函 数即可。这有时候也被称为过程的“黑盒”视角。我们仅需要描述接口：函数名、所需参数，以 及返回值。所有的计算细节都被隐藏了起来，如图 1-1 所示。 图 1-1 过程抽象 1.3.1 何谓编程 编程是指通过编程语言将算法编码以使其能被计算机执行的过程。尽管有众多的编程语言和 不同类型的计算机，但是首先得有一个解决问题的算法。如果没有算法，就不会有程序。 计算机科学的研究对象并不是编程。但是，编程是计算机科学家所做工作的一个重要组成部 分。通常，编程就是为解决方案创造表达方式。因此，编程语言对算法的表达以及创造程序的过 程是这一学科的基础。 通过定义表达问题实例所需的数据，以及得到预期结果所需的计算步骤，算法描述出了问题 的解决方案。编程语言必须提供一种标记方式，用于表达过程和数据。为此，编程语言提供了众 多的控制语句和数据类型。 控制语句使算法步骤能够以一种方便且明确的方式表达出来。算法至少需要能够进行顺序执 行、决策分支、循环迭代的控制语句。只要一种编程语言能够提供这些基本的控制语句，它就能 够被用于描述算法。 计算机中的所有数据实例均由二进制字符串来表达。为了赋予这些数据实际的意义，必须要 有数据类型。数据类型能够帮助我们解读二进制数据的含义，从而使我们能从待解决问题的角度 来看待数据。这些內建的底层数据类型（又称原生数据类型）提供了算法开发的基本单元。 举例来说，大部分编程语言都为整数提供了相应的数据类型。根据整数（如 23、654 以及–19） 的常见定义，计算机内存中的二进制字符串可以被理解成整数。除此以外，数据类型也描述了该 类数据能参与的所有运算。对于整数来说，就有加减乘除等常见运算。并且，对于数值类型的数 据，以上运算均成立。 我们经常遇到的困难是，问题及其解决方案都过于复杂。尽管由编程语言提供的简单的控制 语句和数据类型能够表达复杂的解决方案，但它们在解决问题的过程中仍然存在不足。因此，我 图灵社区会员 Aidenlazz() 专享 尊重版权

📄 Page 19

4 第 1 章 导论 们需要想办法控制复杂度以利于找到解决方案。 1.3.2 为何学习数据结构及抽象数据类型 为了控制问题及其求解过程的复杂度，计算机科学家利用抽象来帮助自己专注于全局，从而 避免迷失在众多细节中。通过对问题进行建模，可以更高效地解决问题。模型可以帮助计算机科 学家更一致地描述算法要用到的数据。 如前所述，过程抽象将功能的实现细节隐藏起来，从而使用户能从更高的视角来看待功能。 数据抽象的基本思想与此类似。抽象数据类型（有时简称为 ADT）从逻辑上描述了如何看待数 据及其对应运算而无须考虑具体实现。这意味着我们仅需要关心数据代表了什么，而可以忽略它 们的构建方式。通过这样的抽象，我们对数据进行了一层封装，其基本思想是封装具体的实现细 节，使它们对用户不可见，这被称为信息隐藏。 图 1-2 展示了抽象数据类型及其原理。用户通过利用抽象数据类型提供的操作来与接口交互。 抽象数据类型是与用户交互的外壳。真正的实现则隐藏在内部。用户并不需要关心各种实现细节。 图 1-2 抽象数据类型 抽象数据类型的实现常被称为数据结构，这需要我们通过编程语言的语法结构和原生数据类 型从物理视角看待数据。正如之前讨论的，分成这两种不同的视角有助于为问题定义复杂的数据 模型，而无须考虑模型的实现细节。这便提供了一个独立于实现的数据视角。由于实现抽象数据 类型通常会有很多种方法，因此独立于实现的数据视角使程序员能够改变实现细节而不影响用户 与数据的实际交互。用户能够始终专注于解决问题。 1.3.3 为何学习算法 计算机科学家通过经验来学习：观察他人如何解决问题，然后亲自解决问题。接触各种问题 解决技巧并学习不同算法的设计方法，有助于解决新的问题。通过学习一系列不同的算法，可以 举一反三，从而在遇到类似的问题时，能够快速加以解决。

📄 Page 20

1.4 Python 基础 5 1 2 3 4 5 8 6 7 各种算法之间往往差异巨大。回想前文提到的平方根的例子，完全可能有多种方法来实现计 算平方根的函数。算法一可能使用了较少的资源，算法二返回结果所需的时间可能是算法一的 10 倍。我们需要某种方式来比较这两种算法。尽管这两种算法都能得到结果，但是其中一种可 能比另一种“更好”——更高效、更快，或者使用的内存更少。随着对算法的进一步学习，你会 掌握比较不同算法的分析技巧。这些技巧只依赖于算法本身的特性，而不依赖于程序或者实现算 法的计算机的特性。 最坏的情况是遇到难以解决的问题，即没有算法能够在合理的时间内解决该问题。因此，至 关重要的一点是，要能区分有解的问题、无解的问题，以及虽然有解但是需要过多的资源和时间 来求解的问题。 在选择算法时，经常会有所权衡。除了有解决问题的能力之外，计算机科学家也需要知晓如 何评估一个解决方案。总之，问题通常有很多解决方案，如何找到一个解决方案并且确定其为优 秀的方案，是需要反复练习、熟能生巧的。 1.4 Python 基础 本节将复习 Python，并且为前一节提到的思想提供更详细的例子。如果你刚开始学习 Python 或者觉得自己需要更多的信息，建议你查看本书结尾列出的 Python 资源。本节的目标是帮助你 复习 Python 并且强化一些会在后续各章中变得非常重要的概念。 Python 是一门现代、易学、面向对象的编程语言。它拥有强大的內建数据类型以及简单易用 的控制语句。由于 Python 是一门解释型语言，因此只需要查看和描述交互式会话就能进行学习。 你应该记得，解释器会显示提示符>>>，然后计算你提供的 Python 语句。例如，以下代码显示了 提示符、print 函数、结果，以及下一个提示符。 >>> print("Algorithms and Data Structures") >>> Algorithms and Data Structures >>> 1.4.1 数据 前面提到，Python 支持面向对象编程范式。这意味着 Python 认为数据是问题解决过程中的 关键点。在 Python 以及其他所有面向对象编程语言中，类都是对数据的构成（状态）以及数据 能做什么（行为）的描述。由于类的使用者只能看到数据项的状态和行为，因此类与抽象数据类 型是相似的。在面向对象编程范式中，数据项被称作对象。一个对象就是类的一个实例。 1. 内建原子数据类型 我们首先复习原子数据类型。Python 有两大內建数据类实现了整数类型和浮点数类型，相应 的 Python 类就是 int 和 float。标准的数学运算符，即+、-、*、/以及**（幂），可以和能够 改变运算优先级的括号一起使用。其他非常有用的运算符包括取余（取模）运算符%，以及整除