数组操作与应用

简介[编辑 | 编辑源代码]

数组是最基础且广泛使用的线性数据结构之一，它由一组连续的内存空间存储的相同类型元素组成，通过索引（通常从0开始）快速访问。数组的静态特性（固定大小）和高效随机访问能力使其在算法设计、数据库、图形处理等领域有核心应用。

核心特性[编辑 | 编辑源代码]

固定大小：声明时需指定长度（动态数组如Python列表除外）。
O(1)随机访问：通过索引直接计算内存地址。
内存连续性：元素物理相邻，利于缓存优化。

基本操作[编辑 | 编辑源代码]

以下是数组的5种基本操作及其时间复杂度：

操作	语法示例	时间复杂度
访问	`arr[index]`	O(1)
插入	需移动后续元素	O(n)
删除	需移动后续元素	O(n)
搜索	遍历或二分查找	O(n)或O(log n)
更新	`arr[index] = value`	O(1)

代码示例：插入与删除[编辑 | 编辑源代码]

  
# 在索引2处插入元素99  
arr = [10, 20, 30, 40]  
arr.insert(2, 99)  # 输出: [10, 20, 99, 30, 40]  

# 删除索引1的元素  
arr.pop(1)         # 输出: [10, 99, 30, 40]

多维数组[编辑 | 编辑源代码]

多维数组（如矩阵）是数组的数组。以二维数组为例：

  
// Java初始化3x2矩阵  
int[][] matrix = {{1, 2}, {3, 4}, {5, 6}};

实际应用案例[编辑 | 编辑源代码]

案例1：图像处理[编辑 | 编辑源代码]

灰度图像通常用二维数组表示像素值，卷积核操作（如边缘检测）依赖数组遍历：

$G_{x} = [\begin{matrix} - 1 & 0 & + 1 \\ - 2 & 0 & + 2 \\ - 1 & 0 & + 1 \end{matrix}] * A$

案例2：哈希表冲突解决[编辑 | 编辑源代码]

开放定址法利用数组存储键值对，通过线性探测解决哈希冲突：

  
// C实现线性探测  
int hash(int key) { return key % SIZE; }  

void insert(int hashTable[], int key) {  
    int index = hash(key);  
    while (hashTable[index] != -1) {  
        index = (index + 1) % SIZE;  // 线性探测  
    }  
    hashTable[index] = key;  
}

常见问题与优化[编辑 | 编辑源代码]

动态扩容[编辑 | 编辑源代码]

当数组满时，动态语言（如Python）自动分配更大内存并复制元素，均摊时间复杂度O(1)。手动实现逻辑：

  
// JavaScript动态扩容  
function resize(arr, newCapacity) {  
    let newArr = new Array(newCapacity);  
    for (let i = 0; i < arr.length; i++) {  
        newArr[i] = arr[i];  
    }  
    return newArr;  
}

缓存友好性[编辑 | 编辑源代码]

顺序访问比随机访问快约10倍（参考[局部性原理]）。优化示例：

  
// C++行优先遍历优化  
for (int i = 0; i < rows; i++) {  
    for (int j = 0; j < cols; j++) {  
        sum += matrix[i][j];  // 连续内存访问  
    }  
}

进阶话题[编辑 | 编辑源代码]

位图（Bitmap）：用二进制位数组表示集合，节省空间。
环形缓冲区：固定大小数组模拟无限队列，用于生产者-消费者模型。
Jagged Array：各行长度不同的二维数组，节省内存。

页面模块:Message box/ambox.css没有内容。

总结[编辑 | 编辑源代码]

数组因其简单性和高效性成为算法基石。掌握其操作与优化技巧对理解更复杂数据结构（如字符串、堆、哈希表）至关重要。