# C 语言常用算法模板

> [!note]
> 以下示例按 C11 编写，强调边界检查和可移植性。知识解释见 [[计算机系/CLanguage/C语言题目知识点梳理.md]]。

## 1. 随机四则运算

```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
    srand((unsigned)time(NULL));

    int a = rand() % 20;
    int b = rand() % 20;
    int op = rand() % 4;

    switch (op) {
    case 0:
        printf("%d + %d = %d\n", a, b, a + b);
        break;
    case 1:
        printf("%d - %d = %d\n", a, b, a - b);
        break;
    case 2:
        printf("%d * %d = %d\n", a, b, a * b);
        break;
    case 3:
        if (b == 0) {
            b = 1 + rand() % 19;
        }
        printf("%d / %d = %.2f\n", a, b, (double)a / b);
        break;
    }

    return 0;
}
```

## 2. 最大公约数与分数约分

```c
#include <stdio.h>

long long gcd(long long a, long long b)
{
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        long long remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

int main(void)
{
    long long numerator, denominator;
    if (scanf("%lld/%lld", &numerator, &denominator) != 2 || denominator == 0) {
        fprintf(stderr, "Invalid fraction.\n");
        return 1;
    }

    long long divisor = gcd(numerator, denominator);
    if (divisor != 0) {
        numerator /= divisor;
        denominator /= divisor;
    }
    if (denominator < 0) {
        numerator = -numerator;
        denominator = -denominator;
    }

    printf("%lld/%lld\n", numerator, denominator);
    return 0;
}
```

递归版本的核心函数为：

```c
long long gcd_recursive(long long a, long long b)
{
    return b == 0 ? a : gcd_recursive(b, a % b);
}
```

## 3. 杨辉三角

```c
#include <stdio.h>

#define MAX_ROWS 20

int main(void)
{
    unsigned long long triangle[MAX_ROWS][MAX_ROWS] = {0};
    int n;

    if (scanf("%d", &n) != 1 || n < 1 || n > MAX_ROWS) {
        fprintf(stderr, "n must be between 1 and %d.\n", MAX_ROWS);
        return 1;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j == 0 || j == i) {
                triangle[i][j] = 1;
            } else {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
            printf("%6llu", triangle[i][j]);
        }
        putchar('\n');
    }

    return 0;
}
```

## 4. 三种基础排序

```c
#include <stddef.h>

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

void bubble_sort(int a[], size_t n)
{
    for (size_t end = n; end > 1; --end) {
        int swapped = 0;
        for (size_t i = 0; i + 1 < end; ++i) {
            if (a[i] > a[i + 1]) {
                swap(&a[i], &a[i + 1]);
                swapped = 1;
            }
        }
        if (!swapped) return;
    }
}

void selection_sort(int a[], size_t n)
{
    for (size_t i = 0; i < n; ++i) {
        size_t min_index = i;
        for (size_t j = i + 1; j < n; ++j) {
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            swap(&a[i], &a[min_index]);
        }
    }
}

void insertion_sort(int a[], size_t n)
{
    for (size_t i = 1; i < n; ++i) {
        int key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = key;
    }
}
```

## 5. 顺序查找与二分查找

```c
#include <stddef.h>

long linear_search(const int a[], size_t n, int target)
{
    for (size_t i = 0; i < n; ++i) {
        if (a[i] == target) return (long)i;
    }
    return -1;
}

long binary_search(const int a[], size_t n, int target)
{
    size_t left = 0;
    size_t right = n;  // 左闭右开区间 [left, right)

    while (left < right) {
        size_t mid = left + (right - left) / 2;
        if (a[mid] == target) return (long)mid;
        if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return -1;
}
```

> [!warning]
> `binary_search` 只适用于已经按升序排列的数组。

## 6. 字符串转大写

```c
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    char line[81];
    if (fgets(line, sizeof line, stdin) == NULL) {
        return 1;
    }

    line[strcspn(line, "\n")] = '\0';
    for (size_t i = 0; line[i] != '\0'; ++i) {
        line[i] = (char)toupper((unsigned char)line[i]);
    }

    puts(line);
    return 0;
}
```

## 7. 密码合法性检查

规则：长度不少于 6，只允许字母、数字和点号，并且必须同时包含字母与数字。

```c
#include <ctype.h>
#include <stdio.h>
#include <string.h>

void check_password(const char *password)
{
    if (strlen(password) < 6) {
        puts("Your password is tai duan le.");
        return;
    }

    int has_letter = 0;
    int has_digit = 0;

    for (size_t i = 0; password[i] != '\0'; ++i) {
        unsigned char ch = (unsigned char)password[i];
        if (isalpha(ch)) {
            has_letter = 1;
        } else if (isdigit(ch)) {
            has_digit = 1;
        } else if (ch != '.') {
            puts("Your password is tai luan le.");
            return;
        }
    }

    if (!has_letter) {
        puts("Your password needs zi mu.");
    } else if (!has_digit) {
        puts("Your password needs shu zi.");
    } else {
        puts("Your password is wan mei.");
    }
}

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n < 0) return 1;

    for (int i = 0; i < n; ++i) {
        char password[81];
        if (scanf("%80s", password) != 1) return 1;
        check_password(password);
    }
    return 0;
}
```

## 8. 指针遍历数组求和

```c
#include <stddef.h>

long long array_sum(const int *a, size_t n)
{
    long long total = 0;
    for (const int *p = a; p < a + n; ++p) {
        total += *p;
    }
    return total;
}
```

## 9. 结构体的值传递与指针传递

```c
#include <stdio.h>

struct Student {
    int id;
    char name[20];
};

void change_copy(struct Student student)
{
    ++student.id;  // 只修改副本
}

void change_original(struct Student *student)
{
    if (student != NULL) {
        ++student->id;  // 修改原对象
    }
}

int main(void)
{
    struct Student student = {20120114, "LiHong"};
    change_copy(student);
    printf("%d\n", student.id);      // 仍为 20120114
    change_original(&student);
    printf("%d\n", student.id);      // 变为 20120115
    return 0;
}
```

## 10. 多个有理数的平均值

```c
#include <stdio.h>

struct Rational {
    long long numerator;
    long long denominator;
};

long long gcd(long long a, long long b)
{
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        long long remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

void normalize(struct Rational *value)
{
    if (value->denominator < 0) {
        value->numerator = -value->numerator;
        value->denominator = -value->denominator;
    }
    long long divisor = gcd(value->numerator, value->denominator);
    if (divisor != 0) {
        value->numerator /= divisor;
        value->denominator /= divisor;
    }
}

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 1;

    struct Rational sum = {0, 1};
    for (int i = 0; i < n; ++i) {
        struct Rational current;
        if (scanf("%lld/%lld", &current.numerator, &current.denominator) != 2 ||
            current.denominator == 0) {
            fprintf(stderr, "Invalid fraction.\n");
            return 1;
        }

        sum.numerator = sum.numerator * current.denominator
                      + current.numerator * sum.denominator;
        sum.denominator *= current.denominator;
        normalize(&sum);
    }

    sum.denominator *= n;
    normalize(&sum);

    if (sum.denominator == 1) {
        printf("%lld\n", sum.numerator);
    } else {
        printf("%lld/%lld\n", sum.numerator, sum.denominator);
    }
    return 0;
}
```

> [!warning]
> 即使使用 `long long`，连续通分仍可能溢出。若题目数据很大，需要在乘法前交叉约分，或使用大整数库。

## 11. 动态数组与插入排序

```c
#include <stdio.h>
#include <stdlib.h>

void insertion_sort(int a[], size_t n)
{
    for (size_t i = 1; i < n; ++i) {
        int key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = key;
    }
}

int main(void)
{
    size_t n;
    if (scanf("%zu", &n) != 1 || n == 0) return 1;

    int *numbers = malloc(n * sizeof *numbers);
    if (numbers == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        return 1;
    }

    for (size_t i = 0; i < n; ++i) {
        if (scanf("%d", &numbers[i]) != 1) {
            free(numbers);
            return 1;
        }
    }

    insertion_sort(numbers, n);
    for (size_t i = 0; i < n; ++i) {
        printf(i + 1 == n ? "%d\n" : "%d ", numbers[i]);
    }

    free(numbers);
    return 0;
}
```

## 12. 文本文件复制

```c
#include <stdio.h>

int main(void)
{
    FILE *source = fopen("D:/source.txt", "r");
    if (source == NULL) {
        perror("Cannot open source file");
        return 1;
    }

    FILE *destination = fopen("D:/destination.txt", "w");
    if (destination == NULL) {
        perror("Cannot open destination file");
        fclose(source);
        return 1;
    }

    char buffer[1024];
    while (fgets(buffer, sizeof buffer, source) != NULL) {
        if (fputs(buffer, destination) == EOF) {
            perror("Write failed");
            fclose(source);
            fclose(destination);
            return 1;
        }
    }

    if (ferror(source)) {
        perror("Read failed");
    }

    fclose(source);
    fclose(destination);
    return 0;
}
```