大话数据结构（ 溢彩加强版）

第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
如果你有梦想的话，就要去捍卫它。当别人做不到的时候，他们就想要告诉你，你也不能。如果你想要些什么，就得去努力争取。就这样！