面试题：C语言指针在内存管理优化中的深度应用

数据结构

内存块结构体：
```
typedef struct MemoryBlock {
    struct MemoryBlock *next;
    size_t size;
    int is_free;
} MemoryBlock;
```
- next 指针用于将内存块链接成链表。
- size 记录该内存块的大小。
- is_free 标识该内存块是否已被分配使用。

内存池结构体：

typedef struct MemoryPool {
    MemoryBlock *head;
} MemoryPool;

head 指向内存池的第一个内存块。

算法

初始化内存池：

首先，在程序启动时，根据预计的内存使用情况，分配一块较大的连续内存空间作为内存池。
将这块大内存按照一定规则划分为多个小的内存块，并初始化每个内存块的 next、size 和 is_free 字段。例如，可以将内存块大小设置为固定值，这样便于管理。所有内存块初始时 is_free 设为 1（表示空闲），并通过 next 指针链接成一个单向链表。

MemoryPool* createMemoryPool(size_t totalSize, size_t blockSize) {
    MemoryPool *pool = (MemoryPool*)malloc(sizeof(MemoryPool));
    if (!pool) {
        return NULL;
    }
    size_t numBlocks = totalSize / blockSize;
    MemoryBlock *current = (MemoryBlock*)malloc(totalSize);
    if (!current) {
        free(pool);
        return NULL;
    }
    pool->head = current;
    for (size_t i = 0; i < numBlocks - 1; i++) {
        current->size = blockSize;
        current->is_free = 1;
        current->next = (MemoryBlock*)((char*)current + blockSize);
        current = current->next;
    }
    current->size = blockSize;
    current->is_free = 1;
    current->next = NULL;
    return pool;
}

内存分配：

遍历内存块链表，寻找第一个 is_free 为 1 且 size 满足需求的内存块。
如果找到合适的内存块，将其 is_free 设为 0，表示已分配，并返回该内存块的地址。

void* allocateMemory(MemoryPool *pool, size_t size) {
    MemoryBlock *current = pool->head;
    while (current) {
        if (current->is_free && current->size >= size) {
            current->is_free = 0;
            return current;
        }
        current = current->next;
    }
    return NULL; // 没有找到合适的内存块
}

内存回收：

当需要回收内存时，根据释放的内存地址找到对应的内存块。
将该内存块的 is_free 设为 1，表示空闲。
可以进一步合并相邻的空闲内存块，以减少碎片化。遍历链表，检查当前内存块的下一个内存块是否也是空闲的，如果是，则合并它们。

void freeMemory(MemoryPool *pool, void *ptr) {
    MemoryBlock *current = pool->head;
    while (current) {
        if (current == ptr) {
            current->is_free = 1;
            if (current->next && current->next->is_free) {
                current->size += current->next->size;
                current->next = current->next->next;
            }
            break;
        }
        current = current->next;
    }
}

指针操作实现

链表链接：通过 MemoryBlock 结构体中的 next 指针将各个内存块链接成链表，在初始化内存池时，使用指针算术运算来确定每个内存块的位置，并设置 next 指针。例如 current->next = (MemoryBlock*)((char*)current + blockSize);
内存分配与回收：在分配内存时，通过遍历链表指针 next 找到合适的内存块，并返回其指针。回收内存时，通过比较指针找到对应的内存块，并进行标记和合并操作。

时间复杂度分析

初始化内存池：时间复杂度为 $O(n)$，其中 $n$ 是内存池中内存块的数量。因为需要遍历所有内存块进行初始化。
内存分配：最坏情况下时间复杂度为 $O(n)$，需要遍历整个链表才能找到合适的内存块。如果链表有序（例如按大小排序），可以使用二分查找优化，时间复杂度降为 $O(\log n)$。
内存回收：时间复杂度为 $O(n)$，需要遍历链表找到要回收的内存块。合并相邻空闲块时，最坏情况也是 $O(n)$，但平均情况下会接近 $O(1)$，因为通常相邻空闲块的情况不会每次都遍历整个链表。

空间复杂度分析

除了程序本身需要的内存外，额外的空间复杂度主要来自内存池结构。内存池结构体 MemoryPool 占用固定大小的空间，而内存块链表占用的空间取决于内存池的大小和内存块的数量。总体空间复杂度为 $O(n)$，其中 $n$ 是内存池中内存块的数量。这里不考虑为实现更复杂优化（如哈希表加速查找等）而增加的额外空间。

星途面试题库

面试题：C语言指针在内存管理优化中的深度应用

知识考点

面试题答案

数据结构

算法

指针操作实现

时间复杂度分析

空间复杂度分析