面试题：C语言结构体泛型编程的内存管理与优化

1. 内存管理

内存分配

动态数组初始化：在创建动态数组时，需要分配足够的内存来存储数组元素和元数据（如当前元素数量、数组容量）。可以使用malloc函数分配内存。

typedef struct {
    void **data;
    size_t size;
    size_t capacity;
} DynamicArray;

DynamicArray* createDynamicArray(size_t initialCapacity) {
    DynamicArray *arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    if (arr == NULL) {
        return NULL;
    }
    arr->data = (void**)malloc(initialCapacity * sizeof(void*));
    if (arr->data == NULL) {
        free(arr);
        return NULL;
    }
    arr->size = 0;
    arr->capacity = initialCapacity;
    return arr;
}

内存扩展：当动态数组的元素数量达到其容量时，需要扩展内存。通常采用成倍增长的方式，以减少频繁内存分配的开销。

void resize(DynamicArray *arr) {
    arr->capacity *= 2;
    arr->data = (void**)realloc(arr->data, arr->capacity * sizeof(void*));
    if (arr->data == NULL) {
        // 处理内存分配失败
        perror("realloc");
        exit(EXIT_FAILURE);
    }
}

内存释放

释放动态数组：在动态数组不再使用时，需要释放分配的内存。不仅要释放存储元素的内存，还要释放动态数组结构本身的内存。

void freeDynamicArray(DynamicArray *arr) {
    // 释放每个元素的内存（如果需要）
    for (size_t i = 0; i < arr->size; ++i) {
        free(arr->data[i]);
    }
    free(arr->data);
    free(arr);
}

防止内存泄漏

异常处理：在内存分配失败时，要确保已经分配的内存被正确释放，防止内存泄漏。如在createDynamicArray函数中，当arr->data分配失败时，先释放arr。
内存跟踪：可以添加一些调试代码来跟踪内存分配和释放，确保所有分配的内存都被释放。例如，使用计数器记录分配和释放的次数，并在程序结束时检查计数器是否为0。

2. 性能优化（频繁插入和删除操作）

实现思路

减少内存重分配：如上述内存扩展策略，采用成倍增长方式减少内存重分配次数。
使用链表结构辅助：对于频繁的插入和删除操作，可以考虑结合链表结构。例如，在动态数组的每个元素位置存储一个链表节点指针，这样插入和删除操作可以在链表上高效进行，而动态数组主要负责管理整体的内存布局。
批量操作优化：如果有批量插入或删除操作，可以先进行预计算，一次性分配足够的内存或调整容量，避免多次小操作导致频繁内存分配。

关键代码片段（结合链表优化插入删除）

typedef struct Node {
    void *value;
    struct Node *next;
} Node;

typedef struct {
    Node **data;
    size_t size;
    size_t capacity;
} DynamicArrayWithList;

DynamicArrayWithList* createDynamicArrayWithList(size_t initialCapacity) {
    DynamicArrayWithList *arr = (DynamicArrayWithList*)malloc(sizeof(DynamicArrayWithList));
    if (arr == NULL) {
        return NULL;
    }
    arr->data = (Node**)malloc(initialCapacity * sizeof(Node*));
    if (arr->data == NULL) {
        free(arr);
        return NULL;
    }
    for (size_t i = 0; i < initialCapacity; ++i) {
        arr->data[i] = NULL;
    }
    arr->size = 0;
    arr->capacity = initialCapacity;
    return arr;
}

void insert(DynamicArrayWithList *arr, void *value) {
    if (arr->size >= arr->capacity) {
        resize(arr);
    }
    size_t index = arr->size % arr->capacity;
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = arr->data[index];
    arr->data[index] = newNode;
    arr->size++;
}

void delete(DynamicArrayWithList *arr, void *value) {
    for (size_t i = 0; i < arr->capacity; ++i) {
        Node *prev = NULL;
        Node *curr = arr->data[i];
        while (curr != NULL) {
            if (curr->value == value) {
                if (prev == NULL) {
                    arr->data[i] = curr->next;
                } else {
                    prev->next = curr->next;
                }
                free(curr);
                arr->size--;
                return;
            }
            prev = curr;
            curr = curr->next;
        }
    }
}

星途面试题库

面试题：C语言结构体泛型编程的内存管理与优化

知识考点

面试题答案

1. 内存管理

内存分配

内存释放

防止内存泄漏

2. 性能优化（频繁插入和删除操作）

实现思路

关键代码片段（结合链表优化插入删除）