10905：游程编码

题目

实现 rle_encode 与 rle_decode。长度为 1 的游程直接写出字符，更长的游程写成十进制长度和字符。成功结果使用动态数组返回；非法输入、大小溢出或申请失败时返回 NULL。

解析

编码和解码都采用“两遍扫描”：

1. 第一遍验证输入并计算结果长度；
2. 只申请一次恰好够用的数组；
3. 第二遍写入结果。

解码时，把每个片段解析为 (count, character, next)。显式长度必须至少为 2；没有显式长度时数量为 1。计算十进制长度和累计输出长度时都要先检查溢出。

解析

#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    size_t count;
    unsigned char character;
    const char *next;
} ParsedRun;

static bool is_plain_character(unsigned char character) {
    static const char letters[] =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";

    return character != '\0'
        && (strchr(letters, (int)character) != NULL
            || isspace((int)character));
}

static size_t decimal_digits(size_t number) {
    size_t digits = 0;
    do {
        ++digits;
        number /= 10;
    } while (number != 0);
    return digits;
}

static size_t write_decimal(char *output, size_t number) {
    size_t digits = decimal_digits(number);

    for (size_t i = digits; i > 0; --i) {
        output[i - 1] = (char)('0' + number % 10);
        number /= 10;
    }
    return digits;
}

static bool parse_encoded_run(
    const char *cursor,
    ParsedRun *run
) {
    const unsigned char *scan =
        (const unsigned char *)cursor;
    bool has_count = false;
    size_t count = 0;

    while (*scan != '\0' && isdigit((int)*scan)) {
        size_t digit = (size_t)(*scan - (unsigned char)'0');
        has_count = true;

        if (count > (SIZE_MAX - digit) / 10) {
            return false;
        }
        count = count * 10 + digit;
        ++scan;
    }

    if (*scan == '\0' || !is_plain_character(*scan)) {
        return false;
    }

    if (has_count) {
        if (count < 2) {
            return false;
        }
    } else {
        count = 1;
    }

    run->count = count;
    run->character = *scan;
    run->next = (const char *)(scan + 1);
    return true;
}

char *rle_encode(const char *input) {
    if (input == NULL) {
        return NULL;
    }

    size_t input_length = strlen(input);
    size_t encoded_length = 0;
    size_t read = 0;

    while (read < input_length) {
        unsigned char character =
            (unsigned char)input[read];
        if (!is_plain_character(character)) {
            return NULL;
        }

        size_t count = 1;
        while (
            count < input_length - read
            && input[read + count] == input[read]
        ) {
            ++count;
        }

        size_t part_length =
            count == 1 ? 1 : decimal_digits(count) + 1;
        if (part_length > SIZE_MAX - 1 - encoded_length) {
            return NULL;
        }
        encoded_length += part_length;
        read += count;
    }

    char *output = malloc(encoded_length + 1);
    if (output == NULL) {
        return NULL;
    }

    read = 0;
    size_t write = 0;

    while (read < input_length) {
        size_t count = 1;
        while (
            count < input_length - read
            && input[read + count] == input[read]
        ) {
            ++count;
        }

        if (count > 1) {
            write += write_decimal(output + write, count);
        }

        output[write++] = input[read];
        read += count;
    }

    output[write] = '\0';
    return output;
}

char *rle_decode(const char *input) {
    if (input == NULL) {
        return NULL;
    }

    const char *cursor = input;
    size_t decoded_length = 0;

    while (*cursor != '\0') {
        ParsedRun run;
        if (!parse_encoded_run(cursor, &run)) {
            return NULL;
        }
        if (run.count > SIZE_MAX - 1 - decoded_length) {
            return NULL;
        }
        decoded_length += run.count;
        cursor = run.next;
    }

    char *output = malloc(decoded_length + 1);
    if (output == NULL) {
        return NULL;
    }

    cursor = input;
    size_t write = 0;

    while (*cursor != '\0') {
        ParsedRun run;
        if (!parse_encoded_run(cursor, &run)) {
            free(output);
            return NULL;
        }
        memset(output + write, run.character, run.count);
        write += run.count;
        cursor = run.next;
    }

    output[write] = '\0';
    return output;
}

来源与改编

题型改编自 Exercism C Track 的 Run-Length Encoding，采用 MIT 许可。本题重新定义了错误语义、文法和精确分配要求，完整说明见习题来源与许可。