重磅推荐
【产品特色】


【编辑】

编辑的话
2008年,一本特立独行的IT技术图书《大话设计模式》横空出世,开创了一种新派技术图书风格,横扫各大排行。
作者程杰并没有满足这个成绩,耗时3年潜心创作了另外一本同样是程序员基础的著作——《大话数据结构》,不出意外地好评如潮。
直到今天,这两本书仍然常驻各大排行。作为本土原创图书,这个成绩简直不可思议——印象里只有国外经典技术图书具备如此强的生命力。
虽然在这十几年里程杰兄未再动笔,但依然与我保持着密切联系。非常荣幸的是,在这本新作中,我依然是他的编辑。
十几年来,IT技术已经有了翻天覆地的变化,当年的桌面程序基本都迁移到了当前的互联网和移动端上,以至人工智能、深度学习,开发语言也从当初C、Java为主力语言变成如今包治百病的Python,我作为一个IT编辑,回顾起来其实还挺有意思的。
关于《大话数据结构【溢彩加强版】》的代码语言,确实跟程杰有过小小的争执,我建议换Python,程杰还是坚持用C。他的理由是:讲解数据结构,还是得用*干净纯粹的通用经典计算机语言,虽然Python很灵动,正是这种灵动,有时在解析数据结构的时候显得不够严肃和“正统”,而程序员的基础必修课,必须要一拳一脚地养成规范的动作习惯。
数据结构在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年卓越程序员的智慧结晶,而数据结构是几百上千年无数科学家、数学家的智慧沉淀,具有更加深厚的背景。
大家知道,程序是利用计算机的高速运算能力来协助我们处理一些需要海量运算得出结果的问题,花哨的界面和良好的用户体验背后,是无数计算机强大的算力得出我们需要的结果——无论是气象预报还是扫脸支付。
一台计算机的CPU运算能力是固定的,只会机械地接收程序的指令,所以,算法的优劣就决定了程序设计水平的高低(关于计算机硬件的运算原理和流程,这里一《大话数据结构【溢彩加强版】》——《大话计算机》【清华大学出版社】)。举个简单的例子,数据库性能优化这个工作,收费是按照小时来计算的,有个段子,真实性无从考证:水平高的每小时可以达到30万美金。为什么会值这么多钱?有价值吗?本质上讲这就是算法的力量,使用优秀的算法可以在为企业节省海量的硬件投入同时带来巨大的效率提升——比如之前需要100台小型机,优化之后只需要10台就够了;之前生成一个数据需要1分钟出来结果,优化之后1秒钟就够了……这对于企业来说,节省的成本可就远远不止投入的几十上百万元的优化费用了。当然,数据库优化有很多算法优化之外的技术,但是如果优化结果发生了质变,那一定主要是算法的功劳。
国内外优秀的程序员很多是数学专业出身,也在一定程度上说明了这个问题。很多程序员被戏称为“码农”——一种流水线机械作业的工种,至今此工种仍大量存在。可以预见的是,随着软件开发集成度的提高和AI技术的发展,“码农”会大量减少,未来的软件开发需要的是“软件架构师”和“算法工程师”,无论走哪条路线,算法都是重中之重。可以说,算法基础不牢靠,职业生涯不牢靠。(关于这个话题,再一《大话数据结构【溢彩加强版】》——《大话软件工程》【清华大学出版社】)
我们的程序员因为在受教育的过程中,由于种种原因,数据结构和算法的基本功通常要差一些,等从业以后想再补课又缺乏好的,或者说适合自学的教材。数据结构不是说没有优秀教材,比如《数据结构》(严蔚敏清华版)、《算法导论》(机工版)这样的经典著作我们*不能说不好,但是作为自学,实在是有点难啃。
《大话数据结构【溢彩加强版】》延续了前作轻松调侃的风格,采用了师生对话的方式展开讨论,其中穿插了大量“接地气”的类比案例,帮助大家迅速“开窍”,在我的建议下,程杰精心将《大话数据结构【溢彩加强版】》图表制作成彩色,阅读起来你会发现,不仅仅是养眼,对一些流程、概念的解说,用彩色图表更为精准,学习体验有了质变。

感谢程杰这样的优秀作者真诚地将自己的感悟奉献出来。与作者的用心相比,作为策划编辑付出的劳动就不值得一提了。这里真心希望读者可以从书中找到需要的东西,也希望国内更多高人涌现出来,为读者创作更适合中国人阅读的优秀科技图书。

清华大学出版社
栾大成


【内容简介】

《大话数据结构【溢彩加强版】》以一个计算机教师的教学过程为场景,讲解数据结构和相关算法的知识。全书以趣味方式来叙述,大量引用各种各样的生活知识来类比,并充分运用全彩色图形语言来解读抽象内容,对数据结构所涉及的一些经典算法做出逐行分析、多算法比较。与同类图书相比,《大话数据结构【溢彩加强版】》内容有趣易读,算法讲解细致深入,是一本非常适合自学的读物。
对于学习数据结构来说,难点之一是对相关算法的理解。《大话数据结构【溢彩加强版】》创新性地采用全彩印刷,图表、流程、代码等内容结合色彩来重新进行约定和归纳,使得对一些难以理解的知识点的解析更加清晰顺畅,极大提升了阅读体验。
《大话数据结构【溢彩加强版】》主要内容包含:数据结构介绍、算法推导大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.4.2?数据元素 6
1.4.3?数据项 7
1.4.4?数据对象 7
1.4.5?数据结构 7
1.5 逻辑结构与物理结构 8
1.5.1?逻辑结构 8
1.5.2?物理结构 9
1.6 数据类型 11
大家都需要房子住,但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型,有几百平米的别墅,也有仅两平米的胶囊公寓……
1.6.1?数据类型定义 11
1.6.2?抽象数据类型 12
1.7 总结回顾 13
1.8 结尾语 14
*终的结果一定是,你对着别人很牛地说“数据结构——就那么回事。”
第2章 算法 15

2.1 开场白 16
2.2 数据结构与算法的关系 16
计算机界的前辈们,是一帮很牛很牛的人,他们使得很多看似没法解决或者很难解决的问题,处理得如此美妙和神奇。
2.3 两种算法的比较 17
高斯在上小学的一天,老师要求每个学生都计算1 2 … 100的结果,谁先算出来谁先回家……
2.4 算法定义 18
现实世界中的算法千变万化,没有通用算法可以解决所有问题。甚至一个小问题,某个解决此类问题很优秀的算法却未必就适合它。
2.5 算法的特性 19
2.5.1?输入输出 19
2.5.2?有穷性 19
2.5.3?确定性 20
2.5.4?可行性 20
2.6 算法设计的要求 20
求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,我们自然追求高效率和低存储的算法来解决问题。
2.6.1?正确性 21
2.6.2?可读性 21
2.6.3?健壮性 21
2.6.4?时间效率高和存储量低 22
2.7 算法效率的度量方法 22
随着n值越来越大,它们在时间效率上的差异也就越来越大。好比有些人每天都在学习,而有些人,打打游戏、睡睡大觉,毕业后前者名企争着要,后者求职处处无门。
2.7.1?事后统计方法 22
2.7.2?事前分析估算方法 23
2.8 函数的渐近增长 25
2.9 算法时间复杂度 27
理解大O阶推导不算难,难的其实是对数列的一些相关运算,这考查的更多是数学知识和能力。
2.9.1?算法时间复杂度定义 27
2.9.2?推导大O阶方法 28
2.9.3?常数阶 28
2.9.4?线性阶 29
2.9.5?对数阶 29
2.9.6?平方阶 29
2.10 常见的时间复杂度 31
有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以招惹吧。
2.11 *坏情况与平均情况 32
2.12 算法空间复杂度 33
事先建立一个有2050个元素的数组,然后把所有年份按下标数字对应,如果是闰年,此数组项的值就是1,如果不是就是0。这样,所谓的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题。
2.13 总结回顾 34
2.14 结尾语 35
愚公移山固然可敬,但发明炸药和推土机,可能更加实在和聪明。
第3章 线性表 37

3.1 开场白 38
门外家长都挤在大门口与门里的小孩子的井然有序,形成了鲜明对比。哎,有时大人的所作所为,其实还不如孩子。
3.2 线性表的定义 39
有时我们想知道某个小朋友(比如麦兜)是否是班级的同学,老师会告诉我说,没有,麦兜是在春田花花幼儿园里。这种查找某个元素是否存在的操作很常用。
3.3 线性表的抽象数据类型 41
3.4 线性表的顺序存储结构 43
他每次一吃完早饭就冲着去了图书馆,挑一个好地儿,把他书包里的书,一本一本地按座位放好,长长一排,九个座硬是被他占了。
3.4.1?顺序存储定义 43
3.4.2?顺序存储方式 43
3.4.3?数据长度与线性表长度的区别 44
3.4.4?地址计算方法 45
3.5 顺序存储结构的插入与删除 46
春运时去买火车票,大家都排着队好好的,这时来了一个美女:“可否让我排在你前面?”这可不得了,后面的人像蠕虫一样,全部都得退后一步。
3.5.1?获得元素操作 46
3.5.2?插入操作 46
3.5.3?删除操作 47
3.5.4?线性表顺序存储结构的优缺点 49
3.6 线性表的链式存储结构 49
反正也是要让相邻元素间留有足够余地,那干脆所有元素都不要考虑相邻位置了,哪有空位就到哪里。而只是让每个元素知道它下一个元素的位置在哪里。
3.6.1?顺序存储结构不足的解决办法 49
3.6.2?线性表链式存储结构定义 50
3.6.3?头指针与头结点的异同 52
3.6.4?线性表链式存储结构代码描述 52
3.7 单链表的读取 53
3.8 单链表的插入与删除 54
本来是爸爸左手牵着妈妈的手、右手牵着宝宝的手在马路边散步。突然迎面走来一美女,爸爸失神般地望着,此情景被妈妈逮个正着,于是扯开父子俩,拉起宝宝的左手就快步朝前走去。
3.8.1?单链表的插入 54
3.8.2?单链表的删除 56
3.9 单链表的整表创建 58
3.10 单链表的整表删除 60
3.11 单链表结构与顺序存储结构的优缺点 61
3.12 静态链表 62
对于一些语言,如Basic、Fortran等早期的编程高级语言,由于没有指针,这链表结构,按照前面我们的讲法,它就没法实现了。怎么办呢?
3.12.1?静态链表的插入操作 64
3.12.2?静态链表的删除操作 65
3.12.3?静态链表的优缺点 67
3.13 循环链表 67
这个轮回的思想很有意思。它强调了不管你今生是穷是富,如果持续行善积德,下辈子就会好过,反之就会遭到报应。
3.14 双向链表 70
就像每个人的人生一样,欲收获就得付出代价。双向链表既然是比单链表多了如可以反向遍历查找等的数据结构,那么也就需要付出一些小的代价。
3.15 总结回顾 72
3.16 结尾语 73
如果你觉得上学读书是受罪,假设你可以活到80岁,其实你*多也就吃了20年苦。用人生四分之一的时间来换取其余时间的幸福生活,这点苦不算啥。
第4章 栈与队列 75

4.1 开场白 76
想想看,在你准备用枪的时候,突然这手枪明明有子弹却打不出来,这不是要命吗。
4.2 栈的定义 76
类似的很多软件,比如Word、Photoshop等,都有撤销(undo)的操作,也是用栈这种思想方式来实现的。
4.2.1?栈的定义 76
4.2.2?进栈出栈变化形式 78
4.3 栈的抽象数据类型 78
4.4 栈的顺序存储结构及实现 79
4.4.1?栈的顺序存储结构 79
4.4.2?栈的顺序存储结构——进栈操作 80
4.4.3?栈的顺序存储结构——出栈操作 81
4.5 两栈共享空间 81
两个大学室友毕业同时到北京工作,他们都希望租房时能找到独自住的一室或一室一厅,可找来找去发现,价格实在是承受不起。
4.6 栈的链式存储结构及实现 83
4.6.1?栈的链式存储结构 83
4.6.2?栈的链式存储结构——进栈操作 84
4.6.3?栈的链式存储结构——出栈操作 85
4.7 栈的作用 85
4.8 栈的应用——递归 86
当你往镜子前面一站,镜子里面就有一个你的图像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个“化身”。
4.8.1?斐波那契数列的实现 86
4.8.2?递归的定义 88
4.9 栈的应用——四则运算表达式求值 89
4.9.1?后缀(逆波兰)表示法的定义 89
4.9.2?后缀表达式的计算结果 90
4.9.3?中缀表达式转后缀表达式 92
4.10 队列的定义 93
电脑有时会处于疑似死机的状态。就当你失去耐心,打算Reset时,突然它像酒醒了一样,把你刚才单击的所有操作全部都按顺序执行了一遍。
4.11 队列的抽象数据类型 94
4.12 循环队列 95
你上了公交车发现前排有两个空座位,而后排所有座位都已经坐满,你会怎么做?立马下车,并对自己说,后面没座了,我等下一辆?没这么笨的人,前面有座位,当然也是可以坐的。
4.12.1?队列顺序存储的不足 95
4.12.2?循环队列的定义 96
4.13 队列的链式存储结构及实现 99
4.13.1?队列的链式存储结构——入队
    操作 100
4.13.2?队列的链式存储结构——出队
    操作 100
4.14 总结回顾 101
4.15 结尾语 102
人生,需要有队列精神的体现。南极到北极,不过是南纬90°到北纬90°的队列,如果你中途犹豫,临时转向,也许你就只能和企鹅相伴永远。可事实上,无论哪个方向,只要你坚持到底,你都可以到达终点。
第5章 串 103

5.1 开场白 104
“枯眼望遥山隔水,往来曾见几心知?壶空怕酌一杯酒,笔下难成和韵诗。途路阻人离别久,讯音无雁寄回迟。孤灯夜守长寥寂,夫忆妻兮父忆儿。”……可再仔细一读发现,这首诗竟然可以倒过来读。
5.2 串的定义 104
我所提到的over、end、lie其实就是lover、friend、believe这些单词字符串的子串。
5.3 串的比较 105
5.4 串的抽象数据类型 107
5.5 串的存储结构 108
感情上发生了问题,为了向女友解释一下,我准备发一条短信,一共打了75个字。*后8个字是“我恨你是不可能的”,点发送。后来得知对方收到的,只有70个字,短信结尾是“……我恨你”。
5.5.1?串的顺序存储结构 108
5.5.2?串的链式存储结构 109
5.6 朴素的模式匹配算法 110
主串为S=“00000000000000000000000000000000000000000000000001”,而要匹配的子串为T=“0000000001”,……在匹配时,每次都得将T中字符循环到*后一位才发现,哦,原来它们是不匹配的。
5.7 KMP模式匹配算法 113
很多年前我们的科学家觉得像这种有多个0和1重复字符的字符串,却需要挨个遍历的算法,是非常糟糕的事情。
5.7.1?KMP模式匹配算法的原理 113
5.7.2?next数组值的推导 116
5.7.3?KMP模式匹配算法的实现 117
5.7.4?KMP模式匹配算法的改进 119
5.7.5?nextval数组值的推导 120
5.8 总结回顾 122
5.9 结尾语 122
《璇玑图》共八百四十字,纵横各二十九字,纵、横、斜、交互、正、反读或退一字、迭一字读均可成诗,诗有三、四、五、六、七言不等,目前有人统计可组成七千九百五十八首诗。听清楚哦,是7958首。
第6章 树 125

6.1 开场白 126
无论多高多大的树,那也是从小到大,由根到叶,一点点成长起来的。俗话说“十年树木,百年树人”,可一棵大树又何止是十年这样容易。
6.2 树的定义 126
树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念,这是比较新的一种定义方法。
6.2.1?结点的分类 127
6.2.2?结点间的关系 128
6.2.3?树的其他相关概念 129
6.3 树的抽象数据类型 129
6.4 树的存储结构 130
6.4.1?双亲表示法 130
6.4.2?孩子表示法 133
6.4.3?孩子兄弟表示法 136
6.5 二叉树的定义 137
苏东坡曾说:“人有悲欢离合,月有阴晴圆缺,此事古难全”。意思就是完美是理想,不完美才是人生。我们通常举的例子也都是左高右低、参差不齐的二叉树。那是否存在完美的二叉树呢?
6.5.1?二叉树的特点 139
6.5.2?特殊二叉树 140
6.6 二叉树的性质 142
6.6.1?二叉树的性质1 142
6.6.2?二叉树的性质2 143
6.6.3?二叉树的性质3 143
6.6.4?二叉树的性质4 144
6.6.5?二叉树的性质5 144
6.7 二叉树的存储结构 145
6.7.1?二叉树的顺序存储结构 145
6.7.2?二叉链表 146
6.8 遍历二叉树 147
你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业等选择,由于选择方式的不同,遍历的次序就完全不同。
6.8.1?二叉树的遍历原理 147
6.8.2?二叉树的遍历方法 148
6.8.3?前序遍历算法 150
6.8.4?中序遍历算法 153
6.8.5?后序遍历算法 156
6.8.6?推导遍历结果 156
6.9 二叉树的建立 158
6.10 线索二叉树 159
我们现在提倡节约型社会,一切都应该节约为本。对待我们的程序当然也不例外,能不浪费的时间或空间,都应该考虑节约。
6.10.1?线索二叉树的原理 159
6.10.2?线索二叉树结构的实现 162
6.11 树、森林与二叉树的转换 165
有个乡镇企业也买了同样的生产线,老板发现这个问题后找了个小工来说:你必须搞定,不然炒你鱿鱼。小工很快想出了办法:他在生产线旁边放了台风扇猛吹,空皂盒自然会被吹走。
6.11.1?树转换为二叉树 166
6.11.2?森林转换为二叉树 167
6.11.3?二叉树转换为树 168
6.11.4?二叉树转换为森林 169
6.11.5?树与森林的遍历 170
6.12 哈夫曼树及其应用 171
压缩而不出错是如何做到的呢?简单地说,就是把我们要压缩的文本进行重新编码,以达到减少不必要的空间的技术。压缩和解压缩技术就是基于哈夫曼的研究之上发展而来,我们应该记住他。
6.12.1?哈夫曼树 171
6.12.2?哈夫曼树的定义与原理 173
6.12.3?哈夫曼编码 176
6.13 总结回顾 177
6.14 结尾语 178
人受伤时会流下泪水。树受伤时,天将不会哭。希望我们的未来不要仅仅是钢筋水泥建造的高楼,也要有那郁郁葱葱的森林和草地,我们人类才可能与自然和谐共处。
第7章 图 181

7.1 开场白 182
如果你不善于规划,很有可能就会出现如玩好新疆后到海南,然后再冲向黑龙江这样的荒唐决策。
7.2 图的定义 182
现实中,人与人之间的关系非常复杂,比如我认识的朋友,可能他们之间也互相认识,这就不是简单的一对一、一对多的关系了,这就是我们今天要研究的主题——图。
7.2.1?各种图的定义 183
7.2.2?图的顶点与边间的关系 185
7.2.3?连通图的相关术语 187
7.2.4?图的定义与术语总结 189
7.3 图的抽象数据类型 190
7.4 图的存储结构 191
因为美国的黑夜就是中国的白天,利用互联网,他的员工白天上班就可以监控到美国仓库夜间的实际情况,如果发生了像火灾、偷盗这样的突发事件,及时打电话给美国当地相关人员进行处理。
7.4.1?邻接矩阵 192
7.4.2?邻接表 195
7.4.3?十字链表 198
7.4.4?邻接多重表 199
7.4.5?边集数组 201
7.5 图的遍历 202
我有一天早晨准备出门,发现钥匙不见了。一定是我儿子拿着玩,不知道丢到哪个犄角旮旯去了,你们说,我应该如何找?
7.5.1?深度优先遍历 203
7.5.2?广度优先遍历 205
7.6 *小生成树 208
如果你加班加点,没日没夜设计出的结果是方案一,我想你离被炒鱿鱼应该是不远了(同学微笑)。因为这个方案比后两个方案一半还多的成本会让老板气晕过去的。
7.6.1?普里姆(Prim)算法 209
7.6.2?克鲁斯卡尔(Kruskal)算法 213
7.7 *短路径 218
有人为了省钱,需路程*短,但换乘站间距离长等原因并不省时间;另一些人,他为赶时间,*的需求是总时间要短;还有一类人,他们不想多走路,关键是换乘要少,这样可以在车上好好休息一下。
7.7.1?迪杰斯特拉(Dijkstra)算法 220
7.7.2?弗洛伊德(Floyd)算法 225
7.8 拓扑排序 229
电影制作不可能在人员到位进驻场地时,导演还没有找到,也不可能在拍摄过程中,场地都没有。这都会导致荒谬的结果。
7.8.1?拓扑排序介绍 229
7.8.2?拓扑排序算法 230
7.9 关键路径 234
假如造一个轮子要0.5天、造一个发动机要3天、造一个车底盘要2天、造一个外壳要2天,造其他零部件2天,全部零部件集中到一处要0.5天,组装成车要2天,请问,在汽车厂造一辆车,*短需要多少天呢?
7.9.1?关键路径算法的原理 236
7.9.2?关键路径算法 237
7.10 总结回顾 242
7.11 结尾语 243
世界上*遥远的距离,不是牛A与牛C之间的狭小空隙,而是你们当中,有人在通往牛×的路上一路狂奔,而有人步入大学校园就学会放弃。
第8章 查找 245

8.1 开场白 246
当你精心写了一篇博文或者上传一组照片到互联网上,来自世界各地的无数“蜘蛛”便会蜂拥而至。所谓蜘蛛就是搜索引擎公司服务器上的软件,它把互联网当成了蜘蛛网,没日没夜地访问上面的各种信息。
8.2 查找概论 247
比如网络时代的新名词,如 “蜗居”“蚁族”等,如果需要将它们收录到汉语词典中,显然收录时就需要查找它们是否存在,以及如果不存在时应该收录的位置。
8.3 顺序表查找 249
8.3.1?顺序表查找算法 249
8.3.2?顺序表查找优化 250
8.4 有序表查找 251
我在纸上已经写好了一个100以内的正整数请你猜,问几次可以猜出来。当时已经介绍了如何才可以*快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找。
8.4.1?折半查找 251
8.4.2?插值查找 253
8.4.3?斐波那契查找 255
8.5 线性索引查找 257
我母亲年纪大了,经常在家里找不到东西,于是她用一小本子,记录了家里所有小东西放置的位置,比如户口本放在右手床头柜下面抽屉中,钞票放在衣……咳,这个就不提了。
8.5.1?稠密索引 258
8.5.2?分块索引 258
8.5.3?倒排索引 260
8.6 二叉排序树 262
后来老虎来了,一人拼命地跑,另一人则急中生智,爬到了树上。而老虎是不会爬树的,结果……。爬树者改变了跑的思想,这一改变何等重要,捡回了自己的一条命。
8.6.1?二叉排序树的查找操作 264
8.6.2?二叉排序树的插入操作 266
8.6.3?二叉排序树的删除操作 267
8.6.4?二叉排序树总结 272
8.7 平衡二叉树(AVL树) 273
平板就是一个世界,当诱惑降临,人们心中的平衡被打破,世界就会混乱,*后留下的只有孤独寂寞失败。这种单调的机械化的社会,禁不住诱惑的侵蚀,*容易被侵蚀的,恰恰是*空虚的心灵。
8.7.1?平衡二叉树的实现原理 275
8.7.2?平衡二叉树的实现算法 278
8.8 多路查找树(B树) 284
要观察一个公司是否严谨,看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴,即兴发言,这肯定是一家不严谨的公司。
8.8.1?2-3树 285
8.8.2?2-3-4树 289
8.8.3?B树 290
8.8.4?B 树 292
8.9 散列表查找(哈希表)概述 294
你很想学太极拳,听说学校有个叫张三丰的人打得特别好,于是到学校学生处找人,工作人员拿出学生名单,*终告诉你,学校没这个人,并说张三丰几百年前就已经在武当山作古了。
8.9.1?散列表查找定义 294
8.9.2?散列表查找步骤 295
8.10 散列函数的构造方法 296
8.10.1?直接定址法 297
8.10.2?数字分析法 297
8.10.3?平方取中法 298
8.10.4?折叠法 298
8.10.5?除留余数法 298
8.10.6?随机数法 299
8.11 处理散列冲突的方法 300
我们每个人都希望身体健康,虽然疾病可以预防,但不可避免,没有任何人可以说,生下来到现在没有生过一次病。
8.11.1?开放定址法 300
8.11.2?再散列函数法 302
8.11.3?链地址法 302
8.11.4?公共溢出区法 302
8.12 散列表查找的实现 303
8.12.1?散列表查找的算法实现 303
8.12.2?散列表查找的性能分析 305
8.13 总结回顾 305
如果我是个喜欢汽车的人,时常搜汽车信息。那么当我在搜索框中输入“甲壳虫”“美洲虎”等关键词时,不要让动物和人物成为搜索的头条。
8.14 结尾语 306
第9章 排序 309

9.1 开场白 310
假如我想买一台iPhone 4的手机,于是上了某电子商务网站去搜索。可搜索后发现,有8863个相关的物品,如此之多,这叫我如何选择。我其实是想买便宜一点的,但是又怕遇到骗子,想找信誉好的商家,如何做?
9.2 排序的基本概念与分类 310
比如我们某些大学为了选拔在主科上更优秀的学生,要求对所有学生的所有科目总分倒序排名,并且在同样总分的情况下将语数外总分做倒序排名。这就是对总分和语数外总分两个次关键字的组合排序。
9.2.1?排序的稳定性 311
9.2.2?内排序与外排序 312
9.2.3?排序用到的结构与函数 313
9.3 冒泡排序 314
无论你学习哪种编程语言,在学到循环和数组时,通常都会介绍一种排序算法,而这个算法一般就是冒泡排序。并不是它的名称很好听,而是说这个算法的思路*简单,*容易理解。
9.3.1?*简单排序的实现 314
9.3.2?冒泡排序算法 315
9.3.3?冒泡排序优化 316
9.3.4?冒泡排序复杂度分析 317
9.4 简单选择排序 318
还有一种做股票的人,他们很少出手,只是在不断观察和判断,等时机一到,果断买进或卖出。他们因为冷静和沉着,以及交易的次数少,而*终收益颇丰。
9.4.1?简单选择排序算法 318
9.4.2?简单选择排序复杂度分析 319
9.5 直接插入排序 320
哪怕你是*次玩扑克牌,只要认识这些数字,理牌的方法都是不用教的。将3和4移动到5的左侧,再将2移动到*左侧,顺序就算是理好了。这里,我们的理牌方法,就是直接插入排序法。
9.5.1?直接插入排序算法 320
9.5.2?直接插入排序复杂度分析 322
9.6 希尔排序 323
不管怎么说,希尔排序算法的发明,使得我们终于突破了慢速排序的时代(超越了时间复杂度为O(n2)),之后,更为高效的排序算法也就相继出现了。
9.6.1?希尔排序原理 324
9.6.2?希尔排序算法 325
9.6.3?希尔排序复杂度分析 328
9.7 堆排序 329
什么叫堆结构呢?回忆一下我们小时候,特别是男同学,基本都玩过叠罗汉的恶作剧。通常都是先把某个要整的人按倒在地,然后大家就一拥而上扑了上去……后果?后果当然就是一笑了之。
9.7.1?堆排序算法 331
9.7.2?堆排序复杂度分析 337
9.8 归并排序 337
即使你是你们班级*、甚至年级*名,如果你没有上分数线,则说明你的成绩排不到全省前1万名,你也就基本失去了当年上本科的机会了。
9.8.1?归并排序算法 338
9.8.2?归并排序复杂度分析 343
9.8.3?非递归实现归并排序 343
9.9 快速排序 346
终于我们的高手要登场了,将来你工作后,你的老板让你写个排序算法,而你会的算法中竟然没有快速排序,我想你还是不要声张,偷偷去把快速排序算法找来敲进电脑,这样至少你不至于被大伙儿取笑。
9.9.1?快速排序算法 346
9.9.2?快速排序复杂度分析 349
9.9.3?快速排序优化 350
9.10 总结回顾 354
目前还没有十全十美的排序算法,有优点就会有缺点,即使是快速排序法,也只是在整体性能上优越,它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。
9.11 结尾语 357
如果你有梦想的话,就要去捍卫它。当别人做不到的时候,他们就想要告诉你,你也不能。如果你想要些什么,就得去努力争取。就这样!


【前言】

本书起因
大家好!我是《大话设计模式》(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); /* 执行一次 */

当前样式:


返回顶部