## 1. 数组基础从内存模型到实战定义 在C语言中数组是最基础且强大的数据结构之一。理解数组的本质需要从计算机内存模型说起——数组本质上是一块连续的内存空间每个元素通过索引下标进行访问。这种连续存储特性使得数组具有O(1)时间复杂度的随机访问能力这也是它区别于链表等数据结构的核心特征。 ### 1.1 数组的声明与初始化 标准的一维数组声明语法为 c 数据类型 数组名[元素数量];例如声明一个包含5个整数的数组int scores[5];数组初始化有多种方式// 方式1全量初始化 int arr1[3] {10, 20, 30}; // 方式2部分初始化未指定元素自动置0 int arr2[5] {1, 2}; // 方式3省略长度声明 int arr3[] {1, 2, 3}; // 编译器自动推导长度为3关键细节数组长度必须是编译期常量表达式C99前VLA变长数组在C99后支持但需谨慎使用。在MSVC编译器中VLA可能不被支持。1.2 数组的内存布局以int arr[3] {10,20,30}为例其内存结构为地址 | 值 0x1000 | 10 (arr[0]) 0x1004 | 20 (arr[1]) 0x1008 | 30 (arr[2])每个int占4字节32位系统地址连续递增。这种布局使得指针运算可以与数组访问等价*(arr1) arr[1] // 均为201.3 多维数组实战二维数组是数组的数组例如int matrix[2][3] { {1, 2, 3}, {4, 5, 6} };内存中仍按行优先连续存储1,2,3,4,5,6。计算元素位置的公式为matrix[i][j]的地址 基地址 (i * 列数 j) * 元素大小2. 数组操作进阶边界陷阱与高效遍历2.1 数组越界的幽灵C语言不检查数组边界越界访问可能导致读取到垃圾值修改其他变量数据引发段错误Segmentation fault典型错误案例int arr[3] {0}; for(int i0; i3; i) { // 越界 arr[i] i; }防御性编程建议始终使用sizeof计算数组长度int length sizeof(arr)/sizeof(arr[0]);2.2 高效遍历的三种范式下标遍历通用但略慢for(int i0; ilength; i) { printf(%d , arr[i]); }指针遍历速度更快for(int *parr; parrlength; p) { printf(%d , *p); }函数指针遍历C11支持void print(int x) { printf(%d , x); } array_foreach(arr, length, print);2.3 数组传参的真相数组作为函数参数时会退化为指针以下三种声明等价void func(int arr[]); void func(int arr[10]); // 数字被忽略 void func(int *arr);因此无法在函数内通过sizeof获取数组长度必须显式传递长度参数。3. 排序算法深度实现3.1 冒泡排序入门首选void bubble_sort(int arr[], int n) { for(int i0; in-1; i) { int swapped 0; for(int j0; jn-i-1; j) { if(arr[j] arr[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; swapped 1; } } if(!swapped) break; // 提前终止优化 } }时间复杂度最优O(n)最差O(n²)3.2 快速排序分治典范int partition(int arr[], int low, int high) { int pivot arr[high]; int i low - 1; for(int jlow; jhigh; j) { if(arr[j] pivot) { i; swap(arr[i], arr[j]); } } swap(arr[i1], arr[high]); return i1; } void quick_sort(int arr[], int low, int high) { if(low high) { int pi partition(arr, low, high); quick_sort(arr, low, pi-1); quick_sort(arr, pi1, high); } }时间复杂度平均O(nlogn)最差O(n²)3.3 选择排序 vs 插入排序选择排序特点void selection_sort(int arr[], int n) { for(int i0; in-1; i) { int min_idx i; for(int ji1; jn; j) { if(arr[j] arr[min_idx]) min_idx j; } swap(arr[i], arr[min_idx]); } }每次选择最小元素放到已排序序列末尾插入排序特点void insertion_sort(int arr[], int n) { for(int i1; in; i) { int key arr[i]; int j i-1; while(j0 arr[j]key) { arr[j1] arr[j]; j--; } arr[j1] key; } }适合近乎有序的数据集最优可达O(n)4. 工程实践中的数组技巧4.1 动态数组实现C语言标准库没有动态数组可自行实现typedef struct { int *data; int size; int capacity; } DynamicArray; void init_array(DynamicArray *arr, int cap) { arr-data malloc(cap * sizeof(int)); arr-size 0; arr-capacity cap; } void push_back(DynamicArray *arr, int val) { if(arr-size arr-capacity) { arr-capacity * 2; arr-data realloc(arr-data, arr-capacity * sizeof(int)); } arr-data[arr-size] val; }4.2 数组与字符串的默契字符数组作为字符串使用时char str1[6] {H,e,l,l,o,\0}; char str2[] World; // 自动添加\0注意strlen计算长度不包含\0但sizeof包含4.3 位运算压缩数组对于布尔型数组可用每个bit表示一个元素unsigned char bits[10]; // 可表示80个布尔值 void set_bit(int pos) { bits[pos/8] | (1 (pos%8)); } int get_bit(int pos) { return (bits[pos/8] (pos%8)) 1; }5. 高频面试题精解5.1 数组去重算法双指针法要求先排序int remove_duplicates(int arr[], int n) { if(n 0) return 0; int slow 0; for(int fast1; fastn; fast) { if(arr[fast] ! arr[slow]) { arr[slow] arr[fast]; } } return slow 1; }5.2 两数之和问题哈希表法O(n)时间复杂度int* twoSum(int* nums, int numsSize, int target) { int hash[20001] {0}; // 简单哈希表 for(int i0; inumsSize; i) { int complement target - nums[i]; if(hash[complement10000] ! 0) { int* res malloc(2*sizeof(int)); res[0] hash[complement10000]-1; res[1] i; return res; } hash[nums[i]10000] i1; } return NULL; }5.3 旋转数组问题三次反转法O(1)空间复杂度void reverse(int* nums, int start, int end) { while(start end) { int temp nums[start]; nums[start] nums[end]; nums[end] temp; start; end--; } } void rotate(int* nums, int numsSize, int k) { k % numsSize; reverse(nums, 0, numsSize-1); reverse(nums, 0, k-1); reverse(nums, k, numsSize-1); }6. 性能优化与调试技巧6.1 缓存友好访问模式二维数组应按行优先访问// 好顺序访问 for(int i0; irows; i) { for(int j0; jcols; j) { sum matrix[i][j]; } } // 差缓存不友好 for(int j0; jcols; j) { for(int i0; irows; i) { sum matrix[i][j]; } }6.2 使用restrict关键字帮助编译器优化void add_arrays(int* restrict a, int* restrict b, int* restrict c, int n) { for(int i0; in; i) { a[i] b[i] c[i]; } }6.3 调试数组越界的方法使用AddressSanitizer编译gcc -fsanitizeaddress -g program.c设置哨兵值#define GUARD_VALUE 0xDEADBEEF int* create_array(int size) { int* arr malloc((size2)*sizeof(int)); arr[0] GUARD_VALUE; arr[size1] GUARD_VALUE; return arr1; // 返回有效区间 } void check_guards(int* arr, int size) { if(arr[-1] ! GUARD_VALUE || arr[size] ! GUARD_VALUE) { printf(Array bounds violated!\n); } }7. 现代C标准中的数组新特性7.1 复合字面量C99允许创建匿名数组// 传统方式 int arr1[] {1,2,3}; // 复合字面量 int *ptr (int[]){1,2,3}; // 生命周期随所在作用域7.2 指定初始化器灵活初始化数组int arr[10] { [0] 10, [5] 20, [9] 30 // 其余自动初始化为0 };7.3 静态断言检查数组大小编译时检查#define STATIC_ASSERT(cond) typedef char static_assert[(cond)?1:-1] int arr[10]; STATIC_ASSERT(sizeof(arr)/sizeof(arr[0]) 10); // 编译时验证