算法-数组的实现

发表于   |   分类于   |  

在每一种语言当中都会有数组这种 数据类型，同时它还是一种最基础的 数据结构。

数组是什么

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

线性表：就是数据排列成像一条线一样的结构。每个线上的数据最多只有前和后两个方向。线性表包括 数组、链表、队列、栈
非线性表：数据排序不是简单的前后关系数据结构，比如 二叉树、堆、图

数组的随机访问

数组有个杀手级的特性：随机访问，因为在它 根据下标查找数据 的时候其时间复杂度为 O(1)。如果你用别的查找方法那就不是这个复杂度了，比如你用 二分查找 他的复杂度就变成了 O(logn)。

假设用一个10个int类型的数组来举例 如下图

array_data1

在申请内存的时候，系统会给数组分配10块连续的内存空间地址从 1000 - 1039（都是假设值） 假设首地址为 base_address = 1000。其中每块内存空间都有一个地址，计算机是通过这个内存地址来访问数据的。当访问数组中的某个元素(假设第i个元素)的时候，系统会根据下面的公式直接计算出内存的地址 

1
a[i]_address = base_address + i * data_type_size

计算出了内存地址后直接读取，所以对于数组这种结构而言对它随机访问的时候，它的复杂度只有 O(1)，因为系统一次计算就得出了具体的内存地址。

数组的插入和删除

有利就有弊，数组有快速的查找，但是对于 插入 和 删除 操作，为了保证数据的连续性需要做大量的数据搬移工作，所以比较低效。

插入操作

先来分析下数组插入操作的时间复杂度。

假设数组长度为n，现在需要将一个数插入到数组的第k的位置上。这时为了把k的位置让出来就需要把 k ~ n 这个范围内的数据都向后移动一位，然后在把数据插入到k的位置。这个时候时间复杂度就需要求一个平均的值也就是 平均时间复杂度，因为会出现很多种情况，如果要操作的k是最后一位就不需要移动数组元素了这时是 最好时间复杂度 为O(1)，如果要操作的是数组第一位这时就是 最坏时间复杂度 为O(n)。因为在每个位置插入元素的概率是一样的都是 1/n 所以平均情况时间复杂度为 (1 + 2 + ...n)/n = O(n) 因为时间复杂度需要去掉常量、系数等。

优化数组的插入

当数组中的元素都是无序的时候并且也不要求有序，只是当做一个存储数据的集合。在这种情况下是可以优化数组的，当需要在第k的位置插入数据的时候，只需要先把第k位置的元素移动到数组的末尾，然后k位置空出来插入新的数据即可。利用这种方式 在特定场景下 可以将k位置插入数据这种时间复杂度降低为 O(1)

array_data2

删除操作

和插入操作一样，对数组的删除操作为了保证数据的连续性也需要大量搬移数据，不然就会出现空洞，内存就不连续了。

和插入的时间复杂度也一样，最好的情况时间复杂度为 O(1),也就是删除数组最后一个元素的时候。最坏的情况时间复杂度为O(n)也就是删除数组第一个元素的时候。平均时间复杂度为O(n)。

优化数组的删除

在某些不需要数组中数据连续的情况下，可以将多次删除操作集中在一起执行，这样就是多次删除只做一次数据连续迁移。比如可以这样，先给数组中的元素标记为已删除，并不会真正的去执行删除，当数组没有更多的存储空间的时候在去执行一次真正的删除，这样就可以大大减少删除操作导致的数据搬移问题。这只是一种思路不要抬杠 具体还会有很多的细节需要处理的。

数组下标从0开始的原因

从学编程开始就都知道下标是从0开始的，为什么不是从1开始呢？

从数组存储的内存模型上看，下标 更确切的说应该是 偏移（offset）。主要看下首地址，首地址对应的是 a[0] 也就是偏移为0的位置。那么 a[k] 就是偏移为k个 type_size 的位置，所以计算 a[k] 的内存地址为：

1
a[k]_address = base_address + k * type_size

如果数组下标是从1开始的 那么计算 a[k]的内存地址就变为：

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

可以发现如果从1开始的话每次计算地址都会多一次减法运算，会有一次资源浪费。对于数组这种基础数据结构，随机访问又多，把性能最大话肯定是必须的 所以从0开始更合理。

其实最主要的还是历史原因，因为从C语言的下标就是从0开始计数的，后面的语言大多是借鉴了C语言，减少学习成本，数组就都从0开始计数了

二维数组的内存地址计算

1
2
3
4
5
$a = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8]
];

元素在内存中的地址应该是下面的样子

erwei_array

所以对于一个二维数组 (n为元素个数) 其内存地址计算公式(求 $array[i][j])为

1
address = base_address + ( i * n + j) * type_size

C语言中的数组越界问题

1
2
3
int i = 0;
int arr[3] = {0};
arr[3] = 0;

正常来说 arr[3] 已经越界了是访问不到的，但是在C语言中

栈的内存地址是由高到低位增长的（也就是越往下地址位越小），而数组的内存地址是从低到高位增长的

先声明的i在内存地址的最高位，然后数组是一个整体，对 arr[0] 分配空间的时候是从最低位开始的 然后就是这块数组内存的最低位了 依次上来

所以，i 和数组的数据从高位地址到低位地址依次是：i, a[2], a[1], a[0]。a[3]通过寻址公式，计算得到地址正好是 i 的存储地址，所以a[3] = 0，就相当于 i = 0 并不会报错.

c_stack

-------------The End-------------