算法-数组

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

数组随机访问的实现

我们拿一个长度为 10 的 int 类型的数组int[] a = new int[10] 来举例,在我画的这个图中，计算机给数组 a[10],分配了一块连续内存空间 1000～1039,其中，内存块的首地址为 base_address = 1000.

我们知道，计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小,我们举的这个例子里，数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。

防止数组越界

值得注意的是防止数组越界行为的发生,数组越界在不同语言中有不同的表现形式,比如数组越界在iOS中会直接崩掉,而在c语言中会出现莫名其妙的逻辑错误

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;

}

比如这段c的代码,hello world会打印几遍呢,有的人可能会说3遍,有的人会说会无限打印.其实它是会无限打印的,why?因为他数组越界,因为，数组大小为 3，a[0]，a[1]，a[2]，而我们的代码因为书写错误,导致 for 循环的结束条件错写为了 i<=3 而非 i<3,所以当 i=3 时，数组 a[3] 访问越界。

我们知道，在 C 语言中，只要不是访问受限的内存,所有的内存空间都是可以自由访问的。根据我们前面讲的数组寻址公式,a[3] 也会被定位到某块不属于数组的内存地址上,而这个地址正好是存储变量 i 的内存地址(这段有疑问的话,建议去查函数调用的栈桢结构细节（操作系统或计算机体系结构的教材应该会讲到）。函数体内的局部变量存在栈上，且是连续压栈。在Linux进程的内存布局中，栈区在高地址空间，从高向低增长。变量i和arr在相邻地址，且i比arr的地址大，所以arr越界正好访问到i。当然，前提是i和arr元素同类型，否则那段代码仍是未决行为。),那么 a[3]=0 就相当于 i=0，所以就会导致代码无限循环.

总结:数组是最简单,最基础的数据结构了,数组用一块连续的内存空间，来存储相同类型的一组数据,最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。