数组简介
数组是存储在连续内存空间中的数据项的集合。 目的是在连续的内存空间中存储多个相同数据类型的数据。 这样,通过数组的首地址和()就可以很方便地计算出数组中每个元素的地址。 数组第一个元素的存储位置是整个数组的首地址(通常用数组的名称来表示),默认起始地址的索引为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),就存在一些明显的缺陷。
对于栈的出栈操作,算法需要以下两个操作:
检查堆栈下溢
将栈顶指针向下移动(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
一般将字符数组称为(),其他类型(如整数、浮点类型、布尔类型等)称为某些类型的数组。
数组的应用
存储一组具有相同数据类型的数据;
数组可用于CPU调度;
用于实现其他数据结构,如堆栈、队列、堆、哈希表等。
C/C++ 中的数组
C/C++ 中的数组是存储在连续内存空间中的数据项的集合。 数组中的元素可以通过索引随机访问,并且所有元素具有相同的数据类型。 数据类型可以是基本数据类型,例如整数类型int、单精度浮点类型float、双精度浮点类型、字符类型char等。 另外,C/C++中的数组还可以存储派生数据类型,例如结构体、指针等。
图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
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
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语言测试数组中的元素存储在连续的内存空间中:
#include
int main()
{
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++语言测试数组中的元素存储在连续内存空间中的演示:
#include
using namespace std;
int main()
{
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库中数组的表示以及动态扩展等,都是语言问题,我们就不深究了。 需要这方面知识的人可以看看 Rich 的《C 编程语言》。
Java 中的数组
java中的数组与C/C++语言中的数组不同。 下面是Java的一些要点:
Java数组是动态分配的(稍后详细介绍)
Java的设计思想是一切皆对象,数组也不例外。 可以使用对象的属性方法来获取数组的长度,而不是使用C/C++中的计算方法
数组中的变量是有序的,通过索引可以获取每个变量
Java 数组还可以用于静态字段、局部变量或方法的参数
数组的大小需要用整型(int)变量指定,不能是long或short
数组类型的直接超类是类。
每个数组类型都实现接口和 java.io.
数组中的元素可以是基本数据类型(int、char 等)或引用类型(对象),具体取决于数组的定义。 对于原始数据类型,数组中的元素存储在连续的内存空间中。 对于类对象,实际对象存储在堆内存中。
一维数组
一维数组在实际开发中肯定会用到,在笔试面试中最常遇到。 您必须熟悉数组的基本操作及其背后的原理。
数组声明
类型 数组名[];
类型[] 数组名;
数组的声明涉及两个关键字:类型和数组名。 类型表示数组中所有元素的类型,数组名用于唯一标识一个数组。 类型可以是原始数据类型(int、char、float 等)或用户定义的引用类型(类对象)。 一旦声明了数组,数组中的元素类型就只能是声明的类型。
示例:声明一个数组
// 这两种形式都可以
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 数组
尽管上面的第一个声明标识了一个数组变量,但此时该数组实际上并不存在。 它只是告诉编译器该变量将保存整数类型的数组。 要链接到实际的物理整数数组,必须使用关键字new来分配连续的内存空间。
请记住,数组是引用数据类型,因此在使用数组之前必须开辟空间(实例化)。 如果使用数组而不开辟空间,肯定会出现异常信息:
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};
在开发中,强烈建议使用全语法模式进行静态数组的初始化,这样可以方便地使用匿名数组的概念。
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:代表int类型
@ :固定分隔符
:表示十六进制的地址,即数组的首地址,数组名表示整个数组的第一个元素的地址。
对象数组
对象数组的创建方式与原始数据类型数组的创建方式相同:
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就会抛出异常,表明我们访问了非法索引。 如果索引为负数或者大于等于数组的大小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]);
}
}
数组中
除了列表等通用容器外,还可以在其定义中处理特定数据类型的容器。 在 中,数组可以由一个名为 array 的模块来处理。 当您只需要操作特定数据类型的值时,数组非常有用。
数组运算
array(data type, value list):该函数用于创建一个数组,其数据类型和值列表在数组的参数中指定。 下表提到了一些数据类型。
类型代码 C 类型 类型 最小字节数
'b'
字符
整数
1
'B'
字符
整数
1
'你'
2
'H'
短的
整数
2
'H'
短的
整数
2
'我'
整数
整数
2
'我'
整数
整数
2
'L'
长的
整数
4
'q'
长长
整数
8
'问'
长长
整数
8
'F'
漂浮
漂浮
4
'd'
漂浮
8
():用于在数组末尾添加元素。
(i, x):用于将元素 x 添加到其参数中指定的第 i 个位置
示例:数组的创建及相关操作
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的元素并返回。
(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 在数组中第一次出现的索引
() :反转数组。
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语言、中数组中数组的声明和使用。 关于其他语言,比如go等,我给你推荐一个网站:你可以快速上手。
最后说一下我为什么写这篇文章。 原因很简单。 我们大多数人在刷题之前都没有弄清楚语言本身的一些特点和语法知识点。 先不说线性表顺序存储结构的特点和用法,数组才是线性表顺序存储结构最典型的体现!
作者:景宇,一个追求极致的分享倡导者,想带领你一起拥有美好的生活,并把它变成你的保护伞。
公众号:晶宇