常见数据结构-数组
【摘要】 数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。数组的两个特点是: 线性表和连续的内存空间和相同类型的数据(随机访问)。
一,如何实现随机访问?
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。数组的两个特点是:
- 线性表
- 连续的内存空间和相同类型的数据(随机访问)
计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:
a[i]_address = base_address + i * data_type_size
// 如果数组从 1 开始计数
a[k]_address = base_address + (k-1)*type_size
数组从
1
开始编号,是因为根据寻址公式,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。
注意:数组支持随机访问,根据下标随机访问的时间复杂度为 ,但找的时间复杂度并不为 。,毕竟即便是排好序的数组,用二分查找,时间复杂度也是 。
这点很多博客没有注明。
二,低效的“插入”和“删除”
假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。平均情况时间复杂度为 。
三,容器能否完全替代数组?
C++
、JAVA
等语言都提供了类似数组的容器类,比如 C++
STL
中的 vector
。根据我的经验,一般情况下,推荐用容器开发,简单省事、代码易懂,底层和高性能开发用数组,毕竟容器的灵活性还是牺牲了一定性能的。
参考资料
《数据结构与算法之美》
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)