MYBLOG

0XFF编程网

还是先复习

  • 程序结构有哪些?

顺序/循环/分支

  • 数据结构有哪些?

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

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

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


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

西方有个谚语——

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

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

工具决定思维。

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


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

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

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

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

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

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

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

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

环形队列解析

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

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

tail=(tail+1)%N

来解释一下哈,%表示求余数;所以上式的意思是:

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

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

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

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

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

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

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


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

不过这里强调,数学模型大致分两类:

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

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


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

计算机数学模型。

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

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

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


阅读 184
全部留言