编写C程序,模拟实现首次/最佳/最坏适应算法的内存块分配与回收,要求每次分配与回收后显示出空闲分区和已分配分区的情况。
时间: 2023-11-17 10:26:39 浏览: 50
好的,以下是一个简单的C程序,实现了首次适应算法的内存块分配与回收,并且在每次分配与回收后显示出空闲分区和已分配分区的情况。最佳适应算法和最坏适应算法的实现方式与此类似。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 内存大小
#define MIN_SIZE 1 // 最小分配单位
// 内存块结构体
typedef struct block {
int start_addr; // 起始地址
int size; // 大小
int free; // 是否空闲
struct block *next; // 指向下一个内存块
} block;
block *free_block; // 空闲内存块链表头指针
block *used_block; // 已分配内存块链表头指针
// 初始化内存块
void init_block() {
block *p = (block *)malloc(sizeof(block));
p->start_addr = 0;
p->size = MAX_SIZE;
p->free = 1;
p->next = NULL;
free_block = p;
}
// 显示空闲分区
void show_free_block() {
printf("空闲分区:\n");
block *p = free_block;
while (p) {
printf("起始地址:%d,大小:%d\n", p->start_addr, p->size);
p = p->next;
}
}
// 显示已分配分区
void show_used_block() {
printf("已分配分区:\n");
block *p = used_block;
while (p) {
printf("起始地址:%d,大小:%d\n", p->start_addr, p->size);
p = p->next;
}
}
// 首次适应算法
block *first_fit(int size) {
block *p = free_block;
while (p) {
if (p->free && p->size >= size) {
return p;
}
p = p->next;
}
return NULL;
}
// 分配内存块
void allocate_block(int size) {
block *p = first_fit(size);
if (!p) {
printf("无法分配内存块!\n");
return;
}
if (p->size == size) {
p->free = 0;
} else {
block *t = (block *)malloc(sizeof(block));
t->start_addr = p->start_addr;
t->size = size;
t->free = 0;
t->next = p->next;
p->next = t;
p->start_addr += size;
p->size -= size;
}
// 将已分配内存块添加到已分配链表中
p->next = used_block;
used_block = p;
printf("分配内存块成功!\n");
show_free_block();
show_used_block();
}
// 回收内存块
void free_block_func() {
int addr;
printf("请输入要回收的内存块的起始地址:");
scanf("%d", &addr);
block *p = used_block, *prev = NULL;
while (p) {
if (p->start_addr == addr) {
p->free = 1;
// 合并相邻空闲内存块
if (prev && prev->free) {
prev->size += p->size;
prev->next = p->next;
free(p);
p = prev;
}
if (p->next && p->next->free) {
p->size += p->next->size;
block *t = p->next;
p->next = t->next;
free(t);
}
// 将已分配内存块从已分配链表中删除
if (prev) {
prev->next = p->next;
} else {
used_block = p->next;
}
printf("回收内存块成功!\n");
show_free_block();
show_used_block();
return;
}
prev = p;
p = p->next;
}
printf("未找到要回收的内存块!\n");
}
int main() {
init_block();
int choice, size;
while (1) {
printf("1.显示空闲分区\n2.显示已分配分区\n3.分配内存块\n4.回收内存块\n5.退出\n");
printf("请输入操作序号:");
scanf("%d", &choice);
switch (choice) {
case 1:
show_free_block();
break;
case 2:
show_used_block();
break;
case 3:
printf("请输入要分配的内存块大小:");
scanf("%d", &size);
allocate_block(size);
break;
case 4:
free_block_func();
break;
case 5:
return 0;
default:
printf("未知操作!\n");
break;
}
}
return 0;
}
```
在这个程序中,我们定义了一个内存块结构体,包含了起始地址、大小、是否空闲和指向下一个内存块的指针。我们还定义了一个空闲内存块链表头指针和一个已分配内存块链表头指针。
在初始化时,我们创建了一个大小为MAX_SIZE的空闲内存块,并将其添加到空闲内存块链表中。在分配内存块时,我们使用首次适应算法查找空闲内存块,如果找到了合适的内存块,则将其标记为已分配,并将其添加到已分配内存块链表中。如果找到的内存块大小超过要求的大小,则将其拆分为两个内存块,并将要分配的内存块添加到已分配内存块链表中。在回收内存块时,我们使用简单的合并算法合并相邻的空闲内存块,并将要回收的内存块标记为空闲,并从已分配内存块链表中删除。
在每次分配与回收后,我们使用show_free_block和show_used_block函数来显示空闲分区和已分配分区的情况。