空闲链表法的代码

空闲链表法是一种内存分配算法，它将可用的内存块组织成一个链表，每个节点代表一个可用的内存块。下面是一个简单的C语言实现：

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

// 内存块结构体
typedef struct Block {
    int size;           // 内存块大小
    struct Block* next; // 指向下一个内存块的指针
} Block;

// 内存块链表头指针
Block* head = NULL;

// 初始化内存块链表
void init() {
    head = (Block*)malloc(sizeof(Block));
    head->size = 0;
    head->next = NULL;
}

// 向内存块链表中添加一个新的内存块
void add(int size) {
    Block* newBlock = (Block*)malloc(sizeof(Block));
    newBlock->size = size;
    newBlock->next = head->next;
    head->next = newBlock;
}

// 从内存块链表中删除一个指定大小的内存块
void removeBlock(int size) {
    Block* p = head;
    while (p->next != NULL && p->next->size != size) {
        p = p->next;
    }
    if (p->next != NULL) {
        Block* temp = p->next;
        p->next = temp->next;
        free(temp);
    }
}

// 分配指定大小的内存块
void* allocate(int size) {
    Block* p = head;
    while (p->next != NULL && p->next->size < size) {
        p = p->next;
    }
    if (p->next == NULL) {
        return NULL;
    } else {
        void* ptr = (void*)(p->next + 1);
        p->next->size -= size;
        if (p->next->size == 0) {
            removeBlock(p->next->size);
        }
        return ptr;
    }
}

// 释放指定指针所指向的内存块
void freeMemory(void* ptr, int size) {
    Block* p = (Block*)ptr - 1;
    p->size = size;
    add(size);
}

int main() {
    init();
    add(100);
    add(50);
    add(200);
    void* ptr1 = allocate(30);
    void* ptr2 = allocate(80);
    void* ptr3 = allocate(150);
    printf("ptr1 = %p\n", ptr1);
    printf("ptr2 = %p\n", ptr2);
    printf("ptr3 = %p\n", ptr3);
    freeMemory(ptr2, 80);
    void* ptr4 = allocate(70);
    void* ptr5 = allocate(100);
    printf("ptr4 = %p\n", ptr4);
    printf("ptr5 = %p\n", ptr5);
    return 0;
}

在上面的代码中，`Block`结构体表示内存块，包括一个大小和一个指向下一个内存块的指针。`head`指向内存块链表的头节点，初始化为空节点。`init()`函数用于初始化内存块链表。`add(size)`函数用于向内存块链表中添加一个新的内存块，大小为`size`。`removeBlock(size)`函数用于从内存块链表中删除一个指定大小的内存块。`allocate(size)`函数用于分配指定大小的内存块。它遍历内存块链表，找到第一个可用的内存块，将其分配出去，并更新剩余空间。`freeMemory(ptr, size)`函数用于释放指定指针所指向的内存块。它将该内存块添加到内存块链表中，并合并相邻的空闲内存块。在`main()`函数中，我们初始化内存块链表，并向其中添加了三个内存块。然后，我们分别分配了三个内存块，并输出它们的指针。接着，我们释放了第二个内存块，并重新分配了两个内存块，并输出它们的指针。最后，我们释放了所有内存块。