30005：可替换的整数序列后端

题目

为同一个不透明整数序列接口分别编写动态数组和双向链表实现，使调用方只需在链接时选择实现文件。

解析

公开头文件只声明不完整类型和操作，不描述任何表示。两个实现文件各自补全 struct IntSequence，并导出完全相同的函数符号；因此它们不能同时参与一次链接，但任意一个都能配合同一份调用方代码。

动态数组在插入前完成扩容，申请失败时旧地址和内容仍然有效。双向链表在修改链接前完成结点申请，并根据下标选择从首端或尾端遍历。删除操作先保存结果，完成不会失败的结构修改后再写入调用方对象。

解析

公开头文件 int_sequence.h：

#ifndef INT_SEQUENCE_H
#define INT_SEQUENCE_H

#include <stddef.h>

typedef struct IntSequence IntSequence;

typedef enum {
    INT_SEQUENCE_OK,
    INT_SEQUENCE_INVALID,
    INT_SEQUENCE_RANGE,
    INT_SEQUENCE_OUT_OF_MEMORY
} IntSequenceResult;

IntSequence *int_sequence_create(void);
void int_sequence_destroy(IntSequence *sequence);
IntSequenceResult int_sequence_insert(
    IntSequence *sequence,
    size_t index,
    int value
);
IntSequenceResult int_sequence_erase(
    IntSequence *sequence,
    size_t index,
    int *out_value
);
IntSequenceResult int_sequence_get(
    const IntSequence *sequence,
    size_t index,
    int *out_value
);
size_t int_sequence_size(const IntSequence *sequence);

#endif

动态数组实现 int_sequence_array.c：

#include "int_sequence.h"

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

struct IntSequence {
    int *items;
    size_t size;
    size_t capacity;
};

IntSequence *int_sequence_create(void) {
    IntSequence *sequence = malloc(sizeof *sequence);
    if (sequence == NULL) {
        return NULL;
    }

    sequence->items = NULL;
    sequence->size = 0;
    sequence->capacity = 0;
    return sequence;
}

void int_sequence_destroy(IntSequence *sequence) {
    if (sequence == NULL) {
        return;
    }

    free(sequence->items);
    free(sequence);
}

static IntSequenceResult ensure_capacity(
    IntSequence *sequence
) {
    if (sequence->size < sequence->capacity) {
        return INT_SEQUENCE_OK;
    }

    size_t next_capacity;
    if (sequence->capacity == 0) {
        next_capacity = 8;
    } else {
        if (sequence->capacity > SIZE_MAX / 2) {
            return INT_SEQUENCE_OUT_OF_MEMORY;
        }
        next_capacity = sequence->capacity * 2;
    }

    if (next_capacity > SIZE_MAX / sizeof *sequence->items) {
        return INT_SEQUENCE_OUT_OF_MEMORY;
    }

    int *new_items = realloc(
        sequence->items,
        next_capacity * sizeof *new_items
    );
    if (new_items == NULL) {
        return INT_SEQUENCE_OUT_OF_MEMORY;
    }

    sequence->items = new_items;
    sequence->capacity = next_capacity;
    return INT_SEQUENCE_OK;
}

IntSequenceResult int_sequence_insert(
    IntSequence *sequence,
    size_t index,
    int value
) {
    if (sequence == NULL) {
        return INT_SEQUENCE_INVALID;
    }
    if (index > sequence->size) {
        return INT_SEQUENCE_RANGE;
    }
    if (sequence->size == SIZE_MAX) {
        return INT_SEQUENCE_OUT_OF_MEMORY;
    }

    IntSequenceResult result = ensure_capacity(sequence);
    if (result != INT_SEQUENCE_OK) {
        return result;
    }

    memmove(
        sequence->items + index + 1,
        sequence->items + index,
        (sequence->size - index) * sizeof *sequence->items
    );
    sequence->items[index] = value;
    ++sequence->size;
    return INT_SEQUENCE_OK;
}

IntSequenceResult int_sequence_erase(
    IntSequence *sequence,
    size_t index,
    int *out_value
) {
    if (sequence == NULL || out_value == NULL) {
        return INT_SEQUENCE_INVALID;
    }
    if (index >= sequence->size) {
        return INT_SEQUENCE_RANGE;
    }

    int value = sequence->items[index];
    memmove(
        sequence->items + index,
        sequence->items + index + 1,
        (sequence->size - index - 1)
            * sizeof *sequence->items
    );
    --sequence->size;
    *out_value = value;
    return INT_SEQUENCE_OK;
}

IntSequenceResult int_sequence_get(
    const IntSequence *sequence,
    size_t index,
    int *out_value
) {
    if (sequence == NULL || out_value == NULL) {
        return INT_SEQUENCE_INVALID;
    }
    if (index >= sequence->size) {
        return INT_SEQUENCE_RANGE;
    }

    int value = sequence->items[index];
    *out_value = value;
    return INT_SEQUENCE_OK;
}

size_t int_sequence_size(const IntSequence *sequence) {
    return sequence == NULL ? 0 : sequence->size;
}

双向链表实现 int_sequence_linked.c：

#include "int_sequence.h"

#include <stdint.h>
#include <stdlib.h>

typedef struct IntSequenceNode {
    int value;
    struct IntSequenceNode *previous;
    struct IntSequenceNode *next;
} IntSequenceNode;

struct IntSequence {
    IntSequenceNode *head;
    IntSequenceNode *tail;
    size_t size;
};

IntSequence *int_sequence_create(void) {
    IntSequence *sequence = malloc(sizeof *sequence);
    if (sequence == NULL) {
        return NULL;
    }

    sequence->head = NULL;
    sequence->tail = NULL;
    sequence->size = 0;
    return sequence;
}

void int_sequence_destroy(IntSequence *sequence) {
    if (sequence == NULL) {
        return;
    }

    IntSequenceNode *node = sequence->head;
    while (node != NULL) {
        IntSequenceNode *next = node->next;
        free(node);
        node = next;
    }
    free(sequence);
}

static IntSequenceNode *node_at(
    const IntSequence *sequence,
    size_t index
) {
    if (index < sequence->size / 2) {
        IntSequenceNode *node = sequence->head;
        for (size_t i = 0; i < index; ++i) {
            node = node->next;
        }
        return node;
    }

    IntSequenceNode *node = sequence->tail;
    for (size_t i = sequence->size - 1; i > index; --i) {
        node = node->previous;
    }
    return node;
}

IntSequenceResult int_sequence_insert(
    IntSequence *sequence,
    size_t index,
    int value
) {
    if (sequence == NULL) {
        return INT_SEQUENCE_INVALID;
    }
    if (index > sequence->size) {
        return INT_SEQUENCE_RANGE;
    }
    if (sequence->size == SIZE_MAX) {
        return INT_SEQUENCE_OUT_OF_MEMORY;
    }

    IntSequenceNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return INT_SEQUENCE_OUT_OF_MEMORY;
    }

    node->value = value;
    node->previous = NULL;
    node->next = NULL;

    if (sequence->size == 0) {
        sequence->head = node;
        sequence->tail = node;
    } else if (index == 0) {
        node->next = sequence->head;
        sequence->head->previous = node;
        sequence->head = node;
    } else if (index == sequence->size) {
        node->previous = sequence->tail;
        sequence->tail->next = node;
        sequence->tail = node;
    } else {
        IntSequenceNode *right = node_at(sequence, index);
        IntSequenceNode *left = right->previous;

        node->previous = left;
        node->next = right;
        left->next = node;
        right->previous = node;
    }

    ++sequence->size;
    return INT_SEQUENCE_OK;
}

IntSequenceResult int_sequence_erase(
    IntSequence *sequence,
    size_t index,
    int *out_value
) {
    if (sequence == NULL || out_value == NULL) {
        return INT_SEQUENCE_INVALID;
    }
    if (index >= sequence->size) {
        return INT_SEQUENCE_RANGE;
    }

    IntSequenceNode *node = node_at(sequence, index);
    int value = node->value;

    if (node->previous == NULL) {
        sequence->head = node->next;
    } else {
        node->previous->next = node->next;
    }

    if (node->next == NULL) {
        sequence->tail = node->previous;
    } else {
        node->next->previous = node->previous;
    }

    free(node);
    --sequence->size;
    *out_value = value;
    return INT_SEQUENCE_OK;
}

IntSequenceResult int_sequence_get(
    const IntSequence *sequence,
    size_t index,
    int *out_value
) {
    if (sequence == NULL || out_value == NULL) {
        return INT_SEQUENCE_INVALID;
    }
    if (index >= sequence->size) {
        return INT_SEQUENCE_RANGE;
    }

    int value = node_at(sequence, index)->value;
    *out_value = value;
    return INT_SEQUENCE_OK;
}

size_t int_sequence_size(const IntSequence *sequence) {
    return sequence == NULL ? 0 : sequence->size;
}