数组
数组将数据存储在计算机中一段连续的存储空间，存储的数据类型相同，并且按照一定的顺序排列。一旦创建，其长度就固定了，数组中元素通过索引(index)标识其在数组中的位置。
1. 数组的常见操作
1.1 初始化数组
初始化数组时计算机会在内存中分配一块连续的空间，然后根据数组元素的类型和数量来确定数组的大小。初始化数组有两种方式：初始化值和不初始化值。
rust
//不初始化值
let a :[i32; 5];
//初始化值
let arr: [i32; 5] = [1, 2, 3, 4, 5]; // [1, 2, 3, 4, 5]
let brr: [i32; 5] = [0;5]; // [0, 0, 0, 0, 0]
let crr: &[i32] = [0;5];
// 在 Rust 中，指定长度时（[i32; 5]）为数组，不指定长度时（&[i32]）为切片
// 由于 Rust 的数组被设计为在编译期确定长度，因此只能使用常量来指定长度
// Vector 是 Rust 一般情况下用作动态数组的类型
// 为了方便实现扩容 extend() 方法，以下将 vector 看作数组（array）1.2 访问数组元素
通过索引index访问数组中的元素,索引从0开始，按照元素排列递增。当索引超出数组长度时会产生无效的访问。下面实现一个时间复杂度为O(1)的数组访问函数：
rust
fn get_element(arr: &[i32]) -> i32 {
let rand_index = rand::thread_rng().gen_range(0, arr.len());
let rand_element = arr[rand_index];
rand_element
}1.3 插入元素
在数组中插入元素，需要把插入位置后面的元素全部向后移一位。当元素超出数组长度的时候，要考虑末端元素将失效。
rust
/* 在数组的索引 index 处插入元素 num */
fn insert(nums: &mut [i32], num: i32, index: usize) {
// 把索引 index 以及之后的所有元素向后移动一位
for i in (index + 1..nums.len()).rev() {
nums[i] = nums[i - 1];
}
nums[index] = num; // 将 num 赋给 index 处的元素
}1.4 删除元素
删除元素需要将删除位置后面的元素都往前移动一位，末端位置的元素将为None
rust
fn delete_element(nums: &mut [i32], index: usize) {
for i in index..nums.len() - 1 {
nums[i] = nums[i + 1];
}
}1.5 遍历数组
遍历数组可以使用索引index来获取元素本身,或者直接遍历元素本身。
rust
fn loop(arr: &[i32]) {
for i in 0..arr.len() {
println!("{}", arr[i]); //通过索引访问
}
for i in arr {
println!("{}", i); /直接访问
}
}1.6 查找元素
在数组有效索引范围内查找元素，需要遍历数组，知道找到对应值，下面实现一个时间复杂度为O(n)的查找算法。
rust
fn find_element(arr: &[i32], target: i32) -> Option<usize> {
for i in 0..arr.len() {
if arr[i] == target {
Some(i)
}
}
None
}1.7 扩容数组
由于数组在创建时的长度固定，也就意味着分配的内存空间大是固定的。扩容数组需要重新分配一块更大的内存空间，然后把原数组中的元素复制到新空间中。
rust
fn enlarge(arr: &mut [i32],enlarge_size: usize) {
let mut new_arr = vec![0; arr.len() + enlarge_size];
for i in 0..arr.len() {
new_arr[i] = arr[i];
}
new_arr;
}数组的优、缺点和应用
优点
- 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
- 支持随机访问：数组可通过索引在时间O(1)内访问任何元素。
- 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。
缺点
- 可能造成内存浪费：数组需要预先分配固定大小的内存空间，如果分配的空间超过需要存储的数据，则会造成浪费.
- 插入和删除操作效率低：数组的插入和删除操作需要大量移动元素，时间复杂度为O(n)，效率较低。
- 长度不可变：数组的长度是固定的，无法动态调整。如需要扩容，则会造成很大的开销。
应用
- 随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
- 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
- 查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。
- 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
- 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组