是时候回到过去上一堂课了。虽然我们今天在我们的高级托管语言中对这些事情的考虑不多，但它们是基于相同的基础构建的，因此让我们看一下如何在C中管理内存。

在我深入之前，请先对“指针”一词的含义进行快速解释。指针仅仅是“指向”内存中某个位置的变量。它不包含该内存区域的实际值，而是包含该内存的地址。将一块内存视为邮箱。指针将是该邮箱的地址。

在C语言中，数组只是具有偏移量的指针，偏移量指定要在内存中查找的距离。这提供了O（1）访问时间。

MyArray [5] ^ ^ Pointer Offset 所有其他数据结构要么以此为基础，要么不使用相邻的存储器进行存储，从而导致差的随机访问查找时间（尽管不使用顺序存储器还有其他好处）。

例如，假设我们有一个数组，其中包含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）查找时间（随着添加每个元素，查找成本会增加）。与购买P4相比，购买P1000的成本要高得多。

更高级别的数据结构（例如哈希表，堆栈和队列）都可以在内部使用一个数组（或多个数组），而“链表”和“二叉树”通常使用节点和指针。

您可能想知道为什么有人会使用需要线性遍历的数据结构来查找值，而不是仅使用数组，但是它们有其​​用途。

再次使用我们的数组。这次，我想找到包含值“ 5”的数组元素。

===================================== | 6 | 4 | 2 | 3 | 1 | 5 |

^ ^ ^ ^ ^ FOUND! 在这种情况下，我不知道要添加到指针的偏移量是多少，因此我必须从0开始，一直向上直到找到它。这意味着我必须执行6次检查。

因此，在数组中搜索值被视为O（N）。随着数组变大，搜索的成本增加。

还记得上面我说过的话，有时使用非顺序数据结构可以带来好处吗？搜索数据是这些优势之一，最好的例子之一是二叉树。

二叉树是一种类似于链表的数据结构，但是每个节点可以链接到两个子节点，而不是链接到单个节点。

     ==========
     |  Root  |         
     ==========
    /          \ 

========= ========= | Child | | Child | ========= ========= /
========= ========= | Child | | Child | ========= =========

Assume that each connector is really a Pointer 将数据插入二叉树时，它使用一些规则来决定将新节点放置在何处。基本概念是，如果新值大于父项，则将其插入到左侧；如果新值小于母项，则将其插入到右侧。

这意味着二叉树中的值可能如下所示：

     ==========
     |   100  |         
     ==========
    /          \ 

========= ========= | 200 | | 50 | ========= ========= /
========= ========= | 75 | | 25 | ========= ========= 在二叉树中搜索值75时，由于这种结构，我们只需要访问3个节点（O（log N））：

75小于100吗？看右边的节点 75大于50吗？看左节点 有75个！ 即使树中有5个节点，我们也不必查看其余两个节点，因为我们知道它们（及其子代）不可能包含我们所寻找的值。这给了我们搜索时间，在最坏的情况下意味着我们必须访问每个节点，但是在最好的情况下，我们只需要访问一小部分节点。

那就是数组被击败的地方，尽管访问时间为O（1），但它们提供了线性的O（N）搜索时间。

这是关于内存中数据结构的令人难以置信的高级概述，跳过了许多细节，但希望它能说明数组与其他数据结构相比的优缺点。 问题来源于stack overflow