30002：顺序表区间插入与删除

题目

为动态整数顺序表实现区间插入和区间删除，同时保持元素次序、表示不变式和失败时状态保证。

解析

顺序表始终满足：

size <= capacity
capacity == 0 当且仅当 items == NULL
capacity <= SIZE_MAX / sizeof(int)

插入区间时，先扩容，再用 memmove 把后缀整体向右移动，最后用 memcpy 写入不重叠的来源区间。删除时则把删除区间之后的后缀整体向左移动。

所有可能失败的检查都在移动元素之前完成。扩容失败时 realloc 保留原存储，因此返回 false 不会破坏原顺序表。

解析

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

typedef struct {
    int *items;
    size_t size;
    size_t capacity;
} IntList;

static bool int_list_valid(const IntList *list) {
    if (list == NULL || list->size > list->capacity) {
        return false;
    }
    if ((list->capacity == 0) != (list->items == NULL)) {
        return false;
    }
    return list->capacity <= SIZE_MAX / sizeof *list->items;
}

void int_list_init(IntList *list) {
    if (list == NULL) {
        return;
    }
    list->items = NULL;
    list->size = 0;
    list->capacity = 0;
}

void int_list_destroy(IntList *list) {
    if (list == NULL) {
        return;
    }
    free(list->items);
    int_list_init(list);
}

static bool int_list_reserve(
    IntList *list,
    size_t minimum
) {
    size_t maximum = SIZE_MAX / sizeof *list->items;
    if (minimum > maximum) {
        return false;
    }
    if (minimum <= list->capacity) {
        return true;
    }

    size_t next = list->capacity == 0
        ? (maximum < 8 ? maximum : 8)
        : list->capacity;

    while (next < minimum) {
        if (next > maximum / 2) {
            next = maximum;
        } else {
            next *= 2;
        }
    }

    int *replacement = realloc(
        list->items,
        next * sizeof *replacement
    );
    if (replacement == NULL) {
        return false;
    }

    list->items = replacement;
    list->capacity = next;
    return true;
}

bool int_list_insert_range(
    IntList *list,
    size_t index,
    const int *source,
    size_t count
) {
    if (!int_list_valid(list) || index > list->size) {
        return false;
    }
    if (count == 0) {
        return true;
    }
    if (source == NULL || count > SIZE_MAX - list->size) {
        return false;
    }

    size_t new_size = list->size + count;
    if (!int_list_reserve(list, new_size)) {
        return false;
    }

    size_t tail_count = list->size - index;
    memmove(
        list->items + index + count,
        list->items + index,
        tail_count * sizeof *list->items
    );
    memcpy(
        list->items + index,
        source,
        count * sizeof *list->items
    );
    list->size = new_size;
    return true;
}

bool int_list_erase_range(
    IntList *list,
    size_t index,
    size_t count
) {
    if (!int_list_valid(list) || index > list->size) {
        return false;
    }
    if (count > list->size - index) {
        return false;
    }
    if (count == 0) {
        return true;
    }

    size_t after = index + count;
    size_t tail_count = list->size - after;
    memmove(
        list->items + index,
        list->items + after,
        tail_count * sizeof *list->items
    );
    list->size -= count;
    return true;
}

来源与改编

题型借鉴 Pat Morin 的 Open Data Structures 中数组表的增长与区间搬移思路，原作采用 CC BY 2.5 Canada。本题改写为 C 接口，并增加重叠规则、大小溢出和失败保证；完整记录见习题来源与许可。