开发者社区> 问答> 正文

为什么我们使用数组而不是其他数据结构?

在编写程序时,我还没有见过这样一个实例:数组比其他形式更适合存储信息。我确实已经发现,编程语言中新增的“功能”对此有所改进,并由此取代了它们。我现在可以看到,它们并没有被取代而是被赋予了新的生命。

那么,基本上,使用数组有什么意义?

这不是为什么我们从计算机的角度使用数组,而是为什么从编程的角度使用数组(微妙的区别)。计算机如何处理阵列并不是问题的重点。

展开
收起
保持可爱mmm 2020-01-16 16:50:10 539 0
1 条回答
写回答
取消 提交回答
  • 是时候回到过去上一堂课了。虽然我们今天在我们的高级托管语言中对这些事情的考虑不多,但它们是基于相同的基础构建的,因此让我们看一下如何在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

    2020-01-16 16:50:27
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
如何使用Tair增强数据结构构建丰富在线实时场景 立即下载
Apache Flink 流式应用中状态的数据结构定义升级 立即下载
低代码开发师(初级)实战教程 立即下载