建设公司自己的网站首页,wordpress 功能 rss,山东网站备案注意事项,国外好的室内设计网站文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
如何实现随机访问
数组是一种线性表数据结构。它用一组连续的内存空间#xff0c;来存储一组具有相同类型的数据。
线性表
线性表的数据最多只有前和后两个方向。…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
如何实现随机访问
数组是一种线性表数据结构。它用一组连续的内存空间来存储一组具有相同类型的数据。
线性表
线性表的数据最多只有前和后两个方向。数组、栈、队列、链表都是线性表。 非线性表树、图、堆。
连续的内存空间
a[i]_addressbase_addressi∗data_type_sizea[i]\_addressbase\_addressi*data\_type\_sizea[i]_addressbase_addressi∗data_type_size,data_type_size表示数组中每个元素的大小。 如果数组下标从1开始那么在查找a[i]_addressbase_address(i−1)∗data_type_sizea[i]\_addressbase\_address(i-1)*data\_type\_sizea[i]_addressbase_address(i−1)∗data_type_size会多一次减法操作。这可能是大多数语言数组下标从0开始的原因。
与链表的区别
数组支持随机访问复杂度O(1)。链表适合插入删除。
低效地插入和删除
插入如果某个位置a[i]已经被占用了就需要将i到最后一个元素拷贝到i1到count位置然后a[i]val。平均时间复杂度O(n)。 改进策略大多数时候我们不需要追求顺序性那么我们可以把a[i]复制到数组末尾将 当前元素赋值给a[i]。例如数组a[10]已经存入元素12345。现在想插入a[2]10那么插入完成后数组变为1210453。
删除因为内存块是连续的当删除i位的元素后从i1到count的元素需要向前迁移。这样平均复杂度也是O(n)。 删除的改进策略可以是删除的位置先做标记不做迁移等空间不够的时候再做迁移。这就是Java虚拟的标记清除算法。
警惕数组越界
数组越界是通常需要处理的问题。在C中数组越界可能会产生意想不到的结果。
容器能否完全替代数组
在某些场合还是用数组不会用容器。例如 1 数组可以存储基本数据类型速度上更快。在已知数组大小并且操作简单的情况下数组是个更好的选择。 2 多维数组一般用数组表示。a[][] 这样的表示比ListList 这样的结构更容易接受。
