引子

什么是数据结构？如果翻阅不同的教材，可以看到五花八门的描述。事实上，这个问题在计算机科学界至今没有标准的定义。

在计算机科学中，数据结构 (英语：data structure) 是计算机中存储、组织数据的方式(维基百科）

思考问题

书籍摆放

问题：如果你是书店的主人，该如何摆放你的书籍，才能让顾客最快捷的找到想要的书籍？

• 方法 1：随便放

放书非常方便，有新书直接插到空位。但是查找很不方便，如果没有这本书，需要翻遍整个书架

• 方法 2：按照书名的拼音字母顺序排放

新书插入需要给新书腾出空间，造成图书需要向后移动

• 方法 3：把书架分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放

查找和插入工作量都减少很多，但是无法预估每种类别的图书会有多少，容易造成空间的浪费

数字打印

问题：写程序实现一个函数 PrintN，使得传入一个正整数为 N 的参数，能顺序打印从 1 到 N 的全部正整数

// 版本一
function PrintN($n)
{for ($i=1; $i <= $n; $i++) {echo "{$i}\n";
    }
}
// 版本二
function PrintN($n)
{if ($n > 0) {PrintN($n-1);
        echo "{$n}\n";
    }
}

当输入 N 为 100、1000、10000…，N 变的越来越大时候，实现版本一和版本二有什么区别？(debug_backtrace)

一元多项式计算

问题：一元多项式的标准表达式可以写成：f(x) = $a_0$ + $a_1$x + … + $a_{n-1}$$x^{n-1}$ + $a_n$$x^n$。现给定一个多项式的阶数 n，并将全体系数 $\{a_i\}^n_{i=0}$ 存放在数组 a[] 里。请写程序计算这个多项式在给定点 x 处的值

function f($n, $a, $x)
{$p = $a[0];
    for ($i=1; $i <= $n; $i++) {$p += $a[$i] * pow($x, $i);
    }
    return $p;
}
$x = 2; $n = 1;
$a = [];
for ($i=0; $i <= $n; $i++) {$a[$i] = $i+1;
}
$fn = f($n, $a, $x);
echo $fn . "\n";

通过提公因式 x 减少乘法的运算次数，把多项式改写为：

f(x) = $a_0$ + x($a_1$ + x(…($a_{n-1}$ + x($a_n$))…))

function f2($n, $a, $x)
{$p = $a[$n];
    for ($i=$n; $i > 0 ; $i--) {$p = $a[$i-1] + $x * $p;
    }
    return $p;
}

解决问题的效率

解决一个非常简单的问题，往往也有多种方法，且不同方法之间的效率可能相差甚远。解决问题方法的效率，跟 数据的组织方式 有关，跟 空间的利用效率 有关，也跟 算法的巧妙程度 有关。

《PHP 面试问答》https://github.com/colinlet/PHP-Interview-QA 欢迎 star 关注~~
结合实际 PHP 面试，汇总自己遇到的问题，以及网上其他人遇到的问题，尝试提供简洁准确的答案
包含网络、数据结构与算法、PHP、Web、MySQL、Redis、Linux、安全、设计模式、架构、面试等部分

数据结构

定义

• 数据结构的定义，首先应该包含数据对象在计算机中的组织方式——这类似于图书的摆放方法。并且，数据对象必定与一系列加在数据对象上的操作相关联，就如我们在书架上摆放图书是为了能找得到想要的书，或者是插入一本新买的书。
• 在讨论数据结构的时候，关心的是 数据对象 本身以及它们在计算机中的 组织方式 ，还要关心与它们相关联的 操作集，以及实现这些操作的最高效的算法。
• 关于数据对象在计算机中的组织方式，包含两个概念：数据对象集的逻辑结构、数据对象集在计算机中的物理存储结构

抽象数据类型

• 抽象数据类型 (Abstract Data Type) 是一种对 ” 数据结构 ” 的描述，这种描述是 ” 抽象 ” 的。数据类型描述内容：数据对象集、与数据集合相关联的操作集。
• 抽象：描述数据类型的方法不依赖于具体实现，即数据对象集合操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。抽象是计算机求解问题的基本方式和重要手段，使得一种设计可以应用于多种场景。

算法

定义

算法 (algorithm) 自于 9 世纪波斯数学家，在数学上提出了算法这个概念。

算法是一个 有限指令集，它接受一些输入(非必须)，产生输出，并一定在有限步骤之后终止。

算法不是程序，算法比程序更抽象，强调表现做什么，忽略细节性怎么做。这样的好处是使整体思路清晰易懂，形成模块化的风格。

算法复杂度

衡量、比较算法的指标主要有以下两个：

• 空间复杂度 S(n)：根据算法写成的程序在执行时占用存储单元的长度
• 时间复杂度 T(n)：根据算法写成的程序在执行时耗时时间的长度

分析一般算法效率：

• 最坏情况复杂度 $T_{worst}$(n)
• 平均复杂度 $T_{avg}$(n)

《数据结构与算法概述》原文链接：https://blog.maplemark.cn/2019/07/ 数据结构与算法概述.html

了解和学习一种知识的最好方法是带着相关的问题去探索，当我们把一些常见的问题全部解答了，我们也就能对这种事物有一些初步的了解了。试着回答下面的几个问题，让我们对数据结构和算法有一个基本的认识吧。

• 什么是数据结构？
• 为什么要了解数据结构？
• 作为一个前端，日常工作当中，我们接触的数据结构有哪几种？
• 数据结构和算法是什么关系？
• 如何判断一个算法是否是最优？

什么是数据结构？

从字面意思来理解就是一种数据的多种表现方法，什么是结构——由组成整体的各部分的搭配和安排（百度百科）。我的理解是：数据的排列，不同的数据结构就是数据的多种排列形式，然后根据排列的情况我们通常用一个学名来表示它，比如说：数组，集合，树，图等。

为什么要了解数据结构？

当我们了解了数据结构之后，在实际的编程过程当中，我们遇到某一类的数据的时候，我们就能够找到一种最合适的数据结构来表示他们了。这样再处理跟数据相关问题的时候就会变得高效，因为确定了数据结构，我们也就确定了针对该结构的数据，使用那些方法来对数据进行相关的操作了。比如说，我们需要一种数据结构来记录每天的天气情况，当我们说到某一天的时候，就能立刻知道当天的天气是怎么样的时候我们可以用一个数组来表现。又如，我们要描述一个家族的族谱的时候，用树型结构比较合适；描述一个人的年龄，身高，体重，民族，学历这种用集合比较合适；描述排队的情况用队列。

作为前端，通常我们接触到的数据结构有哪几种？

最常用的应该有两种了：数组，对象。到了 ES6 又增加了两种新的数据结构 Set 和 Map，其实 Set 和 Map 应该算是数组和对象的一种变种，但总的来说它们又是另外两种类型的数据结构；

• Set 类数组结构——成员唯一，没有重复的值
• Map 类对象结构——不同 Object，键值通常是字符串，Map 的键值可以是任何类型。

数据结构和算法的关系

数据结构只不过是我们描述数据的一种手段，但我们最终的目的通常是对这些数据进行相关的操作，比如：添加，删除，查找，排序等。所谓的算法就是如何去实现这种操作的一种计算方式。但算法往往不止一种，有道是条条道路通罗马，通常要达到某种目的，我们可能会有很多种的算法。比如一个数组我们要给他进行去重，就有很多种方法。你可以循环遍历，把每个值跟其他的值比较一遍，也可以把数组转成 Set 结构的数据。

如何判断一个算法是否最优？

上面说到实现某种操作的方法有很多种，但是哪一种是最好的，我们要如何判断呢。我们可以通过算法的执行时间对吧，那种算法执行的速度越快，当然那种算法就最好。但计算机当中，还要考虑到算法的空间复杂度，也就是算法执行过程当中，可能占用的内存空间，一个算法执行的速度非常块，但执行的时候，需要 1T 的内存空间，这就不行。所以好的算法往往有两个条件:

1. 运算的速度快
2. 占用的内存（存储空间）小

我还有个第三点，那就是代码便于理解，但这部分优秀的算法，往往涉及到很多数学相关的问题，如果没有这部分相关的概念，理解起来是非常不容易的。

其它

涉及到前端数据结构和算法的一些学习笔记，我放到了 github 上面，内容还在更新，尽量一周分享一个，欢迎大家一起来讨论并参与分享，github 地址如下:

https://github.com/mmcai/Stru…