C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloca（）和回收过程free（）。其中空闲分区通过空闲分区链来管理；在进行内存分配时，系统优先是有空闲分区低端的空间,假设初始状态下的可用的内存空间为640KB，自行设计作业的请求序列,分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况的代码

首次适应算法的代码实现：

#include <stdio.h>

// 定义内存块结构体
typedef struct mem_block {
    int start_addr;  // 起始地址
    int size;        // 大小
    struct mem_block *next;  // 下一个空闲内存块
} MemBlock;

MemBlock *free_head;  // 空闲分区链表头指针

// 初始化空闲分区链表
void init_free_list() {
    free_head = (MemBlock *)malloc(sizeof(MemBlock));
    free_head->start_addr = 0;
    free_head->size = 640;
    free_head->next = NULL;
}

// 显示空闲分区链表状态
void display_free_list() {
    MemBlock *p = free_head;
    printf("空闲内存分区链表：\n");
    while (p != NULL) {
        printf("起始地址：%d，大小：%d\n", p->start_addr, p->size);
        p = p->next;
    }
}

// 首次适应算法的内存分配函数
int first_fit_alloc(int size) {
    MemBlock *p = free_head;
    MemBlock *pre = NULL;

    // 遍历空闲分区链表，找到第一个符合要求的分区
    while (p != NULL) {
        if (p->size >= size) {
            break;
        }
        pre = p;
        p = p->next;
    }

    // 没有找到符合要求的内存块
    if (p == NULL) {
        printf("没有足够的内存空间！\n");
        return -1;
    }

    // 找到了符合要求的内存块，进行分配
    int start_addr = p->start_addr;
    int remaining_size = p->size - size;

    // 如果分配后剩余空间不足以存放一个 MemBlock 结构体，则直接将这个分区作为已分配分区
    if (remaining_size < sizeof(MemBlock)) {
        if (pre == NULL) {
            free_head = p->next;
        } else {
            pre->next = p->next;
        }
    } else {
        // 否则，将这个分区分裂成两个
        p->size = size;
        p->start_addr = start_addr;
        start_addr += size;
        p = (MemBlock *)start_addr;
        p->size = remaining_size - sizeof(MemBlock);
        p->start_addr = start_addr;
        p->next = NULL;
        if (pre == NULL) {
            free_head = p;
        } else {
            pre->next = p;
        }
    }

    printf("分配成功！起始地址：%d，大小：%d\n", start_addr, size);
    return start_addr;
}

// 内存回收函数
void my_free(int start_addr) {
    MemBlock *p = (MemBlock *)start_addr;
    MemBlock *pre = NULL;

    // 遍历空闲分区链表，找到要回收的内存块应该插入的位置
    while (p > free_head && p < free_head->next) {
        pre = free_head;
        free_head = free_head->next;
    }

    // 将要回收的内存块插入到空闲分区链表中
    if (pre == NULL) {
        p->next = free_head;
        free_head = p;
    } else {
        p->next = pre->next;
        pre->next = p;
    }

    // 尝试合并相邻的空闲分区
    MemBlock *curr = free_head;
    while (curr != NULL && curr->next != NULL) {
        if (curr->start_addr + curr->size == curr->next->start_addr) {
            curr->size += curr->next->size + sizeof(MemBlock);
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }

    printf("回收成功！\n");
}

int main() {
    init_free_list();
    display_free_list();

    // 采用首次适应算法进行内存分配和回收
    printf("\n采用首次适应算法进行内存分配和回收：\n");
    first_fit_alloc(80);
    display_free_list();
    first_fit_alloc(120);
    display_free_list();
    first_fit_alloc(200);
    display_free_list();
    my_free(80);
    display_free_list();
    first_fit_alloc(100);
    display_free_list();
    first_fit_alloc(250);
    display_free_list();
    my_free(200);
    display_free_list();

    return 0;
}

最佳适应算法的代码实现：

#include <stdio.h>

// 定义内存块结构体
typedef struct mem_block {
    int start_addr;  // 起始地址
    int size;        // 大小
    struct mem_block *next;  // 下一个空闲内存块
} MemBlock;

MemBlock *free_head;  // 空闲分区链表头指针

// 初始化空闲分区链表
void init_free_list() {
    free_head = (MemBlock *)malloc(sizeof(MemBlock));
    free_head->start_addr = 0;
    free_head->size = 640;
    free_head->next = NULL;
}

// 显示空闲分区链表状态
void display_free_list() {
    MemBlock *p = free_head;
    printf("空闲内存分区链表：\n");
    while (p != NULL) {
        printf("起始地址：%d，大小：%d\n", p->start_addr, p->size);
        p = p->next;
    }
}

// 最佳适应算法的内存分配函数
int best_fit_alloc(int size) {
    MemBlock *p = free_head;
    MemBlock *pre = NULL;
    MemBlock *best_p = NULL;
    MemBlock *best_pre = NULL;
    int best_size = 640;

    // 遍历空闲分区链表，找到最小的符合要求的分区
    while (p != NULL) {
        if (p->size >= size && p->size < best_size) {
            best_p = p;
            best_pre = pre;
            best_size = p->size;
        }
        pre = p;
        p = p->next;
    }

    // 没有找到符合要求的内存块
    if (best_p == NULL) {
        printf("没有足够的内存空间！\n");
        return -1;
    }

    // 找到了符合要求的内存块，进行分配
    int start_addr = best_p->start_addr;
    int remaining_size = best_p->size - size;

    // 如果分配后剩余空间不足以存放一个 MemBlock 结构体，则直接将这个分区作为已分配分区
    if (remaining_size < sizeof(MemBlock)) {
        if (best_pre == NULL) {
            free_head = best_p->next;
        } else {
            best_pre->next = best_p->next;
        }
    } else {
        // 否则，将这个分区分裂成两个
        best_p->size = size;
        best_p->start_addr = start_addr;
        start_addr += size;
        best_p = (MemBlock *)start_addr;
        best_p->size = remaining_size - sizeof(MemBlock);
        best_p->start_addr = start_addr;
        best_p->next = NULL;
        if (best_pre == NULL) {
            free_head = best_p;
        } else {
            best_pre->next = best_p;
        }
    }

    printf("分配成功！起始地址：%d，大小：%d\n", start_addr, size);
    return start_addr;
}

// 内存回收函数
void my_free(int start_addr) {
    MemBlock *p = (MemBlock *)start_addr;
    MemBlock *pre = NULL;

    // 遍历空闲分区链表，找到要回收的内存块应该插入的位置
    while (p > free_head && p < free_head->next) {
        pre = free_head;
        free_head = free_head->next;
    }

    // 将要回收的内存块插入到空闲分区链表中
    if (pre == NULL) {
        p->next = free_head;
        free_head = p;
    } else {
        p->next = pre->next;
        pre->next = p;
    }

    // 尝试合并相邻的空闲分区
    MemBlock *curr = free_head;
    while (curr != NULL && curr->next != NULL) {
        if (curr->start_addr + curr->size == curr->next->start_addr) {
            curr->size += curr->next->size + sizeof(MemBlock);
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }

    printf("回收成功！\n");
}

int main() {
    init_free_list();
    display_free_list();

    // 采用最佳适应算法进行内存分配和回收
    printf("\n采用最佳适应算法进行内存分配和回收：\n");
    best_fit_alloc(80);
    display_free_list();
    best_fit_alloc(120);
    display_free_list();
    best_fit_alloc(200);
    display_free_list();
    my_free(80);
    display_free_list();
    best_fit_alloc(100);
    display_free_list();
    best_fit_alloc(250);
    display_free_list();
    my_free(200);
    display_free_list();

    return 0;
}