第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