数组与字符串基础操作
深度解析 ↓核心要点
- 数组连续存储，
a[i]就是*(a + i)，按下标访问 O(1)（推导见 A1） - 数组作函数参数会退化为首元素指针，
sizeof当场失效；长度必须显式传入 - 二维数组按行主序布局：要么传
int (*p)[n]，要么扁平化成a[r * n + c]，不能写成int **（详见 A2） - C 没有字符串类型：
char *以'\0'结尾，strlen是 O(n)，写操作必须自带目标容量 - 拼接 / 复制一律用
snprintf或手动拷贝并显式传容量；strcpy/strcat/sprintf不知道目标有多大（详见 B2） - 标准库没有动态数组：尾部追加要用
realloc自己实现，扩容策略与失败语义见 B1
复杂度速查
| 操作 / 场景 | 时间 | 空间 | 说明 |
|---|---|---|---|
按下标访问 a[i] | O(1) | O(1) | 编译为基址 + i × sizeof(T)，一次乘法一次偏移 |
sizeof(a) / sizeof(a[0]) | O(1) | O(1) | 只对「真数组」有效；传参退化为指针后必然是错的 |
strlen(s) | O(n) | O(1) | 逐字节找 '\0'；写进循环条件会退化为 O(n²) |
| 按行扫描二维数组 | O(m·n) | O(1) | 行主序，行内地址连续，缓存友好 |
| 中间插入 / 删除 | O(n) | O(1) | 后续元素整体搬移，memmove 处理重叠 |
| 动态数组尾部追加 | 均摊 O(1) | O(n) | realloc 按倍数扩容，几何级数摊还（推导见 B1） |
| 复制 n 字节 | O(n) | O(n) | 源目标可能重叠时用 memmove，memcpy 要求不重叠 |
模板代码
模板 1：方向数组遍历二维网格把行列偏移放进数组，一次循环枚举 4 / 8 连通邻居；网格按行优先扁平化，避免二维参数类型陷阱。
#include <stdbool.h>
// 4 向（上下左右）与 8 向（含对角线）的行、列偏移
static const int DR4[4] = {-1, 1, 0, 0};
static const int DC4[4] = {0, 0, -1, 1};
static const int DR8[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
static const int DC8[8] = {0, 0, -1, 1, -1, 1, -1, 1};
// 收集 (r, c) 的合法邻居：网格是行主序的 m × n 矩阵。
// out_r / out_c 由调用方提供，容量至少 8；返回邻居个数。
int neighbors(int r, int c, int m, int n, bool diagonal, int *out_r, int *out_c) {
const int *dr = diagonal ? DR8 : DR4;
const int *dc = diagonal ? DC8 : DC4;
int k = diagonal ? 8 : 4;
int cnt = 0;
for (int i = 0; i < k; ++i) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
out_r[cnt] = nr;
out_c[cnt] = nc;
++cnt;
}
}
return cnt;
}模板 2：字符串切分、拼接与数值转换不修改原串、无静态状态的手动切分；
strtoll 必须检查 endptr 才算真正解析成功；拼接口一律显式传容量。#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 按分隔符切分：每段写入 out[i]（容量 cap 字节），最多 top 段，返回段数。
// 空段跳过；超长段截断而不是溢出。out 由调用方提供二维缓冲区。
int split(const char *s, char delim, char out[][64], int top) {
int cnt = 0;
const char *p = s;
while (cnt < top && *p != '\0') {
const char *q = strchr(p, delim);
size_t len = q ? (size_t)(q - p) : strlen(p);
if (len > 63) len = 63; // 截断保护，绝不越界写
memcpy(out[cnt], p, len);
out[cnt][len] = '\0';
if (len > 0) ++cnt; // 跳过空段
if (q == NULL) break;
p = q + 1;
}
return cnt;
}
// 严格解析整数：整串都必须是合法十进制数，否则返回 false（atoi 做不到这一点）
bool parse_int(const char *t, long long *out) {
char *end = NULL;
long long v = strtoll(t, &end, 10);
if (end == t || *end != '\0') return false; // 空串或残留非法字符
*out = v;
return true;
}
// 把整数数组拼成 "1,2,3"；放不下就返回 -1，绝不截断
int join_ints(const long long *a, int n, char *buf, size_t cap) {
size_t used = 0;
if (cap == 0) return -1;
buf[0] = '\0';
for (int i = 0; i < n; ++i) {
int w = snprintf(buf + used, cap - used, i ? ",%lld" : "%lld", a[i]);
if (w < 0 || (size_t)w >= cap - used) return -1;
used += (size_t)w;
}
return (int)used;
}模板 3：原地删除元素（快慢指针雏形）O(n) 时间、O(1) 额外空间；C 里「返回新长度」比返回新数组更自然，前 k 个位置就是结果。
// 删除所有等于 val 的元素，返回新长度；nums[0..k-1] 即保留元素。
// 注意：C 的「数组」没有长度，n 必须由调用方给出。
int removeElement(int *nums, int n, int val) {
int k = 0; // 慢指针：保留区间的下一个写入位置
for (int i = 0; i < n; ++i)
if (nums[i] != val)
nums[k++] = nums[i]; // 快指针扫到的非目标值前移
return k;
}模板 4：原地反转（数组 / 字符串）数组用双指针对撞交换；C 字符串原地反转必须先用
strlen 定位 NUL，且只能按字节反转。#include <stddef.h>
#include <string.h>
// 一、整型数组原地反转：双指针对撞交换
void reverseArray(int *a, int n) {
for (int i = 0, j = n - 1; i < j; ++i, --j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
// 二、C 字符串原地反转：长度由 strlen 给出，j 指向最后一个有效字节
// ⚠️ 这是字节级反转：对 UTF-8 中文会把多字节码点切碎成非法序列（详见 A3）
void reverseString(char *s) {
if (s == NULL) return;
for (size_t i = 0, j = strlen(s); i + 1 < j; ++i, --j) {
char t = s[i];
s[i] = s[j - 1];
s[j - 1] = t;
}
}易错点
- 数组传参后
sizeof失真：void f(int a[10])的形参实际是int *，函数内sizeof(a)得到指针大小（8 字节）而不是数组大小。长度必须单独传；宏sizeof(a)/sizeof(a[0])只在实参那一层有效。 - 字符串缓冲区溢出：
strcpy/strcat/sprintf只认'\0'不认容量，目标太小时静默踩烂相邻内存（UB）。必须用snprintf(buf, sizeof buf, ...)或手动memcpy并自己保证容量（详见 B2）。 strlen写进循环条件：for (i = 0; i < strlen(s); ++i)每轮重算一次长度，整体退化为 O(n²)。先size_t n = strlen(s);缓存。atoi/atol无法报错："abc"返回 0、溢出是 UB，与真正的 0 无法区分。要用strtoll+endptr+ 可选errno判断。- 有符号 / 无符号混用导致下溢：
size_t n = strlen(s); for (int i = (int)n - 1; i >= 0; --i)在n == 0时先算出SIZE_MAX再截断，行为依赖实现；正确写法是for (size_t i = n; i-- > 0;)或显式用int转换并单独判空（推导见 B3）。 - 把二维数组强转成
int **：int a[3][4]是一片连续的 12 个int，int **是「指向指针的指针」，两者布局不同；强转后按a[i][j]解引用是 UB。应传int (*p)[4]或扁平化成一维加下标算术（详见 A2）。