#include
using?namespace?std;
enum?Status{FREEBUSYOKERROR};
struct?PST
{//partition?specification?table
	int?ID;//分區號
	int??addr;//起始地址
	int?size;//分區長度
	Status?state;//狀態
};
struct?Node
{//雙向鏈表結點
	PST?data;
	Node?*back;//前驅
	Node?*next;//后繼
	Node（）
	{
		back=NULL;
		next=NULL;
	}
	Node（int?idint?size）
	{
		data.ID=id;
		data.size=size;
		back=NULL;
		next=NULL;
	}
};
int?area;//輸入內存空間
Node?*head*last;//表頭指針和表尾指針
void?Init（int?area）
{
	head=new?Node（）;
	last=new?Node（）;
	head->next=last;
	head->data.ID=-1;
	head->data.addr=-1;
	head->data.size=0;
	last->back=head;
	last->data.addr=0;
	last->data.ID=0;
	last->data.size=area;
	last->data.state=FREE;
}
Status?FFA（int?idint?size）
{//First?fit?algorithm
	Node?*temp=new?Node（idsize）;
	temp->data.state=BUSY;
	Node?*cur=head->next;
	while（cur）
	{
		if（cur->data.state==FREE&&cur->data.size==size）
		{//如果空閑塊大小剛好與請求大小相等直接分配?
			cur->data.ID=id;
			cur->data.state=BUSY;
			return?OK;
			break;
		}
		if（cur->data.state==FREE&&cur->data.size>size）
		{//如果大于
			temp->back=cur->back;
			temp->next=cur;
			cur->back->next=temp;
			temp->data.addr=cur->data.addr;
			cur->back=temp;
			cur->data.addr=cur->data.addr+size;
			cur->data.size=cur->data.size-size;
			return?OK;
			break;
		}
		cur=cur->next;
	}
	return?ERROR;
	
}
Status?BFA（int?idint?size）
{//Best?fit?algorithm
	Node?*temp=new?Node（idsize）;
	temp->data.state=BUSY;
	int?min;//記錄符合滿足請求的最小空閑塊大小
	Node?*fit;//指向采用最佳適應算法的插入位置
	Node?*cur=head->next;
	while（cur）
	{//取得第一個可以分配的位置（不一定是最佳位置）
		if（cur->data.state==FREE&&cur->data.size>=size）
		{
			fit=cur;
			min=cur->data.size;
			break;
		}
		cur=cur->next;
	}
	while（cur）
	{
		if（cur->data.state==FREE&&cur->data.size==size）
		{//如果相等直接分配?
			cur->data.state=BUSY;
			cur->data.ID=id;
			return?OK;
			break;
		}
		if（cur->data.state==FREE&&cur->data.size>size）
		{//獲取最佳位置
			if（cur->data.size			{
				min=cur->data.size;
				fit=cur;
			}
		}
		cur=cur->next;
	}
	if（fit）
	{//若最佳，插入
		temp->back=fit->back;
		temp->next=fit;
		fit->back->next=temp;
		temp->data.addr=fit->data.addr;
		fit->back=temp;
		fit->data.addr=fit->data.addr+size;
		fit->data.size=fit->data.size-size;
		return?OK;
	}
	else
	return?ERROR;
}
Status?WFA（int?idint?size）
{//worst?fit?algorithm
	Node?*temp=new?Node（idsize）;
	temp->data.state=BUSY;
	int?max;//記錄符合滿足請求的最大空閑塊大小
	Node?*fit;//指向采用最壞適應算法的插入位置
	Node?*cur=head->next;
	while（cur）
	{//取得第一個可以分配的位置（不一定是最佳位置）
		if（cur->data.state==FREE&&cur->data.size>=size）
		{
			fit=cur;
			max=cur->data.size;
			break;
		}
		cur=cur->next;
	}
	while（cur）
	{
		if（cur->data.state==FREE&&cur->data.size>size）
		{//獲取最佳位置
			if（cur->data.size>max）
			{
				max=cur->data.size;
				fit=cur;
			}
		}
		cur=cur->next;
	}
	if（fit）
	{//若最佳，插入
		temp->back=fit->back;
		temp->next=fit;
		fit->back->next=temp;
		fit->back=temp;
		temp->d

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????430080??2012-01-11?15:10??模擬設計動態分區存儲管理的分配與回收11.doc

?????文件???????6797??2012-01-10?22:48??模擬設計動態分區存儲管理的分配與回收.cpp

-----------?---------??----------?-----??----

???????????????436877????????????????????2