跳转至

0.1   关于本书

本项目旨在创建一本开源、免费、对新手友好的数据结构与算法入门教程。

  • 全书采用动画图解,内容清晰易懂、学习曲线平滑,引导初学者探索数据结构与算法的知识地图。
  • 源代码可一键运行,帮助读者在练习中提升编程技能,了解算法工作原理和数据结构底层实现。
  • 提倡读者互助学习,欢迎大家在评论区提出问题与分享见解,在交流讨论中共同进步。

0.1.1   读者对象

若你是算法初学者,从未接触过算法,或者已经有一些刷题经验,对数据结构与算法有模糊的认识,在会与不会之间反复横跳,那么本书正是为你量身定制的!

如果你已经积累一定的刷题量,熟悉大部分题型,那么本书可助你回顾与梳理算法知识体系,仓库源代码可以当作“刷题工具库”或“算法字典”来使用。

若你是算法“大神”,我们期待收到你的宝贵建议,或者一起参与创作。

前置条件

你需要至少具备任一语言的编程基础,能够阅读和编写简单代码。

0.1.2   内容结构

本书的主要内容如图 0-1 所示。

  • 复杂度分析:数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示例等。
  • 数据结构:基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。
  • 算法:搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤和示例问题等。

图 0-1   本书主要内容

图解 0-1:全书知识地图

按主题回查全书的数据结构、复杂度分析和算法知识。

导图左侧为数据结构板块,右上为复杂度分析,右下为算法。三个板块分别有 7、3、6 个主题分支,共 16 个;连线表示主题归属,不规定唯一阅读顺序。图中没有标章节号。

下方三张表分别对应三个板块;先选择板块表,再按主题行标题查找各分支的概念、实现和例题。其中数据结构表的首行“数据结构”是与板块同名的概述分支。

知识地图:数据结构板块的 7 个主题
主题分支内容与例题
数据结构逻辑结构与物理结构;基本数据类型、数字编码与字符编码。
数组与链表连续存储与分散存储方式、操作方法与优缺点对比、基于动态数组实现列表、计算机内存与缓存。
栈与队列先入后出栈、先入先出队列、双向队列,以及基于数组与链表实现栈和队列。
哈希表工作原理与基于数组实现;哈希冲突与链式地址、开放寻址;哈希算法用途与设计目标。
树完美、完全、完满与平衡二叉树;链表与数组表示对比;层序、前序、中序与后序遍历;二叉搜索树与 AVL 树。
堆小顶堆、大顶堆与优先队列;基于数组实现堆与建堆操作;Top-k 问题。
图有向图、连通图与有权图;邻接表与邻接矩阵表示对比;广度优先遍历与深度优先遍历。
知识地图:复杂度分析板块的 3 个主题
主题分支内容与例题
迭代与递归for 循环、while 循环与嵌套循环;递归调用栈、尾递归与递归树;迭代与递归对比。
时间复杂度函数渐近上界;推算方法与常见类型;最差、最佳与平均时间复杂度。
空间复杂度推算方法与常见类型;权衡时间与空间。
知识地图:算法板块的 6 个主题
主题分支内容与例题
搜索暴力搜索(线性搜索、广度与深度优先搜索);高效搜索(二分查找、哈希查找、树查找);搜索算法的选取。
排序评价维度包括就地性、稳定性、自适应性、是否基于比较;按原图分支依次归入“遍历”(选择排序、冒泡排序、插入排序)、“分治”(快速排序、归并排序、堆排序)和“非比较”(桶排序、计数排序、基数排序)。
分治问题特性与判断方法;例题包括二分、构建树、汉诺塔。
回溯问题特性与框架代码;例题包括全排列、子集和、n 皇后。
动态规划暴力搜索、记忆化递归与递推;重叠子问题、最优子结构与无后效性;问题判断方法与求解步骤;例题包括 0-1 背包、完全背包、编辑距离。
贪心问题特性与解题步骤;例题包括分数背包、最大容量、最大切分乘积。

0.1.3   致谢

本书在开源社区众多贡献者的共同努力下不断完善。感谢每一位投入时间与精力的撰稿人,他们是(按照 GitHub 自动生成的顺序):krahets、coderonion、Gonglja、nuomi1、Reanon、justin-tse、hpstory、danielsss、curtishd、night-cruise、S-N-O-R-L-A-X、rongyi、msk397、gvenusleo、khoaxuantu、rivertwilight、K3v123、gyt95、zhuoqinyue、yuelinxin、Zuoxun、mingXta、Phoenix0415、FangYuan33、GN-Yu、longsizhuo、pengchzn、QiLOL、Cathay-Chen、guowei-gong、xBLACKICEx、IsChristina、JoseHung、qualifier1024、hello-ikun、magentaqin、Guanngxu、thomasq0、sunshinesDL、L-Super、Transmigration-zhou、WSL0809、Slone123c、lhxsm、yuan0221、what-is-me、theNefelibatas、Shyam-Chen、sangxiaai、longranger2、codeberg-user、xiongsp、JeffersonHuang、prinpal、seven1240、Wonderdch、malone6、xiaomiusa87、gaofer、bluebean-cloud、a16su、SamJin98、hongyun-robot、nanlei、XiaChuerwu、yd-j、iron-irax、mgisr、steventimes、junminhong、heshuyue、danny900714、Nigh、Dr-XYZ、MolDuM、XC-Zero、reeswell、PXG-XPG、NI-SW、Horbin-Magician、Enlightenus、YangXuanyi、xjr7670、beatrix-chan、DullSword、qq909244296、iStig、boloboloda、hts0000、gledfish、fbigm、echo1937、jiaxianhua、wenjianmin、keshida、kilikilikid、lclc6、lwbaptx、linyejoe2、liuxjerry、szu17dmy、dshlstarr、Yucao-cy、coderlef、czruby、bongbongbakudan、beintentional、ZongYangL、ZhongYuuu、ZhongGuanbin、hezhizhen、linzeyan、ZJKung、JTCPOWI、KawaiiAsh、luluxia、xb534、ztkuaikuai、yw-1021、ElaBosak233、baagod、zhouLion、yishangzhang、yi427、yanedie、yabo083、weibk、wangwang105、th1nk3r-ing、tao363、4yDX3906、syd168、sslmj2020、smilelsb、siqyka、selear、sdshaoda、Xi-Row、popozhu、nuquist19、noobcodemaker、XiaoK29、chadyi、lyl625760、lucaswangdev、llql1211、0130w、shanghai-Jerry、EJackYang、Javesun99、eltociear、lipusheng、KNChiu、BlindTerran、ShiMaRing、lovelock、FreddieLi、FloranceYeh、fanchenggang、gltianwen、goerll、nedchu、curly210102、CuB3y0nd、KraHsu、CarrotDLaw、youshaoXG、bubble9um、Asashishi、Asa0oo0o0o、fanenr、eagleanurag、akshiterate、52coder、foursevenlove、KorsChen、hopkings2008、yang-le、realwujing、Evilrabbit520、Umer-Jahangir、Turing-1024-Lee、Suremotoo、paoxiaomooo、Chieko-Seren、Senrian、Allen-Scai、19santosh99、ymmmas、Risuntsy、Richard-Zhang1019、RafaelCaso、qingpeng9802、primexiao、Urbaner3、codetypess、nidhoggfgg、MwumLi、CreatorMetaSky、martinx、ZnYang2018、hugtyftg、logan-qiu、psychelzh、Kunchen-Luo、Keynman 和 KeiichiKasai。

本书的代码审阅工作由 coderonion、curtishd、Gonglja、gvenusleo、hpstory、justin-tse、khoaxuantu、krahets、night-cruise、nuomi1、Reanon 和 rongyi 完成(按照首字母顺序排列)。感谢他们付出的时间与精力,正是他们确保了各语言代码的规范与统一。

本书的英文版由 yuelinxin、K3v123、magentaqin、QiLOL、Phoenix0415、SamJin98、yanedie、RafaelCaso、pengchzn 和 thomasq0 审阅;日文版由 eltociear 审阅;俄文版由 И. А. Шевкун 和 Yuyan Huang 审阅;繁体中文版由 Shyam-Chen 和 Dr-XYZ 审阅。正是因为他们的贡献,这本书才能够服务于更广泛的读者群体,感谢他们。

本书的 ePub 电子书生成工具由 zhongfq 开发。感谢他的贡献,为读者提供了更灵活的阅读方式。

在本书的创作过程中,我得到了许多人的帮助。

  • 感谢我在公司的导师李汐博士,在一次畅谈中你鼓励我“快行动起来”,坚定了我写这本书的决心;
  • 感谢我的女朋友泡泡作为本书的首位读者,从算法小白的角度提出许多宝贵建议,使得本书更适合新手阅读;
  • 感谢腾宝、琦宝、飞宝为本书起了一个富有创意的名字,唤起大家写下第一行代码“Hello World!”的美好回忆;
  • 感谢校铨在知识产权方面提供的专业帮助,这对本开源书的完善起到了重要作用;
  • 感谢苏潼为本书设计了精美的封面和 logo ,并在我的强迫症的驱使下多次耐心修改;
  • 感谢 @squidfunk 提供的排版建议,以及他开发的开源文档主题 Material-for-MkDocs 。

在写作过程中,我阅读了许多关于数据结构与算法的教材和文章。这些作品为本书提供了优秀的范本,确保了本书内容的准确性与品质。在此感谢所有老师和前辈的杰出贡献!

本书倡导手脑并用的学习方式,在这一点上我深受《动手学深度学习》的启发。在此向各位读者强烈推荐这本优秀的著作。

衷心感谢我的父母,正是你们一直以来的支持与鼓励,让我有机会做这件富有趣味的事。

欢迎在评论区留下你的见解、问题或建议