我们为什么使用数组，而不是其他的数据结构？ [英] Why do we use arrays instead of other data structures?
问题描述
当我编程，我还没有看到这样的情况：一个数组是用于存储比其另一种形式的信息更好。我的确想通编程语言中增加了功能在此得到了改善，并通过取而代之。我现在，他们是不会被替换，而是赋予了新的生命看，可以这么说。
As I was programming, I haven't seen an instance where an array is better for storing information than another form thereof. I had indeed figured the added "features" in programming languages had improved upon this and by that replaced them. I see now that they aren't replaced but rather given new life, so to speak.
所以，基本上，什么是使用数组的地步？
So, basically, what's the point of using arrays?
这是没有这么多，我们为什么使用数组从计算机的角度来看，而是我们为什么要使用数组从编程的角度来看（一个微妙的差异）。什么是电脑做与阵列是不是问题的地步。
This is not so much why do we use arrays from a computer standpoint, but rather why would we use arrays from a programming standpoint (a subtle difference). What the computer does with the array was not the point of the question.
推荐答案
时间回去及时的一课。虽然我们不认为这些事情在很多我们的想像力托管语言今天，他们都建立在同一个基础，让我们来看看内存如何用C来管理。
Time to go back in time for a lesson. While we don't think about these things much in our fancy managed languages today, they are built on the same foundation, so let's look at how memory is managed in C.
在我深入探究，什么样的术语指针手段的简单说明。指针是一个简单的点到内存中的位置的变量。它不包含在该区域的存储器的实际值，它包含存储器地址给它。觉得作为一个邮箱的内存块。该指针将是地址到该邮箱。
Before I dive in, a quick explanation of what the term "pointer" means. A pointer is simply a variable that "points" to a location in memory. It doesn't contain the actual value at this area of memory, it contains the memory address to it. Think of a block of memory as a mailbox. The pointer would be the address to that mailbox.
在C，一个数组是简单地用一个偏移指针，偏移指定多远内存看看。这提供 O（1）的访问时间。
In C, an array is simply a pointer with an offset, the offset specifies how far in memory to look. This provides O(1) access time.
MyArray [5]
^ ^
Pointer Offset
所有其他数据结构或者建立在这一点，或者不使用相邻的存储进行存储，从而在恶劣的随机存取查找时间（虽然有不使用连续内存的其他好处）。
All other data structures either build upon this, or do not use adjacent memory for storage, resulting in poor random access look up time (Though there are other benefits to not using sequential memory).
例如，假设我们有在这6个号码（6,4,2,3,1,5）的阵列，在内存中是这样的：
For example, let's say we have an array with 6 numbers (6,4,2,3,1,5) in it, in memory it would look like this:
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
在一个数组中，我们知道，每个元素在存储器彼此相邻。 C数组（这里称为MYARRAY）仅仅是一个指向第一个元素：
In an array, we know that each element is next to each other in memory. A C array (Called MyArray here) is simply a pointer to the first element:
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
^
MyArray
如果我们想查找MYARRAY [4]，在内部它会是这样访问：
If we wanted to look up MyArray[4], internally it would be accessed like this:
0 1 2 3 4
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
^
MyArray + 4 ---------------/
(Pointer + Offset)
由于我们可以直接通过将偏移到指针访问任何元件阵列中，我们可以查找任何元件在相同的时间量，而不管该数组的大小。这意味着，得到MYARRAY [1000]将采取的时间相同数量的越来越MYARRAY [5]
Because we can directly access any element in the array by adding the offset to the pointer, we can look up any element in the same amount of time, regardless of the size of the array. This means that getting MyArray[1000] would take the same amount of time as getting MyArray[5].
这是另一种数据结构是一个链表。这是指针的线性列表，每个指向下一节点
An alternative data structure is a linked list. This is a linear list of pointers, each pointing to the next node
======== ======== ======== ======== ========
| Data | | Data | | Data | | Data | | Data |
| | -> | | -> | | -> | | -> | |
| P1 | | P2 | | P3 | | P4 | | P5 |
======== ======== ======== ======== ========
P(X) stands for Pointer to next node.
请注意，我把每一个节点到自己的块。这是因为它们没有保证是（并且很可能不会）相邻的存储器
Note that I made each "node" into its own block. This is because they are not guaranteed to be (and most likely won't be) adjacent in memory.
如果我想访问P3，我不能直接访问它，因为我不知道它是在内存中。我所知道的是根（P1）是，所以不是我在P1开始，并按照每个指针到所需的节点。
If I want to access P3, I can't directly access it, because I don't know where it is in memory. All I know is where the root (P1) is, so instead I have to start at P1, and follow each pointer to the desired node.
这是一个O（N）查询时间（查找费用增加每次添加元素）。这是更昂贵的去P1000相比，获得到P4。
This is a O(N) look up time (The look up cost increases as each element is added). It is much more expensive to get to P1000 compared to getting to P4.
更高级别的数据结构，如哈希表，栈和队列，都可以用一个阵列（或多个阵列）内部，而链表和二叉树通常用节点和指针。
Higher level data structures, such as hashtables, stacks and queues, all may use an array (or multiple arrays) internally, while Linked Lists and Binary Trees usually use nodes and pointers.
您可能会问，为什么会有人使用需要线性遍历查找值的数据结构，而不是只使用一个数组，但他们有自己的用途。
You might wonder why anyone would use a data structure that requires linear traversal to look up a value instead of just using an array, but they have their uses.
再以我们的数组。这一次，我想找到一个保存值数组元素5。
Take our array again. This time, I want to find the array element that holds the value '5'.
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
^ ^ ^ ^ ^ FOUND!
在这种情况下，我不知道是什么偏移添加到指针找到它，所以我必须在0开始，而我的工作方式，直到我找到它。这意味着我必须执行6检查。
In this situation, I don't know what offset to add to the pointer to find it, so I have to start at 0, and work my way up until I find it. This means I have to perform 6 checks.
由于这一点，对于在阵列中的值搜索被认为是O（N）。搜索的成本增加作为数组变大。
Because of this, searching for a value in an array is considered O(N). The cost of searching increases as the array gets larger.
记住了上面，我说，有时使用非连续的数据结构可以有优势？搜索数据是这些优势之一，也是一个最好的例子是二叉树。
Remember up above where I said that sometimes using a non sequential data structure can have advantages? Searching for data is one of these advantages and one of the best examples is the Binary Tree.
一个二叉树类似于一个链表的数据结构，但是代替连接到单个节点，每个节点可以连接到两个孩子节点
A Binary Tree is a data structure similar to a linked list, however instead of linking to a single node, each node can link to two children nodes.
==========
| Root |
==========
/ \
========= =========
| Child | | Child |
========= =========
/ \
========= =========
| Child | | Child |
========= =========
Assume that each connector is really a Pointer
当数据被插入到一个二叉树，它使用几个规则来决定在何处放置新的节点。的基本概念是，如果新值大于父母时，将它插入到左侧，如果是低，将它插入到右边。
When data is inserted into a binary tree, it uses several rules to decide where to place the new node. The basic concept is that if the new value is greater than the parents, it inserts it to the left, if it is lower, it inserts it to the right.
这意味着，在二叉树的值可能是这样的：
This means that the values in a binary tree could look like this:
==========
| 100 |
==========
/ \
========= =========
| 200 | | 50 |
========= =========
/ \
========= =========
| 75 | | 25 |
========= =========
当搜索75值二叉树，我们只需要到3个节点（O（日志N）），因为这种结构的：
When searching a binary tree for the value of 75, we only need to visit 3 nodes ( O(log N) ) because of this structure:
- 是小于100 75？看看右节点
- 是大于50 75？再看左节点
- 还有就是75！
虽然没有在我们的树5个节点，我们并不需要看剩下的两个，因为我们知道他们（和他们的孩子）不可能包含我们正在寻找的价值。这为我们提供了在最坏的情况下意味着我们必须访问每个节点搜索时间，但是在最好的情况下，我们只需要访问的节点的一小部分。
Even though there is 5 nodes in our tree, we did not need to look at the remaining two, because we knew that they (and their children) could not possibly contain the value we were looking for. This gives us a search time that at worst case means we have to visit every node, but in the best case we only have to visit a small portion of the nodes.
这就是阵列得到节拍，他们提供了一个恒定的O（N）搜索时间，尽管O（1）访问时间。
That is where arrays get beat, they provide a constant O(N) search time, despite O(1) access time.
这是对内存中的数据结构，跳过很多细节令人难以置信的高度概括，但希望它说明了相对于其他的数据结构数组的实力和弱点。
This is an incredibly high level overview on data structures in memory, skipping over a lot of details, but hopefully it illustrates an array's strength and weakness compared to other data structures.
这篇关于我们为什么使用数组，而不是其他的数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
