数据结构与算法笔记 - 数组

   |   1 minute read   |   Using 392 words

数组定义

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

数组支持【随机访问】,根据下标随机访问的时间复杂度为 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");
    }
    return 0;
}

编译器实现问题会导致上面代码进入无限循环打印hello world,arr[3]越界后会访问到变量i的地址,因为【函数栈是向地址减小的方向增长】。



© 2019 by guangmean. All Rights Reserved.