1.1 一维数组（markdown版）

一维数组简介

数组是最简单的，也最基础的数据结构。数组是一个有序的数据集合，用索引（或者叫下标）访问数据。在大多数编程语言，比如C/C++/java/javascript中，数组的索引都是以0开始。它的逻辑结构是一段连续的空间（因为虚拟内存的原因，实际情况下大数组可能由多个不连续的内存页组成）。
如下图所示：

上图中，第一行表示数据第二行表示索引

应用案例

需求

一维数组，我会以一个案例来开始。

假设有这么一个需求，求11个点能构成多少种二叉树。比如3个点，可以构成五种二叉树：
​​​​

按照序言里的步骤，我们第一步是仔细研究需求。从上图看，所有的树都是线性结构。那么不同在哪里？可见这个问题其实是数学里的组合计数问题。

解题思路

以3个点为例子，作为二叉树必须要有根节点。那么利用分类归纳法，可以这样计算出来。

• 场景1 只有左节点
  

• 场景2 左右节点都存在
  

• 场景3 只有右节点
  

以上场景实际上是什么问题？是结点的左右分配问题！那么假设N个结点能组成二叉树的数目为C(n)

• 场景1
  左节点数量2，右节点数量0，树的数量为左边树的数量C(2)*右边树的数量 C(0)
• 场景2
  左节点数量1，右节点数量1，树的数量为左边树的数量C(1)*右边树的数量 C(1)
• 场景3
  左节点数量0，右节点数量2，树的数量为左边树的数量C(0)*右边树的数量 C(2)
  所以对于N个结点，就可以分成N种场景。左边的数目确定了，右边的数目就也确定了。所以可以写出递归公式，是乘积的求和：
  C ( n ) = ∑ i = 0 n − 1 C ( i ) C ( n − i − 1 ) C(n) = \sum_{i = 0}^{n - 1}C(i)C(n - i - 1)C(n)=i=0∑n−1​C(i)C(n−i−1)
  那么这个问题，用什么数据结构呢？根据递归公式，可以清楚地知道我们需要存储C(0)到C(n-1)的所有数据，所以这个问题，一维数组这种数据结构最合适了。经过分析之后，代码就非常容易写了。

代码实现

Python代码

defc(n):ifn<2:return1array=[0]*(n+1)array[1]=array[0]=1foriinrange(2,n+1):forjinrange(0,i):array[i]+=array[j]*array[i-j-1]returnarray[n]

需要注意的是python中没有严格意义上的数组。为了严谨，这里附上java代码。

Java代码

publicstaticintcatalan(intn){if(n<2){return1;}int[]array=newint[n+1];array[1]=array[0]=1;for(inti=2;i<n+1;i++){for(intj=0;j<i;j++){array[i]+=array[j]*array[i-j-1];}}returnarray[n];}

这个数列就是著名的明安图数列，也叫卡特兰数列。不过在我们这个例子中，与卡特兰数列错了一位而已。
我们的例子中c(0)=1 c(1)=1 c(2)=2……
而卡特兰数列是c(1)=1 c(2)=1 c(3)=2……
递归公式，与卡特兰数列一模一样。
这个题目属于数学专业研究生的组合计数学课程。其实我是反对把知识分什么中学知识、大学知识、硕士阶段、博士阶段的。我们要做的仅仅是，按照编程的套路，先仔细分析需求，选择合适的数据结构，然后设计算法，编写代码，就可以了。