编辑“︁数组操作与应用”︁

{{DISPLAYTITLE:数组操作与应用}}  
{{Note|本内容适用于编程初学者及需要巩固线性数据结构基础的程序员}}  

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

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

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

{| class="wikitable"  
! 操作 !! 语法示例 !! 时间复杂度  
|-  
| 访问 || <code>arr[index]</code> || O(1)  
|-  
| 插入 || 需移动后续元素 || O(n)  
|-  
| 删除 || 需移动后续元素 || O(n)  
|-  
| 搜索 || 遍历或二分查找 || O(n)或O(log n)  
|-  
| 更新 || <code>arr[index] = value</code> || O(1)  
|}  

=== 代码示例：插入与删除 ===  
<syntaxhighlight lang="python">  
# 在索引2处插入元素99  
arr = [10, 20, 30, 40]  
arr.insert(2, 99)  # 输出: [10, 20, 99, 30, 40]  

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

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

<mermaid>  
graph LR  
    A[0,0] --> B[0,1] --> C[0,2]  
    D[1,0] --> E[1,1] --> F[1,2]  
</mermaid>  

<syntaxhighlight lang="java">  
// Java初始化3x2矩阵  
int[][] matrix = {{1, 2}, {3, 4}, {5, 6}};  
</syntaxhighlight>  

== 实际应用案例 ==  
=== 案例1：图像处理 ===  
灰度图像通常用二维数组表示像素值，卷积核操作（如边缘检测）依赖数组遍历：  

<math>  
G_{x} = \begin{bmatrix}  
-1 & 0 & +1 \\  
-2 & 0 & +2 \\  
-1 & 0 & +1  
\end{bmatrix} * A  
</math>  

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

<syntaxhighlight lang="c">  
// 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;  
}  
</syntaxhighlight>  

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

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

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

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

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

{{Warning|数组越界访问是常见错误，可能导致程序崩溃或安全漏洞！}}  

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]