1.題目要求
編寫C語(yǔ)言程序，模擬實(shí)現(xiàn)首次/最佳/最壞適應(yīng)算法(選擇其中之一即可)的內(nèi)存塊分配和回收，要求每次分配和回收后顯示出空閑分區(qū)和已分配分區(qū)的情況。假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為640KB。
假設(shè)下列作業(yè)請(qǐng)求序列：
（1）作業(yè)1 申請(qǐng)130 KB （2）作業(yè)2 申請(qǐng)60 KB （3）作業(yè)3 申請(qǐng)100 KB
（4）作業(yè)2 釋放60 KB （5）作業(yè)3 釋放100 KB （6）作業(yè)1 釋放130 KB
顯示每次作業(yè)申請(qǐng)或釋放后當(dāng)前內(nèi)存情況。
2.分析設(shè)計(jì)
根據(jù)題目，分析設(shè)計(jì)如下：
（1）程序初始需要提供用戶選擇方式。選擇首次適應(yīng)算法，還是最佳是適應(yīng)算法，選擇作業(yè)的回收，作業(yè)的展示，程序的退出能。
（2）當(dāng)用戶選擇首次適應(yīng)算法或者最佳適應(yīng)算法，需要用戶輸入分配內(nèi)存的大小。在輸入大小時(shí)在根據(jù)算法的設(shè)計(jì)進(jìn)行分配。
（3）當(dāng)內(nèi)存分配過(guò)后，如果分配成功就需要提示成功，如果失敗則需要提示失敗。
（4）內(nèi)存回收需要用戶輸入回收作業(yè)的ID，根據(jù)作業(yè)的ID對(duì)內(nèi)存進(jìn)行回收。在回收時(shí)要分多種情況進(jìn)行判斷。
（5）作業(yè)展示，需要向用戶展示，作業(yè)的ID，起始地址，內(nèi)存大小，狀態(tài)是已分配還是空閑。
（6）一個(gè)作業(yè)需要用到數(shù)據(jù)結(jié)構(gòu)中的雙向列表，用一個(gè)雙向列表來(lái)表示節(jié)點(diǎn)。
3.程序代碼
#include <stdio.h>
#include <stdlib.h>
struct area
{
int id; // 編號(hào)
int addr_front; //首地址
int addr_end; //結(jié)束地址
int size; //分區(qū)大小
int flag; //分配標(biāo)志,0表示空閑，1表示占用
struct area *front; //上一分區(qū)
struct area *next; //下一分區(qū)
};
typedef struct area partion;
partion *head = NULL; //分區(qū)隊(duì)列頭節(jié)點(diǎn)
int need; //需求
int choice = 1; //操作選項(xiàng)
partion *createPartion(int id, int addr_front, int size, int flag); //生成一個(gè)節(jié)點(diǎn)
void inputNeed(); //輸入需求量
void assign(partion *ptr, int need); //分配分區(qū)
void first_fit(); //首次適應(yīng)算法
void best_fit(); //最佳適應(yīng)算法
void showMemoryInfo(); //打印分區(qū)分配狀況
void recovery(); //分區(qū)回收
void changeIdValue(partion *ptr, int delta); //改變從ptr開始所有節(jié)點(diǎn)的id值
int main(void)
{
head = createPartion(0, 0, 640, 0);
while (choice != 0)
{
puts("-------------------\n請(qǐng)選擇操作:\n1:首次適應(yīng);\n2:最佳適應(yīng);\n3:內(nèi)存回收;\n4:展示詳細(xì)信息;\n0:推出......\n-------------------");
scanf("%d", &choice);
switch (choice)
{
case 1:
inputNeed();
first_fit();
break;
case 2:
inputNeed();
best_fit();
break;
case 3:
recovery();
showMemoryInfo();
break;
case 4:
showMemoryInfo();
break;
case 0:
puts("byebye");
break;
default:
break;
}
}
return 0;
}
//創(chuàng)建一個(gè)節(jié)點(diǎn)
partion *createPartion(int id, int addr_front, int size, int flag)
{
partion *p = (partion *)malloc(sizeof(partion));
p->id = id;
p->addr_front = addr_front;
p->addr_end=addr_front+size-1;
p->size = size;
p->flag = flag;
p->front = NULL;
p->next = NULL;
return p;
}
void inputNeed()
{
printf("請(qǐng)輸入需要的內(nèi)存大小:");
scanf("%d", &need);
}
void first_fit()
{
partion *fit = NULL;
partion *ptr = head;
while (ptr != NULL)
{
if (ptr->size >= need && ptr->flag == 0)//如果是空閑并且大小大于則給予分配
{
fit = ptr;
break;
}
ptr = ptr->next;
}
if (fit != NULL)
{
assign(fit, need);
printf("內(nèi)存分配成功,分配如下：\n");
showMemoryInfo();
}
else
{
puts("抱歉，內(nèi)存分配失敗!");
free(fit);
}
}
void best_fit()
{
partion *fit = NULL;
partion *ptr = head;
int flag = 0; //flag 表示是否找到可分配的分區(qū)
while (ptr != NULL)
{
if (ptr->flag == 0 && ptr->size >= need)
{
if (flag == 0)
{
//只有遇到的第一個(gè)可分配分區(qū)會(huì)執(zhí)行此操作
fit = ptr;
flag = 1;
}
else
{
//若遇到可分配且分區(qū)更小即更適合的則更新
if (ptr->size < fit->size)
{
fit = ptr;
}
}
}
ptr = ptr->next;
}
//先處理沒找到合適分區(qū)的情況
if (flag == 0)
{
puts("抱歉，未找到合適的分區(qū)!");
free(fit);
return;
}
//找到則分配
assign(fit, need);
puts("內(nèi)存分配成功，分配如下:\n!");
showMemoryInfo();
}
void showMemoryInfo()
{
partion *ptr = head;
puts("\n\n---------------------------------------------");
puts("總內(nèi)存分配情況如下:");
puts("---------------------------------------------");
puts("序號(hào)ID****開始地址****結(jié)束地址****內(nèi)存大小****狀態(tài)****");
while (ptr != NULL)
{
printf("%-12d%-12d%-12d%-12d",ptr->id,ptr->addr_front,ptr->addr_end,ptr->size);
// printf("序號(hào)id:%21d%10c\n開始地址:%10d%10c\n", ptr->id, '|', ptr->addr_front, '|');
//printf("結(jié)束地址:%10d%10c\n", ptr->addr_end, '|');
//printf("內(nèi)存大小:%11d%10c\n", ptr->size, '|');
printf("%-12s\n", ptr->flag == 0 ? "空閑" : "已分配");
puts("-----------------------------------------------------");
ptr = ptr->next;
}
puts("---------------------------------------------\n\n");
}
void assign(partion *ptr, int need)
{
if (need == ptr->size)//空閑的空間恰好等同需要的空間
{
ptr->flag = 1;
return;
}
//空閑的空間大于需要的空間
partion *assigned = createPartion(ptr->id, ptr->addr_front, need, 1);
assigned->next = ptr;
assigned->front = ptr->front;
changeIdValue(ptr, 1);//把后面的節(jié)點(diǎn)的id值都增加1
ptr->addr_front += need;
ptr->size -= need;
if (ptr->front != NULL)//空閑區(qū)的頭不空，就在前一個(gè)節(jié)點(diǎn)后面添加分配的節(jié)點(diǎn)
{
ptr->front->next = assigned;
}
else//空閑節(jié)點(diǎn)前沒有節(jié)點(diǎn)
{
head = assigned;
}
ptr->front = assigned;//空閑節(jié)點(diǎn)的頭指向新分配的
}
void recovery()
{
printf("請(qǐng)輸入需要回收作業(yè)的ID號(hào)：");
int id, flag = 0;
scanf("%d", &id);
partion *ptr = head;
while (ptr != NULL)
{
if (id == ptr->id)
{
flag = 1;
break;
}
ptr = ptr->next;
}
if (flag == 0)
{
puts("沒有找到你需要回收的作業(yè)！");
return;
}
if (ptr->flag == 0)
{
puts("該ID已經(jīng)是空閑的了");
return;
}
if (ptr->front == NULL)
{
//第一個(gè)分區(qū)
if (ptr->next == NULL || ptr->next->flag == 1)
{
//后面不空或后面沒有
ptr->flag = 0;
return;
}
if (ptr->next->flag == 0)
{
//后面空
ptr->size += ptr->next->size;
ptr->flag = 0;//標(biāo)記為空閑
if (ptr->next->next != NULL)//把下一個(gè)節(jié)點(diǎn)的頭指向該節(jié)點(diǎn)
{
ptr->next->next->front = ptr;
}
ptr->next = ptr->next->next;//合并兩個(gè)節(jié)點(diǎn)
free(ptr->next);//真實(shí)釋放節(jié)點(diǎn)
return;
}
}
if (ptr->next == NULL)
{
//最后一個(gè)分區(qū)
if (ptr->front == NULL || ptr->front->flag == 1)
{
//前面不空或者前沒有
ptr->flag = 0;
return;
}
if (ptr->front->flag == 0)
{
//前面為空
ptr->front->size += ptr->size;
ptr->front->next = NULL;
free(ptr);
return;
}
}
if (ptr->front->flag == 0 && ptr->next->flag == 0)
{
//上下都空
ptr->front->size += ptr->size + ptr->next->size;
ptr->front->next = ptr->next->next;
if (ptr->next->next != NULL)
{
ptr->next->next->front = ptr->front;
}
changeIdValue(ptr->front->next, -2); //更改id
free(ptr->next);
free(ptr);
return;
}
if (ptr->front->flag == 0 && ptr->next->flag == 1)
{
//上空下不空
ptr->front->size += ptr->size;
ptr->front->next = ptr->next;
ptr->next->front = ptr->front;
changeIdValue(ptr->front->next, -1);
free(ptr);
return;
}
if (ptr->front->flag == 1 && ptr->next->flag == 0)
{
//上不空下空
ptr->size += ptr->next->size;
if (ptr->next->next != NULL)
{
ptr->next->next->front = ptr;
}
partion *p_next = ptr->next; //保存一下下方為空的那個(gè)分區(qū)，以便一會(huì)釋放
ptr->next = ptr->next->next;
ptr->flag = 0;
changeIdValue(ptr->next, -1);
free(p_next);
return;
}
if (ptr->front->flag == 1 && ptr->next->flag == 1)
{
//上下都不空
ptr->flag = 0;
return;
}
}
void changeIdValue(partion *ptr, int delta)
{
while (ptr != NULL)
{
ptr->id += delta;
ptr = ptr->next;
}
}
4.運(yùn)行截圖
首次適應(yīng)算法
開始
（1）作業(yè)1 申請(qǐng)130 KB
（2）作業(yè)2 申請(qǐng)60 KB
（3）作業(yè)3 申請(qǐng)100 KB
（4）作業(yè)2 釋放60 KB
（5）作業(yè)3 釋放100 KB
（6）作業(yè)1 釋放130 KB
最佳適應(yīng)算法
開始：
（1）作業(yè)1 申請(qǐng)130 KB
（2）作業(yè)2 申請(qǐng)60 KB
（3）作業(yè)3 申請(qǐng)100 KB
（4）作業(yè)2 釋放60 KB
（5）作業(yè)3 釋放100 KB
（6）作業(yè)1 釋放130 KB
5.程序說(shuō)明
總流程圖：
總流程圖是提供程序開始運(yùn)行的界面圖，供用戶選擇，其中用戶可以選擇的選項(xiàng)有，首次適應(yīng)算法，最佳適應(yīng)算法，內(nèi)存回收，內(nèi)存作業(yè)的顯示。每選擇一個(gè)功能就執(zhí)行相應(yīng)的函數(shù)代碼。
首次適應(yīng)算法流程圖：
首次適應(yīng)算法，首先用戶輸入作業(yè)需要的內(nèi)存大小，然后程序從低地址向高地址尋找空間空間，如果找到空閑空間，如果空閑空間的大小比作業(yè)需要的空間大則進(jìn)行分配，如果空閑空間比作業(yè)需要的空間小，則繼續(xù)尋找下一個(gè)空閑空間。如果所有的空閑空間都尋找完也沒有符合要求的，那么作業(yè)的內(nèi)存分配失敗。
最佳適應(yīng)算法流程圖
最佳適應(yīng)算法，首頁(yè)用戶輸入作業(yè)需要的內(nèi)存空間，程序從低地址開始尋找空閑空間，如果第一次找合適的空間分配，就臨時(shí)存儲(chǔ)這個(gè)空間地址，繼續(xù)向下繼續(xù)尋找符合的地址空間，如果尋找到合適的空間空間范圍，且新的空間大小比臨時(shí)存儲(chǔ)的空間大小還小，則新的符合空間更新為臨時(shí)符合空間，依次類推到最后。如果程序沒有臨時(shí)最佳的地址空間，則并沒有分配到內(nèi)存，所以作業(yè)內(nèi)存分配失敗。如果有臨時(shí)最佳空間地址，則把最佳的地址空間分配給作業(yè)。
內(nèi)存回收流程圖：
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-450471.html
作業(yè)回收，首先需要需要輸入回收作業(yè)的ID，先判斷作業(yè)ID是否存在，存在才能進(jìn)行釋放，在ID存在的前提下判斷，該ID的作業(yè)狀態(tài)，只有為已分配狀態(tài)猜才進(jìn)行釋放。釋放則的分情況討論。釋放的節(jié)點(diǎn)分為頭部，中間，尾部。如果釋放的節(jié)點(diǎn)前后已經(jīng)有空閑空間，就需要進(jìn)行合并。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-450471.html
到了這里，關(guān)于Ubuntu22.2下C語(yǔ)言編程實(shí)現(xiàn)，首次，最佳適應(yīng)算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
