【基础篇】3 # 数组：为什么很多编程语言中数组都从0开始编号？

说明

【数据结构与算法之美】专栏学习笔记

什么是数组

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

线性表和非线性表

• 线性表Linear List就是数据排成像一条线一样的结构每个线性表上的数据最多只有前和后两个方向比如数组链表、队列、栈都是线性表结构。
• 非线性表数据之间并不是简单的前后关系比如二叉树、堆、图等。

数组是如何实现根据下标随机访问数组元素的

随机访问的意思就是可以随机选择下标进行数据访问根据下标随机访问的时间复杂度为 O(1)。

如下图计算机给数组 int a[10]分配了一块连续内存空间 1000～1039。

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

a[i]_address = base_address + i * data_type_size

• data_type_size表示数组中每个元素的大小a[10] 是 int 类型该值为 4 个字节
• base_address内存块的首地址a[10] 这里就是 1000

插入和删除操作为什么低效

插入操作

假设数组的长度为 n如果将一个数据插入到数组中的第 k 个位置那么需要将第 k～n 这部分的元素都顺序地往后挪一位把第 k 个位置腾出来给新来的数据。

插入操作的时间复杂度分析

• 最坏时间复杂度为开头插入元素所有的数据都需要依次往后移动一位时间复杂度为 O(n)
• 最好时间复杂度末尾插入元素无需移动时间复杂度为 O(1)
• 平均时间复杂度插入到每一个位置的概率都是 1/n插入到数组的第一个位置需要移动 n 个元素插入到数组的第二个位置需要移动 n -1 个元素以此类推插入到数组中的最后一个位置需要移动1个元素.(n + n - 1 + n - 2 + ... + 1)/n = (n+1)/2时间复杂度为 O(n)

如果数组中存储的数据并没有任何规律数组只是被当作一个存储数据的集合直接将第 k 位的数据搬移到数组元素的最后把新的元素直接放入第 k 个位置这样时间复杂度就会降为 O(1)。

示意图如下

删除操作

如果要删除第 k 个位置的数据为了内存的连续性需要移动数据。

删除操作的时间复杂度分析

• 最坏时间复杂度为删除开头的数据所有的数据都需要依次往前移动一位时间复杂度为 O(n)
• 最好时间复杂度删除数组末尾的数据无需移动时间复杂度为 O(1)
• 平均时间复杂度和插入类似时间复杂度为 O(n)

如果不一定非得追求数组中数据的连续性可以将多次删除操作集中在一起执行提高删除的效率。比如标记清除垃圾回收算法里就有用到。

数组访问越界问题

看个例子

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i <= 3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

如果 i < 3那么结果输出如下

上面这段代码是 i <= 3当 i = 3 时数组 a[3] 访问越界而 a[3] 内存地址指向的是 i 对应内存地址的位置所以修改 a[3] 的值也就是修改 i 的值这时 i 也等于 0就出现了死循环。

因为 C 语言里并没有规定数组访问越界时编译器应该如何处理而 Java 会做越界检查超出就会抛出java.lang.ArrayIndexOutOfBoundsException。访问数组的本质就是访问一段连续内存只要数组通过偏移计算得到的内存地址是可用的那么程序就可能不会报任何错误。

数组从 0 开始编号的原因

1. 底层计算机寻址指令可以少计算一个减法
2. 历史原因沿用了 C 语言从 0 开始计数的习惯

从数组存储的内存模型上来看下标最确切的定义应该是偏移offset。

a[0] 表示偏移为 0 的位置也就是首地址a[k] 表示偏移 k 个 type_size 的位置计算 a[k] 的内存地址

a[k]_address = base_address + k * type_size

如果从 1 开始计算每次随机访问数组元素都多了一次减法运算对于 CPU 来说就是多了一次减法指令。

a[k]_address = base_address + (k - 1) * type_size

JavaScript 中的数组

JavaScript 中的数组数据可以是不同类型它的语法相对宽松。

数组的创建与读写

字面量方式创建数组

var kaimo = [3, 1, 3];

构造函数方式创建数组

var kaimo = new Array(3, 1, 3);

判断一个对象是否是数组

Array.isArray(kaimo);

可以使用循环读写数组

var kaimo = [3, 1, 3];
for (var i = 0; i < kaimo.length; i++) {
	console.log(kaimo[i]);
}

数组的深复制与浅复制

• 浅复制当把数组赋给另外一个数组然后改变其中一个数组的值另一数组也会随之改变这就是数组的浅复制。
• 深复制指的就是不改变原来的数组而去创建一个新的数组这种情况是经常使用的为了不破坏原数组。

存取函数

JavaScript 提供了一组用来访问数组元素的函数叫存取函数。最常用的存取函数就是 indexOf() 函数还有 join 和 toString 函数concat 和 splice 函数。

可变函数

不去引用数组中的某个元素就能改变数组内容这种函数称它为可变函数。

• push() 方法可以在数组末尾添加元素
• unshift() 方法可以在数组开头添加元素
• pop() 可以删除数组末尾的元素
• shift() 删除数组的第一个元素
• splice() 不仅可以用来删除元素还可以添加元素进数组
• sort() 可以为数组排序
• reverse() 将数组内的元素翻转

sort() 方法用原地算法对数组的元素进行排序并返回数组。默认排序顺序是在将元素转换为字符串然后比较它们的 UTF-16 代码单元值序列时构建的。

var kaimo = [30, 100, 40, 500, 200];
kaimo.sort();

解决这种排序的错误在调用 sort() 的时候传入一个函数该函数可以比较出大小。

function compare(a1, a2) {
    return a1 - a2;
}
var kaimo = [30, 100, 40, 500, 200];
kaimo.sort(compare);

迭代器方法

迭代函数通过对数组中的元素逐个应用来操作返回相应的值。

不返回新数组 forEach() 、every()、some()、reduce()

• every() 返回值为布尔类型对于应用的所有元素该函数返回 true则该方法返回 true
• some() 与 every() 的不同就是只要有一个元素使改函数返回 true 那么该方法就返回 true
• reduce() 可以对数组元素进行求和、也能将数组元素连接成字符串。

返回新数组 map() 、filter()

map 的作用与 forEach 是一样的区别就是 map 函数返回的是一个新数组。

filter 和 every 相似区别在于当所有的元素使改函数为 true 时它并不返回布尔类型而是返回一个新数组。

二维数组

JavaScript 可以通过在数组里在嵌套一个数组来形成二维数组。

var kaimo = [
    [11, 12, 13, 14],
    [21, 22, 23, 24],
    [31, 32, 33, 34],
    [41, 42, 43, 44]
];
console.log(kaimo[1][2]); // 23

二维数组的处理可以分为两种

• 按列访问外层循环对应行内层循环对应列。
• 按行访问外层循环对应列内层循环对应行。

JavaScript 可以处理一些参差不齐的数组JavaScript 可以处理运行而不报错。

对象数组

数组里面的元素可以是对象可以用 push() 等操作方法来操作对象数组。