数组简介
数组就是 存储在连续内存空间 的数据项的集合，目的就是将多个 具有相同数据类型 的数据存储在一段连续的内存空间。这样就可以很容易的通过数组的 首地址 和 偏移量（offset） 计算数组中每一个元素的地址，数组的第一个元素的存储位置是整个数组的首地址（通常由数组的名称表示），默认起始地址的索引为 0，两个索引之间的差值为偏移量。
图 1-1
想象一下，你（0 号）站在地面，你的若干个朋友（编号 1，2，3，4，5）分别站在一段楼梯的不同台阶上，那么你只需要知道你的朋友上了几个台阶，就可以确定他（她）的位置。
那么你就是首地址（索引为 0），而你与你的每一位朋友之间的台阶数就是该朋友相对于你的偏移量，比如 4 号朋友的偏移量就是 4 （两个索引的差值），你要找到你的 4 号朋友就需要上 4 个台阶。
为什么是相同数据类型呢？因为只有相同数据类型才可以通过首地址和偏移量来确定其他元素的地址。
图 1-2
图 1-2 可以看作是 图 1-1 楼梯的俯视图，您在楼梯的底部。数组中的每个元素都可以通过索引唯一标识（就像您在上面的示例中通过上台阶的步数确定朋友的方式类似）。
数组大小
在 C 语言中，数组具有固定的大小。一旦指定大小，便无法更改，既无法缩小，也无法扩展。因为，如果我们对数组进行扩展，我们无法确保获得的下一个内存位置是空闲的（可分配的）。对数组进行缩小也不起作用，因为数组在声明时会获得一块静态的内存空间，只有编译器才可以销毁它。
数组中的索引类型：
0 (基于 0 的索引)：数组的第一个元素用下标 0 索引。1 (基于 1 的索引)：数组的第一个元素被下标 1 索引。n (基于 n 的索引)：数组的基索引可以自由选择。通常编程语言允许基于 n 的索引，也允许负索引值和其他标量数据类型，如枚举，或者字符可以用作数组索引。
注意：我们的文章中的数组的第一个元素的下标均为 0 。
数组的优点：
-
数组支持随机访问元素。查找的时间复杂度为 。 -
数组具有更好的缓存局部性，可以在很大程度上提高访问速度。 -
数组可以使用一个变量名表示同一数据类型的多个数据项。
数组的缺点:
-
数组一旦声明，就不能更改大小。因为声明时分配给数组的是连续的静态内存空间，要想更改大小，只能由编译器释放原来的内存空间，重新声明。
-
数组的插入和删除时间复杂度为 O(n)，因为数组中的元素被存储在连续的内存位置中，插入和删除的移位操作比较耗时。
比如，如果使用数组实现数据结构栈 (Stack)，则存在一些明显的缺陷。
对于栈的 pop(出栈)操作，算法需要以下两个操作:
-
检查栈是否下溢出 -
栈顶指针下移(top–)
栈顶指针下移，我们就认为完成了出栈操作，但是下移前所指向的内存空间并不会释放，对于基本数据类型，占用的空间可以忽略不计，但若是对象将浪费大量的内存空间。
数组的例子
// 字符数组
char arr1[] = {'J','I','N','G','Y','U'};
// 整型数组
int arr2[] = {2,0,2,1,5,2,0};
// 获取数组中的任意一个数据项
arr1[3]; // 字符数组中的下标为 3 的元素，即 'G'
arr2[4]; // 整型数组中下标为 4 的元素，即 5
一般将字符数组称为 字符串（String），其他类型（比如整型、浮点型、布尔类型等）称为某某类型的数组即可。
数组的应用
-
存储具有相同数据类型的一组数据； -
数组可以用于 CPU 的调度； -
用于实现其他数据结构，如栈、队列、堆、哈希表等等。
C/C++中的数组
C/C++ 中的数组是一个存储在连续内存空间的数据项的集合，数组中的元素可以通过索引随机访问，且所有元素具有相同的数据类型。数据类型可以是基本数据类型，如整型 int、单精度浮点型 float、双精度浮点型 double、字符型 char 等等。此外，C/C++ 中的数组还可以存储派生的数据类型，如结构体 structure、指针 pointer 等等。
图 1-3
数组的声明
图 1-4
如图 1-4 所示，C/C++ 中数组的声明大致分为四种，int a[3]; 表示仅声明，未赋值，数组中的元素为随机数；int a[3] = {5,2,0}; 表示声明大小为 3 的整型数组，并全部初始化；int a[3] = {}; 表示声明一个大小为 3 的整型数组，编译器初始化为 0；int a[3] = {1}; 表示声明并初始化部分元素；int a[3] = {[0..1]=2} ，自 GCC 2.5 之后，这种声明就已经过时了，不建议使用。int* a 表示声明一个指向数组的指针，建议使用 ’*‘ 靠近变量类型的声明方式。
指定大小声明数组：
int arr[10]; // 声明一个大小为 10 的整型数组;
int n = 10; // 用户指定
int arr2[n]; // 使用用户指定的大小初始化数组;
初始化数组元素并声明：
int arr[] = {2,0,2,1,5,2,0}; // 初始化一个包含 7 个元素的整型数组
// 编译器会自动将数组 arr 的大小初始化为 4.
// 相当于 int arr[] = {2,0,2,1,5,2,0};
指定大小并初始化：
int arr[10] = {1,2,3,4,5}; // 声明一个大小为 10 的整型数组，并初始化部分元素。
// 编译器创建一个大小为 10 的整型数组，初始化前 5 个元素为指定元素
// 剩余的都将初始化 0.
// 即 int arr[] = {1,2,3,4,5,0,0,0,0,0};
获取数组中的元素
数组中的元素通过索引获取。设数组的大小为 n，则数组索引从 0 开始，一直到数组大小减去 1，即 n-1 。
C 语言的示例代码：
#include <stdio.h>
int main()
{
int arr[4];
arr[0] = 20;
arr[3/2] = 10; // 相当于 arr[1] = 10;
arr[2] = -2020;
arr[3] = arr[1];
printf("%d %d %d %dn", arr[0], arr[1], arr[2], arr[3]);
return 0;
}
输出：
20 10 -2020 10
C++ 语言的示例代码：
#include <iostream>
using namespace std;
int main()
{
int arr[4];
arr[0] = 20;
arr[3/2] = 10; // 相当于 arr[1] = 10;
arr[2] = -2020;
arr[3] = arr[1];
cout << arr[0] << " " << arr[1] << " " << arr[2] << " " << arr[3];
return 0;
}
输出：
20 10 -2020 10
C/C++ 中没有数组下标越界的检查，下面的程序可以正常编译，但运行时会产生莫名其妙的输出，所以自己写代码要注意数组下标越界问题。
// C 代码数组越界
// C 语言的编译器对数组的下标是否越界不做检查，
// 下面的程序编译正常，运行时输出莫名其妙的结果
int main()
{
int arr[4];
printf("%d ", arr[-1]); // cout << arr[-1] << " ";
printf("%d ", arr[4]); // cout << arr[4] << " ";
return 0;
}
输出：
// 不同的机器，结果都可能不同
4200875 0
数组中的元素存储在连续的内存空间。
C 语言测试数组中元素存储在连续内存空间的 demo：
/*
* C 程序说明数组存储在连续的内存空间
*/
#include <stdio.h>
int main()
{
/* 包含 10 个整数的整型数组
* 如果 arr[0] 存储在地址 x,则 arr[1] 存储在 x+sizeof(int),
* arr[2] 存储在 arr[1] 的地址 + sizeof(int)
*/
int arr[10]; // 大家也可以换成char double float long等类型
int i;
printf("编译器中整型的大小：%lun",sizeof(int));
for (i = 0; i < 10; i++)
// '&' 表示取变量的地址.
printf("arr[%d] 的地址为: %pn", i, &arr[i]);
return 0;
}
输出：
编译器中整型的大小：4
arr[0] 的地址为: 0028FF14
arr[1] 的地址为: 0028FF18
arr[2] 的地址为: 0028FF1C
arr[3] 的地址为: 0028FF20
arr[4] 的地址为: 0028FF24
arr[5] 的地址为: 0028FF28
arr[6] 的地址为: 0028FF2C
arr[7] 的地址为: 0028FF30
arr[8] 的地址为: 0028FF34
arr[9] 的地址为: 0028FF38
C++ 语言测试数组中元素存储在连续内存空间的 demo：
/*
* C++ 程序说明数组存储在连续的内存空间
*/
#include <iostream>
using namespace std;
int main()
{
/* 包含 10 个整数的整型数组
* 如果 arr[0] 存储在地址 x,则 arr[1] 存储在 x+sizeof(int),
* arr[2] 存储在 arr[1] 的地址 + sizeof(int)
*/
int arr[10]; // 大家也可以换成char double float long等类型
cout << "编译器中整型的大小：" << sizeof(int) << "n";
for (int i = 0; i < 10; i++)
// '&' 表示取变量的地址.
cout << "arr[" << i << "] 的地址为: " << &arr[i] << "n";
return 0;
}
更多关于数组的问题，比如数组和指针的区别，C++ STL 库中的 vector 表示一个数组，及动态扩容等等，那就是语言问题了，我们就不再深究，需要这方面知识的可以看看丹尼斯里奇的《C程序设计语言》。
Java 中的数组
java中的数组和C/C++语言的数组不同，以下是Java的一些关键点:
-
java 数组均是动态分配的(随后详细说明) -
Java 的设计思想就是一切皆对象，数组也不例外，可以使用对象的属性方法 length获取数组的长度，而不用像C/C++中使用sizeof计算得来 -
数组中的变量是有序的，每个变量都可以通过索引获取 -
Java 数组也可以用于静态字段，局部变量或方法的参数 -
数组的大小需用一个整型（int）变量指定，而不是 long 或 short -
数组类型的直接超类是Object类。 -
每个数组类型都实现了接口 cloneable和java.io.Serialable -
数组中的元素可以是基本数据类型(int、char 等)，也可以是引用类型（对象），这取决于数组的定义。对于基本数据类型，数组中的元素存储在连续的内存空间。对于类对象，实际对象存储在堆内存中。
一维数组
一维数组在实际开发中一定会使用，笔试面试中也最常碰见，务必熟悉数组的基本操作和背后的原理。
数组的声明
类型 数组名[];
类型[] 数组名;
数组的声明涉及两个关键词：类型 和 数组名 ，类型标明数组中所有元素的类型，数组名用来唯一地标识一个数组。类型 可以是基本数据类型（int、char、float、double 等），也可以是用户定义的引用类型（类对象）。数组一旦声明，则数组中的元素类型只能是声明的类型。
范例： 声明一个数组
// 这两种形式都可以
int intArray[];
int[] intArray;
byte byteArray[]; // 字节数组
short shortArray[]; // 短整型数组
boolean booleanArray[]; // 布尔类型的数组
long longArray[]; // 长整型数组
float floatArray[]; // 单精度浮点型
double doubleArray[]; // 双精度浮点型
char charArray[]; // 字符型数组
// 数组的类型也可以是引用数据类型（类对象）
MyClass myClassAarry[];
Object[] objectArr; // 对象数组
Collection[] cArr; // Collection 数组
尽管上面的第一个声明确定了 intArray 是一个数组变量，但实际上这个数组此时还是不存在的。它只是告诉编译器这个变量 intArray 将保存一个整数类型的数组。要将 intArray 链接到一段实际的物理整数数组，必须使用关键字 new 为 intArray 分配一段连续的内存空间。
千万要记住，数组属于引用数据类型，所以在数组使用之前一定要开辟空间（实例化），如果使用了没有开辟空间的数组，则一定会出现 NullPointerException 异常信息：
public class ArrayTest {
public static void main(String[] args){
int intArray[] = null;
System.out.println(intArray.length);
}
}
数组的实例化
声明数组时，仅创建数组的引用。要实际创建数组或为数组提供内存，可以使用关键字 new 来实例化数组，一维数组的一般形式如下所示：
var-name = new type[size];
在这里，type 指定要分配的数据的类型，size 指定数组中元素的数量，而 var-name 是链接到数组的数组变量的名称。也就是说，要使用 new 分配内存，必须指定要分配的元素的类型和数量。
int intArray[]; // 声明一个整型数组
intArray = new int[10]; // 为数组intArray分配内存
或者：
int[] intArray = new int[10]; // 结合了声明和实例化
注意：
-
由 new分配的数组中的元素将默认初始化为 0（对于数字类型），false（对于布尔值）或null（对于引用类型）。 -
获取数组包含两步。第一步，必须声明指定类型的数组变量；第二步，必须使用 new 分配用于保存数组的内存，并将其分配给数组变量。因此，在 Java 中，所有数组都是动态分配的。
数组静态初始化
有些情况下，数组的大小和数组中的元素已知，我们就可以用数组的静态初始化完成：
int[] intArray = new int[]{1,2,3,4,5,6,7,8,9,10};
-
数组中元素的个数确定了创建的数组的长度，上面的数组包含 10 个元素，数组的长度为 10. -
静态初始化也可以简化成 int[] intArray = {1,2,3,4,5,6,7,8,9,10};
在开发之中，对于静态数组的初始化强烈建议使用完整语法模式，这样可以轻松地使用匿名数组这一概念。
public class ArrayTest {
public static void main(String[] args){
System.out.println(new int[]{1,2,3,4,5,6,7,8,9,10});
}
}
使用 for 循环遍历数组
数组中的元素通过索引来获取，索引从 0 到 size - 1 ，size 表示数组的长度，则数组中的所有元素可以用一个 for 循环来获取。
for(int i = 0; i < arr.length; i++){
System.out.println("arr[" + i + "] = " + arr[i]);
}
范例： for 循环遍历数组
public class ArrayTest {
public static void main(String[] args){
int[] arr = new int[7];
arr[0] = 2;
arr[1] = 0;
arr[2] = 2;
arr[3] = 1;
arr[4] = 5;
arr[5] = 2;
arr[6] = 0;
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}
一维数组的内存表示
一维数组的变量名 arr 存储的是数组中第一个元素的地址：
public class ArrayTest {
public static void main(String[] args){
int[] arr = new int[3];
arr[0] = 5;
arr[1] = 2;
arr[2] = 0;
System.out.println(arr); //输出 [I@1b6d3586，每个人机器不同，运行结果不同。
}
}
[I@1b6d3586 的解释：
[ ：代表是数组，几个就是几维
I ：代表是 int 类型
@ ：固定的分割符号
1b6d3586 ：代表的是 16 进制的地址，也就是数组的首地址，而数组名表示的就是整个数组第一个元素的地址。
对象数组
对象数组和基本数据类型数组的创建一样：
Student[] arr = new Student[5]; // Student 是自定义的类
学生数组包含 5 个内存空间，每个内存空间可容纳 1 个学生类的地址。必须使用学生类的构造函数实例化学生对象，并将其引用分配给数组中的元素。
范例： 创建一个学生（对象）数组
class Student {
public int number;
public int age;
public String name;
public Student(int number, int age, String name) {
this.number = number;
this.age = age;
this.name = name;
}
}
public class ArrayTest {
public static void main(String[] args) {
Student[] arr = new Student[3];
arr[0] = new Student(1, 42, "Kobe");
arr[1] = new Student(2, 36, "James");
arr[2] = new Student(3, 32, "Curry");
for (int i = 0; i < arr.length; i++) {
System.out.println("Element is " + arr[i].number + " " +
arr[i].name + ":" + arr[i].age);
}
}
}
数组越界问题
当我们访问数组的索引超出了数组的索引范围，JVM 就会抛出 ArrayIndexOutOfBoundsException ，表明我们访问了不合法的索引，索引为负值或者大于等于数组的大小 n ，就会抛出该异常。
class JY
{
public static void main (String[] args)
{
int[] arr = new int[2];
arr[0] = 10;
arr[1] = 20;
for (int i = 0; i <= arr.length; i++) // 注意这里不能是 <= ,而应该是 <
System.out.println(arr[i]);
}
}
多维数组
多维数组就是数组的数组，该数组的元素为其他数组的引用，也称为交错数组。
int[][] intArray = new int[10][20]; // 二维数组，矩阵
int[][][] intArray = new int[2][3][4]; // 三维数组
其中使用最多的多维数组也就是二维数组，也称为矩阵。
范例： 多维数组的声明和遍历
class multiDimensional
{
public static void main(String[] args)
{
// 声明并初始化二维数组
int arr[][] = { {1,2,3},{3,6,9},{8,4,2} };
// 打印二维数组
for (int i=0; i< 3 ; i++)
{
for (int j=0; j < 3 ; j++)
System.out.print(arr[i][j] + " ");
System.out.println();
}
}
}
数组 int arr[][] = { {1,2,3},{3,6,9},{8,4,2} }; 的内存结构图：
数组作为入参
与变量一样，我们也可以将数组作为入参传入其他方法中。
**范例：**数组作为方法的参数
class test{
public static void main(String[] args){
int[] arr = {1,2,3,4,5,6,7,8,9};
sum(arr);
}
public static void sum(int[] arr){
int sum = 0;
for(int i = 0; i < arr.length; i++){
sum += arr[i];
}
System.out.println(sum);
}
}
数组作为返回值
class test{
public static void main(String[] args){
int[] arr = fun();
for(int i = 0; i< arr.length; i++){
System.out.print(arr[i] + " ");
}
}
public static int[] fun(){
return new int[]{1,2,3,4,5,6,7,8,9};
}
}
数组的复制
讲这部分主要是让大家对两个概念，“深拷贝” 和 “浅拷贝”有一个较深入的印象。
深拷贝，在拷贝引用类型成员变量时，为引用类型的数据成员另辟了一个独立的内存空间，实现真正内容上的拷贝。
class Test
{
public static void main(String args[])
{
int intArr[] = {1,2,3};
int cloneArr[] = intArr.clone();
// 输出 false, 深拷贝创建了一个新的数组
System.out.println(intArr == cloneArr);
for (int i = 0; i < cloneArr.length; i++) {
System.out.print(cloneArr[i]+" ");
}
}
}
浅拷贝： 对于引用类型，比如数组或者类对象，因为引用类型是引用传递，所以浅拷贝只是把内存地址赋值给了成员变量，它们指向了同一内存空间。改变其中一个，会对另外一个也产生影响。
范例：多维数组的拷贝
class Test12
{
public static void main(String args[])
{
int intArr[][] = {{1,2,3},{4,5,6}};
int cloneArr[][] = intArr.clone();
// 打印 false
System.out.println(intArr == cloneArr);
// 打印 true, 对子数组的拷贝属于浅拷贝
System.out.println(intArr[0] == cloneArr[0]);
System.out.println(intArr[1] == cloneArr[1]);
}
}
Python 中的数组
除了 list 之类的泛型容器外，Python在其定义中还可以处理具有特定数据类型的容器。在python 中，数组可以由一个名为 array 的模块来处理。当只需要操作特定数据类型值时，array 就会变得非常有用。
array 的操作
-
array(data type, value list)： 这个函数用于创建一个数组，数组的参数中指定了数据类型和值列表。下表中提到了一些数据类型。
| 类型码 | C 类型 | Python 类型 | 最小字节数 |
|---|---|---|---|
| ‘b’ | signed char | int | 1 |
| ‘B’ | unsigned char | int | 1 |
| ‘u’ | Py_UNICODE | unicode character | 2 |
| ‘h’ | signed short | int | 2 |
| ‘H’ | unsigned short | int | 2 |
| ‘i’ | signed int | int | 2 |
| ‘I’ | unsigned int | int | 2 |
| ‘L’ | unsigned long | int | 4 |
| ‘q’ | signed long long | int | 8 |
| ‘Q’ | unsigned long long | int | 8 |
| ‘f’ | float | float | 4 |
| ‘d’ | double | float | 8 |
-
append():用于在数组的末尾添加元素。 -
insert(i, x): 用于在其参数中指定的第 i 个位置添加元素 x
范例：数组的创建和相关操作
import array
# 初始化一个 signed integer 数组
arr = array.array('i', [1, 2, 3])
# 打印数组
print ("新创建的数组 : ",end=" ")
for i in range (0, 3):
print (arr[i], end=" ")
print("r")
# 在数组的末尾插入元素 4 [1,2,3,4]
arr.append(4);
# 打印插入后的数组
print("插入元素 4 之后的数组 : ", end="")
for i in range (0, 4):
print (arr[i], end=" ")
# 在下标为 2 的位置插入元素 5，[1,2,5,3,4]
arr.insert(2, 5)
print("r")
# 打印插入之后的数组
print ("插入元素后的数组 : ", end="")
for i in range (0, 5):
print (arr[i], end=" ")
-
pop(i): 删除索引为 i 的元素，并返回该元素。 -
remove(x): 函数用来移除数组中第一个出现的值 x
import array
# 初始化一个带重复元素的整型数组
arr= array.array('i',[1, 2, 3, 1, 5])
# 打印原数组
print ("原数组为 : ",end="")
for i in range (0,5):
print (arr[i],end=" ")
print ("r")
# 打印 pop 的元素 arr[2] = 3
print ("pop(2) 为 : ",end="")
print (arr.pop(2));
# 打印 pop(2) 之后数组中剩余元素 [1,2,1,5]
print ("pop(2) 之后数组剩余元素为 : ",end="")
for i in range (0,4):
print (arr[i],end=" ")
print("r")
# 移除数组中的第一个值为 1 的元素，即 arr[0]
arr.remove(1)
# 打印移除后的数组 [2,1,5]
print ("The array after removing is : ",end="")
for i in range (0,3):
print (arr[i],end=" ")
-
index(x): 返回数组中第一个出现值为 x 的索引 -
reverse(): 反转数组。
import array
arr= array.array('i',[1, 2, 3, 1, 2, 5])
# 打印数组中第一个值为 2 的元素的索引值，即 1
print ("元素 2 第一次出现的索引位置为 : ",end="")
print (arr.index(2))
# 反转数组 [5,2,1,3,2,1]
arr.reverse()
# 反转数组后
print ("反转数组之后的值为 : ",end="")
for i in range (0,6):
print (arr[i],end=" ")
总结
本文主要给大家介绍了数组，数组的优缺点，以及C/C++ 语言、Java 语言和 Python 中数组的声明和使用，关于其他各类语言，比如 go、JavaScript等等，给大家推荐一个网站：https://www.runoob.com/ 可以快速上手。
最后说一下为什么写这篇文章，原因很简单，我们大部分人在刷题之前都没有搞清楚语言本身的一些特性和语法知识点，帮大家总结梳理，其次是从更实际的角度出发，而不是讲线性表的顺序存储结构的特点以及使用方法，数组就是线性表顺序存储结构的最典型体现！
