网站的安全建设或者解决方案,东莞做网站的公司哪家最好,企业网站营销解决方案,网页设计师个人网站2019 年第 75 篇文章#xff0c;总第 99 篇文章”数据结构算法入门系列的第二篇#xff0c;这次介绍下数组#xff0c; 数组是一个最基础而且常见的数据结构#xff0c;几乎每种编程语言都有。上一篇文章#xff1a;数据结构算法入门--一文了解什么是复杂度今日推荐阅读… 2019 年第 75 篇文章总第 99 篇文章”数据结构算法入门系列的第二篇这次介绍下数组 数组是一个最基础而且常见的数据结构几乎每种编程语言都有。上一篇文章数据结构算法入门--一文了解什么是复杂度今日推荐阅读深度学习在推荐系统中的应用如何实现随机访问数组的定义数组(Array)是一种线性表数据结构。它用一组连续的内存空间来存储一组具有相同类型的数据。”这里指出了数组的三个特点线性表(Linear List)连续的内存空间存储相同类型数据首先线性表就是数据排成一条线一样的结构每个线性表最多只有前后两个方向线性表结构如下图所示数组、链表、队列和栈都属于这种结构。和线性表对立的就是非线性表比如二叉树、堆、图等它们不仅仅是简单的前后关系如下图所示接着就是需要连续内存空间和保存相同类型的数据。这两个特点让数组有一个非常好的特性随机访问。也就是根据下标访问数组的时间复杂度是 O(1) 但问题就是插入和删除需要 O(n)因为需要进行大量的数据移动操作。那么数组是如何实现随机访问的操作的呢首先给定一个长度为 10 的 int 类型的数组 a[10] 计算机会分配一块存储空间这里假设就是 1000~1039 其中内存块的首地址是 base_address1000如下图所示计算机给每个内存单元分配一个地址然后通过地址访问内存中的数据。因此这里如果需要随机访问数组的某个元素同样也是根据地址访问也就是首先需要找到该元素存储所在的地址寻址公式如下所示a[i]_address base_address i * data_type_sizedata_type_size 表示数组每个元素的大小这里 int 类型是 4 个字节。注意对于数组来说它支持随机访问根据下标随机访问的时间复杂度是 O(1) 但查找时间复杂度并非是 O(1) , 因为即便排好序的数值通过二分查找时间复杂度是 O(logn) 。低效的插入和删除数组的插入和删除操作由于其内存数据的连续性问题这两个操作会非常低效那么为什么会导致低效有哪些改进方法呢插入操作假设数组长度是 n 现在需要将一个数据插入到数组的第 k 位置如果需要执行这样的操作需要将第 k 到 n 位置上的元素都按顺序往后移动一位。这个操作的时间复杂度是多少呢最好的情况就是末尾插入元素这样不需要移动O(1) 复杂度最坏的情况数组开头就插入元素那么就是 O(n) 的时间复杂度。平均情况时间复杂度则如下所示每个位置插入元素概率是相同的当然如果数组是有序的就需要按照上述做法移动元素。如果数组无序呢一个快速的方法就是仅移动目标位置的元素即第 k 个位置的元素放到数组末尾然后插入元素即可这样时间复杂度就是 O(1)。一个简单的例子如下图所示数组有 5 个元素a,b,c,d,e现在希望在第三个位置插入新元素 x此时可以直接将 c 放到末尾即 a[5] a[2]然后 a[2]x即可完成操作。这种特殊的处理技巧可以在特定场景下(比如数组无序)将插入元素的时间复杂度降到 O(1)。删除操作和插入数据类似删除第 k 个位置元素同样需要将后续的元素往前移动。最好的情况是删除末尾数据O(1)最坏就是删除开头的元素O(n)平均情况时间复杂度也是 O(n)。同样在某些特定场景下并不需要时刻追求数组中数组的连续性可以将多次删除操作集中在一起进行操作。如下图所示是一个长度为 10 的数组存储了 8 个元素现在是需要依次删除前三个元素abc。如果每次删除操作都将所有元素往前移动那么后续的 5 个元素总共需要移动 3 次为了避免这个情况我们可以先记录被删除的数据每次操作仅仅记录那个位置的元素被删除。当数组没有空间存储数据时再进行一次真正的删除操作这样可以避免删除操作导致的数据搬移。这个做法其实就是 Java 中 JVM 标记清除垃圾回收算法的核心思想。所以我们对于数据结构和算法的学习不应该只是死记硬背而是需要了解它背后的思想和处理技巧明白为什么需要这种数据结构和这种算法。数组的越界问题首先来看一段 C 语言的代码如下所示int main(int argc, char* argv[]){ int i0; int arr[3] {0}; for(; i3; i){ arr[i] 0; printf(hello world\n) } return 0;
}这段代码的问题就是打印结果的时候因为循环结束条件问题会无限打印 hello world给定的数组长度是 3 但是循环结束条件是 i3 而 a[3] 其实就是访问越界了。但是在 C 语言中只要不是访问受限的内存所有的内存空间都是可以自由访问的。也就是说a[3] 也是可以访问的但是会定位到非数组所在的内存上而这个地址正好是存储变量 i 的内存地址也就是 a[3]0 就相当于 i0 最终导致代码的无限循环。数组越界在 C 语言中是一种未决行为没有规定这种情况编译器应该如何处理所以通常会出现各种奇怪的逻辑错误。不过其他编程语言并不会将数组越界的工作丢给程序员来做它们会有做越界的检查。数组索引从 0 开始的原因大多数的编程语言中数组或者说数据结构索引都是从 0 开始而不是从 1 开始。首先从数组存储的内存模型上看索引或者说“下标”最确切的定义应该是偏移(offset)。前面介绍了数组的寻址公式a[i]_address base_address i * data_type_size如果数组是从 1 开始计数那么寻址公式就会为a[i]_address base_address (i-1) * data_type_size对比两个公式可以知道每次访问数组元素从 1 开始计数的方式会多一次减法运算相当于让 CPU 多一次减法指令但随即访问数组元素应该是非常基础的操作需要尽可能高效因此为了减少一次减法操作数组采用从 0 开始计数而非从 1 开始。其次主要是 C 语言设计者用 0 开始计数后续的编程语言如 Java 等都效仿了 C 语言这也是方便 C 语言程序员学习其他语言的学习成本。当然像 Python 还支持负数下标。参考极客时间的数据结构与算法之美课程欢迎关注我的微信公众号--算法猿的成长或者扫描下方的二维码大家一起交流学习和进步如果觉得不错在看、转发就是对小编的一个支持
