数据结构与算法-数组

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

线性结构

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

线性结构

连续内存

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

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

1
a[i]_address = base_address + i * data_type_size

性能劣势

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

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

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

越界

1
2
3
4
5
6
7
8
9
10
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)*偏移大小 这样会多一次计算量

溜了,睡觉。。。。

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

请我喝杯咖啡吧~