数组(数据结构)
数组的属性
数组最简单的实现只存储其第一个索引的内存地址。一些语言还存储数组的大小以防止缓冲区溢出错误。在给定索引中插入和检索项是通过获取索引来执行的 ,乘以物品大小 字节数,并将其添加到基内存地址 .
对于从零开始的编号语言,为内存地址 的值由
考虑下面的C语言代码片段:
1 2 3 4 5 6uint32_tprime_numbers[5];prime_numbers[0]=2;prime_numbers[1]=3.;prime_numbers[2]=5;prime_numbers[3.]=7;prime_numbers[4]=11;
第1行声明了一个长度为5的数组,其中包含32位无符号整数。32位是4个字节,所以我们的项目大小 是4。这意味着我们的数组是 总大小的字节。第一个索引被分配一个任意的内存地址;在我们的例子中 .整个数组使用内存地址 通过 .
第2-6行分别计算给定索引的内存地址,并将值写成一个4字节无符号整数。例如,在第5行,索引3的内存地址为 因此,值7被写入一个从address开始的4字节无符号整数 .
要在C语言的数组中存储大小不同的项,指针必须显式地存储到这些项,而不是项本身。这就是数组在Java和Python等高级语言中的工作方式。存储的不是直接在数组中存储原始项,而是对实际项的引用。这一切都是隐式发生的,因为Java和Python没有指针类型。这样做的一个后果是,按顺序遍历数组实际上可能意味着访问内存的非连续部分。不是所有值都存在于内存的连续部分中,值存储在内存中的任意位置,这些位置可能彼此相距很远。数据的局部性和CPU有效缓存数据的能力将会丢失。
数组有一个固定的大小,在创建时声明。类型是允许在创建后调整数组大小的更复杂的数据结构动态数组.
时间复杂度
数组是最快的数据结构之一,因为索引查找过程只是一个整数乘法操作,然后是一个整数加法操作——这在现代cpu上都是非常快的操作。函数所需的基本函数的时间复杂度如下阵列(ADT).
操作 | 复杂性 |
得到 | |
集 |
空间复杂度
数组占用的线性空间与元素的数量有关 他们持有。它们还有一个好处,就是不会浪费内存空间(因为它是用一定的大小初始化的):
二维数组
二维数组也存储在连续内存中。对于从零开始的编号语言,指某项在给定索引处的内存地址 而且 在项大小的数组中 字节, 行, 列和基内存地址 是由
考虑下面的C语言代码片段:
1 2 3 4 5 6 7uint32_t变换[3.] [2];变换[0] [0]=37;变换[0] [1]=0;变换[1] [0]=0;变换[1] [1]=39;变换[2] [0]=1;变换[2] [1]=4;
第1行声明了一个二维数组 行和 包含32位无符号整数的列。32位是4个字节,所以我们的项目大小 是4。这意味着我们的数组是 总大小的字节。第一个索引被分配一个任意的内存地址;在我们的例子中 .整个数组使用内存地址 通过 .
第2-7行分别计算给定索引的内存地址,并将值写成一个4字节无符号整数。例如,在第7行,索引的内存地址 , 是 因此,值4被写入一个从address开始的4字节无符号整数 .
该技术可推广用于存储 连续内存中的多维数组。
交错数组
涵盖的二维数组以上都是矩形的。通常情况下,这并不适合手头的问题,最终会浪费空间。这可以通过使用一维数组来避免,该数组存储对其他不同长度的一维数组的引用。这稍微慢一点,因为它增加了一个间接级别,但通常节省的内存是值得的。高级语言,如Java和Python,只允许在多维数组中使用锯齿数组。