1、题目描述
● 请实现一个简易内存池,根据请求命令完成内存分配和释放。
● 内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
● REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
● RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
注意：内存池总大小为100字节。
内存池地址分配必须是连续内存，并优先从低地址分配。
内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
不会释放已申请的内存块的中间地址。
释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。
2、输入描述
首行为整数 N , 表示操作命令的个数，取值范围：0 < N <= 100。
接下来的N行, 每行将给出一个操作命令，操作命令和参数之间用 “=”分割。3、输出描述
请求分配指定大小内存时，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error
释放掉之前分配的内存时，释放成功无需输出，如果释放不存在的首地址则输出error。
用例：输入
5
REQUEST=10
REQUEST=20
RELEASE=0
REQUEST=20
REQUEST=10输出
0
10
30
0ps：
第一条，申请地址0~9的10个字节内存，返回首地址0
第二条，申请地址10~29的20字节内存，返回首地址10
第三条，释放首地址为0的内存申请，0~9地址内存被释放，变为空闲，释放成功，无需输出
第四条，申请20字节内存，09地址内存连续空间不足20字节，往后查找到3049地址，返回首地址30
第五条，申请10字节，0~9地址内存空间足够，返回首地址0
————————————————版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_52914380/article/details/138459806
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.请实现一个简易内存池，根据请求命令完成内存分配和释放
2.内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
REQUEST=请求的内存大小，表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
RELEASE=释放的内存首地址，表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
3.注意：（1）内存池总大小为100字节。
（2）内存池地址分配必须是连续内存，并优先从低地址分配
（3）内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放
（4）不会释放已申请的内存块的中间地址
（5）释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其他内存块。
4.输入描述：首行为整数N，表示操作命令的个数，取值范围：N大于0小于等于100.
接下来的N行，每行将给出一个操作命令，操作命令和参数之间用“=”分割。
5.输出描述：请求分配指定大小内存时，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error
释放掉之前分配的内存时，释放成功无需输出，如果释放不存在的首地址则输出error。
二、解题思路
1.内存池一共有两种命令，一种是REQUEST，后面跟请求分配的内存大小
一种是RELEASE后面跟要释放内存的首地址
2.首先我们引入标准输入输出库、标准库、字符串处理库定义内存池总大小为100字节
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MEMORY_POOL_SIZE 100
3.然后定义MemoryBlock结构体用来表示内存池中的内存块信息。其中startAddress记录内存块的起始地址，size表示内存块的大小（字节数），isAllocated用于标记该内存块是否已经被分配出去（1表示已分配，0表示空闲），next指针用于链接下一个内存块，形成一个链表结构，方便管理内存池中多个内存块的情况。
typede struct MemoryBlock {
int startAddress; // 内存块起始地址
int size; // 内存块大小
int isAllocated; // 内存块是否已分配
struct MemoryBlock *next; // 指向下一个内存块的指针
} MemoryBlock;
4.然后声明一个函数用于创建并初始化内存池，通过动态分配内存创建一个MemoryBlock结构体来表示整个内存池，将其起始地址设为0，大小设为定义好的MEMORY_POOL_SIZE（也就是100字节），标记为未分配状态（isAllocated设为0），并将next指针设为NULL，表示初始时只有这一个代表整个内存池的空闲内存块，最后返回这个表示内存池的结构体指针。
MemoryBlock* initMemoryPool() {
MemoryBlock *pool = (MemoryBlock *)malloc(sizeof(MemoryBlock));
if(pool == NULL) {
perror("内存分配失败");
return NULL;
}
pool->startAddress = 0;
pool->size = MEMORY_POOL_SIZE;
pool->isAllocated = 0;
pool->next = NULL;
return pool;
}
5.声明一个函数用来查找空闲内存块，该函数接收内存池的头指针pool和请求分配的内存大小requestSize作为参数，通过遍历内存池链表（从内存池的头指针开始，沿着next指针逐个访问内存块），查找是否存在未分配（isAllocated为0）且大小足够（size大于等于requestSize）的空闲内存块，找到则返回该内存块的指针，若遍历完整个链表都没有找到符合条件的空闲内存块，就返回NULL。
MemoryBlock* findFreeBlock(MemoryBlock *pool, int requestSize) {
MemoryBlock *current = pool;
while(current != NULL) {
if(current->isAllocated == 0 && current->size >= requestSize) {
return current;
}
current = current->next;
}
return NULL;
}
6.声明一个内存分配函数用于实际分配内存，首先判断请求分配的内存大小是否为0，若是则输出error并返回-1表示分配失败。然后调用findFreeBlock函数在内存池中查找合适的空闲内存块，如果没找到（返回NULL），同样输出error并返回-1.若找到了空闲内存块，分两种情况处理：
如果找到的空闲内存块大小正好等于请求的大小，直接将该内存块的isAllocated标记为1，表示已分配，然后返回该内存块的起始地址。
如果空闲内存块大小大于请求的大小，需要将其拆分成两个内存块，一个用于分配（大小设为requestSize，标记为已分配），另一个保持空闲（大小为原空闲内存块大小减去请求的大小，标记为未分配），并通过调整链表指针将新的空闲内存块插入到链表中合适的位置，最后返回分配的内存块的起始地址。
int allocateMemory(MemoryBlock **pool, int requestSize) {
if(requestSize == 0) {
printf("error\n");
return -1;
}
MemoryBlock *freeBlock = findFreeBlock(*pool, requestSize);
if(freeBlock == NULL) {
printf("error\n");
return -1;
}
if(freeBlock->size == requestSize) {
freeBlock->isAllocated = 1;
} else {
MemoryBlock *newBlock = (MemoryBlock *)malloc(sizeof(MemoryBlock));
if(newBlock == NULL) {
perror("内存分配失败");
return -1;
}
newBlock->startAddress = freeBlock->startAddress + requestSize;
newBlock->size = freeBlock->size - requestSize;
newBlock->isAllocated = 0;
newBlock->next = freeBlock->next;
freeBlock->size = requestSize;
freeBlock->isAllocated = 1;
freeBlock->next = newBlock;
}
return freeBlock->startAddress;
}
7.然后是释放内存函数，用于释放指定首地址对应的内存块，通过遍历内存池链表来查找要释放的内存块（根据起始地址匹配），如果找到了对应的内存块且该内存块是已分配状态，则将其标记为未分配，并且和前后有可能存在的空闲内存块合并，
void releaseMemory(MemoryBlock **pool, int relaseAddress) {
MemoryBlock *prev = NULL;
MemoryBlock *current = *pool;
while(current != NULL) {
if(current->startAddress == releaseAddress) {
if(current->isAllocated == 0) {
printf("error\n");
return;
}
current->isAllocated = 0;
// 如果前面有空闲内存块我们尝试合并
if(prev != NULL && prev->isAllocated == 0) {
prev->size += current->size;
prev->next = current->next;
free(current);
current = prev;
}
// 如果后面有空闲内存块，我们尝试合并
if(current->next != NULL && current->next->isAllocated == 0) {
current->size += current->next->size;
current->next = current->next->next;
}
return;
}
prev = current;
current = current->next;
}
printf("error\n");
}
8.主函数首先定义一个整数int N;用于读取命令的个数
int main() {
int N;
scanf("%d", &N);
MemoryBlock *memoryPool = initMemoryPool();
for(int i = 0;i < N; i++) {
char command[20];
scanf("%s",command);
if(strncmp(command,"REQUEST", 7) == 0) {
int requestSize;
sscanf(command + 7, "=%d", &requestSize);
int address = allocateMemory(&memoryPool, requestSize);
if(address != -1) {
printf("%d\n", address);
}
}
else if(strncmp(command,"RELEASE", 7) == 0) {
int relaseAddress;
sscanf(command + 7, "=%d", &releaseAddress);
releaseMemory(&memoryPool, releaseAddress);
}
}
return 0;
}
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MEMORY_POOL_SIZE 100
// 内存块结构体
typedef struct MemoryBlock {
int startAddress;
int size;
bool isAllocated;
struct MemoryBlock *next;
} MemoryBlock;
// 初始化内存池
MemoryBlock* initMemoryBlock() {
MemoryBlock *pool = (MemoryBlock *)malloc(sizeof(MemoryBlock));
if(pool == NULL) {
perror("内存分配失败");
return NULL;
}
pool->startAddress = 0;
pool->size = MEMORY_POOL_SIZE;
pool->isAllocated = false;
pool->next = NULL;
return pool;
}
// 寻找空闲内存池
MemoryBlock* findFreeBlock(MemoryBlock* pool, int requestSize) {
MemoryBlock *current = pool;
while(current != NULL) {
if(current->isAllocated == false && current->size >= requestSize) {
return current;
}
current = current->next;
}
return NULL;
}
// 为空闲地址池分配内存
int allocateMemory(MemoryBlock** pool, int requestSize) {
if(requestSize == 0) {
printf("error\n");
return -1;
}
MemoryBlock *freeBlock = findFreeBlock(*pool, requestSize);
if(freeBlock == NULL) {
printf("error\n");
return -1;
}
if(freeBlock->size == requestSize) {
freeBlock->isAllocated = true;
} else {
MemoryBlock *newBlock = (MemoryBlock*)malloc(sizeof(MemoryBlock));
if(newBlock == NULL) {
perror("内存分配失败");
return -1;
}
newBlock->size = freeBlock->size - requestSize;
newBlock->isAllocated = false;
newBlock->startAddress = freeBlock->startAddress + requestSize;
newBlock->next = freeBlock->next;
freeBlock->isAllocated = true;
freeBlock->size = requestSize;
freeBlock->next = newBlock;
}
return freeBlock->startAddress;
}
void releaseMemory(MemoryBlock** pool, int relaseAddress) {
MemoryBlock* prev = NULL, *current = *pool;
while(current != NULL) {
if(current->startAddress == relaseAddress) {
if(current->isAllocated == false) {
printf("error\n");
return;
}
current->isAllocated = false;
if(prev!= NULL && prev->isAllocated == false) {
prev->size += current->size;
prev->next = current->next;
free(current);
current = prev;
}
if(current->next != NULL && current->next->isAllocated == 0) {
current->size += current->next->size;
current->next = current->next->next;
}
return;
}
prev = current;
current = current->next;
}
printf("error\n");
}
int main() {
int N;
scanf("%d", &N);
MemoryBlock *memoryPool = initMemoryBlock();
for(int i = 0; i < N; i++) {
char command[20];
int num;
scanf("%s", command);
char *temp;
temp = strtok(command, "=");
num = atoi(strtok(NULL, "="));
//printf("%s=%d\n", temp, num);
if(strcmp(temp,"REQUEST") == 0) {
int address = allocateMemory(&memoryPool, num);
if(address != -1) {
printf("%d\n", address);
}
} else if(strcmp(temp, "RELEASE") == 0) {
releaseMemory(&memoryPool, num);
}
}
return 0;
}