常用的C语言模板

这篇记录一些算法竞赛和刷题中常用的 C 语言手写模板，包括哈希表、堆、快速排序和二分查找。方便之后随时查阅和复制。

1. 手写哈希表

使用「开放寻址法」实现的整数哈希表，适合整数键值对的快速存取。

#include <stdio.h>
#include <string.h>

#define N 200003    // 通常取大于数据量 2~3 倍的一个质数
#define NUL 0x3f3f3f3f  // 空标记（需保证不会与实际键冲突）

int h[N];

int find(int x) {
    int k = (x % N + N) % N;  // 处理负数
    while (h[k] != NUL && h[k] != x) {
        k++;
        if (k == N) k = 0;
    }
    return k;
}

void insert(int x) {
    int k = find(x);
    h[k] = x;
}

int contains(int x) {
    int k = find(x);
    return h[k] == x;  // 存在返回1，否则返回0
}

int main() {
    memset(h, 0x3f, sizeof(h));
    insert(10);
    insert(-3);
    printf("%d\n", contains(10));  // 1
    printf("%d\n", contains(5));   // 0
    return 0;
}

2. 手写堆（小根堆）

数组实现的小根堆，支持插入和弹出最小值。

#include <stdio.h>

#define MAXN 100010

int heap[MAXN], sz;

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

void up(int u) {
    while (u / 2 && heap[u / 2] > heap[u]) {
        swap(&heap[u / 2], &heap[u]);
        u /= 2;
    }
}

void down(int u) {
    int t = u;
    if (u * 2 <= sz && heap[u * 2] < heap[t]) t = u * 2;
    if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
    if (t != u) {
        swap(&heap[t], &heap[u]);
        down(t);
    }
}

void push(int x) {
    heap[++sz] = x;
    up(sz);
}

int pop() {          // 弹出并返回堆顶（最小值）
    int top = heap[1];
    heap[1] = heap[sz--];
    down(1);
    return top;
}

int main() {
    push(5); push(3); push(8);
    printf("%d\n", pop());  // 3
    printf("%d\n", pop());  // 5
    return 0;
}

3. 快速排序

标准快排模板，以中间元素为基准，hoare 风格分区。

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[(l + r) >> 1];  // 基准取中间值
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(&q[i], &q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main() {
    int q[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = sizeof(q) / sizeof(q[0]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", q[i]);
    return 0;
}

4. 二分查找

两种常用模板：查找左边界（第一个大于等于 target 的位置）和右边界（最后一个小于等于 target 的位置）。

#include <stdio.h>

// 查找左边界：第一个 >= x 的位置
int lower_bound(int a[], int n, int x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 查找右边界：最后一个 <= x 的位置
int upper_bound(int a[], int n, int x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;  // 注意 +1 避免死循环
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main() {
    int a[] = {1, 2, 2, 3, 4, 5, 5, 6};
    int n = 8;
    printf("%d\n", lower_bound(a, n, 2));  // 1
    printf("%d\n", upper_bound(a, n, 2));  // 2
    return 0;
}

以上就是目前整理的几个常用模板。