数据结构与算法-数组

数组是一种线性表结构，用连续的内存来储存一组相同类型的数据,在C语言自学数组和指针中有做过这方面的一些笔记

线性结构

线性表包括 数组 队列 栈 链表，他们的特点就是有前后两个方向并且数据排成一条线

连续内存

连续的内存和相同的数据类型是数组的另一个特性，它构造了一个高效的特性随机访问。

顺序访问:类似于链表要找到下标为3的元素，需要1->2->3一级一级往下找 O(n)
随机访问:获取起始内存地址，偏移3找到对应的值 O(1)

a[i]_address = base_address + i * data_type_size

性能劣势

虽然数组有随机访问访问的特性，访问时间复杂度只有O(1),但是在删除或者插入的时候有最好O(1)最差O(n)平均O(n)的时间复杂度是不高效的。

插入优化：数组若无序插入新的元素时，可以把这个元素放到数组尾部，然后再这个元素的位置上插入新元素O(1)

删除优化：合并多次删除操作，只是单纯标记删除。在内存不够或者特点情况下触发物理删除，可以减少后面元素移动次数

越界

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;
}

上面这段代码，arr的长度是3，i<=3。说明for循环体内会进行4次操作，但是arr的最大容量为3超出了我们划分的数组容量。C语言中的变量会放在内存栈中顺序是 i，a[2]，a[1]，a[0]。在a[3]这次寻址中会找到对应i的内存地址赋值为0会造成死循环。（数组越界后的执行结果未决，和编程语言和编译器都有关系）

为什么数组下标为0

1. 最早的C语言是这样，后续语言为了延续习惯
2. 寻址是 a[n] = 起始地址+n*偏移大小 如果小标1开始就是 a[n] = 起始地址+(n-1)*偏移大小 这样会多一次计算量

---

溜了，睡觉。。。。