在我编程的时候,我还没有看到一个实例,其中数组比其他形式更适合存储信息.我确实认为编程语言中增加的"特性"已经改进了,并且取而代之.我现在看到他们没有被取代,而是被赋予了新的生命,可以这么说.
那么,基本上,使用数组有什么意义呢？
这不是为什么我们从计算机的角度使用数组,而是为什么我们从编程的角度使用数组(一个细微的差别).计算机对阵列的作用不是问题的关键.
是时候回到课堂了.虽然我们今天在我们花哨的托管语言中没有考虑过这些问题,但它们是建立在同一个基础之上的,所以让我们来看看如何在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(N)搜索时间,尽管O(1)访问时间.
这是对内存中数据结构的非常高级别的概述,跳过了很多细节,但希望它能说明数组与其他数据结构相比的优势和劣势.
对于O(1)随机访问,不能被打败.
并非所有程序都执行相同的操作或在相同的硬件上运行.
这通常是为什么存在各种语言特征的答案.数组是核心计算机科学概念.用列表/矩阵/向量/任何高级数据结构替换数组会严重影响性能,并且在许多系统中都是不切实际的.有许多情况下,由于有问题的程序,应该使用这些"高级"数据收集对象之一.
在业务编程中(我们大多数人都这样做),我们可以针对相对强大的硬件.在这些情况下,使用C#中的List或Java中的Vector是正确的选择,因为这些结构允许开发人员更快地完成目标,从而使这种类型的软件更具特色.
在编写嵌入式软件或操作系统时,阵列通常是更好的选择.虽然阵列提供的功能较少,但占用的RAM较少,编译器可以更有效地优化代码,以便查找数组.
我相信我会遗漏这些案件的一些好处,但我希望你明白这一点.
京公网安备 11010802040832号 | 京ICP备19059560号-6 