这是一系列关于数据结构与算法的精彩文章,强烈推荐你持续关注。
自2020年4月29日起,我们将带你深入了解数据结构的奥秘。本文首先介绍了“数组篇”。我力求用简洁明了的文字和代码,来解释数据结构与算法。
1. 数组是一种“线性数据结构”,此外还有“链表”,“栈”,“队列”等同样重要的数据结构。
2. 与线性表相对的是“非线性表”,如“二叉树”,“堆”,“图”等,它们的数据流向不只有“前”和“后”。
3. 数组的原理是在内存地址中找到一个起始点,然后划定一片连续的内存地址。它只存储相同类型的数据,这样寻址更为方便。
4. 由于其连续的内存地址特性,数组能够实现随机访问元素。寻址算法可以表示为:a[i] = 数组开始的位置 + i 固定大小。
5. 在分析数组的复杂度时,不同的操作有不同的时间复杂度。例如,array的增删操作时间复杂度为O(n),而根据下标查找的时间复杂度为O(1)。如果是循环查找,时间复杂度为O(logn)。
7. 在删除操作时,不必每次删除都给元素移位。可以先标记被删除的元素,等删除的元素积累到一定程度再一并删除。
8. 大多数编程语言都支持数组扩展,如JavaScript中的Array。实际上,JavaScript并没有严格意义上的数组。
9. 在开发时,一般推荐使用arrayList。如果在初始化时设定一个长度,可以起到优化作用,减少部分O(n)操作。
10. 当数据长度固定时,建议使用数组,这样执行效率更高。
以上仅为初步探讨,如有不足,欢迎补充。
这个系列文章将带你深入了解数据结构与算法的各个方面,让你在编程之路上更加游刃有余。持续关注,更多精彩内容等着你! |