面试题：C语言结构体动态内存分配的复杂场景优化

内存分配算法选择

使用定制内存分配器：
- 标准的C库内存分配函数（如malloc和free）在处理频繁的小块内存分配和释放时，容易产生内存碎片。可以考虑使用定制的内存分配器，例如基于对象池（Object Pool）的分配器。
- 原理是预先分配一块较大的内存块，将其分割成固定大小的小块，这些小块用于分配给特定类型的对象（如这里的单词、句子、段落和文档结构体）。当对象被销毁时，对应的小块内存被返回给对象池，而不是归还给系统堆，这样可以减少内存碎片。
伙伴系统（Buddy System）：
- 伙伴系统是一种内存分配算法，适用于管理大块内存。它将内存空间划分为不同大小的块，当需要分配内存时，从合适大小的块中选取，如果没有合适大小的块，则将大的块分裂成两个“伙伴”块。当块被释放时，系统尝试将相邻的空闲伙伴块合并成更大的块，从而减少内存碎片。
- 在我们的项目中，可以将整个堆空间看作一个大的块，根据需求分裂和合并，为文档、段落、句子和单词分配内存。

结构体设计优化

减少结构体成员的对齐要求：
- C语言中结构体成员会按照一定的对齐规则进行内存布局，这可能导致一些空间浪费。尽量将相同数据类型的成员放在一起，以减少结构体内部的填充字节。例如，对于句子结构体中的字符指针数组，可以将其声明为char* words[max_words_per_sentence]，而不是分散地声明多个指针成员。
考虑结构体的内存布局：
- 对于文档、段落和句子结构体，可以采用嵌套结构体数组的方式，但要注意结构体数组的大小。如果每个文档的段落数量、每个段落的句子数量相对固定，可以将这些数组的大小设置为合适的固定值，避免频繁的动态内存分配。例如：

#define MAX_PARAGRAPHS 100
#define MAX_SENTENCES_PER_PARAGRAPH 50
#define MAX_WORDS_PER_SENTENCE 20

typedef struct {
    char** words;
    int word_count;
} Sentence;

typedef struct {
    Sentence sentences[MAX_SENTENCES_PER_PARAGRAPH];
    int sentence_count;
} Paragraph;

typedef struct {
    Paragraph paragraphs[MAX_PARAGRAPHS];
    int paragraph_count;
} Document;

延迟内存分配：
- 对于一些不太常用的结构体成员，可以延迟其内存分配。例如，在文档结构体中，如果有一些元数据字段，只有在特定操作时才需要动态分配内存，可以在需要时再进行分配，而不是在创建文档对象时就分配。

关键代码示例

基于对象池的单词内存分配示例：

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

#define MAX_WORDS 1000
#define WORD_POOL_SIZE 100

typedef struct {
    char data[50]; // 假设单词最大长度为50
    int in_use;
} Word;

Word word_pool[WORD_POOL_SIZE];

char* allocate_word(const char* str) {
    for (int i = 0; i < WORD_POOL_SIZE; i++) {
        if (!word_pool[i].in_use) {
            word_pool[i].in_use = 1;
            strcpy(word_pool[i].data, str);
            return word_pool[i].data;
        }
    }
    return NULL;
}

void free_word(char* word) {
    for (int i = 0; i < WORD_POOL_SIZE; i++) {
        if (word_pool[i].data == word) {
            word_pool[i].in_use = 0;
            break;
        }
    }
}

文档创建和销毁示例：

Document* create_document() {
    Document* doc = (Document*)malloc(sizeof(Document));
    if (!doc) {
        return NULL;
    }
    doc->paragraph_count = 0;
    return doc;
}

void destroy_document(Document* doc) {
    for (int i = 0; i < doc->paragraph_count; i++) {
        Paragraph* para = &doc->paragraphs[i];
        for (int j = 0; j < para->sentence_count; j++) {
            Sentence* sent = &para->sentences[j];
            for (int k = 0; k < sent->word_count; k++) {
                free_word(sent->words[k]);
            }
        }
    }
    free(doc);
}

星途面试题库

面试题：C语言结构体动态内存分配的复杂场景优化

知识考点

面试题答案

内存分配算法选择

结构体设计优化

关键代码示例