//***************************************************************

//********?????????????動態(tài)分區(qū)分配方式的模擬???????????*********

//***************************************************************

?

#include

#include

?

#define?Free?0?//空閑狀態(tài)

#define?Busy?1?//已用狀態(tài)

#define?OK?1????//完成

#define?ERROR?0?//出錯

#define?MAX_length?640?//最大內(nèi)存空間為640KB

typedef?int?Status;

?

typedef?struct?freearea//定義一個空閑區(qū)說明表結(jié)構(gòu)

{

????int?ID;???//分區(qū)號

????long?size;???//分區(qū)大小

????long?address;?//分區(qū)地址

????int?state;???//狀態(tài)

}ElemType;

?

//----------??線性表的雙向鏈表存儲結(jié)構(gòu)??------------

typedef?struct?DuLNode?//double?linked?list

{

????ElemType?data;?

????struct?DuLNode?*prior;?//前趨指針

????struct?DuLNode?*next;??//后繼指針

}DuLNode*DulinkList;

?

DulinkList?block_first;?//頭結(jié)點

DulinkList?block_last;??//尾結(jié)點

?

Status?alloc（int）;//內(nèi)存分配

Status?free（int）;?//內(nèi)存回收

Status?First_fit（intint）;//首次適應(yīng)算法

Status?Best_fit（intint）;?//最佳適應(yīng)算法

void?show（）;//查看分配

Status?Initblock（）;//開創(chuàng)空間表

?

Status?Initblock（）//開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表

{

????block_first=（DulinkList）malloc（sizeof（DuLNode））;

????block_last=（DulinkList）malloc（sizeof（DuLNode））;

????block_first->prior=NULL;

????block_first->next=block_last;

????block_last->prior=block_first;

????block_last->next=NULL;

????block_last->data.address=0;

????block_last->data.size=MAX_length;

????block_last->data.ID=0;

????block_last->data.state=Free;

????return?OK;

}

?

//-----------------------?分?配?主?存?-------------------------

Status?alloc（int?ch）

{

????int?IDrequest;

????cout<<“請輸入作業(yè)（分區(qū)號）：“;?

????cin>>ID;

????cout<<“請輸入需要分配的主存大小（單位:KB）：“;?

????cin>>request;

????if（request<0?||request==0）?

????{

????????cout<<“分配大小不合適，請重試！“<
????????return?ERROR;

????}

?

????if（ch==2）?//選擇最佳適應(yīng)算法

????{

????????if（Best_fit（IDrequest）==OK）?cout<<“分配成功！“<
????????else?cout<<“內(nèi)存不足，分配失敗！“<
????????return?OK;

????}

????else?//默認首次適應(yīng)算法

????{

????????if（First_fit（IDrequest）==OK）?cout<<“分配成功！“<
????????else?cout<<“內(nèi)存不足，分配失敗！“<
????????return?OK;

????}

}

//------------------?首次適應(yīng)算法?-----------------------

Status?First_fit（int?IDint?request）//傳入作業(yè)名及申請量

{

????//為申請作業(yè)開辟新空間且初始化

????DulinkList?temp=（DulinkList）malloc（sizeof（DuLNode））;?

????temp->data.ID=ID;?

????temp->data.size=request;

????temp->data.state=Busy;

?

????DuLNode?*p=block_first->next;

????while（p）

????{

????????if（p->data.state==Free?&&?p->data.size==request）

????????{//有大小恰好合適的空閑塊

????????????p->data.state=Busy;

????????????p->data.ID=ID;

????????????return?OK;

????????????break;

????????}

????????if（p->data.state==Free?&&?p->data.size>request）

????????{//有空閑塊能滿足需求且有剩余“

????????????temp->prior=p->prior;

????????????temp->next=p;??????

????????????temp->data.address=p->data.address;

????????????