数组详解：定义、作用、应用场景及与链表的区别（C/C++ 代码讲解）

1. 什么是数组

数组是一种线性数据结构，它把相同类型的多个元素按连续的内存空间依次存储，并通过下标（索引）来访问每个元素。数组是编程语言中最基础、最常用的数据结构之一。

在 C/C++ 中，数组的声明格式为：

// 声明一个包含 5 个 int 元素的数组
int arr[5];

// 声明并初始化
int nums[5] = {10, 20, 30, 40, 50};

// 省略长度，由编译器根据初始化列表推断
int scores[] = {90, 85, 92, 88};

数组的下标从 0 开始，例如 nums[0] 表示第一个元素 10，nums[4] 表示第五个元素 50。数组在内存中是连续存放的，因此可以通过下标直接计算出元素的地址，实现 O(1) 的随机访问。

2. 数组的作用

数组的核心作用可以概括为以下几点：

• 批量存储同类型数据：用一个变量名管理多个数据，避免为每个数据单独声明变量。
• 高效随机访问：通过下标可以在常数时间内访问任意元素，时间复杂度为 O(1)。
• 内存连续、缓存友好：由于元素在内存中连续排列，遍历时能充分利用 CPU 缓存，提升访问速度。
• 作为其他数据结构的基础：栈、队列、哈希表、堆等高级数据结构，底层往往都依赖数组实现。

下面通过一段代码演示数组的基本操作：

#include <iostream>
using namespace std;

int main() {
int arr[5] = {10, 20, 30, 40, 50};

// 随机访问：O(1)
cout << "第三个元素：" << arr[2] << endl;

// 遍历数组
for (int i = 0; i < 5; i++) {
cout << "arr[" << i << "] = " << arr[i] << endl;
}

// 修改元素
arr[0] = 99;
cout << "修改后第一个元素：" << arr[0] << endl;

return 0;
}

3. 数组的应用场景

数组在实际开发中应用非常广泛，常见场景包括：

• 存储固定数量的数据：例如存储一个班级学生的成绩、一周七天的温度等。
• 实现查找和排序算法：二分查找、冒泡排序、快速排序等算法都直接基于数组操作。
• 作为动态数据结构的底层存储：例如用数组实现栈、队列、循环队列等。
• 矩阵和图像处理：二维数组天然适合表示矩阵、图像像素等二维数据。
• 字符串处理：C 语言中字符串本质上就是字符数组。
• 哈希表的冲突解决：开放寻址法直接使用数组存储键值对。

下面给出一个用数组实现栈的简单示例：

#include <iostream>
using namespace std;

class ArrayStack {
private:
int* data;
int capacity;
int topIndex;

public:
ArrayStack(int cap) {
capacity = cap;
data = new int[capacity];
topIndex = -1;
}

void push(int value) {
if (topIndex < capacity – 1) {
data[++topIndex] = value;
}
}

int pop() {
if (topIndex >= 0) {
return data[topIndex–];
}
return -1; // 栈空
}

~ArrayStack() {
delete[] data;
}
};

int main() {
ArrayStack stack(10);
stack.push(1);
stack.push(2);
stack.push(3);
cout << "出栈：" << stack.pop() << endl; // 输出 3
return 0;
}

4. 数组与链表的区别

数组和链表是两种最基础的线性数据结构，它们在内存布局、访问方式、插入删除效率等方面有显著差异。下面从多个维度进行对比：

下面用代码直观展示数组和链表在插入、访问上的差异：

#include <iostream>
using namespace std;

// 链表节点定义
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

// 在链表头部插入节点：O(1)
Node* insertHead(Node* head, int val) {
Node* newNode = new Node(val);
newNode->next = head;
return newNode;
}

// 遍历链表查找元素：O(n)
int getByIndex(Node* head, int index) {
Node* cur = head;
int i = 0;
while (cur != nullptr && i < index) {
cur = cur->next;
i++;
}
return (cur != nullptr) ? cur->data : -1;
}

int main() {
// 数组：随机访问 O(1)
int arr[5] = {10, 20, 30, 40, 50};
cout << "数组下标访问 arr[3] = " << arr[3] << endl;

// 链表：插入 O(1)，访问 O(n)
Node* head = nullptr;
head = insertHead(head, 50);
head = insertHead(head, 40);
head = insertHead(head, 30);
cout << "链表第 2 个元素 = " << getByIndex(head, 2) << endl;

return 0;
}

5. 总结

数组和链表各有优劣，选择哪种数据结构取决于具体场景：

• 如果读多写少、需要频繁按下标访问元素，优先选择数组。
• 如果写多读少、需要频繁在中间插入或删除元素，优先选择链表。
• 如果数据规模固定且对性能要求高，数组通常更合适；如果数据规模动态变化较大，链表更灵活。

理解数组和链表的本质区别，是掌握数据结构与算法的基础，也是写出高效代码的关键一步。