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

//********?????????????動態分區分配方式的模擬???????????*********

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

?

#include

#include

?

#define?Free?0?//空閑狀態

#define?Busy?1?//已用狀態

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

#define?ERROR?0?//出錯

#define?MAX_length?640?//最大內存空間為640KB

typedef?int?Status;

?

typedef?struct?freearea//定義一個空閑區說明表結構

{

????int?ID;???//分區號

????long?size;???//分區大小

????long?address;?//分區地址

????int?state;???//狀態

}ElemType;

?

//----------??線性表的雙向鏈表存儲結構??------------

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

{

????ElemType?data;?

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

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

}DuLNode*DulinkList;

?

DulinkList?block_first;?//頭結點

DulinkList?block_last;??//尾結點

?

Status?alloc（int）;//內存分配

Status?free（int）;?//內存回收

Status?First_fit（intint）;//首次適應算法

Status?Best_fit（intint）;?//最佳適應算法

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

Status?Initblock（）;//開創空間表

?

Status?Initblock（）//開創帶頭結點的內存空間鏈表

{

????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<<“請輸入作業（分區號）：“;?

????cin>>ID;

????cout<<“請輸入需要分配的主存大?。▎挝?KB）：“;?

????cin>>request;

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

????{

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

????}

?

????if（ch==2）?//選擇最佳適應算法

????{

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

????}

????else?//默認首次適應算法

????{

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

????}

}

//------------------?首次適應算法?-----------------------

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

{

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

????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;

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