大话数据结构 溢彩加强版

本书起因
大家好！我是《大话设计模式》（2008年出版）的作者，多年来，承蒙广大读者的厚爱，《大话设计模式》取得了较大的成功。成为当当网终身五星图书，截至本文写作时，销量已经突破30万册，成为国内众多程序员的启蒙书籍之一。
对于这样一件自己喜欢做、可以做得好，而且已经得到了市场广泛认可，为很多朋友提供帮助的事情，我没有理由不继续做下去。这就是我准备再写书的原因。
我曾做过调查，数据结构的学习者大多都有这样的感慨：数据结构很重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困难，学得很累。可我更希望传达这样的信息：数据结构非常有趣，很多算法是智慧的结晶，学习它是去感受计算机编程技术的魅力，在理解掌握它的同时，整个过程都是一种愉悦的心情感受，而非枯燥乏味的一门课程。因此我决定写作一本关于数据结构的有趣的书。
不过现实总比理想来得更“现实”。要想把书写好，谈何容易，我需要突破很多困难……嗐！不管如何，现在您看到了本书，那就说明我已经克服了困难战胜了自己。希望您可以喜欢上这本书。
本书定位
本书的定位是适合读者自学数据结构的书籍，它又区别于教材，希望带给大家另一种阅读体验。
通常讲解数据结构的图书都是以教材的方式呈现。在写作前，我购买或在图书馆借阅了十几本非常好的数据结构相关的教材用来为写作本书做准备。但经过认真阅读后，我发现，它们大多不是一本好的“自学”读物。
我没有轻视这些好书的意思，不过教材和自学读物，所面向的读者是完全不同的。
好的教材应该是提纲挈领、重点突出，一定要留出思考的空间，否则就没必要再听老师上课了。很多内容的讲解是由老师在课堂完成，教材中有练习、课后习题、思考题等，这些大多也可以通过老师来解答。比如我们中学时的语文、数学课本，很薄的一本书通常要用一学期、甚至一年的时间来学习，这就是因为它们是教材而不是自学读物。如果是小说，可能一两天就读完了。
好的自学读物的目标是让初学者“独自”全盘掌握知识。强调“独自”一词，这就说明读者在阅读时，是完全依靠自己的力量来向未知发出挑战。因此书中内容，要么不写，写了就应该写透。如果读者在阅读时总是疑惑重重，那么这本书就有很大的问题了。
基于这样的认识，我决心将《大话数据结构》真正写成一本关于数据结构和算法的自学读物。
本书特色
1. 趣味引导
大部分的编程类图书，在内容上基本都是直奔主题。但是尼采曾说过：“人们无法理解他没有经历过的事情。”换句话说，我们只接受过去早已理解的事物的相关信息。这是一种比较学习过程，在这个过程中，大脑寻找每条信息之间的联系。所以教育专家普遍认为，吸引学生的注意力，比较好的办法是从他们比较熟知的知识开始。
因此在本书中，我会用一个故事、一个趣味题目、一部电影的介绍等形式来作为每一章甚至很多小节的开头，选择的内容也多多少少与要讲的主题内容相关。这并不是多余，而是有意为之。事实上，这样的形式在《大话设计模式》中已经得到了普遍认可。
2. 图文并茂
西方有句谚语，“A picture is worth a thousand words.（一图值千言）”。用上千字描述不清的事，很可能一张图就能解释清楚。
我非常认可这个观点，所以本书虽没有达到每一页都有图，但基本做到了绝大部分讲解都有相关图示，关键算法更是通过多图逐步分解剖析。尽管这带来了写作上的难度，但却可以达到较好的效果。毕竟，读者通过本书开始学习数据结构时，要从一无所知或略知一二到完全理解，甚至掌握应用，需要一个比较艰苦的过程，用大量的图示可以降低这个过程的难度。
3. 代码详解
我在写作中尽量摒弃传统数据结构教材的“重理论思想而轻代码讲解”的做法。在准备数据结构写作时我发现，很多教材对数据结构理论和算法设计思想讲得比较好，可一到实际代码时，有的把代码贴出来加少量注释，有的直接用伪代码形式。这对于上课的学生还好，毕竟有老师在课堂中去详解代码编写原理，可是对于初学数据结构和算法的自学者而言，如果书中不去解释代码某些细节为什么那样编写的原因，甚至代码根本不可能在某个编译器中运行通过，其挫折感是很强烈的。比如即使理解了图结构中的短路径求解原理，也可能无法写出短路径的算法。
我把代码在运行过程中变量的变化融入到整个算法设计思想的讲解中，配合相应的示意图，会帮助大家更加容易理解算法的实质。这种讲解模式在本书的第6～9章的很多复杂算法中都有具体体现，越是复杂的代码越是讲解细致。这算是本书的一个特色，希望对读者有帮助。
4. 形式新颖
我把本书的内容虚构成了一个老师上课的场景，所有内容都通过这位老师表达出来，书中的文字非常口语化，这样做的目的是为了更加直观地让读者感觉，自己是在学习，是在上课。有人可能会说，现在的课堂大都是让人昏昏欲睡，把读者带入上课场景，不是更加让读者犯困吗？我觉得如果你的学习经历中听过一些优秀老师的课，你就不会下这样的结论。好的老师讲课，是可以做到引人入胜的。
有人可能会问，我为什么不用《大话设计模式》中的对话形式，而采用讲课形式呢？这是基于数据结构这门学问的特点考虑的。设计模式主要都是思想体现，通常会仁者见仁、智者见智，用对话展开比较容易；而数据结构中更多的是定义、术语、经典算法等，这些公认的知识，可讨论的地方并不多，更多的是需要把它讲清楚。让两个人在一起讨论某个设计模式的优缺点，会非常合适，而讨论数据结构定义的好坏，就没有太大意义了，不如让一个老师告诉学生数据结构的定义好在哪里更符合实际。因此用传统的讲课形式会好一些。
另外，本书没有习题，有思考的题目也一定会给出某种答案。本书每个复杂知识点的末尾，都会提供另一本书的进一步阅读建议。这也是基于它是一本自学读物的原则。读者阅读本书可能是任何时间任何地方，如果书中存在没有解答的问题，碰到了困难是没法及时找到老师来帮助你的，因此本书尽量避免让读者有这样的困惑存在。需要练习的同学，我觉得还是应该考虑再去买本习题集来学习。学习数据结构和算法，做题和上机写代码非常有必要，从这个角度也说明，阅读完本书其实也只是完成入门而已。
本书既然是以老师上课的形式来进行，那就免不了要融入一名教师除了授业解惑以外，还要传达一些个人价值观的体现。书中很多细微处，如对某位科学家的尊敬、对某个算法的推崇、对勤奋励志故事的讲述等都在表达着一个老师向学生传递真、善、美的意愿。我始终认为，读者拿到的虽然只是一本没有表情、不会说话的书，但其实也是在隔空与另一个朋友交流。人与人的交流不可能只是就事论事，一定会有情感的沟通，这种情感如果能产生共鸣、达成互信，就会让事情（比如学习数据结构与算法这件事）本身更容易理解和接受。
本书内容
本书主要是按照关于计算机专业数据结构课程大纲的要求略微增减来组织内容的。
本书内容主要包括：数据结构介绍，算法推导大O阶的方法，线性表结构的介绍，顺序结构与链式结构差异，栈与队列的应用，串的朴素模式匹配、KMP模式匹配算法，树结构的介绍，二叉树前中后序遍历，线索二叉树，哈夫曼树及应用，图结构的介绍，图的深度、广度遍历，小生成树两种算法，短路径两种算法，拓扑排序与关键路径算法，查找应用的相关介绍，折半查找、插值查找、斐波那契查找等静态查找，稠密索引、分块索引、倒排索引等索引技术，二叉排序树、平衡二叉树等动态查找，B树、B 树技术，散列表技术，排序应用的相关介绍，冒泡、选择、插入等简单排序，希尔、堆、归并、快速等改进排序，各种排序算法的对比等。
本书读者
“数据结构”是计算机软件相关专业的基础课程，几乎可以说，要想从事编程工作，无论你是否是科班出身，都不可以绕过这部分知识。因此，适合阅读本书的读者非常广泛，包括在读的本专科、中专、职高、技校等计算机专业学生，想转行做开发的非专业人员，欲考计算机研究生的应届生或在职人员，以及工作后需要补学或温习数据结构和算法的程序员等。
本书对读者的技术背景要求比较低，只要是学过一门高级编程语言，例如C、C 、Java、C#、VB等就可以开始阅读本书。不过由于当中涉及比较复杂的算法知识，需要读者有一定的数学修养和逻辑思维能力，否则可能书籍的后半部分阅读起来会比较吃力。
本书研读方法
事实上，任何有难度的知识和技巧，都不是那么容易被掌握的。我尽管已经朝着通俗易懂的方向努力，可有些数据结构，特别是经典算法，是几代科学家的智慧结晶，因此要掌握它们还是需要读者的全力投入。
美国畅销书《如何阅读一本书》中提到“阅读可以是一件主动的事，阅读越主动，效果越好。拿同样的书给背景相近的两个人阅读，一个人却比另一个人从书中得到了更多，这是因为，首先在于这人的主动，其次，在于他在阅读中的每一种活动都参与了更多的技巧。这两件事是息息相关的。阅读是一个复杂的活动，就跟写作一样，包含了大量不同的活动。要达到良好的阅读，这些活动都是不可或缺的。一个人越能良好从事这些活动，阅读的效果也就越好。”
我当然希望读者在阅读本书后收获巨大，但这显然是一厢情愿。要想获得更多，你可能也需要付出类似我写作一样的精力来阅读，例如摘抄文字、眉批心得、稿纸演算、代码输入，以及您自己在编程工作中的运用等。这些相应活动的执行，将会使您得到巨大的收获。
作为作者，建议本书的研读方法为：
复习C语言的基础知识。如果你掌握的是别的语言也不要紧，适当了解一些C语言和你掌握的编程语言的语法差异还是有必要的。甚至将本书代码改造成另一种语言本身就是一种非常好的学习方法。
阅读遍时，建议从头至尾进行。如果你对前面的知识有足够了解，当然可以跳过直接阅读后面的章节。不过若要学习一门完整的知识并形成体系，通读本书，还是好的学习方法。
阅读时，摘抄是非常好的习惯。“淡的墨水也胜于强的记忆！”有不少读者会认为摘抄了将来也不会再去看，没什么必要。但其实写字的过程就是大脑学习的过程，写字在减缓你阅读的速度，从而让你更好地消化阅读的内容。相信大家都能理解，“囫囵吞枣”和“慢慢品味”的差异，学习同样如此。
阅读每一章时，特别是在阅读算法的推导过程时，一定要在电脑中运行代码（本书源码扫码下载，也可以到http://cj723.cnblogs.com中的《大话数据结构》相关主题中找到），了解代码的运行过程。本书的很多算法都做到了逐行讲解，但单纯阅读可能真的很难达到理解的程度（这是纸质书无法克服的缺陷），需要你通过开发工具调试，设置断点和逐行执行，并参照书中的讲解，观察变量的变化情况来理解算法的编写原理。
阅读完每一章时，一定要在理解基础上记忆一些关键东西。的效果就是你可以不看书也做到一点不错地默写出相关算法。
阅读完每一章时，一定要适当练习。本书没有提供练习题，但网络上相关的数据结构习题集比比皆是，可以选择尝试。另外互联网上也可以获得足够的习题来供你练习。练习的目的是为了检测自己是否真的完全理解了书中的内容。事实上很多时候，阅读中的人们只是自我感觉理解，而并非真正的明白。
学习不可能一蹴而就，数据结构和算法如果通过一本书就可以掌握，那本身就是笑话。本书提供了写作时的参考书目（扫码下载），基本都是秀的数据结构或相关的中文书籍，各有侧重，建议大家可以适当地阅读。
在之后的编程学习和工作中，尽量把已经学到的数据结构和算法知识运用到现实开发中。遗忘时翻阅本书回顾相关内容，终达到精通数据结构和相关算法的境界。
关于PPT课件
在《大话数据结构》上一版的发行过程中，有很多读者问我要PPT课件，其中大部分是自学的读者，也有一部分是老师。上一版没有提供课件，当时感觉书中内容已经很容易理解了，提供通常意义上的课件有点画蛇添足。但后来发现，很多代码仅仅看书确实不够直观，有些读者无法清晰明了地理解算法的执行过程。这算是本书上一个版本的一个小小的遗憾。
借着本次更新的动力，我精心制作了一套超过200页的PPT课件，对本书大部分知识点结合代码进行了“动效”梳理，尤其是一些书中难以表达清楚的知识点。
在使用上，这套PPT课件特别适合自学的读者，您可以一边看书，一边打开PPT播放相关知识点来了解算法执行时的数据变化和图形变化。另外，老师也可以直接用其中的元素来讲课使用。
编程语言说明
本书是用C语言编写的，基于C90（ISO C）的标准。读者可以选择任何一款基于C90标准的C语言开发工具或更高版本的开发工具来学习本书中的代码。
本人一直习惯于用Visual Studio作为开发工具，因此在写作此书时，也是用此工具的Visual C 来编译调试代码，一切都相安无事，但写作完成后，考虑到不同读者应用开发工具的习惯不同，终在编辑的建议下，决定提供一份可在C90标准的C语言开发环境中编译通过的代码，结果发现错误百出。
例如C90标准的注释要求是“/* 注释文字 */”而不允许是“//注释文字”：要求变量声明必须要在函数的前面，只能是“int i; for(i=0;i<n;i )……”，而不允许如“for (int i=0;i<n;i )”这样的方式：再比如C 中函数的参数可以传递如“void CreateBiTree(BiTree &T)”的地址变量，但在C语言中，只能传递如“void CreateBiTree(BiTree *T)”的指针变量。因此当你看到书中的有些代码到处都是“*”时，就用不着奇怪了。
出于代码可以在低端编译环境通过的考虑，牺牲一些代码的简捷性和优雅性也是无可奈何和必要的。终我将书中全部代码都改成C90标准的代码。
C语言初学者可能会因为刚接触编程语言，特别是对指针的理解不深，而担心阅读困难。我个人感觉，单纯学习指针是很难理解它的真正用途和好处的，而通过学习数据结构，特别是像链式存储结构在各种结构算法中的运用，反而可以让读者进一步理解指针的优越之处。从这个角度说，数据结构的学习可以反过来加强读者对C语言，特别是指针概念的理解。
编程语言差异
C语言是一种历史悠久的高级语言，它的应用范围非常广泛，因此我选择它作为本书的算法展示语言。如果读者之前学过它，那么阅读本书就不存在语言障碍。懂得C 语言的读者，同样也不会有任何语言上的问题。
掌握Java、Python、C#等面向对象语言的读者，当面对书中大量的C语言式的结构（struct）声明和针对结构的参数传递的代码时，可以理解为是类的定义和由类生成对象的传递。尽管的确存在差异，但并不影响整体对数据结构知识和算法原理的理解。
我个人感觉，哪怕是对C语言不熟悉，也不妨利用学习数据结构的机会，学习一下C语言的编程方法，这对于将来应用其他高级语言也是有很大帮助的。斗转星移，时光荏苒，时间证明C语言的生命力是顽强的。
本书源代码和PPT课件扫码下载

书友会
之前聊过学习方法这个话题。对学习本身，笔者并不赞同整个学习过程的“孤军奋战”。
在学习初期，建议仔细阅读书中内容，遇到不容易理解的地方，一定要尝试着去独立思考，只有以这样的学习方式，才能让这些难点被理解得更为深刻和到位。但是，如果三番五次地攻关仍然攻克不了，那我建议可以记录下来，继续阅读，不要打断了独立学习、独立思考的状态。
看完全书，相信绝大部分难点会在上下文中得到解答，剩下的疑问，那就找志同道合的“书友”去寻求答案吧。
书友会Q群：835154766
加入组织，与书友并肩作战吧！
除了学习，书友会不定期提供勘误、更多学习资源、视频、直播预告、购书代金券等资源，并会不定期展开赠书活动。
不是一个人在战斗
首先要感谢我的妻子李秀芳对我写作本书期间的全力支持，我辞职写作，没有她的理解鼓励和生活上的悉心照顾，是不可能走出这一步并顺利完成书稿的。我们的儿子程晟涵如今已经三周岁，我是在他每日的欢声笑语和哭哭啼啼中进行每一章节的构思和写作的，希望他可以茁壮成长。我的父母已经年迈，他们为我的全职创作也甚为担心和忧虑，这里也要说一声抱歉。
写作过程中，本人购买和借阅了与数据结构相关的大量书籍，详细书目见本书扫码平台。没有前辈的贡献，就没有本书的出版，也希望本书能成为这些书籍的前期读物。在此向这些图书作者表示衷心的感谢。
仅有作者是不可能完成图书的出版的，本人要非常感谢清华大学出版社的朋友们，他们是本书的初读者，也是协助本人将此书由毛糙变精良的有力助手。本书的封面设计程瑜、插图设计周翔，都是在反反复复的修改中完成创作的。写作中还得到了周筠、卢鸫翔、张伸、胡文佳、Milo、陈钢、刘超、刘、杨绣国、戚妩婷、雷顺、杨诗盈、高宇翔、林健的友情帮助，他们都在本人的创作中提出了宝贵建议。
在此向所有帮助与支持我的朋友道一声：谢谢！

程?杰
?

再版说明
写作起因
大家好！我是《大话数据结构》（2011年版）的作者，9年来，承蒙广大读者的厚爱，《大话数据结构》（2011年版）取得了较大的成功。
仅在，截至本文写作时，此书就已经有3.1万次评论，98%的好评度。这本书出版至今一直是国内原创计算机类图书畅销的书籍之一。
不过由于这本书写作于9年前，受当时的认知和能力限制，确实存在一些不足和缺憾。因此在2020年这个特殊的年份里，我对本书做了修订，改进前作的技术问题和解读方式，力争让学习数据结构变得更加容易，让阅读体验更加舒适。
例图升级
版的图书，是单色印刷，图形以平面为主。对于一些简单讲解，这应该是可以的，但有些时候，要讲的知识点比较复杂，仅仅黑白灰的平面图形，很难一目了然地把差异表达清楚。通过学习国内外优秀图书的制作，我对所有的图表做了全面升级。
1. 通过三维立体方式，让阅读体验更加舒适，记忆起来会更加深刻。
老版：

新版：

2. 利用色彩变化，突出要讲解的知识点和流程线索。
老版：
       
新版：
??
3. 对部分示意图做了改进，更清晰明了。
老版：

新版：

4. 在讲解中增加了大量趣味示意图。

内容升级
内容是一本书的重中之重。我对书中的大量细节都做了更新，增补或者替换了更加便于理解的解读和案例。
有一些算法，版时，是直接通过代码来分析讲解的，本书在这些方面都有所改进。比如小生成树的两个算法，都以先讲解算法思路、再剖析代码的方式，这样更加容易理解。
另外，在重新编写中还发现了版中的多处大小错误，一并修正了。在此对前作的读者说声抱歉，也感谢为本书前作指出错误的热心读者。
代码样式升级
本书所有代码，我又重新梳理了一遍，消灭了不少问题。并在编辑器里重新跑过，展示方式也采取直接截屏编辑器的方式，力争让读者有一种实地开发的既视感。
原代码样式：

int i, j, x = 0,sum = 0,n = 100;  /* 执行一次 */
for(i = 1; i < = n; i )
{
 for (j = 1; j < = n; j )
 {
 x ;     /* 执行n×n次 */
 sum = sum x;
 }
}
printf(“%d”, sum);    /* 执行一次 */

当前样式：

《大话数据结构【溢彩加强版】》以一个计算机教师的教学过程为场景，讲解数据结构和相关算法的知识。全书以趣味方式来叙述，大量引用各种各样的生活知识来类比，并充分运用全彩色图形语言来解读抽象内容，对数据结构所涉及的一些经典算法做出逐行分析、多算法比较。与同类图书相比，《大话数据结构【溢彩加强版】》内容有趣易读，算法讲解细致深入，是一本非常适合自学的读物。
对于学习数据结构来说，难点之一是对相关算法的理解。《大话数据结构【溢彩加强版】》创新性地采用全彩印刷，图表、流程、代码等内容结合色彩来重新进行约定和归纳，使得对一些难以理解的知识点的解析更加清晰顺畅，极大提升了阅读体验。
《大话数据结构【溢彩加强版】》主要内容包含：数据结构介绍、算法推导大O阶的方法；顺序结构与链式结构差异、栈与队列的应用；串的朴素模式匹配、KMP模式匹配算法；二叉树前中后序遍历、哈夫曼树及应用；图的深度、广度遍历；*小生成树两种算法、*短路径两种算法；拓扑排序与关键路径算法；折半查找、插值查找、斐波那契查找等静态查找；稠密索引、分块索引、倒排索引等索引技术；二叉排序树、平衡二叉树等动态查找；B树、B 树技术，散列表技术；冒泡、选择、插入等简单排序；希尔、堆、归并、快速等改进排序。
《大话数据结构【溢彩加强版】》适合学过一门编程语言的各类读者，包括在读的大中专计算机专业学生、想转行做开发的非专业人员、欲考计算机专业研究生的应届生或在职人员，以及工作后需要补学或温习数据结构和算法的程序员等。

程杰，一个被读者誉为很适合写IT技术书的家伙。
著有 《大话设计模式》（简体版销量破25万册、繁体版印刷12次，开创了一种适合国人阅读的趣味讲解IT知识的风格与模式）。
作者参与过政府、证券、游戏、交通等多种行业的软件开发及项目管理工作，也曾做过软件培训的教师，目前从事教育类APP/微信小程序的开发与运营。因为有过两年半高中数学教学的独特经历，使得其书作当中处处以初学者视角考虑和分析问题，成为了当前很受欢迎的IT技术图书作者之一。

第1章  数据结构绪论 1

1.1　开场白 2
如果你交给某人一个程序，你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子。
1.2　你数据结构怎么学的 3
他完成开发并测试通过后，得意地提交了代码。项目经理看完代码后拍着桌子对他说：“你数据结构是怎么学的？”
1.3　数据结构起源 4
1.4　基本概念和术语 5
正所谓“巧妇难为无米之炊”，再强大的计算机，也要有“米”下锅才可以干活，否则就是一堆破铜烂铁。这个“米”就是数据。
1.4.1?数据 5
1.