用单链表实现内存分配与回收

单链表可以用来实现内存分配与回收。可以定义一个内存块的结构体，包含该块内存的大小和指向下一个内存块的指针。初始时，可以定义一个头指针指向整个链表的头部。当需要分配内存时，可以遍历链表，查找第一个大小足够的内存块，并将其分配出去。如果链表中没有合适的内存块，则可以申请新的内存块并将其加入到链表中。当需要释放内存时，可以将该内存块加入到链表的头部，这样可以方便地重复使用该内存块。具体实现可以参考下面的代码：

#include <iostream>
using namespace std;

// 定义内存块结构体
struct Block {
    int size;
    Block* next;
};

Block* head = NULL;  // 头指针

// 分配内存
void* allocate(int size) {
    // 遍历链表
    Block* p = head;
    Block* prev = NULL;
    while (p) {
        if (p->size >= size) {
            // 找到合适的内存块，分配出去
            void* ptr = p + 1;
            if (p->size == size) {
                // 如果刚好相等，直接删除该内存块
                if (prev) {
                    prev->next = p->next;
                } else {
                    head = p->next;
                }
                delete p;
            } else {
                // 如果大于要求大小，分割出一块给用户
                Block* q = new Block;
                q->size = size;
                q->next = NULL;
                memcpy(q + 1, ptr, size);
                if (prev) {
                    prev->next = q;
                } else {
                    head = q;
                }
                // 剩下的一块仍然加入链表中
                p->size -= size;
                memcpy(ptr, (char*)ptr + size, p->size);
            }
            return ptr;
        }
        prev = p;
        p = p->next;
    }
    // 如果链表中没有合适的内存块，申请新的内存块
    Block* q = new Block;
    q->size = size;
    q->next = head;
    head = q;
    return q + 1;
}

// 释放内存
void deallocate(void* ptr) {
    Block* p = (Block*)ptr - 1;
    p->next = head;
    head = p;
}

int main() {
    // 分配内存
    int* p = (int*)allocate(sizeof(int));
    *p = 123;
    cout << *p << endl;
    // 释放内存
    deallocate(p);
    return 0;
}