用C++实现内存的分配和回收 使用最坏适应算法

最坏适应算法（Worst Fit Algorithm）是内存分配的一种策略，该算法将请求的内存块分配给最大的可用空闲区域。

C++通过malloc和free函数提供了动态内存分配和释放功能。下面是使用最坏适应算法实现内存的分配和回收的示例代码：

#include <iostream>
#include <cstdlib>
#include <cstring>

#define MEM_SIZE 1024 // 内存池大小

struct memory_block {
    int size; // 块大小
    bool free; // 是否空闲
    memory_block *next; // 下一个空闲块
};

memory_block *start = (memory_block*) malloc(MEM_SIZE); // 内存池起始地址

void initialize_memory() {
    start->size = MEM_SIZE - sizeof(memory_block); // 初始空闲块大小
    start->free = true; // 初始块为空闲
    start->next = NULL; // 初始块为最后一个块
}

void *worst_fit_allocate(int size) {
    memory_block *current = start;
    memory_block *worst_fit = NULL;
    while (current != NULL) {
        if (current->free && current->size >= size) { // 找到空闲块
            if (worst_fit == NULL || current->size > worst_fit->size) { // 找到最大的可用空闲区域
                worst_fit = current;
            }
        }
        current = current->next;
    }

    if (worst_fit == NULL) { // 没有找到合适的块
        return NULL;
    }

    if (worst_fit->size == size) { // 找到了刚好合适的块
        worst_fit->free = false;
        return (void*)(worst_fit + 1);
    } else { // 找到了大于所需的块，需要将多余的空间分裂成新的块
        memory_block *new_block = (memory_block*)((char*)worst_fit + sizeof(memory_block) + size);
        new_block->size = worst_fit->size - sizeof(memory_block) - size;
        new_block->free = true;
        new_block->next = worst_fit->next;
        worst_fit->size = size;
        worst_fit->free = false;
        worst_fit->next = new_block;
        return (void*)(worst_fit + 1);
    }
}

void worst_fit_free(void *ptr) {
    if (ptr == NULL) {
        return;
    }

    memory_block *current = (memory_block*)ptr - 1;
    current->free = true;

    // 合并连续的空闲块
    memory_block *prev = NULL, *next = start;
    while (next != NULL) {
        if (prev != NULL && prev->free && next->free) { // 合并前一个块和当前块
            prev->size += sizeof(memory_block) + next->size;
            prev->next = next->next;
            next = prev->next;
        } else { // 不需要合并，继续查找下一个块
            prev = next;
            next = next->next;
        }
    }
}

int main() {
    initialize_memory();

    // 分配内存
    int *a = (int*)worst_fit_allocate(100 * sizeof(int));
    int *b = (int*)worst_fit_allocate(200 * sizeof(int));
    int *c = (int*)worst_fit_allocate(50 * sizeof(int));
    int *d = (int*)worst_fit_allocate(300 * sizeof(int));

    // 输出分配的地址
    std::cout << "a: " << a << std::endl;
    std::cout << "b: " << b << std::endl;
    std::cout << "c: " << c << std::endl;
    std::cout << "d: " << d << std::endl;

    // 释放内存
    worst_fit_free(b);
    worst_fit_free(d);

    // 再次分配内存
    int *e = (int*)worst_fit_allocate(150 * sizeof(int));
    int *f = (int*)worst_fit_allocate(100 * sizeof(int));

    // 输出分配的地址
    std::cout << "e: " << e << std::endl;
    std::cout << "f: " << f << std::endl;

    free(start);

    return 0;
}

在该示例中，使用一个链表来管理内存块，每个内存块包含块大小、是否空闲和下一个空闲块的指针。initialize_memory函数初始化内存池，worst_fit_allocate函数使用最坏适应算法分配内存，worst_fit_free函数释放内存，并在必要时合并相邻的空闲块。