11. 数组的定义和存储结构

# 1. 介绍

## 1.1 什么是数组

数组是一种存储相同类型数据元素的线性数据结构。它由连续的内存空间组成，每个元素都可以通过索引来访问。数组可以用于存储和操作多个数据项，例如整数、浮点数、字符等。

## 1.2 数组的作用和优点

数组在编程中有着重要的作用，它可以提供高效的数据访问和操作方式。数组的优点包括：
- 提供快速访问元素的能力：通过索引，可以在O(1)的时间复杂度内访问数组元素；
- 节省存储空间：由于数组的元素是连续存储的，不需要额外的指针和链接信息，因此相对于其他数据结构，数组的存储空间相对较小；
- 方便的内存分配：数组的内存分配是连续的，便于预先分配一块连续的内存空间来存储数据。

## 1.3 数组的定义和声明

在各种编程语言中，数组的定义和声明方式略有不同。以Python为例，我们可以使用列表（list）来表示数组。

# 定义一个整数数组
my_array = [1, 2, 3, 4, 5]

# 定义一个字符串数组
my_array = ["apple", "banana", "orange"]

在Java中，数组的定义和声明稍有不同：

// 定义一个整型数组
int[] myArray = {1, 2, 3, 4, 5};

// 定义一个字符串数组
String[] myArray = {"apple", "banana", "orange"};

无论使用哪种编程语言，数组的定义都需要指定元素类型和初始值，通过索引来访问和修改数组的元素。

# 2. 数组存储结构

数组是一种线性数据结构，其存储结构可以分为一维数组和多维数组两种形式。在内存中，数组的存储是连续的，这也是数组访问速度快的原因之一。接下来将详细介绍数组的存储结构。

### 2.1 一维数组的存储结构

一维数组是最简单的数组形式，其元素在内存中是连续存储的。数组元素之间的地址关系可以使用以下公式表示：

address(a[i]) = address(a[0]) + i * size

其中，`address(a[i])` 表示数组元素 `a[i]` 的地址，`address(a[0])` 表示数组首元素 `a[0]` 的地址，`i` 表示元素的索引，`size` 表示数组元素的大小。

### 2.2 多维数组的存储结构

多维数组可以是二维、三维甚至更高维度的数组，其存储结构也是连续的。对于二维数组，其元素的地址计算公式为：

address(a[i][j]) = address(a[0][0]) + (i * n + j) * size

其中，`address(a[i][j])` 表示数组元素 `a[i][j]` 的地址，`address(a[0][0])` 表示数组首元素 `a[0][0]` 的地址，`i` 和 `j` 分别表示元素在第一维和第二维的索引，`n` 表示第二维的长度，`size` 表示数组元素的大小。

### 2.3 数组的内存分配方式

在大多数编程语言中，数组的内存分配是静态的或动态的。静态数组的大小在编译时就确定，并分配固定大小的内存空间；动态数组的大小可以在运行时动态确定，并在需要时动态分配或释放内存空间。这种静态或动态的内存分配方式影响了数组的使用灵活性和性能表现。

以上是关于数组存储结构的基本介绍，下一节将介绍数组的基本操作。

# 3. 数组的基本操作

数组作为一种常见的数据结构，在使用过程中需要进行一些基本的操作，包括初始化、访问和修改数组元素、插入和删除数组元素，以及扩展和缩小数组容量等操作。下面将逐一介绍数组的基本操作及其实现方式。

#### 3.1 数组的初始化

数组的初始化是指在使用数组之前为数组分配内存，并初始化数组元素的值。在不同的编程语言中，数组的初始化操作可能会有所不同。以下是几种常见语言中数组的初始化方法。

##### Python

在Python中，可以使用以下方式初始化一个数组：

# 初始化一个包含5个元素的数组，初始值为0
arr = [0] * 5

# 初始化一个数组并赋予初始值
arr = [1, 2, 3, 4, 5]

##### Java

在Java中，可以使用以下方式初始化一个数组：

// 初始化一个包含5个元素的数组，初始值为0
int[] arr = new int[5];

// 初始化一个数组并赋予初始值
int[] arr = {1, 2, 3, 4, 5};

##### JavaScript

在JavaScript中，可以使用以下方式初始化一个数组：

// 初始化一个包含5个元素的数组，初始值为0
let arr = new Array(5).fill(0);

// 初始化一个数组并赋予初始值
let arr = [1, 2, 3, 4, 5];

#### 3.2 访问和修改数组元素

数组元素的访问和修改是数组操作中最基本的功能之一。通过数组下标可以快速定位到数组中的某个元素，并对其进行读取或修改。

##### Python

arr = [1, 2, 3, 4, 5]
# 访问数组元素
print(arr[0])  # 输出 1
# 修改数组元素
arr[0] = 100
print(arr)  # 输出 [100, 2, 3, 4, 5]

##### Java