[数据结构与算法]06 数组( Array )

ゝ一纸荒年。 2023-06-24 08:24 13阅读 0赞

什么是数组呢?你的脑海中是不是第一反应是这样的:

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

在定义上,咱们来死扣两个概念.

*  线性表.  
    线性线性,就是数据排成像一条线一样的结构,每个线性表上的数据最多只有前和后两个方向.这样看定义的话,除了数组,链表,队列,栈也是线性表结构.
 *  是一组连续的内存空间,存储一组具有相同类型的数据.  
    这句话能够看出来,对于数组有两个限制:第一空间必须是连续的,第二,数据需要是相同类型的.  
    也就是说,如果内存空间剩余 1MB 但是不是连续的,此时创建数组就会失败;如果数组内存储的不是相同类型的数据,就会报错

## 数组是如何实现"随机访问"的 ##

当我们申请创建一个数组时,比如此时我申请一个数组 `int[] a = new int[10]` ,计算机会给数组 `a[10]` 分配一块连续内存空间.  
计算机会给每个内存单元分配一个地址,通过地址来访问内存中的数据.当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,来计算出想要访问元素的存储内存地址:

> a\[i\]\_address = base\_address + i \* data\_type\_size

根据 CPU 的预读机制,存储的数组就有可能被 CPU 全部读入,在 CPU 中进行访问,那个速度你可以想象~

## 警惕数组越界问题 ##

咱们先来看一段 C 语言代码:

#include <stdio.h>
    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;
    }

仔细看,发现问题了嘛?这段代码不会打印 3 行" hello world “,而是会无限打印” hello world ".  
因为,数组大小为 3 , a\[0\] , a\[1\] , a\[2\] ,实例代码中因为书写错误,导致 for 循环的结束条件错写成了 `i<=3` ,而不是 `i<3` ,所以当 `i=3` 时,会导致数组 `a[3]` 访问越界.在 C 语言中,只要不是访问受限的内存,那么所有的内存空间都是可以自由访问的.如果 `a[3]=0` 恰好是 `i=0` ,循环就会又开始.  
所以这段代码就陷入了死循环.

--------------------

参考:

*   极客时间<数据结构与算法之美>

以上,感谢您的阅读(这篇文章写得确实有些仓促了,逃;  
最后,祝您冬至快乐~