为什么我们使用数组而不是其他数据结构？
在编程时，我还没有看到一个数组比其他forms更好地存储信息的实例。 我确实已经认识到编程语言中增加的“特征”在这方面有所改进，并由此取而代之。 我现在看到，他们没有被取代，而是被赋予了新的生命，可以这么说。
所以，基本上，使用数组有什么意义呢？
这不是为什么我们从计算机的angular度来使用数组，而是为什么我们会从编程的angular度使用数组（一个细微的差别）。 计算机对arrays的作用并不是问题的关键。
及时回去上课。 虽然我们今天在我们的花哨的托pipe语言中没有考虑到这些东西，但它们build立在同一个基础之上，所以让我们来看看如何在C中pipe理内存。
在我深入之前，快速解释一下“指针”是什么意思。 指针只是一个“指向”内存位置的variables。 它不包含这个内存区域的实际值，它包含了它的内存地址。 将一块内存视为一个邮箱。 指针将是该邮箱的地址。
在C中，数组只是一个带有偏移量的指针，偏移量指定了内存在多大程度上查找。 这提供了O（1）的访问时间。
MyArray [5] ^ ^ Pointer Offset 所有其他的数据结构要么build立在这个基础上，要么不使用相邻的存储器进行存储，导致随机访问查找时间很差（尽pipe不使用顺序存储器还有其他好处）。
例如，假设我们有一个6个数字（6,4,2,3,1,5）的数组，在内存中它看起来像这样：
===================================== | 6 | 4 | 2 | 3 | 1 | 5 | =====================================
在一个数组中，我们知道每个元素在内存中彼此相邻。 AC数组（这里称为MyArray）只是指向第一个元素的指针：
===================================== | 6 | 4 | 2 | 3 | 1 | 5 | ===================================== ^ MyArray
如果我们想查找MyArray [4]，在内部它将被这样访问：
0 1 2 3 4 ===================================== | 6 | 4 | 2 | 3 | 1 | 5 | ===================================== ^ MyArray + 4 ---------------/ (Pointer + Offset)
因为我们可以通过向指针添加偏移量来直接访问数组中的任何元素，所以无论数组大小如何，我们都可以在相同的时间内查找任何元素。 这意味着获取MyArray [1000]将花费与获得MyArray [5]相同的时间量。
另一种数据结构是一个链表。 这是一个线性的指针列表，每个指向下一个节点
======== ======== ======== ======== ======== | Data | | Data | | Data | | Data | | Data | | | -> | | -> | | -> | | -> | | | P1 | | P2 | | P3 | | P4 | | P5 | ======== ======== ======== ======== ======== P(X) stands for Pointer to next node.
请注意，我把每个“节点”放到了自己的块中。 这是因为他们不能保证（而且很可能不会）在记忆中相邻。
如果我想访问P3，我不能直接访问它，因为我不知道它在内存中的位置。 我所知道的只是根（P1）的位置，所以我必须从P1开始，然后跟随每个指针指向所需的节点。
这是一个O（N）查找时间（查找成本随着每个元素的添加而增加）。 到达P1000的成本要高于P4。
更高级别的数据结构（如散列表，堆栈和队列）都可以在内部使用数组（或多个数组），而链接列表和二进制树通常使用节点和指针。
您可能想知道为什么有人会使用需要线性遍历的数据结构来查找一个值，而不是仅仅使用一个数组，而是使用它们。
再次采取我们的arrays。 这一次，我想find保存值“5”的数组元素。
===================================== | 6 | 4 | 2 | 3 | 1 | 5 | ===================================== ^ ^ ^ ^ ^ FOUND!
在这种情况下，我不知道添加到指针的偏移量是多less，所以我必须从0开始，一直工作直到find它。 这意味着我必须执行6次检查。
因此，在数组中search一个值被认为是O（N）。 search成本随着数组变大而增加。
记得上面我说的有时使用非顺序数据结构可以有优势吗？ search数据是这些优点之一，最好的例子之一是二叉树。
二叉树是一种类似于链表的数据结构，但不是链接到单个节点，而是每个节点可以链接到两个子节点。
========== | Root | ========== / \ ========= ========= | Child | | Child | ========= ========= / \ ========= ========= | Child | | Child | ========= ========= Assume that each connector is really a Pointer
当数据插入到二叉树中时，它将使用多个规则来决定放置新节点的位置。 基本概念是，如果新值大于父项，则将其插入左侧，如果较低，则将其插入到右侧。
这意味着二叉树中的值可能如下所示：
========== | 100 | ========== / \ ========= ========= | 200 | | 50 | ========= ========= / \ ========= ========= | 75 | | 25 | ========= =========
当search二叉树的值为75时，我们只需要访问3个节点（O（log N）），因为这种结构：
- 75less于100？ 看右边的节点
- 75大于50？ 看左节点
- 有75！
即使树中有5个节点，我们也不需要看剩下的两个节点，因为我们知道他们（和他们的孩子）不可能包含我们正在寻找的值。 这给我们一个search时间，在最坏的情况下意味着我们必须访问每个节点，但是在最好的情况下，我们只需要访问一小部分节点。
这就是arrays被击败的地方，尽pipe存在O（1）的访问时间，但它们提供了恒定的O（N）search时间。
这是关于内存中数据结构的一个令人难以置信的高层次概述，跳过了很多细节，但是希望能够说明与其他数据结构相比数组的优点和缺点。
对于O（1）随机访问，不能被打的。
并不是所有的程序都做同样的事情，或者在同一个硬件上运行。
这通常是为什么存在各种语言特征的答案。 数组是计算机科学的核心概念。 用列表/matrix/向量来replacearrays/无论先进的数据结构如何，都会严重影响性能，而且在许多系统中是不切实际的。 由于所涉及的程序，应该使用这些“高级”数据收集对象之一的情况有多种。
在业务编程（我们大多数人都这样做）中，我们可以针对比较强大的硬件。 在C＃中使用List或者在Java中使用Vector是在这些情况下做出的正确select，因为这些结构允许开发人员更快地完成目标，从而使这类软件更具特色。
在编写embedded式软件或操作系统时，数组往往是更好的select。 虽然数组提供的function较less，但占用较less的RAM，编译器可以更高效地优化代码以查找数组。
我确信我正在为这些案例留下一些好处，但我希望你明白这一点。
查看数组优点的一种方法是查看数组的O（1）访问能力在哪里需要，因此大写：
-
在您的应用程序的查找表（用于访问某些分类响应的静态数组）
-
记忆（已经计算出复杂的函数结果，所以你不要再计算函数值，比如loggingx）
-
需要image processing的高速计算机视觉应用（ https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing ）
