DSA_03:数组
2020-03-28 16:01:53来源:博客园 阅读 ()
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 纯虚函数与基类指针数组的运用 代码参考 2020-04-30
- STL之deque 2020-04-29
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- 寻找两个有序数组的中位数 2020-04-09
- STL之vector 2020-04-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash