数组

速记

数组的特点

数组,一种线性表数据结构,用连续的存储空间存储相同类型数据

特点：

线性表结构 以及 连续的内存空间 相同的数据类型,使数组支持高效的下标 随机访问 的能力

// 下标原理是寻址公式,找出该元素内存地址
a[i]_address = base_address + i * data_type_size

缺点：
2. 低效的插入操作,最好O(1) 最坏O(n) 平均O(n)

优化方案,若数组无序,将第K个移至末尾,新元素插入到第K个位置,复杂度O(1)

低效的删除操作,最好O(1) 最坏O(n) 平均O(n)

优化方案,记录删除数据,当数组无储存空间时,统一真正删除.同JVM标记清楚垃圾回收算法
大小固定

数组的访问越界问题(C语言)

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0}; // 数组大小为3
    for(; i<=3; i++){ // 访问了arr[3],已越界
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

C语言中数组越界属于未决行为,没有规定数组越界时编译器应该如何处理
此时a[3]会根据寻址公式正常访问

函数体内的局部变量保存在栈上,栈区在高地址空间,从高向低增长,
对栈来说 10000是栈底,i被压入处于10000上,则arr 的base_address 为9997,
arr[2] 位于9999,则 arr[3],被判定为 10000,此处正好为 i的地址,
实际上 a[3] = 0 就是 i = 0,i又被归于0,导致无限循环

为何数组从0开始编号

1.a[n],n代表偏移量

// 下标原理是寻址公式,a[0],代表偏移为0,就是首地址
a[n]_address = base_address + n * data_type_size
// 如果从1开始计数,则a[1],代表偏移为0
a[n]_address = base_address + (n-1) * data_type_size