在编写程序时,我还没有见过这样一个实例:数组比其他形式更适合存储信息。我确实已经发现,编程语言中新增的“功能”对此有所改进,并由此取代了它们。我现在可以看到,它们并没有被取代而是被赋予了新的生命。
那么,基本上,使用数组有什么意义?
这不是为什么我们从计算机的角度使用数组,而是为什么从编程的角度使用数组(微妙的区别)。计算机如何处理阵列并不是问题的重点。
是时候回到过去上一堂课了。虽然我们今天在我们的高级托管语言中对这些事情的考虑不多,但它们是基于相同的基础构建的,因此让我们看一下如何在C中管理内存。
在我深入之前,请先对“指针”一词的含义进行快速解释。指针仅仅是“指向”内存中某个位置的变量。它不包含该内存区域的实际值,而是包含该内存的地址。将一块内存视为邮箱。指针将是该邮箱的地址。
在C语言中,数组只是具有偏移量的指针,偏移量指定要在内存中查找的距离。这提供了O(1)访问时间。
MyArray [5] ^ ^ Pointer Offset 所有其他数据结构要么以此为基础,要么不使用相邻的存储器进行存储,从而导致差的随机访问查找时间(尽管不使用顺序存储器还有其他好处)。
例如,假设我们有一个数组,其中包含6个数字(6,4,2,3,1,5),在内存中看起来像这样:
在数组中,我们知道每个元素在内存中彼此相邻。AC数组(此处称为MyArray)只是指向第一个元素的指针:
^ MyArray 如果我们要查找MyArray [4],则可以在内部进行如下访问:
^
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”的数组元素。
^ ^ ^ ^ ^ 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
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。