1、编写C程序，模拟实现首次/最佳/最坏适应算法的内存块分配与回收，要求每次分割与回收后显示出空闲分区和已分配分区的情况。 2、假设初始状态下，可用内存空间为640KB，并有下列请求序列： 序号 操作 1 作业1申请130KB 2 作业2申请60KB 3 作业3申请100KB 4 作业2释放60KB 5 作业3释放100KB 6 作业1释放130KB 请分别采用首次/最佳/最坏适应算法，对内存进行分配与回收，要求每次分配和回收后显示空闲内存分区链的情况。

好的，我会尽力回答你的问题。但是需要注意，我是一个语言模型 AI，无法直接运行代码。我会用文字模拟实现首次/最佳/最坏适应算法的内存块分配与回收，并根据给出的请求序列进行模拟。

首先，我们需要了解一下内存分配算法：

- 首次适应算法（First Fit）：从空闲分区链的头开始，找到第一个能满足要求的空闲分区进行分配。
- 最佳适应算法（Best Fit）：从空闲分区链中找到最小的能满足要求的空闲分区进行分配。
- 最坏适应算法（Worst Fit）：从空闲分区链中找到最大的空闲分区进行分配。

下面，我们分别用这三种算法进行模拟。

首先，我们定义一个结构体表示内存块：

typedef struct MemoryBlock {
    int size;  // 内存块大小
    int start; // 内存块起始地址
    int end;   // 内存块结束地址
    int pid;   // 进程 ID，为 0 表示空闲块
    struct MemoryBlock* next; // 指向下一个内存块
} MemoryBlock;

然后，我们定义一个全局变量表示空闲分区链：

MemoryBlock* freeList; // 空闲分区链表头指针

接下来，我们实现内存分配和回收的函数。

首次适应算法（First Fit）：

MemoryBlock* allocateFirstFit(int size, int pid) {
    MemoryBlock* p = freeList;
    MemoryBlock* prev = NULL;
    while (p != NULL) {
        if (p->size >= size) { // 找到满足要求的空闲分区
            MemoryBlock* newBlock = (MemoryBlock*) malloc(sizeof(MemoryBlock));
            newBlock->size = size;
            newBlock->start = p->start;
            newBlock->end = p->start + size - 1;
            newBlock->pid = pid;
            newBlock->next = NULL;
            if (prev == NULL) { // 分配的空闲分区在链表头
                freeList = p->next;
            } else { // 分配的空闲分区在链表中间
                prev->next = p->next;
            }
            if (p->size > size) { // 剩余空闲分区
                MemoryBlock* remainBlock = (MemoryBlock*) malloc(sizeof(MemoryBlock));
                remainBlock->size = p->size - size;
                remainBlock->start = newBlock->end + 1;
                remainBlock->end = p->end;
                remainBlock->pid = 0;
                remainBlock->next = freeList;
                freeList = remainBlock;
            }
            return newBlock;
        }
        prev = p;
        p = p->next;
    }
    return NULL; // 没有满足要求的空闲分区
}

void freeFirstFit(MemoryBlock* block) {
    MemoryBlock* p = freeList;
    MemoryBlock* prev = NULL;
    while (p != NULL) {
        if (p->start > block->end) { // 在该空闲分区前面
            break;
        }
        prev = p;
        p = p->next;
    }
    if (prev == NULL) { // 需要插入到链表头
        block->next = freeList;
        freeList = block;
    } else { // 插入到链表中间
        block->next = prev->next;
        prev->next = block;
    }
}

最佳适应算法（Best Fit）：

MemoryBlock* allocateBestFit(int size, int pid) {
    MemoryBlock* p = freeList;
    MemoryBlock* prev = NULL;
    MemoryBlock* bestBlock = NULL;
    while (p != NULL) {
        if (p->size >= size) { // 找到满足要求的空闲分区
            if (bestBlock == NULL || p->size < bestBlock->size) {
                bestBlock = p;
                prev = prev;
            }
        }
        prev = p;
        p = p->next;
    }
    if (bestBlock != NULL) {
        MemoryBlock* newBlock = (MemoryBlock*) malloc(sizeof(MemoryBlock));
        newBlock->size = size;
        newBlock->start = bestBlock->start;
        newBlock->end = bestBlock->start + size - 1;
        newBlock->pid = pid;
        newBlock->next = NULL;
        if (prev == NULL) { // 分配的空闲分区在链表头
            freeList = bestBlock->next;
        } else { // 分配的空闲分区在链表中间
            prev->next = bestBlock->next;
        }
        if (bestBlock->size > size) { // 剩余空闲分区
            MemoryBlock* remainBlock = (MemoryBlock*) malloc(sizeof(MemoryBlock));
            remainBlock->size = bestBlock->size - size;
            remainBlock->start = newBlock->end + 1;
            remainBlock->end = bestBlock->end;
            remainBlock->pid = 0;
            remainBlock->next = freeList;
            freeList = remainBlock;
        }
        return newBlock;
    }
    return NULL; // 没有满足要求的空闲分区
}

void freeBestFit(MemoryBlock* block) {
    MemoryBlock* p = freeList;
    MemoryBlock* prev = NULL;
    while (p != NULL) {
        if (p->start > block->end) { // 在该空闲分区前面
            break;
        }
        prev = p;
        p = p->next;
    }
    if (prev == NULL) { // 需要插入到链表头
        block->next = freeList;
        freeList = block;
    } else { // 插入到链表中间
        block->next = prev->next;
        prev->next = block;
    }
    // 如果前后空闲分区相连，合并它们
    if (block->next != NULL && block->next->start == block->end + 1) {
        block->size += block->next->size;
        block->end = block->next->end;
        block->next = block->next->next;
    }
    if (prev != NULL && prev->end == block->start - 1) {
        prev->size += block->size;
        prev->end = block->end;
        prev->next = block->next;
    }
}

最坏适应算法（Worst Fit）：

MemoryBlock* allocateWorstFit(int size, int pid) {
    MemoryBlock* p = freeList;
    MemoryBlock* prev = NULL;
    MemoryBlock* worstBlock = NULL;
    while (p != NULL) {
        if (p->size >= size) { // 找到满足要求的空闲分区
            if (worstBlock == NULL || p->size > worstBlock->size) {
                worstBlock = p;
                prev = prev;
            }
        }
        prev = p;
        p = p->next;
    }
    if (worstBlock != NULL) {
        MemoryBlock* newBlock = (MemoryBlock*) malloc(sizeof(MemoryBlock));
        newBlock->size = size;
        newBlock->start = worstBlock->start;
        newBlock->end = worstBlock->start + size - 1;
        newBlock->pid = pid;
        newBlock->next = NULL;
        if (prev == NULL) { // 分配的空闲分区在链表头
            freeList = worstBlock->next;
        } else { // 分配的空闲分区在链表中间
            prev->next = worstBlock->next;
        }
        if (worstBlock->size > size) { // 剩余空闲分区
            MemoryBlock* remainBlock = (MemoryBlock*) malloc(sizeof(MemoryBlock));
            remainBlock->size = worstBlock->size - size;
            remainBlock->start = newBlock->end + 1;
            remainBlock->end = worstBlock->end;
            remainBlock->pid = 0;
            remainBlock->next = freeList;
            freeList = remainBlock;
        }
        return newBlock;
    }
    return NULL; // 没有满足要求的空闲分区
}

void freeWorstFit(MemoryBlock* block) {
    MemoryBlock* p = freeList;
    MemoryBlock* prev = NULL;
    while (p != NULL) {
        if (p->start > block->end) { // 在该空闲分区前面
            break;
        }
        prev = p;
        p = p->next;
    }
    if (prev == NULL) { // 需要插入到链表头
        block->next = freeList;
        freeList = block;
    } else { // 插入到链表中间
        block->next = prev->next;
        prev->next = block;
    }
    // 如果前后空闲分区相连，合并它们
    if (block->next != NULL && block->next->start == block->end + 1) {
        block->size += block->next->size;
        block->end = block->next->end;
        block->next = block->next->next;
    }
    if (prev != NULL && prev->end == block->start - 1) {
        prev->size += block->size;
        prev->end = block->end;
        prev->next = block->next;
    }
}

接下来，我们用给出的请求序列进行模拟。

首先，我们初始化空闲分区链，可用内存空间为640KB：

void init() {
    MemoryBlock* block = (MemoryBlock*) malloc(sizeof(MemoryBlock));
    block->size = 640;
    block->start = 0;
    block->end = 639;
    block->pid = 0;
    block->next = NULL;
    freeList = block;
}

然后，我们按照顺序进行分配和回收操作：

int main() {
    init(); // 初始化空闲分区链
    // 请求序列：作业1申请130KB，作业2申请60KB，作业3申请100KB
    MemoryBlock* block1 = allocateFirstFit(130, 1);
    MemoryBlock* block2 = allocateBestFit(60, 2);
    MemoryBlock* block3 = allocateWorstFit(100, 3);
    printMemory(); // 显示空闲分区链和已分配分区
    // 请求序列：作业2释放60KB，作业3释放100KB，作业1释放130KB
    freeFirstFit(block2);
    freeBestFit(block3);
    freeWorstFit(block1);
    printMemory(); // 显示空闲分区链和已分配分区
    return 0;
}

最后，我们实现显示空闲分区链和已分配分区的函数：

void printMemory() {
    printf("空闲分区链：\n");
    MemoryBlock* p = freeList;
    while (p != NULL) {
        printf("[%d, %d] -> ", p->start, p->end);
        p = p->next;
    }
    printf("NULL\n已分配分区：\n");
    p = freeList;
    while (p != NULL) {
        if (p->pid != 0) {
            printf("[%d, %d]: %d\n", p->start, p->end, p->pid);
        }
        p = p->next;
    }
    printf("\n");
}

这样，我们就完成了模拟实现首次/最佳/最坏适应算法的内存块分配与回收。