常见数据结构-数组

举报
嵌入式视觉 发表于 2023/03/25 17:17:33 2023/03/25
【摘要】 数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。数组的两个特点是: 线性表和连续的内存空间和相同类型的数据(随机访问)。

一,如何实现随机访问?

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。数组的两个特点是:

  • 线性表
  • 连续的内存空间和相同类型的数据(随机访问

计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:

a[i]_address = base_address + i * data_type_size
// 如果数组从 1 开始计数
a[k]_address = base_address + (k-1)*type_size

数组从 1 开始编号,是因为根据寻址公式,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

注意:数组支持随机访问,根据下标随机访问的时间复杂度为 O ( 1 ) O(1) ,但找的时间复杂度并不为 O ( 1 ) O(1) 。,毕竟即便是排好序的数组,用二分查找,时间复杂度也是 O ( l o g n ) O(logn)

这点很多博客没有注明。

二,低效的“插入”和“删除”

假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。平均情况时间复杂度为 ( 1 + 2 + . . . n ) / n = O ( n ) (1+2+...n)/n=O(n)

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

C++JAVA 等语言都提供了类似数组的容器类,比如 C++ STL 中的 vector。根据我的经验,一般情况下,推荐用容器开发,简单省事、代码易懂,底层和高性能开发用数组,毕竟容器的灵活性还是牺牲了一定性能的。

参考资料

《数据结构与算法之美》

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。