前言 本书起因
大家好！我是《大话设计模式》（2008年初出版）的作者，三年来，承蒙广大读者的厚爱，《大话设计模式》取得了较大的成功。仅在当当网，截止本文写作时，就已经有1073次评论，705次5星评价，位居五星图书榜计算机/网络类的累计总榜第二名。此书已经成为国内原创计算机类图书最畅销的书籍之一。
对于这样一个自己喜欢做、可以做得好，而且已经得到了市场广泛认可，为很多朋友提供帮助的事情，我没有理由不去继续做下去。这就是我准备再写书的原因。
我曾做过调查，数据结构的学习者大多都有这样的感慨：数据结构很重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困难，学得很累。可我更希望传达这样的信息：数据结构非常有趣，很多算法是智慧的结晶，学习它是去感受计算机编程技术的魅力，在理解掌握它的同时，整个过程都是一种愉悦的精神感受，而非枯燥乏味的一门课程。因此我决定写作一本关于数据结构有趣的书。
不过现实总比理想来得更“现实”。要想把书写好，谈何容易，我需要突破很多困难……嗐！不管如何，现在您看到了本书，那就说明我已经克服了困难战胜了自己。希望您可以喜欢上这本书。
本书定位
本书的定位就是一本适合读者自学数据结构的书籍，它有区别于教材，希望给大家另一种阅读体验。
通常讲解数据结构的图书都是以教材的方式呈现。在写作前，我购买或在图书馆借阅了十几本非常好的数据结构相关教材用来为写作本书做准备。但经过认真阅读后，我发现，它们大多不是一本好的“自学读物”。
我没有轻视这些好书的意思，不过教材和自学读物，所面向的读者是完全不同的。
好的教材应该是提纲挈领、重点突出，一定要留出思考的空间，否则就没必要再听老师上课了。很多内容的讲解是由老师在课堂完成，教材中有练习、课后习题、思考题等，这些大多可以通过老师来解答。比如我们中学时的语文、数学课本，很薄的一本书通常要用一学期、甚至一年的时间来学习，这就是因为它们是教材而不是自学读物。如果是小说，可能一两天就读完了。
好的自学读物的目标是让初学者“独自”全盘掌握知识，需要强调“独自”一词，这就说明读者在阅读时，是完全依靠自己的力量来向未知发出挑战。因此书中内容，要么不写，写了就应该写透。如果读者在阅读时总是疑惑重重，那么这本书就有很大的问题了。
我也就是在基于这样的认识，决心将《大话数据结构》真正写成一本关于数据结构和算法的自学读物来展开写作的。
本书特色
1．趣味引导
大部分的编程类图书，在内容上基本都是直奔主题。但是尼采曾说过：“人们无法理解他没有经历过的事情。”换句话说，我们只接受过去早已理解的事物相关的信息。这是一种比较学习过程，在这个过程中，大脑寻找每条信息之间的联系。所以教育专家普遍认为，吸引学生的注意力，比较好的办法是用他们比较熟知的知识开始。
因此在本书中，我会用一个故事、一个趣味题目、一部电影的介绍等形式来作为每一章甚至很多小节的开头，选择的内容也多多少少与要讲的主题内容相关。这并不是多余，而是有意为之。事实上，这样的形式在我的前一本书中已经得到了普遍认可。
2．图文并茂
西方有句谚语，“A picture is worth a thousand words.（一图值千言）”。用上千个字描述不明白的东西，很可能一张图就能解释清楚。
我非常认可这个观点，所以本书虽没有达到每一页都有图，但基本做到了绝大部分讲解都有相关图示，关键算法更是通过多图逐步分解剖析。尽管这带来了写作上的难度，但却可以达到较好的效果。毕竟，读者通过本书开始学习数据结构时，要从一无所知或略知一二到完全理解，甚至掌握应用，是需要一个比较艰苦的过程，用大量的图示可以减少这个过程的长度。
3．代码详解
. 我在写作中尽量摒弃了传统数据结构教材的“重理论思想而轻代码讲解”的作法。在准备数据结构写作时我发现，很多教材对数据结构理论和算法设计思想讲得比较好，可一到实际代码时，有的把代码贴出来加少量注释，有的直接用伪代码形式。这对于上课的学生还好，毕竟有老师在课堂中去详解代码编写原理，可是对于初学数据结构和算法的自学者而言，如果书中不去解释代码某些细节为什么那样编写的原因，甚至代码根本不可能在某个编译器中运行通过，其挫折感是很强烈的。比如即使理解了图结构中的最短路径求解原理，也可能无法写出最短路径的算法。
我把代码在运行过程中变量的变化融入到整个算法设计思想的讲解中，配合相应的示意图，会帮助大家更加容易理解算法的实质。这种讲解模式在本书的第6、7、8、9章的很多复杂算法中有具体体现，越是复杂的代码越是讲解细致。这算是本书的一个特色，希望对读者有帮助。
4．形式新颖
我把本书的内容虚构成了一个老师上课的场景，所有内容都通过这位老师表达出来，书中的文字非常口语化，这样做的目的是为了更加直观地让读者感觉，自己是在学习，是在上课。有人可能会说，现在的课堂大都是让人昏昏欲睡，把读者带入上课场景，不是更加让读者犯困吗？我觉得如果你的学习经历中听过一些优秀老师的课，你就不会下这样的结论。好的老师讲课，是可以做到引人入胜的。
有人可能会问，我为什么不用《大话设计模式》中的对话形式，而采用讲课形式呢？这是对数据结构这门学问的特点考虑的。设计模式主要都是思想体现，通常会仁者见仁、智者见智，用对话展开比较容易；而数据结构中更多的是定义、术语、经典算法等，这些公认的知识，可讨论的地方并不多，更多的是需要把它讲清楚。让两个人在一起讨论某个设计模式的优缺点，会非常合适，而讨论数据结构定义的好坏，就没有太大意义了，不如让一个老师告诉学生数据结构的定义好在哪里更符合实际。因此用传统的讲课形式会好一些。
另外，本书没有习题，有思考的题目也一定会给出某种答案。但本书每个复杂知识点的末尾，都会提供另一本书的进一步阅读建议。这也是基于它是一本自学读物的原则。读者阅读本书可能是任何时间任何地方，如果书中存在没有解答的习题，碰到了困难是没法及时找到老师来帮助的，因此本书尽量避免让读者有这样的困惑存在。如果需要练习的同学，我觉得还是应该考虑再去买本习题集来学习。学习数据结构和算法，做题和上机写代码非常有必要，从这个角度也说明，阅读完本书其实也只是完成入门而已。
本书既然是以老师上课的形式来进行，那就免不了要融入一名教师除了授业解惑以外，还要传达一些个人价值观的体现。书中很多细微处，如对某位科学家的尊敬、对某个算法的推崇、对勤奋励志故事的讲述等都在表达着一个老师向学生传递真、善、美的意愿。我始终认为，读者拿到的虽然只是一本没有表情、不会说话的书，但其实也是在隔空与另一个朋友交流。人与人的交流不可能只是就事论事，一定会有情感的沟通，这种情感如果能产生共鸣、达成互信，就会让事情（比如学习数据结构与算法这件事）本身更容易理解和接受。
本书内容
本书主要是按照教育部关于计算机专业数据结构课程大纲的要求略微增减来组织内容的。
主要包括：数据结构介绍，算法推导大O阶的方法，线性表结构的介绍，顺序结构与链式结构差异，栈与队列的应用，串的朴素模式匹配、KMP模式匹配算法，树结构的介绍，二叉树前中后序遍历，线索二叉树，赫夫曼树及应用，图结构的介绍，图的深度、广度遍历，最小生成树两种算法，最短路径两种算法，拓扑排序与关键路径算法，查找应用的相关介绍，折半查找、插值查找、斐波那契查找等静态查找，稠密索引、分块索引、倒排索引等索引技术，二叉排序树、平衡二叉树等动态查找，B树、B+树技术，散列表技术，排序应用的相关介绍，冒泡、选择、插入等简单排序，希尔、堆、归并、快速等改进排序，各位排序算法的对比等。
本书读者
数据结构是计算机软件相关专业的基础课程，几乎可以说，要想从事编程工作，无论你是否是科班出身，都不可以绕过这部分知识。因此，适合阅读本书的读者非常广泛，包括在读的本专科、中专职高技校等计算机专业学生、想转行做开发的非专业人员、欲考计算机研究生的应届或在职人员，以及工作后需要补学或温习数据结构和算法的程序员等各类读者。
本书对读者的技术背影要求比较低，只要是学过一门高级编程语言，例如C、C++、Java、C#、VB等就可以开始阅读本书。不过由于当中涉及到比较复杂的算法知识，需要读者有一定的数学修养和逻辑思维能力，否则可能书籍的后半部分阅读起来会比较吃力。
本书研读方法
事实上，任何有难度的知识和技巧，都不是那么容易被掌握的。我尽管已经朝着通俗易懂的方向努力，可有些数据结构，特别是经典算法，是几代科学家的智慧结晶，因此要掌握它们还是需要读者的全力投入。
美国畅销书《如何阅读一本书》中提到“阅读可以是一件主动的事，阅读越主动，效果越好。拿同样的书给背景相近的两个人阅读，一个人却比另一个人从书中得到了更多，这是因为，首先在于这人的主动，其次，在于他在阅读中的每一种活动都参与了更多的技巧。这两件事是息息相关的。阅读是一个复杂的活动，就跟写作一样，包含了大量不同的活动。要达成良好的阅读，这些活动都是不可或缺的。一个人越能良好运作这些活动，阅读的效果也就越好。”
我当然希望读者在阅读本书后收获巨大，但这显然是一厢情愿。要想获得更多，您可能也需要付出类似我写作一样的力气来阅读，例如摘抄文字、眉批心得、稿纸演算、代码输入电脑，以及您自己在编程工作中的运用等。这些相应活动的执行，将会使您得到巨大的收获。
作为作者，建议本书的研读方法为：
1．复习C语言的基础知识。如果你掌握的是别的语言也不要紧，适当了解一些C语言和你掌握的编程语言的语法差异还是有必要的。甚至将本书代码改造成另一种语言本身就是一种非常好的学习方法。
2．阅读第一遍时，建议从头至尾进行。如果你对前面的知识有足够了解，当然可以跳过直接阅读后面的章节。不过若要学习一门完整的知识并形成体系。通读本书，还是最好的学习方法。
3．阅读时，摘抄是非常好的习惯。“最淡的墨水也胜于最强的记忆！”有不少读者会认为摘抄了将来也不会再去看，有什么必要，但其实在写字的过程就是大脑学习的过程，写字在减缓你阅读的速度，从而让你更好地消化阅读的内容。相信大家都能理解，“囫囵吞枣”和“慢慢品味”的差异，学习同样如此。
4．阅读每一章时，特别是在阅读算法的推导过程时，一定要在电脑中运行代码（本书源码的下载地址可以到
http://cj723.cnblogs.com中的《大话数据结构相关主题》中找到），了解代码的运行过程。本书的很多算法都做到了逐行讲解，但单纯阅读可能真的很难达到理解的程度（这是纸质书无法克服的缺陷），需要你通过开发工具调试，并设置断点和逐行执行，并参照书中的讲解，观察变量的变化情况来理解算法的编写原理。
5．阅读完每一章时，一定要在理解基础上记忆一些关键东西。最佳的效果就是你可以不看书也做到一点不错地默写出相关算法。
6．阅读完每一章时，一定要适当练习。本书没有提供练习题，但市场上相关的数据结构习题集比比皆是，可以选择尝试。另外互联网上也可以获得足够的习题来给你练习。练习的目的是为了检测自己是否真的完全理解了书中的内容。事实上很多时候，阅读中的人们只是自我感觉理解，而并非真正的明白。
7．学习不可能一蹴而就，数据结构和算法如果通过一本书就可以掌握，那本身就是笑话。本书附录提供了本书写作时的参考书目，基本都是最优秀的数据结构或相关的中文书籍各有侧重，建议大家可以适当地阅读。
8．在之后的编程学习和工作中，尽量把已经学到的数据结构和算法知识运用到现实开发中。遗忘时翻阅本书回顾相关内容，最终达到精通数据结构和相关算法的境界。
编程语言说明
本书是用C语言编写，基于C90（ISO C）的标准。读者可以选择任何一款基于C90标准的C语言开发工具或更高版本的开发工具来学习本书中的代码。
本人一直习惯于用Visual Studio 2008作为开发工具，因此在写作此书时，也是用此工具的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、C#、VB等面向对象语言的读者，当面对书中大量的C语言式的结构（struct）声明和针对结构的参数传递的代码时，都可以理解为是类的定义和由类生成对象的传递。尽管的确存在差异，但是并不影响整体对数据结构知识和算法原理的理解。
我个人感觉，哪怕是对C语言不熟悉，也不妨利用学习数据结构的机会，学习一下C语言的编程方法，这对于将来应用其他高级语言也是有很大帮助的。
不是一个人在战斗
首先要感谢我的妻子李秀芳对我写作本书期间的全力支持，我辞职写作，没有她精神上的理解鼓励和生活上的悉心照顾，是不可能走出这一步并顺利完成书稿的。我们的儿子程晟涵如今已经三周岁，我是在他每日的欢声笑语和哭哭啼啼中进行每一章节的构思和写作，希望他可以茁壮成长。我的父母已经年迈，他们为我的全职创作也甚为担心和忧虑，这里也要说一声抱歉。
本人数据结构的知识，是源自清华大学出版社出版的《数据结构（C语言版）》（严蔚敏、吴伟民编著）一书，严老师和吴老师算是我在数据结构方面的启蒙老师，本书的不少内容和代码也是参考了此书。机械工业出版社的《算法导论》对于本人的算法知识提高帮助很大，写作中也大量吸收了书中的精华。写作过程中，本人购买和借阅了与数据结构相关的大量书籍，详细书目见附录。没有前辈的贡献，就没有本书的出版，也希望本书能成为这些书籍的前期读物。在此向这些图书作者表示衷心的感谢。
仅有作者是不可能完成图书的出版的，本人要非常感谢清华大学出版社的朋友们，他们是本书的最初读者，也是协助本人将此书由毛糙变精良的最有力帮手。
本书的封面设计程瑜、插图设计周翔，都是在反反复复的修改中完成创作的。
写作中，还得到了周筠、卢鸫翔、张伸、胡文佳、Milo、陈钢、刘超、刘唯一、杨绣国、戚妩婷、雷顺、杨诗盈、高宇翔、林健的友情帮助，他们都在本人的书稿创作中提出了宝贵建议。
在此向所有帮助与支持我的朋友道一声：谢谢！
程 杰
《大话数据结构》
第1章数据结构绪论 1
1.1开场白 2
如果你交给某人一个程序，你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子。
1.2你数据结构怎么学的？ 3
他完成开发并测试通过后，得意地提交了代码。项目经理看完代码后拍着桌子对他说：“你数据结构是怎么学的？”
1.3数据结构起源 4
1.4基本概念和术语 5
正所谓“巧妇难为无米之炊”，再强大的计算机，也要有“米”下锅才可以干活，否则就是一堆破铜烂铁。这个“米”就是数据。
1.4.1数据 5
1.4.2数据元素 5
1.4.3数据项 6
1.4.4数据对象 6
1.4.5数据结构 6
1.5逻辑结构与物理结构 7
1.5.1逻辑结构 7
1.5.2物理结构 9
1.6抽象数据类型 11
大家都需要房子住，但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型，有几百平米的别墅，也有仅两平米的胶囊公寓……
1.6.1数据类型 11
.1.6.2抽象数据类型 12
1.7总结回顾 14
1.8结尾语 15
最终的结果一定是，你对着别人很牛的说“数据结构——就那么回事。”
第2章算法 17
2.1开场白 18
2.2数据结构与算法关系 18
计算机界的前辈们，是一帮很牛很牛的人，他们使得很多看似没法解决或者很难解决的问题，变得如此美妙和神奇。
2.3两种算法的比较 19
高斯在上小学的一天，老师要求每个学生都计算1+2+…+100的结果，谁先算出来谁先回家……
2.4算法定义 20
现实世界中的算法千变万化，没有通用算法可以解决所有问题。甚至一个小问题，某个解决此类问题很优秀的算法却未必就适合它。
2.5算法的特性 21
2.5.1输入输出 21
2.5.2有穷性 21
2.5.3确定性 21
2.5.4可行性 21
2.6算法设计的要求 22
求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异，我们自然追求高效率和低存储的算法来解决问题。
2.6.1正确性 22
2.6.2可读性 23
2.6.3健壮性 23
2.6.4时间效率高和存储量低 23
2.7算法效率的度量方法 24
随着n值越来越大，它们在时间效率上的差异也就越来越大。好比有些人每天都在学习，而另一些人，打打游戏、睡睡大觉，毕业后前者名企争着要，后者求职处处无门。
2.7.1事后统计方法 24
2.7.2事前分析估算方法 25
2.8函数的渐近增长 27
2.9算法时间复杂度 29
理解大o推导不算难，难的其实是对数列的一些相关运算，这考察的更多的是数学知识和能力。
2.9.1算法时间复杂度定义 29
2.9.2推导大o阶方法 30
2.9.3常数阶 30
2.9.4线性阶 31
2.9.5对数阶 32
2.9.6平方阶 32
2.10常见的时间复杂度 35
有些时候，告诉你某些东西不可以去尝试，也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。
2.11最坏情况与平均情况 35
2.12算法空间复杂度 36
事先建立一个有2050大的数组，然后把所有年份按下标数字对应，如果是闰年，此数组项的值就是1，如果不是就是0。这样，所谓的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题。
2.13总结回顾 37
2.14结尾语 38
愚公移山固然可敬，但发明炸药和推土机，可能更加实在和聪明。
第3章线性表 41
3.1开场白 42
门外家长都挤在大门口与门里的小孩子的井然有序，形成了鲜明对比。哎，有时大人的所作所为，其实还不如孩子。
3.2线性表的定义 42
3.3线性表的抽象数据类型 45
有时我们想知道某个小朋友（比如麦兜）是否是班级的同学，老师会告诉我说，没有，麦兜是在春田花花幼儿园里。这种查找某个元素是否存在的操作很常用。
3.4线性表的顺序存储结构 47
他每次一吃完早饭就冲着去了图书馆，挑一个好地儿，把他书包里的书，一本一本的按座位放好，长长一排，九个座硬是被他占了。
3.4.1顺序存储定义 47
3.4.2顺序存储方式 47
3.4.3数据长度与线性表长度区别 48
3.4.4地址计算方法 49
3.5顺序存储结构的插入与删除 50
春运时去买火车票，大家都排队排着好好的，这时来了一个美女：“可否让我排在你前面？”这可不得了，后面的人像蠕虫一样，全部都得退后一步。
3.5.1获得元素操作 50
3.5.2插入操作 51
3.5.3删除操作 52
3.5.4线性表顺序存储结构的优缺点 54
3.6线性表的链式存储结构 55
反正也是要让相邻元素间留有足够余地，那干脆所有元素都不要考虑相邻位置了，哪有空位就到哪里。而只是让每个元素知道它下一个元素的位置在哪里。
3.6.1顺序存储结构不足的解决
办法 55
3.6.2线性表链式存储结构定义 56
3.6.3头指针与头结点的异同 58
3.6.4线性表链式存储结构代码描述 58
3.7单链表的读取 60
3.8单链表的插入与删除 61
本来是爸爸左牵着妈妈的手、右牵着宝宝的手在马路边散步。突然迎面走来一美女，爸爸失神般地望着，此情景被妈妈逮个正着，于是扯开父子俩，拉起宝宝的左手就快步朝前走去。
3.8.1单链表的插入 61
3.8.2单链表的删除 64
3.9单链表的整表创建 66
3.10单链表的整表删除 69
3.11单链表结构与顺序存储结构优缺点 70
3.12静态链表 71
对于一些语言，如basic、fortran等早期的编程高级语言，由于没有指针，这链表结构，按照前面我们的讲法，它就没法实现了。怎么办呢？
3.12.1静态链表的插入操作 73
3.12.2静态链表的删除操作 75
3.12.3静态链表优缺点 77
3.13循环链表 78
这个轮回的思想很有意思。它强调了不管你今生是穷是富，如果持续行善积德，下辈子就会好过，反之就会遭到报应。
3.14双向链表 81
就像每个人的人生一样，欲收获就得付代价。双向链表既然是比单链表多了如可以反向遍历查找等的数据结构，那么也就需要付出一些小的代价。
3.15总结回顾 84
3.16结尾语 85
如果你觉得上学读书是受罪，假设你可以活到80岁，其实你最多也就吃了20年苦。用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥。
第4章栈与队列 87
4.1开场白 88
想想看，在你准备用枪的时候，突然这手枪明明有子弹却打不出来，这不是要命吗。
4.2栈的定义 89
类似的很多软件，比如word、photoshop等，都有撤消（undo）的操作，也是用栈这种思想方式来实现的。
4.2.1栈的定义 89
4.2.2进栈出栈变化形式 90
4.3栈的抽象数据类型 91
4.4栈的顺序存储结构及实现 92
4.4.1栈的顺序存储结构 92
4.4.2栈的顺序存储结构进栈操作 93
4.4.3栈的顺序存储结构出栈操作 94
4.5两栈共享空间 94
两个大学室友毕业同时到北京工作，他们都希望租房时能找到独自住的一室户或一室一厅，可找来找去发现，实在是承受不起。
4.6栈的链式存储结构及实现 97
4.6.1栈的链式存储结构 97
4.6.2栈的链式存储结构进栈操作 98
4.6.3栈的链式存储结构出栈操作 99
4.7栈的作用 100
4.8栈的应用——递归 100
当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗？如果a、b两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”。
4.8.1斐波那契数列实现 101
4.8.2递归定义 103
4.9栈的应用——四则运算表达式求值 104
4.9.1后缀（逆波兰）表示法定义 104
4.9.2后缀表达式计算结果 106
4.9.3中缀表达式转后缀表达式 108
4.10队列的定义 111
电脑有时会处于疑似死机的状态。就当你失去耐心，打算了reset时。突然它像酒醒了一样，把你刚才点击的所有操作全部都按顺序执行了一遍。
4.11队列的抽象数据类型 112
4.12循环队列 113
你上了公交车发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做？立马下车，并对自己说，后面没座了，我等下一辆？没这么笨的人，前面有座位，当然也是可以坐的。
4.12.1队列顺序存储的不足 112
4.12.2循环队列定义 114
4.13队列的链式存储结构及实现 117
4.13.1队列链式存储结构入队操作118
4.13.2队列链式存储结构出队操作 119
4.14总结回顾 120
4.15结尾语 121
人生，需要有队列精神的体现。南极到北极，不过是南纬90度到北纬90度的队列，如果你中途犹豫，临时转向，也许你就只能和企鹅相伴永远。可事实上，无论哪个方向，只要你坚持到底，你都可以到达终点。
第5章串 123
5.1开场白 124
“枯眼望遥山隔水，往来曾见几心知？壶空怕酌一杯酒，笔下难成和韵诗。途路阻人离别久，讯音无雁寄回迟。孤灯夜守长寥寂，夫忆妻兮父忆儿。”……可再仔细一读发现，这首诗竟然可以倒过来读。
5.2串的定义 124
我所提到的“over”、“end”、“lie”其实就是“lover”、“friend”、“believe”这些单词字符串的子串。
5.3串的比较 126
5.4串的抽象数据类型 127
5.5串的存储结构 128
感情上发生了问题，为了向女友解释一下，我准备发一条短信，一共打了75个字。最后八个字是“我恨你是不可能的”，点发送。后来得知对方收到的，只有70个字，短信结尾是“……我恨你”。
5.5.1串的顺序存储结构 129
5.5.2串的链式存储结构 131
5.6朴素的模式匹配算法 131
主串为s=”00000000000000000000000000000000000000000000000001”，而要匹配的子串为t=”0000000001”，……在匹配时，每次都得将t中字符循环到最后一位才发现，哦，原来它们是不匹配的。
5.7kmp模式匹配算法 135
很多年前我们的科学家觉得像这种有多个0和1重复字符的字符串，却需要挨个遍历的算法，是非常糟糕的事情。
5.7.1kmp模式匹配算法原理 135
5.7.2next数组值推导 139
5.7.3kmp模式匹配算法实现 141
5.7.4kmp模式匹配算法改进 142
5.7.5nextval数组值推导 144
5.8总结回顾 146
5.9结尾语 146
《璇玑图》共八百四十字，纵横各二十九字，纵、横、斜、交互、正、反读或退一字、迭一字读均可成诗，诗有三、四、五、六、七言不等，目前有人统计可组成七千九百五十八首诗。听清楚哦，是7958首。
第6章树 149
6.1开场白 150
无论多高多大的树，那也是从小到大的，由根到叶，一点点成长起来的。俗话说十年树木，百年树人，可一棵大树又何止是十年这样容易。
6.2树的定义 150
树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念，这是比较新的一种定义方法。
6.2.1结点分类 152
6.2.2结点间关系 152
6.2.3树的其他相关概念 153
6.3树的抽象数据类型 154
6.4树的存储结构 155
6.4.1双亲表示法 155
6.4.2孩子表示法 158
6.4.3孩子兄弟表示法 162
6.5二叉树的定义 163
苏东坡曾说：“人有悲欢离合，月有阴晴圆缺，此事古难全”。意思就是完美是理想，不完美才是人生。我们通常举的例子也都是左高右低、参差不齐的二叉树。那是否存在完美的二叉树呢？
6.5.1二叉树特点 164
6.5.2特殊二叉树 166
6.6二叉树的性质 169
6.6.1二叉树性质1 169
6.6.2二叉树性质2 169
6.6.3二叉树性质3 169
6.6.4二叉树性质4 170
6.6.5二叉树性质5 171
6.7二叉树的存储结构 172
6.7.1二叉树顺序存储结构 172
6.7.2二叉链表 173
6.8遍历二叉树 174
你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择，由于选择方式的不同，遍历的次序就完全不同。
6.8.1二叉树遍历原理 174
6.8.2二叉树遍历方法 175
6.8.3前序遍历算法 178
6.8.4中序遍历算法 181
6.8.5后序遍历算法 184
6.8.6推导遍历结果 184
6.9二叉树的建立 187
6.10线索二叉树 188
我们现在提倡节约型社会，一切都应该节约为本。对待我们的程序当然也不例外，能不浪费的时间或空间，都应该考虑节省。
6.10.1线索二叉树原理 188
6.10.2线索二叉树结构实现 191
6.11树、森林与二叉树的转换 195
有个乡镇企业也买了同样的生产线，老板发现这个问题后找了个小工来说：你必须搞定，不然炒你鱿鱼。小工很快想出了办法：他在生产线旁边放了台风扇猛吹，空皂盒自然会被吹走。
6.11.1树转换为二叉树 196
6.11.2森林转换为二叉树 197
6.11.3二叉树转换为树 197
6.11.4二叉树转换为森林 199
6.11.5树与森林的遍历 199
6.12赫夫曼树及其应用 200
压缩而不出错是如何做到的呢？简单的说，就是把我们要压缩的文本进行重新编码，以达到减少不必要的空间的技术。压缩和解压缩技术就是基于赫夫曼的研究之上发展而来，我们应该记住他。
6.12.1赫夫曼树 200
6.12.2赫夫曼树定义与原理 203
6.12.3赫夫曼编码 205
6.13总结回顾 208
6.14结尾语 209
人受伤时会流下泪水。树受伤时，天将再不会哭。希望我们的未来不要仅仅是钢筋水泥建造的高楼，也要有那郁郁葱葱的森林和草地，我们人类才可能与自然和谐共处。
第7章图 211
7.1开场白 212
如果你不善于规划，很有可能就会出现如玩好新疆后到海南，然后再冲向黑龙江这样的荒唐决策。
7.2图的定义 213
现实中，人与人之间关系就非常复杂，比如我的认识的朋友，可能他们之间也互相认识，这就不是简单的一对一、一对多的关系了，那就是我们今天要研究的主题——图。
7.2.1各种图定义 214
7.2.2图的顶点与边间关系 217
7.2.3连通图相关术语 219
7.2.4图的定义与术语总结 222
7.3图的抽象数据类型 222
7.4图的存储结构 223
因为美国的黑夜就是中国的白天，利用互联网，他的员工白天上班就可以监控到美国仓库夜间的实际情况，如果发生了像火灾、偷盗这样的突发事件，及时电话到美国当地相关人员处理
7.4.1邻接矩阵 224
7.4.2邻接表 228
7.4.3十字链表 232
7.4.4邻接多重表 234
7.4.5边集数组 236
7.5图的遍历 237
我有一天早晨准备出门，发现钥匙不见了。一定是我儿子拿着玩，不知道丢到哪个犄角旮旯去了，你们说，我应该如何找？
7.5.1深度优先遍历 238
7.5.2广度优先遍历 242
7.6最小生成树 245
如果你加班加点，没日没夜设计出的结果是方案一，我想你离被炒鱿鱼应该是不远了（同学微笑）。因为这个方案比后两个方案一半还多的成本会让老板气晕过去的。
7.6.1普里姆（prim）算法 247
7.6.2克鲁斯卡尔（kruskal）算法 251
7.7最短路径 257
有人为了省钱，需路程最短，但换乘站间距离长等原因并不省时间；另一些人，他为赶时间，最大的需求是总时间要短；还有一类人，他们都不想多走路，关键是换乘要少，这样可以在车上好好休息一下。
7.7.1迪杰斯特拉（dijkstra）算法 259
7.7.3弗洛伊德（floyd）算法 265
7.8拓扑排序 270
电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这都会导致荒谬的结果。
7.8.1拓扑排序介绍 271
7.8.2拓扑排序算法 272
7.9关键路径 277
假如造一个轮子要0.5天、造一个发动机要3天、造一个车底盘要2天、造一个外壳要2天，其它零部件2天，全部零部件集中到一处要0.5天，组装成车要2天，请问，在汽车厂造一辆车，最短需要多少天呢？
7.9.1关键路径算法原理 279
7.9.2关键路径算法 280
7.10总结回顾 287
7.11结尾语 289
世界上最遥远的距离，不是牛a与牛c之间狭小空隙，而是你们当中，有人在通往牛逼的路上一路狂奔，而有人步入大学校园就学会放弃。
第8章查找 291
8.1开场白 292
当你精心写了一篇博文或者上传一组照片到互联网上，来自世界各地的无数“蜘蛛”便会蜂拥而至。所谓蜘蛛就是搜索引擎公司服务器上软件，它把互联网当成了蜘蛛网，没日没夜的访问上面的各种信息。
8.2查找概论 293
比如网络时代的新名词，如“蜗居”、“蚁族”等，如果需要将它们收录到汉语词典中，显然收录时就需要查找它们是否存在，以及找到如果不存在时应该收录的位置。
8.3顺序表查找 295
8.3.1顺序表查找算法 296
8.3.2顺序表查找优化 297
8.4有序表查找 298
我在纸上已经写好了一个100以内的正整数请你猜，问几次可以猜出来。当时已经介绍了如何才可以最快的猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找。
8.4.1折半查找 298
8.4.2插值查找 301
8.4.3斐波那契查找 302
8.5线性索引查找 306
我母亲年纪大了，经常在家里找不到东西，于是她用一小本子，记录了家里所有小东西放置的位置，比如户口本放在右手床头柜下面抽屉中，钞票放在衣……咳，这个就不提了。
8.5.1稠密索引 307
8.5.2分块索引 308
8.5.3倒排索引 311
8.6二叉排序树 313
后来老虎来了，一人拼命地跑，另一人则急中生智，爬到了树上。而老虎是不会爬树的，结果……。爬树者改变了跑的思想，这一改变何等重要，捡回了自己的一条命。
8.6.1二叉排序树查找操作 316
8.6.2二叉排序树插入操作 318
8.6.3二叉排序树删除操作 320
8.6.4二叉排序树总结 327
8.7平衡二叉树（avl树） 328
平板就是一个世界，当诱惑降临，人心中的平衡被打破，世界就会混乱，最后留下的只有孤独寂寞失败。这种单调的机械化的社会，禁不住诱惑的侵蚀，最容易被侵蚀的，恰恰是最空虚的心灵。
8.7.1平衡二叉树实现原理 330
8.7.2平衡二叉树实现算法 334
8.8多路查找树（b树） 341
要观察一个公司是否严谨，看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴，即兴发言，这肯定是一家不严谨的公司。
8.8.12-3树 343
8.8.22-3-4树 348
8.8.3b树 349
8.8.4b+树 351
8.9散列表查找（哈希表）概述 353
你很想学太极拳，听说学校有个叫张三丰的人打得特别好，于是到学校学生处找人，工作人员拿出学生名单，最终告诉你，学校没这个人，并说张三丰几百年前就已经在武当山作古了。
8.9.1散列表查找定义 354
8.9.2散列表查找步骤 355
8.10散列函数的构造方法 356
8.10.1直接定址法 357
8.10.2数字分析法 358
8.10.3平方取中法 359
8.10.4折叠法 359
8.10.5除留余数法 359
8.10.6随机数法 360
8.11处理散列冲突的方法 360
我们每个人都希望身体健康，虽然疾病可以预防，但不可避免，没有任何人可以说，生下来到现在没有生过一次病。
8.11.1开放定址法 361
8.11.2再散列函数法 363
8.11.3链地址法 363
8.11.4公共溢出区法 364
8.12散列表查找实现 365
8.12.1散列表查找算法实现 365
8.12.2散列表查找性能分析 367
8.13总结回顾 368
8.14结尾语 369
如果我是个喜欢汽车的人，时常搜汽车信息。那么当我在搜索框中输入“甲壳虫”、“美洲虎”等关键词时，不要让动物和人物成为搜索的头条。
第9章排序 373
9.1开场白 374
假如我想买一台iphone4的手机，于是上了某电子商务网站去搜索。可搜索后发现，有8863个相关的物品，如此之多，这叫我如何选择。我其实是想买便宜一点的，但是又怕遇到骗子，想找信誉好的商家，如何做？
9.2排序的基本概念与分类 375
比如我们某些大学为了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分倒序排名，并且在同样总分的情况下将语数外总分做倒序排名。这就是对总分和语数外总分两个次关键字的组合排序。
9.2.1排序的稳定性 376
9.2.2内排序与外排序 377
9.2.3排序用到的结构与函数 378
9.3冒泡排序 378
无论你学习哪种编程语言，在学到循环和数组时，通常都会介绍一种排序算法，而这个算法一般就是冒泡排序。并不是它的名称很好听，而是说这个算法的思路最简单，最容易理解。
9.3.1最简单排序实现 379
9.3.2冒泡排序算法 380
9.3.3冒泡排序优化 382
9.3.4冒泡排序复杂度分析 383
9.4简单选择排序 384
还有一种做股票的人，他们很少出手，只是在不断观察和判断，等时机一到，果断买进或卖出。他们因为冷静和沉着，以及交易的次数少，而最终收益颇丰。
9.4.1简单选择排序算法 384
9.4.2简单选择排序复杂度分析 385
9.5直接插入排序 386
哪怕你是第一次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到最左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。
9.5.1直接插入排序算法 386
9.5.2直接插入排序复杂度分析 388
9.6希尔排序 389
不管怎么说，希尔排序算法的发明，使得我们终于突破了慢速排序的时代（超越了时间复杂度为o(n2)），之后，更为高效的排序算法也就相继出现了。
9.6.1希尔排序原理 391
9.6.2希尔排序算法 391
9.6.3希尔排序复杂度分析 395
9.7堆排序 396
什么叫堆结构呢？回忆一下我们小时候，特别是男同学，基本都玩过叠罗汉的恶作剧。通常都是先把某个要整的人按倒在地，然后大家就一拥而上扑了上去……后果？后果当然就是一笑了之。
9.7.1堆排序算法 398
9.7.2堆排序复杂度分析 405
9.8归并排序 406
即使你是你们班级第一、甚至年级第一名，如果你没有上分数线，则说明你的成绩排不到全省前1万名，你也就基本失去了当年上本科的机会了。
9.8.1归并排序算法 407
9.8.2归并排序复杂度分析 413
9.8.3非递归实现归并排序 413
9.9快速排序 417
终于我们的高手要登场了，将来你工作后，你的老板让你写个排序算法，而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。
9.9.1快速排序算法 417
9.9.2快速排序复杂度分析 421
9.9.3快速排序优化 422
9.10总结回顾 428
目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。
9.11结尾语 430
如果你有梦想的话，就要去捍卫它。当别人做不到的时候，他们就想要告诉你，你也不能。如果你想要些什么，就得去努力争取。就这样！
附录参考文献 435
京公网安备 11010802033920号
