前言

前言

数据结构与算法并不只是抽象的概念,掌握好的话可以写出更高效、运行得更快的代码,这对于如今盛行的网页和移动应用开发来说尤为重要。如果你最近一次使用算法是在大学课堂上或求职面试时,那你应该还没见识到它的真正威力。

这个主题的大多数资料都有一种通病——晦涩难懂。满纸的数学术语,搞得除非你是数学家,不然真不知道作者在说什么。即使是一些声称“简化”过的书,看起来也好像已经认定读者都掌握了高深的数学知识。这就导致了很多人对此主题望而生畏,以为自己的智商不足以理解这些概念。

但事实上,数据结构与算法都是能够从常识推导出来的。数学符号只是一种特定的语言,数学里的一切都是可以用常识去解释的。本书用到的数学知识就只有加减乘除和指数,所有的概念都可以用文字来解释。我还会采用大量的图表以便读者轻松地理解。

一旦掌握了这些知识,你就能写出高效、快速、优雅的代码。你还能权衡各种写法的优劣,并能合理判断适用于给定情况的最优方案。

一些读者可能是因为学校开设了这门课或者为准备技术面试而阅读本书的。本书对计算机科学基础的解释能有效地帮助你达到目的。此外,我还鼓励你正视这些概念在日常编程中的实用价值。为此,我将书中阐述的概念与实际结合,其中的用例都可供大家使用。

目标读者

本书适合以下读者。

  • 有编程基础的初级开发者,想学习一些计算机科学的基本概念,以优化代码,提高编程技能。
  • 自学编程的开发者,没学过正规的计算机科学课程(或者学过但忘光了),现在想利用数据结构与算法使代码更灵活、更具扩展性。
  • 计算机科学专业的学生,希望找到用简洁语言阐述数据结构与算法的资料。这本书很适合作为“经典”教材的补充参考。
  • 开发人员,平时也许没怎么利用过数据结构与算法的知识,希望复习这些概念为下次技术面试做准备。

为了使本书不特定于某种语言,我们的示例代码会用到多种语言,包括Ruby、Python和JavaScript,了解这些语言的话可能会学得更快。不过,这些示例代码都没有严格按照惯用语法来写,避免读者因看不懂某种语言的特有语法而困惑。所以即使不太熟悉某种语言,也还是能跟得上的。

本书内容

本书的主旨就是数据结构与算法,具体内容如下。

第1章和第2章,解释数据结构和算法是什么,并探索时间复杂度这一判断算法效率的概念。此过程中还会经常提及数组、集合和二分查找。

第3章,以老奶奶都听得懂的方式去揭示大O记法的本质。因为大O记法全书都会用到,所以对这一章的理解非常重要。

第4章、第5章和第6章,进一步探索大O记法,并以实例来演示如何利用它来加快代码运行速度。这一路上,我们还会提到各种排序算法,包括冒泡排序、选择排序和插入排序。

第7章和第8章会再探讨几种数据结构,包括散列表、栈和队列,展示它们对代码速度和可读性的影响,并学会用其解决实际问题。

第9章会介绍递归,计算机科学中的核心概念。我们会对其进行分解,考察它在某些问题上的利用价值。第10章会运用递归来实现一些飞快的算法,例如快速排序和快速选择,提升读者的算法开发能力。

第11章、第12章和第13章会探索基于结点的数据结构,包括链表、二叉树和图,并展示它们在各种应用中的完美表现。

最后一章,第14章,介绍空间复杂度。当程序运行环境的内存空间不多,或处理的数据量很大时,理解空间复杂度便显得特别重要。

如何阅读本书

你得按顺序从第1章开始读起。虽然有些书允许读者单独翻阅某些章节,或跳过某些章节,但这本不是。本书的每一章都假定你已经读过其之前的内容,而且全书内容也确实是精心安排的,使得你在按序阅读的过程中逐步提高认知水平。

此外还有很重要的一点:为了易于大家理解,当介绍一个概念时,我可能不会把它一下子全部展露出来。有时候,理解一个复杂概念的最好方法就是把它拆分成小块,并且在完全明白某一块以后才去着手其他部分。要是我在描述某个术语时说得比较模糊,千万别把它当成一个完整的定义,想看清该术语的全貌,你得读完关于它的所有内容才行。

这其实是一种权衡:为了便于理解,我只能把一个概念先极度简化,然后再一步步去完善。当然这就导致了有些句子写得不够彻底、不够学术,或不够精确。但无须担心,因为到最后你一定能对它有一个完整的印象。

在线资源

本书网址是https://pragprog.com/book/jwdsal。读者可从中获取更多关于本书的信息,或以下面的方式互动:

  • 在论坛跟其他读者和笔者交流;
  • 提交勘误1,改进本书。

1本书中文版勘误请到http://ituring.cn/book/2538查看和提交。——编者注

各章习题以及示例代码下载见http://commonsensecomputerscience.com2

2读者也可以到图灵社区本书页面下载示例代码,网址是http://ituring.cn/book/2538。——编者注

电子书

扫描如下二维码,即可购买本书电子版。

致谢

虽然写书好像只是个人的事情,但这个过程如果没有大家的支持,是不可能完成的。我想感谢所有帮助过我的人。

感谢我的妻子Rena,谢谢你一直陪伴我,给予我情感上的支持。当我像隐士般久坐写书时,你帮我料理好了一切事情。感谢我可爱的孩子们——Tuvi、Leah和Shaya,谢谢你们耐心地等候我完成这本“算发”书。是的,我终于写完了。

感谢我的父母——Howard Wengrow先生和Debbie Wengrow夫人,谢谢你们当初激发了我对计算机编程的兴趣,并鼓励我追逐梦想。你们可能不知道,正是你们作为9岁生日礼物送给我的计算机,为我奠定了职业生涯的基础,也为如今这本书埋下了种子。

当初我给Pragmatic出版公司提交草稿时,我认为自己写得挺不错。但融合了诸位优秀编辑的各种专业意见和要求之后,我发现它比初稿好太多了。感谢总编Brian MacDonald,你教会了我如何写书,你的见解使得本书的每一章都更为清晰,可以说本书随处可见你的思想印记。感谢我的责任编辑Susannah Pfalzer,你让我心中显现了成书的模样,把只有理论的草稿变成一本真正能给每一位程序员阅读的书。感谢出版商Andy Hunt和Dave Thomas,谢谢你们信任我的作品,谢谢你们把Pragmatic打造成世界上最值得投稿的出版社。

感谢Colleen McGuckin这位天才软件开发者以及艺术家,谢谢你把我简陋的图画变成了精美的数码图片。没有这些你以才华和技巧细心描绘的图片,这本书可能一文不值。

让我感到很幸运的是,这本书还经过了不少专家的评审。各位的反馈都非常有益,令本书内容之精确达到了极致。非常感谢你们的贡献:Aaron Kalair、Alberto Boschetti、Alessandro Bahgat、Arun S. Kumar、Brian Schau、Daivid Morgan、Derek Graham、Frank Ruiz、Ivo Balbaert、Jasdeep Narang、Jason Pike、Javier Collado、Jeff Holland、Jessica Janiuk、Joy McCaffrey、Kenneth Parekh、Matteo Vaccari、Mohamed Fouad、Neil Hainer、Nigel Lowry、Peter Hampton、Peter Wood、Rod Hilton、Sam Rose、Sean Lindsay、Stephan K?mper、Stephen Orr、Stephen Wolff和Tibor Simic。

我还要感谢所有Actualize的同事、同学和校友。感谢大家通过各种方式为这个本属于Actualize内部的项目做出了贡献。特别感谢Luke Evans,是他让我萌生了写书的想法。

感谢大家让此书成真。

Jay Wengrow

jay@actualize.co

2017年8月

目录

  • 版权声明
  • 前言
  • 第 1 章 数据结构为何重要
  • 第 2 章 算法为何重要
  • 第 3 章 大O记法
  • 第 4 章 运用大O来给代码提速
  • 第 5 章 用或不用大O来优化代码
  • 第 6 章 乐观地调优
  • 第 7 章 查找迅速的散列表速的散列表
  • 第 8 章 用栈和队列来构造灵巧的代码
  • 第 9 章 递归
  • 第 10 章 飞快的递归算法
  • 第 11 章 基于结点的数据结构
  • 第 12 章 让一切操作都更快的二叉树
  • 第 13 章 连接万物的图
  • 第 14 章 对付空间限制