0%

数组

image

概念

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

特性

数组下标由0开始

为什么?

数组查找数据时的寻址公式为:start_address + n*data_block_size

一方面是按照上述公式,如果下标由1开始,则公式为:start_address + (n-1)*data_block_size

每次寻址时会做一次 n-1的运算。

另一方面是历史原因,都是从0开始的。

快速查找

根据下标随机查找,时间复杂度为O(1)。

插入、删除慢

插入、删除会导致数组后续元素的后移,时间复杂度为O(n)。

编程