古典風格網(wǎng)站模板htmlseo的搜索排名影響因素主要有
1、題目描述
● 請實現(xiàn)一個簡易內(nèi)存池,根據(jù)請求命令完成內(nèi)存分配和釋放。
● 內(nèi)存池支持兩種操作命令，REQUEST和RELEASE，其格式為：
● REQUEST=請求的內(nèi)存大小 表示請求分配指定大小內(nèi)存，如果分配成功，返回分配到的內(nèi)存首地址；如果內(nèi)存不足，或指定的大小為0，則輸出error。
● RELEASE=釋放的內(nèi)存首地址 表示釋放掉之前分配的內(nèi)存，釋放成功無需輸出，如果釋放不存在的首地址則輸出error。
注意：內(nèi)存池總大小為100字節(jié)。
內(nèi)存池地址分配必須是連續(xù)內(nèi)存，并優(yōu)先從低地址分配。
內(nèi)存釋放后可被再次分配，已釋放的內(nèi)存在空閑時不能被二次釋放。
不會釋放已申請的內(nèi)存塊的中間地址。
釋放操作只是針對首地址所對應(yīng)的單個內(nèi)存塊進行操作，不會影響其它內(nèi)存塊。
2、輸入描述
首行為整數(shù) N , 表示操作命令的個數(shù)，取值范圍：0 < N <= 100。
接下來的N行, 每行將給出一個操作命令，操作命令和參數(shù)之間用 “=”分割。3、輸出描述
請求分配指定大小內(nèi)存時，如果分配成功，返回分配到的內(nèi)存首地址；如果內(nèi)存不足，或指定的大小為0，則輸出error
釋放掉之前分配的內(nèi)存時，釋放成功無需輸出，如果釋放不存在的首地址則輸出error。
用例：輸入
5
REQUEST=10
REQUEST=20
RELEASE=0
REQUEST=20
REQUEST=10輸出
0
10
30
0ps：
第一條，申請地址0~9的10個字節(jié)內(nèi)存，返回首地址0
第二條，申請地址10~29的20字節(jié)內(nèi)存，返回首地址10
第三條，釋放首地址為0的內(nèi)存申請，0~9地址內(nèi)存被釋放，變?yōu)榭臻e，釋放成功，無需輸出
第四條，申請20字節(jié)內(nèi)存，09地址內(nèi)存連續(xù)空間不足20字節(jié)，往后查找到3049地址，返回首地址30
第五條，申請10字節(jié)，0~9地址內(nèi)存空間足夠，返回首地址0
————————————————? ? ? ? ? ? ? ? ? ? ? ? ? ? 版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接和本聲明。
? ? ? ? ? ? ? ? ? ? ? ??
原文鏈接：https://blog.csdn.net/weixin_52914380/article/details/138459806
一、問題分析
首先讀題，仔細看描述中的內(nèi)容，發(fā)現(xiàn)需求是
1.請實現(xiàn)一個簡易內(nèi)存池，根據(jù)請求命令完成內(nèi)存分配和釋放
2.內(nèi)存池支持兩種操作命令，REQUEST和RELEASE，其格式為：
REQUEST=請求的內(nèi)存大小，表示請求分配指定大小內(nèi)存，如果分配成功，返回分配到的內(nèi)存首地址；如果內(nèi)存不足，或指定的大小為0，則輸出error。
RELEASE=釋放的內(nèi)存首地址，表示釋放掉之前分配的內(nèi)存，釋放成功無需輸出，如果釋放不存在的首地址則輸出error。
3.注意：（1）內(nèi)存池總大小為100字節(jié)。
（2）內(nèi)存池地址分配必須是連續(xù)內(nèi)存，并優(yōu)先從低地址分配
（3）內(nèi)存釋放后可被再次分配，已釋放的內(nèi)存在空閑時不能被二次釋放
（4）不會釋放已申請的內(nèi)存塊的中間地址
（5）釋放操作只是針對首地址所對應(yīng)的單個內(nèi)存塊進行操作，不會影響其他內(nèi)存塊。
4.輸入描述：首行為整數(shù)N，表示操作命令的個數(shù)，取值范圍：N大于0小于等于100.
接下來的N行，每行將給出一個操作命令，操作命令和參數(shù)之間用“=”分割。
5.輸出描述：請求分配指定大小內(nèi)存時，如果分配成功，返回分配到的內(nèi)存首地址；如果內(nèi)存不足，或指定的大小為0，則輸出error
釋放掉之前分配的內(nèi)存時，釋放成功無需輸出，如果釋放不存在的首地址則輸出error。
二、解題思路
1.內(nèi)存池一共有兩種命令，一種是REQUEST，后面跟請求分配的內(nèi)存大小
一種是RELEASE后面跟要釋放內(nèi)存的首地址
2.首先我們引入標準輸入輸出庫、標準庫、字符串處理庫定義內(nèi)存池總大小為100字節(jié)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MEMORY_POOL_SIZE 100
3.然后定義MemoryBlock結(jié)構(gòu)體用來表示內(nèi)存池中的內(nèi)存塊信息。其中startAddress記錄內(nèi)存塊的起始地址，size表示內(nèi)存塊的大小（字節(jié)數(shù)），isAllocated用于標記該內(nèi)存塊是否已經(jīng)被分配出去（1表示已分配，0表示空閑），next指針用于鏈接下一個內(nèi)存塊，形成一個鏈表結(jié)構(gòu)，方便管理內(nèi)存池中多個內(nèi)存塊的情況。
typede struct MemoryBlock {
int startAddress; // 內(nèi)存塊起始地址
int size; // 內(nèi)存塊大小
int isAllocated; // 內(nèi)存塊是否已分配
struct MemoryBlock *next; // 指向下一個內(nèi)存塊的指針
} MemoryBlock;
4.然后聲明一個函數(shù)用于創(chuàng)建并初始化內(nèi)存池，通過動態(tài)分配內(nèi)存創(chuàng)建一個MemoryBlock結(jié)構(gòu)體來表示整個內(nèi)存池，將其起始地址設(shè)為0，大小設(shè)為定義好的MEMORY_POOL_SIZE（也就是100字節(jié)），標記為未分配狀態(tài)（isAllocated設(shè)為0），并將next指針設(shè)為NULL，表示初始時只有這一個代表整個內(nèi)存池的空閑內(nèi)存塊，最后返回這個表示內(nèi)存池的結(jié)構(gòu)體指針。
MemoryBlock* initMemoryPool() {
MemoryBlock *pool = (MemoryBlock *)malloc(sizeof(MemoryBlock));
if(pool == NULL) {
perror("內(nèi)存分配失敗");
return NULL;
}
pool->startAddress = 0;
pool->size = MEMORY_POOL_SIZE;
pool->isAllocated = 0;
pool->next = NULL;
return pool;
}
5.聲明一個函數(shù)用來查找空閑內(nèi)存塊，該函數(shù)接收內(nèi)存池的頭指針pool和請求分配的內(nèi)存大小requestSize作為參數(shù)，通過遍歷內(nèi)存池鏈表（從內(nèi)存池的頭指針開始，沿著next指針逐個訪問內(nèi)存塊），查找是否存在未分配（isAllocated為0）且大小足夠（size大于等于requestSize）的空閑內(nèi)存塊，找到則返回該內(nèi)存塊的指針，若遍歷完整個鏈表都沒有找到符合條件的空閑內(nèi)存塊，就返回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.聲明一個內(nèi)存分配函數(shù)用于實際分配內(nèi)存，首先判斷請求分配的內(nèi)存大小是否為0，若是則輸出error并返回-1表示分配失敗。然后調(diào)用findFreeBlock函數(shù)在內(nèi)存池中查找合適的空閑內(nèi)存塊，如果沒找到（返回NULL），同樣輸出error并返回-1.若找到了空閑內(nèi)存塊，分兩種情況處理：
如果找到的空閑內(nèi)存塊大小正好等于請求的大小，直接將該內(nèi)存塊的isAllocated標記為1，表示已分配，然后返回該內(nèi)存塊的起始地址。
如果空閑內(nèi)存塊大小大于請求的大小，需要將其拆分成兩個內(nèi)存塊，一個用于分配（大小設(shè)為requestSize，標記為已分配），另一個保持空閑（大小為原空閑內(nèi)存塊大小減去請求的大小，標記為未分配），并通過調(diào)整鏈表指針將新的空閑內(nèi)存塊插入到鏈表中合適的位置，最后返回分配的內(nèi)存塊的起始地址。
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("內(nèi)存分配失敗");
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.然后是釋放內(nèi)存函數(shù)，用于釋放指定首地址對應(yīng)的內(nèi)存塊，通過遍歷內(nèi)存池鏈表來查找要釋放的內(nèi)存塊（根據(jù)起始地址匹配），如果找到了對應(yīng)的內(nèi)存塊且該內(nèi)存塊是已分配狀態(tài)，則將其標記為未分配，并且和前后有可能存在的空閑內(nèi)存塊合并，
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;
// 如果前面有空閑內(nèi)存塊我們嘗試合并
if(prev != NULL && prev->isAllocated == 0) {
prev->size += current->size;
prev->next = current->next;
free(current);
current = prev;
}
// 如果后面有空閑內(nèi)存塊，我們嘗試合并
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.主函數(shù)首先定義一個整數(shù)int N;用于讀取命令的個數(shù)
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// 內(nèi)存塊結(jié)構(gòu)體
typedef struct MemoryBlock {int startAddress;int size;bool isAllocated;struct MemoryBlock *next;
} MemoryBlock;// 初始化內(nèi)存池
MemoryBlock* initMemoryBlock() {MemoryBlock *pool = (MemoryBlock *)malloc(sizeof(MemoryBlock));if(pool == NULL) {perror("內(nèi)存分配失敗");return NULL;}pool->startAddress = 0;pool->size = MEMORY_POOL_SIZE;pool->isAllocated = false;pool->next = NULL;return pool;
}// 尋找空閑內(nèi)存池
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;
}// 為空閑地址池分配內(nèi)存
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("內(nèi)存分配失敗");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;
}