DSA_03:数组

2020-03-28 16:01:53来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

DSA_03:数组

数组,相信大家再熟悉不过。

 

这里还是对其进行简单总结,最重要的是,给出一维数组多维数组内存模型寻址公式,这是很多新手甚至有一定基础的同学任然搞不懂的地方。

  1. 数组是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

  2. 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。

  3. 非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系

  4. 连续的内存空间相同类型的数据:正是因为这两个限制,数组才有了一个堪称“杀手锏”的特性:随机访问

  5. 说:数组适合查找,查找时间复杂度为O(1),这句话准确吗?

    答:有序数组用二分法查找复杂度是 O(logn),因此自然这句话并不准确。应该说:数组支持随机访问,根据下标随机访问的时间复杂度为O(1)

 

一维数组内存模型和寻址公式:

  有一个 int arr[7] 的数组,其内存模型如图:

      

  a[n] 寻址公式:a[i]_address = base_address + i * data_type_size,其中 base_address 是数组第一个元素所在地址。

 

二维数组内存模型和寻址公式:

  这对于很多人来说,是一直没弄懂的,相信看完该图能够让你足够清晰。

  int arr[3][3] 的内存模型为:

      

  OK,有了内存模型,不妨自己推导一下二维数组的寻址公式再继续往下看。

  a[m][n] 寻址公式:a[i][j]_address = base_address + (i * n + j) * data_type_size,其中 base_address 是数组第一个元素所在地址。

  data_type_size 代表数据类型所占字节

 

需要注意,数组的查找和删除,为了保证数据的连续性,需要将后面的元素整体搬移。

数组 插入、删除、查找 的性能就不再啰嗦了,与链表的性能对比,应用场合等也不再过多说明。

 

最后,容器能否完全替代数组?

如 java 中的 ArrayList,C++ 中的 vector 等,能否完全代替数组呢?

  前者:最大的优势就是可以将很多数组操作的细节封装起来,支持动态扩容。

  后者:数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间。

  对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发, 比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选。

 


原文链接:https://www.cnblogs.com/teternity/p/DSA_03.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:DSA_04:链表

下一篇:C语言中%与/