还是先复习

• 程序结构有哪些？

顺序/循环/分支。

• 数据结构有哪些？

低阶的有：数组/链表/堆栈/队列

高阶的有：树/集/映射/图

算法设计的基础知识就是这些。

为什么老是强调数据结构？

西方有个谚语——

手里拿三年锤子，看什么都是钉子。

所以，有的时候真的是——

工具决定思维。

对于编写算法来说，掌握的数据结构越多，相当于手里的工具越多，再加上灵活应用，解决问题的思路就越宽，往往可以化困难为简易，化腐朽为神奇。

数据结构案例1——环形队列

先提个问题，如果现在我们需要设计一个环形的数据结构，怎样做呢？

环形结构的意思就是，一列数的尾部再加入一个新数时，这个新数会回到这一列数的头部。

就好像一只咬住自己尾巴的小蛇一样。

环形数据结构就好像这只小蛇

有童鞋说，那我就判断是否到达蛇尾，如果到了，再从蛇头开始计呗。

NO NO。看看下面这种环形队列的方式吧：

图中tail代表队列尾巴的地址，比如当前tail=7。

环形队列解析

用于存数据的格子数为N，这里N=11。

那么，神奇的事情来了，每当加入一个新数时，只需要

tail=(tail+1)%N

来解释一下哈，%表示求余数；所以上式的意思是：

来一个新数后，尾巴的地址就是尾巴加1再对总格子数求余数。

这样，原有数据都不需要任何移动。

一个数据结构的诞生，一个难题的迎刃而解。

请读者自己练习一个小问题，知道一个数据的地址为a，那么如何访问这个数据在环上的后一个数据呢？（顺时针）

找到数据结构就是建立数学模型

本专栏的第1课就讲到，算法程序的设计三要素：

数学模型/算法步骤/输入输出。

其中的数学模型是算法能够启动设计的基础，没有数学模型就无法开始算法。

不过这里强调，数学模型大致分两类：

物理数学模型 和 计算机数学模型。

物理数学模型是指，将物理现象归纳为数学规律，比如牛顿第二定律构建了物体运动中加速度与力之间的关系，再比如借助流体动力学研究管路中的流速场规律，再比如研究材料在环境内的传热模型等等。

上面这类物理问题，确实是许多算法的核心中的核心，只不过，想要建好物理数学模型首先是需要学好上面那些学科的，而算法的研究仅限于——

计算机数学模型。

再具体一点，建立计算机数学模型的主要工作，就是寻找一个合适的数据结构。

数据结构案例2——有向图应用

工程项目中，经常涉及到一个重要的问题，那就是项目是否能如期进行，并且项目中的子项目经常会有先后关系，所以我们常常使用类似于Project这样的软件来绘制甘特图来分析项目的最短时间路径，如下图。