数据结构思维 前言

前言

原文:Preface

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

本书背后的哲学

数据结构和算法是过去 50 年来最重要的发明之一,它们是软件工程师需要了解的基础工具。但是在我看来,这些话题的大部分书籍都过于理论,过于庞大,也是“自底向上”的:

过于理论

算法的数学分析基于许多简化假设,它们限制了实践中的可用性。这个话题的许多描述都掩盖了简化,并专注于数学。在这本书中,我介绍了这个话题的最实际的子集,并省略或不强调其余的内容。

过于庞大

这些话题的大多数书籍至少有 500 页,有些超过 1000 页。通过关注我认为对软件工程师最有用的话题,我把这本书限制在 200 页以下。

过于“自底向上”

许多数据结构的书籍着重于数据结构如何工作(实现),而不是使用它们(接口)。在这本书中,我从接口开始,“自底向上”。读者在学习如何使用 Java 集合框架中的结构之后,再了解它们的工作原理。

最后,有些书将这个材料展示在上下文之外,缺少动机:这只是另一个的数据结构!我试图使之生动刚起来,通过围绕一个应用程序 - 网页搜索 - 来组织这些话题,它广泛使用数据结构,并且是一个有趣和重要的话题。

这个应用激发了一些话题,通常不会在介绍性数据结构的课中涵盖,包括 Redis 的持久化数据结构。

我已经做出了一些艰难的决定,来进行取舍,但我也做了一些妥协。我包括了大多数读者永远不会使用的一些话题,但是可能在技术面试中,你需要知道这些话题。对于这些话题,我提出了传统的观点和我怀疑的理由。

本书还介绍了软件工程实践的基本方面,包括版本控制和单元测试。大多数章节都包括一个练习,允许读者应用他们学到的内容。每个练习都提供自动化测试,来检查解决方案。对于大多数练习,我在下一章的开头展示我的解决方案。

0.1 预备条件

本书面向计算机科学及相关领域的大学生,专业软件工程师,软件工程培训人员和技术面试准备人员。

在你开始读这本书之前,你应该很熟悉 Java,尤其应该知道如何定义一个扩展现有类的新类,或实现一个interface。如果你不熟悉 Java 了,这里有两本书可以用于起步:

  • Downey 和 Mayfield,《Think Java》(O'Reilly Media,2016),它面向以前从未编程过的人。
  • Sierra 和 Bates,《Head First Java》(O'Reilly Media,2005),它适用于已经知道另一种编程语言的人。

如果你不熟悉 Java 中的接口,你可能需要在 http://thinkdast.com/interface 上完成一个名为“什么是接口”的教程 。

一个词汇注解:“接口”这个词可能会令人困惑。在应用编程接口(API)的上下文中,它指代一组提供某些功能的类和方法。

在 Java 的上下文中,它还指代一个与类相似的语言特性,它规定了一组方法。为了避免混淆,我将使用正常字体中的“接口”来表示接口的一般思想,代码字体的interface用于 Java 语言特性。

你还应该熟悉类型参数和泛型类型。例如,你应该知道如何使用类型参数创建对象,如ArrayList<Integer>。如果不是,你可以在 http://thinkdast.com/types 上了解类型参数。

你应该熟悉 Java 集合框架(JCF​​),你可以阅读 http://thinkdast.com/collections。特别是,你应该知道List interface,以及ArrayListLinkedList类。

理想情况下,你应该熟悉 Apache Ant,它是 Java 的自动化构建工具。你可以在 http://thinkdast.com/anttut 上阅读 Ant 的更多信息。

你应该熟悉 JUnit,它是 Java 的单元测试框架。你可以在 http://thinkdast.com/junit 上阅读更多信息。

处理代码

本书的代码位于 http://thinkdast.com/repo 上的 Git 仓库中 。

Git 是一个“版本控制系统”,允许你跟踪构成项目的文件。Git 控制下的文件集合称为“仓库”。

GitHub 是一个托管服务,为 Git 仓库提供存储和方便的 Web 界面。它提供了几种使用代码的方法:

  • 你可以通过按下Fork(派生)按钮,在 GitHub 上创建仓库的副本。如果你还没有 GitHub 帐户,则需要创建一个。派生之后,你可以在 GitHub 上拥有你自己的仓库,你可以使用它们来跟踪你编写的代码。然后,你可以“克隆”仓库,它将文件的副本下载到你的计算机。
  • 或者,你可以克隆仓库而不进行派生。如果你选择此选项,则不需要 GitHub 帐户,但你无法将更改保存在 GitHub 上。
  • 如果你不想使用 Git,你可以使用 GitHub 页面上的Download(下载)按钮或此链接http://thinkdast.com/zip,以 ZIP 压缩包格式下载代码。

克隆仓库或解压 ZIP 文件后,你应该有一个名为ThinkDataStructures的目录,其中有一个名为code的子目录。

本书中的示例是使用 Java SE 7 开发和测试的。如果你使用的是较旧的版本,一些示例将无法正常工作。如果你使用的是更新版本,那么它们都应该能用。

贡献者

这本书是我为纽约市 Flatiron School 写的课程的一个改编版,它提供了编程和网页开发相关的各种在线课程。他们提供基于这个材料的课程,提供在线开发环境,来自教师和其他学生的帮助,以及结业证书。你可以在 http://flatironschool.com上找到更多信息 。

  • 在 Flatiron School,Joe Burgess,Ann John 和 Charles Pletcher 通过实现和测试,提供了来自初始规范的指导,建议和更正。谢谢你们!
  • 我非常感谢我的技术审校员 Barry Whitman, Patrick White 和 Chris Mayfield,他提出了许多有用的建议,并捕获了许多错误。当然,任何剩余的错误都是我的错,而不是他们的错!
  • 感谢 Olin College 的数据结构和算法课程中的教师和学生,他们读了这本书并提供了有用的反馈。

如果你对文本有任何意见或建议,请发送至:feedback@greenteapress.com

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,504评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,434评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,089评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,378评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,472评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,506评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,519评论 3 413
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,292评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,738评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,022评论 2 329
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,194评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,873评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,536评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,162评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,413评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,075评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,080评论 2 352

推荐阅读更多精彩内容