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]表示第一个元素 10nums[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. 数组与链表的区别数组和链表是两种最基础的线性数据结构它们在内存布局、访问方式、插入删除效率等方面有显著差异。下面从多个维度进行对比对比维度数组链表内存布局连续内存空间非连续节点通过指针连接随机访问O(1)通过下标直接访问O(n)需要从头遍历插入/删除已知位置O(n)需要移动大量元素O(1)只需修改指针空间分配静态分配或动态一次性分配大小固定动态分配按需申请节点空间利用率高无额外指针开销较低每个节点需额外存储指针缓存友好性高连续内存利于 CPU 缓存低节点分散缓存命中率低扩容需要重新分配更大的内存并拷贝天然支持动态增长下面用代码直观展示数组和链表在插入、访问上的差异#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. 总结数组和链表各有优劣选择哪种数据结构取决于具体场景如果读多写少、需要频繁按下标访问元素优先选择数组。如果写多读少、需要频繁在中间插入或删除元素优先选择链表。如果数据规模固定且对性能要求高数组通常更合适如果数据规模动态变化较大链表更灵活。理解数组和链表的本质区别是掌握数据结构与算法的基础也是写出高效代码的关键一步。
