数据结构和算法：揭秘数据结构与算法的奥秘

内容简介

1. 前言
2. 什么是算法
3. 算法无处不在
4. 计算机的“特权”角色
5. 什么是数据结构
6. 第一部分第二课预告

1. 前言

程序员应该知道：程序 = 数据结构 + 算法（Program = Data Structure + Algorithm ）。

作为一个程序员，如果不了解数据结构和算法，应该会不太好意思出门跟人家打招呼。

在这个课程里，我会带大家以循序渐进、轻松幽默的形式从入门到精通数据结构和算法，相信我们会度过一段非常愉快的时光。

你会发现，入门数据结构和算法，其实一点都不难。

话休絮烦，我们直接进入主题。

2. 什么是算法

算法的英语是 Algorithm。

首先我们来思考一个问题：

什么是算法？

要很准确地回答这个问题并不容易，但其实也没那么难，我不需要用一大堆理论来说清楚什么是算法，况且算法也不仅限于 IT（Information Technology 的简称，表示“信息技术”）编程领域。

所以一个通俗易懂的回答可以是：

算法是以简单概念的形式对如何解决问题的一种精确描述。

所以说：

• 算法是一种描述（description），且是一种精确的描述。
• 描述什么？描述如何解决问题。
• 以什么样的形式来描述？以简单概念的形式。

说到问题，在日常生活中，我们经常需要解决问题。有的人可能每天需要解决很多问题，有的人可能就是问题本身。

下面我就来描述一个生活中的问题，从广义上来考虑“问题”和“算法”的概念。

3. 无所不在的算法

我们可以用一个几乎关乎所有人的问题来开始说明：烹饪。毕竟“民以食为天”。

假设你饿了，你来到厨房，想整点什么吃的，正好你看到了一包方便面，然后你不自觉舔了舔舌头，你想吃方便面了（如果你正好是在睡觉前看到这里，请不要打我。不鼓励大家多吃方便面。这里的例子也可以是煮饭、煮面或者烹饪其他食物），那你应该怎么烹饪它呢？

这是一个简单的过程（这里只说最简单的水煮的方式，请大家不要纠结烹饪的细节，也许你有其他更好的烹饪方便面的方式）：

1. 在锅子里倒入适量水
2. 在炉子上点起火来（如果是电磁炉就不用火）
3. 把锅子放在炉子上
4. 等待水开，转中火
5. 把方便面饼放入锅中
6. 煮半分钟
7. 放入所有调料包
8. 煮 1 分钟
9. 出锅

可以看到，我已经以简单概念的形式精确描述了如何解决“煮方便面”这个问题。

所以上面这套流程的描述，你可以把它称为“算法”，这个算法是专门针对“煮方便面”这个问题的。

你会注意到上面的例子中有许多暗含的东西：我说你最初拥有一包方便面，但你也需要锅子、水，等。

我们可能会处于所有这些东西都不可用的特定情况下，然后我们就得使用另一种算法（或许先得自己造口锅出来）。

上面的流程里，我使用的各条指令（步骤）是比较“精确的”，但我们可以精简到更少的指令，或扩充到更多指令。你也许会说，如果要更精确地说，得说明如何把水装进锅子里。

如果要根据这个食谱来烹饪方便面的人不知道如何执行“在锅子里倒入适量水”这一指令，则有必要用更简单的术语解释（例如，需要解释如何使用水龙头）。

类似地，在我们编程时，你使用的算法的精度取决于许多参数：你使用的编程语言，可用的库，等等。

4. 计算机的“特权”角色

如果在日常生活中能找到算法的痕迹，为什么我们却主要在计算机科学（Computer Science）中讨论它呢？

原因很简单：计算机（或电脑）非常擅长执行重复性任务。它们快速，高效，“任劳任怨”，从不喊累。

假设我们可以描述用于计算 3 的平方根的小数的算法（这算法得是人类可以操作的）。利用这个算法，你可以使用纸和笔来计算 3 的平方根的前 7 个小数位（1.7320508）。

但如果需要你计算 3 的平方根的前 10 万个小数位呢？用纸和笔会计算到怀疑人生。这种时候，计算机将变得更加合适。

我们可以设计出不少用于信息处理的算法。说到信息处理，通常有以下几类：

• 研究
• 比较
• 分析
• 分类
• 提取

计算机通常在这些方面更加有优势，可以很好地处理大量信息。

你可能已经想到了著名搜索引擎谷歌（最初谷歌正是靠着其搜索算法的实力才能主导市场，成就了今天超高的市值），但这种活动并不仅限于互联网领域。

当你玩即时战略游戏（Real-Time Strategy Game，简称 RTS。例如红警，星际争霸，等等）的时候，如果你下达指令给一个单位，让它移动。此时电脑需要掌握很多的信息（例如地图的结构，单位的起点，单位的终点），它也必须产生新的信息：单位应走的路线。

所以其实算法源于生活（毕竟算法是人想出来的），但是我们通常在 IT 这个领域才讨论算法，因为计算机的特殊性。

5. 什么是数据结构

上面说到了算法，现在我们来聊聊数据结构。数据结构的英语是 Data Structure。data 表示“数据”，structure 表示“结构”。

除了处理信息（数据是信息的符号表示或称载体，信息则是数据的内涵）外，还必须考虑如何存储信息。存储信息的方式可能会对其处理方式产生非常重要的影响。

具体地说，我们可以用字典作为例子。我们可以将字典定义为“单词及其定义的一个集合”（一个单词对应一个定义）。

如果一部字典里的单词是胡乱排序的，这样的字典应该很难使用吧。比如你要找一个单词的定义，你得一页页地翻字典，直到找到那个单词。

按字母顺序来排列单词显然是一种非常有效的解决方案，可以快速找到你所要的单词。因此，这是一种不错的存储信息的方式。

算法（描述方法）和数据结构（描述组织）之间存在非常紧密的联系。简单来说，对信息的存储方式就是数据结构关心的事，对信息的处理方式就是算法关心的事。

通常，某些数据结构对于某些算法的实现至关重要；反之亦然。

例如，如果我们想要在已经按字母顺序排列好的字典中添加一个新单词，我们就不能只是将这个新单词写在字典的最后一页的空白处，而是必须使用算法将其添加到正确的位置。

因此，数据结构的研究与算法的研究是密不可分的，需要同时来学习它们。