数据结构与算法概述

引子

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

在计算机科学中，数据结构(英语：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;
}

解决问题的效率

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

数据结构

定义

• 数据结构的定义，首先应该包含数据对象在计算机中的组织方式——这类似于图书的摆放方法。并且，数据对象必定与一系列加在数据对象上的操作相关联，就如我们在书架上摆放图书是为了能找得到想要的书，或者是插入一本新买的书。

• 在讨论数据结构的时候，关心的是 数据对象 本身以及它们在计算机中的 组织方式 ，还要关心与它们相关联的 操作集 ，以及实现这些操作的最高效的算法。

• 关于数据对象在计算机中的组织方式，包含两个概念：数据对象集的逻辑结构、数据对象集在计算机中的物理存储结构

抽象数据类型

• 抽象数据类型(Abstract Data Type)是一种对”数据结构”的描述，这种描述是”抽象”的。数据类型描述内容：数据对象集、与数据集合相关联的操作集。

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

算法

定义

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

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

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

算法复杂度

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

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

分析一般算法效率：

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