04数据结构之数组

数组可以说是最基础、最简单的数据结构了。思考一个问题，为什么数组要从0开始编号，而不是从1开始呢？

1.数组的概念

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

• 线性表是数据排列成像一条线一样的结构。每个线性表的数据最多只有前后两个方向。包括数组、链表、队列、栈都是线性结构。
• 与相对立的概念是非线性，比如二叉树、堆、图，在非线性结构中，数据间并不是简单的前后关系。

2.数组时如何实现根据下标随机访问数据元素的。

举例子，一个长度为10的int类型的数组int[] a = new int[10],内存分配如下图：

image.png

寻址公式为：a[i]_address = base_address i * data_type_size
数组适合查找，它支持随机访问，根据下标随机访问的时间复杂度为O（1），链表适合插入、删除，时间复杂度是O(1)

3.警惕数组的访问越界问题

下面一段代码：

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;![image](https://img.haomeiwen.com/i2651250/abed9bff495b9631.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

        printf("hello world\n");
    }
    return 0;
}

该段程序的运行结果会无限打印“hello world”。
在c语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据数组的寻址公式，a[3]会被定为到某块不属于数组的内存地址上，而这个地址正好是储存变量i的内存地址，现在a[3]就被定位到i处了，将a[3] = 0相当于给i赋值为0，该循环就永远符合条件，无限执行。通过查询函数调用的栈帧结构细节，函数体内的局部变量存在栈上，且是连续压栈。在Linux进程的内存布局中，栈区在高地址空间，从高向低增长，变量i和arr在相邻地址，且i的地址比arr大。所以arr越界正好访问到。前提是i和arr是同类型元素，否则代码仍是未决行为。

4.总结

• 二维数组的寻址公式，对于一个m*n的二维数组。a[i][j] = base_address + j * data_type_size + i * n * data_type_size = base_address + (j + i * n) * base_address
  在平时的业务开发中，我们可以直接使用编程语言提供的容器类。如果是底层开发，用数组更合适。