大话数据结构(程杰著)(1)

商家名称	信用等级	购买信息	订购本书
		大话数据结构(程杰著)
		大话数据结构(程杰著)

编辑推荐

《大话数据结构》为超级畅销书《大话设计模式》作者程杰潜心三年推出的扛鼎之作！以一个计算机教师教学为场景，讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述，大量引用了各种各样的生活知识来类比，并充分运用图形语言来体现抽象内容，对数据结构所涉及到的一些经典算法做到逐行分析、多算法比较。与市场上的同类数据结构图书相比，本书内容趣味易读，算法讲解细致深刻，是一本非常适合自学的读物。

名人推荐

超级畅销书《大话设计模式》作者的新作！用户群更为广泛，写作风格一如既往，技术沉淀更加深厚，势必掀起全民数据结构的热潮！

作者简介

程杰，一个被读者誉为很适合写IT技术书的家伙。《大话设计模式》作者。此书07年末出版至今已经简体版印刷9次、繁体版印刷6次，取得了较好的成绩，开创了一种适合国人阅读的趣味讲解IT知识的风格模式。其本人参与过政府、证券、游戏、交通等多种行业的软件开发及项目管理工作，也曾做过软件培训的教师。因曾有过两年半高中数学教学的独特经历，使得其书作当中处处以初学者视角考虑和分析问题，他成为了当前很受欢迎的IT技术图书作者之一。

目录

第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.7 KMP模式匹配算法 135
很多年前我们的科学家觉得像这种有多个0和1重复字符的字符串，却需要挨个遍历的算法，是非常糟糕的事情。
5.7.1 KMP模式匹配算法原理 135
5.7.2 next数组值推导 139
5.7.3 KMP模式匹配算法实现 141
5.7.4 KMP模式匹配算法改进 142
5.7.5 nextval数组值推导 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