福州电商网站设计,快手刷评论推广网站,做搜狗pc网站优化点,泰安网站销售公司1、题目描述 ● 请实现一个简易内存池,根据请求命令完成内存分配和释放。 ● 内存池支持两种操作命令#xff0c;REQUEST和RELEASE#xff0c;其格式为#xff1a; ● REQUEST请求的内存大小 表示请求分配指定大小内存#xff0c;如果分配成功#xff0c;返回分配到的内存… 1、题目描述 ● 请实现一个简易内存池,根据请求命令完成内存分配和释放。 ● 内存池支持两种操作命令REQUEST和RELEASE其格式为 ● REQUEST请求的内存大小 表示请求分配指定大小内存如果分配成功返回分配到的内存首地址如果内存不足或指定的大小为0则输出error。 ● RELEASE释放的内存首地址 表示释放掉之前分配的内存释放成功无需输出如果释放不存在的首地址则输出error。 注意 内存池总大小为100字节。 内存池地址分配必须是连续内存并优先从低地址分配。 内存释放后可被再次分配已释放的内存在空闲时不能被二次释放。 不会释放已申请的内存块的中间地址。 释放操作只是针对首地址所对应的单个内存块进行操作不会影响其它内存块。2、输入描述 首行为整数 N , 表示操作命令的个数取值范围0 N 100。 接下来的N行, 每行将给出一个操作命令操作命令和参数之间用 “”分割。 3、输出描述 请求分配指定大小内存时如果分配成功返回分配到的内存首地址如果内存不足或指定的大小为0则输出error 释放掉之前分配的内存时释放成功无需输出如果释放不存在的首地址则输出error。用例 输入 5 REQUEST10 REQUEST20 RELEASE0 REQUEST20 REQUEST10 输出 0 10 30 0 ps 第一条申请地址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;
}
