您现在的位置是:门户> 算法与数据结构

最简单易懂的10堂算法入门课——数据结构与数学模型
x0ffer 2018-12-19 359人围观 0条评论
简介对于编写算法来说,掌握的数据结构越多,相当于手里的工具越多,再加上灵活应用,解决问题的思路就越宽,往往可以化困难为简易,化腐朽为神奇

    还是先复习

    • 程序结构有哪些?

    顺序/循环/分支

    • 数据结构有哪些?

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

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

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


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

    西方有个谚语——

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

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

    工具决定思维。

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


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

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

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

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

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

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

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

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

    环形队列解析

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

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

    tail=(tail+1)%N

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

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

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

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

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

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

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

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


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

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

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

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


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

    计算机数学模型。

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

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

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


分享:

文章评论