#include <iostream> 
#include <stdlib.h> 
#include <time.h> 
using namespace std; 
struct memory 
{ 
struct memory *former; 
int address;//地址 
int num;//作業號 
int size;//分配內存大小 
int state;//狀態0表示空閑1表示已分配 
struct memory *next; 
}; 
typedef struct memory MEMORY; 
MEMORY *mem; 
const int size_min=10;//內存允許的最小空閑塊的大小 
bool is_optimist=false;//判斷是否是最佳適應算法 

void init(); 
void FF(); 
void alloc(MEMORY *,MEMORY *);//首次適應算法分配內存 
void free(MEMORY *);//首次適應算法回收內存 
void sort(MEMORY *);//對內存鏈進行排序 
void insert(MEMORY *,MEMORY *); 
void free_optimist(MEMORY *); 
void print(MEMORY *);//打印內存鏈 
void main() 
{ 
int i=0; 
while(1) 
{ 
cout<<("\nPlease select a number(1,2,0)"); 
cout<<("\n 1--首次適應算法"); 
cout<<"\n 2--最佳適應算法"<<endl; 
cout<<" 0--中止程序"<<endl; 
cin>>i; 

if(i==1) 
{ 
cout<<("\nThis is an example for FF:\n"); 
is_optimist=false; 
init(); 
FF(); 
} 
else if(i==2) 
{ 
cout<<"\nThis is an example for optimist method;\n"; 
is_optimist=true; 
init(); 
FF(); 

} 
else if(i==0) 
{ 
exit(1); 
} 
} 
} 
void init() 
{ 
mem=new MEMORY; 
mem->size=640; 
//mem->state=0; 
mem->former=0; 
mem->next=0; 
} 
void FF()//首次適應算法 
{ 
int i; 
int work[]={130,60,100,200,140,60,50};//作業序列 
//int assignment; 
MEMORY *running; 
for(i=0;i<sizeof(work)/sizeof(int);i++) 
{ 
running=(MEMORY *)malloc(sizeof(MEMORY));//初始化作業 
if(running!=NULL) 
{ 
running->former=NULL; 
running->address=0; 
running->num=i+1; 
running->size=work[i]; 
running->state=0; 
running->next=NULL; 
//cout<<"作業初始化成功"<<running->num<<endl; 
if(is_optimist==true)//最佳適應算法 
{ 
//cout<<"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"<<endl; 
alloc(mem,running); 
} 
else//首次適應算法 
{ 
alloc(mem,running); 
} 
print(mem); 
cout<<endl; 
} 
else 
cout<<"沒有足夠的內存空間"<<endl; 


if(rand()%3==1) 
{ 
if(is_optimist==false)//首次適應算法 
{ 
free(mem); 
} 
else//最佳適應算法 
{ 
::free_optimist(mem); 
} 
} 
} 
} 
void free(MEMORY *ptr)//作業處理完后釋放內存空間 
{ 
MEMORY *previous,*current; 
previous=ptr; 
current=previous->next; 
while(current!=NULL) 
{ 
if(current->state==1&&rand()%3==1) 
{ 
break; 
} 
previous=current; 
current=current->next; 
} 
if(current==NULL) 
{ 
//cout<<"內存中沒有任何作業！！！"<<endl; 
return; 
} 
else if(current->next==NULL) 
{ 
if(previous->state==0) 
{ 
MEMORY *temp; 
temp=current; 
previous->size=previous->size+current->size; 
previous->next=NULL; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp; 
print(mem); 
} 
else 
{ 
current->state=0; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
print(mem); 
} 
} 
else if((current->next)->next==NULL) 
{ 
if(previous->state==0&&(current->next)->state==0) 
{ 
MEMORY *temp1,*temp2; 
temp1=current; 
temp2=current->next; 
previous->size=previous->size+current->size+(current->next)->size; 
previous->next=NULL; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp1; 
delete temp2; 
print(mem); 
} 
else if(previous->state==0)//釋放的地址空間前面有空閑塊則把它和前面的合并 
{ 
MEMORY *temp; 
temp=current; 
previous->size=previous->size+current->size; 
(current->next)->former=previous; 
previous->next=current->next; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp; 
print(mem); 
} 
else if((current->next)->state==0)//釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并 
{ 
MEMORY *temp; 
temp=current->next; 
current->size=current->size+(current->next)->size; 
current->state=0; 
current->next=NULL; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 

delete temp; 
print(mem); 

} 
else//處理完的作業前后都沒有空閑塊時直接把它的狀態改為沒分配 
{ 
current->state=0; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
print(mem); 
} 

} 
else 
{ 
if(previous->state==0&&(current->next)->state==0) 
{ 
MEMORY *temp1,*temp2; 
temp1=current; 
temp2=current->next; 
previous->size=previous->size+current->size+(current->next)->size; 
((current->next)->next)->former=previous; 
previous->next=(current->next)->next; 

cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp1; 
delete temp2; 
print(mem); 
} 
else if(previous->state==0)//釋放的地址空間前面有空閑塊則把它和前面的合并 
{ 
MEMORY *temp; 
temp=current; 
previous->size=previous->size+current->size; 
(current->next)->former=previous; 
previous->next=current->next; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp; 
print(mem); 
} 
else if((current->next)->state==0)//釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并 
{ 
MEMORY *temp; 
temp=current->next; 
current->size=current->size+(current->next)->size; 
current->state=0; 
((current->next)->next)->former=current; 
current->next=(current->next)->next; 

cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 

delete temp; 
print(mem); 

} 
else//處理完的作業前后都沒有空閑塊時直接把它的狀態改為沒分配 
{ 
current->state=0; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
print(mem); 
} 
} 
} 

void alloc(MEMORY *ptr,MEMORY *assign)//內存分配 
{ 
if(ptr->next==NULL)//內存沒有作業運行 
{ 
if(ptr->size>=assign->size)//內存空間大于作業所需空間 
{ 
ptr->size=ptr->size-assign->size;//為內存分配空間 
assign->state=1; 
ptr->next=assign; 
assign->former=ptr; 

cout<<"作業 "<<(assign->num)<<"申請"<<(assign->size)<<" "<<"k的內存空間"<<endl; 
} 
else 
{ 
cout<<"沒有足夠的內存空間為作業"<<(assign->num)<<"分配"<<endl; 
delete assign; 
} 
} 
else//內存中如果已經分配了空間 
{ 
MEMORY *previous,*current; 
previous=ptr; 
current=previous->next; 
while(current!=NULL) 
{ 
if(current->size>assign->size&current->state==0)//如果當前內存空間大于作業所需空間并且內存沒有被分配 
{ 
break; 
} 
previous=current; 
current=current->next; 
} 

if(current==NULL)//空閑鏈中沒有為作業分配所需的空間 
{ 

if(ptr->size>=assign->size)//內存中還有足夠沒分配的空間為此作業分配 
{ 
assign->address =640-(ptr->size);//max+size_offset;//作業在內存中的首地址 
ptr->size=ptr->size-assign->size; 
assign->state=1; 
assign->former=previous; 
previous->next=assign; 


cout<<"作業 "<<(assign->num)<<"申請"<<(assign->size)<<" "<<"k的內存空間"<<endl; 
} 
else 
{ 
cout<<"沒有足夠的內存空間為作業"<<(assign->num)<<"分配"<<endl; 
} 
} 
else//空閑鏈中有可為此作業分配的空間 
{ 

if((current->size-assign->size)<=size_min)//空閑鏈所具備的空間與作業所需空間大小差不多時 
{ //直接把整個空閑塊的空間分配給作業否則從空閑塊中 
current->num=assign->num; //劃出與作業等同的空間 
current->state=1; 
delete assign;//free(assign); 

cout<<"作業 "<<(current->num)<<"申請"<<(current->size)<<" "<<"k的內存間"<<endl; 
} 
else//從空閑塊中劃分一塊與作業大小等同的空間 
{ 
current->size=current->size-assign->size; 
assign->state=1; 
assign->address=current->address+current->size; 

if(current->next==NULL)//此要分配的空間是空閑鏈的最后一個元素 
{ 
assign->former=current; 
current->next=assign; 
} 
else 
{ 
assign->next=current->next; 
(current->next)->former=assign; 
assign->former=current; 
current->next=assign; 
} 
cout<<"作業 "<<(assign->num)<<"申請"<<(assign->size)<<" "<<"k的內存空間"<<endl; 
} 
} 

} 

if((ptr->next)->next!=NULL&&is_optimist==true) 
sort(ptr);//排序由空閑塊從小到大 
//print(ptr); 

} 
void sort(MEMORY *ptr) 
{ 
MEMORY *temp=new MEMORY; 
temp->next=0; 
temp->former=0; 

while(ptr->next) 
{ 
if((ptr->next)->next==NULL)//內存鏈中只有兩個元素 
{ 
MEMORY *p; 
p=ptr->next; 
ptr->next=NULL; 
insert(temp,p); 
} 
else//內存鏈中有多個元素 
{ 
MEMORY *p; 
p=ptr->next; 
p->former=ptr; 
ptr->next=p->next; 
(p->next)->former=ptr; 
insert(temp,p); 
} 

} 
ptr->next=temp->next; 
(temp->next)->former=ptr; 
delete temp; 
} 
void insert(MEMORY *queue,MEMORY *item) 
{ 
MEMORY *previous,*current; 
previous=queue; 
current=previous->next; 
while(current!=NULL && item->size>=current->size) 
{ 
previous=current; 
current=current->next; 
} 

if(previous==queue)//所要插入的元素最小 
{ 

if(queue->next==NULL)//內存鏈中只有一個元素 
{ 
item->next=0; 
queue->next=item; 
item->former=queue; 
} 
else//內存鏈中有多個元素 
{ 
item->next=queue->next; 
(queue->next)->former=item; 
item->former=queue; 
queue->next=item; 
} 
} 
else//定位到要插入的元素 
{ 
item->next=current; 
item->former=previous; 
if(current==NULL) 
{ 
previous->next=item; 
} 
else 
{ 
current->former=item; 
previous->next=item; 
} 

} 
} 
void free_optimist(MEMORY *ptr) 
{ 
MEMORY *previous,*current; 
previous=ptr; 
current=previous->next; 
while(current!=NULL) 
{ 
if(current->state==1&&rand()%3==1) 
{ 
break; 
} 
previous=current; 
current=current->next; 
} 
if(current==NULL) 
{ 
//cout<<"內存中沒有任何作業！！！"<<endl; 
return; 
} 
else if(current->next==NULL) 
{ 
if(previous->state==0&&((previous->address+previous->size)==current->address)) 
{ 
MEMORY *temp; 
temp=current; 
previous->size=previous->size+current->size; 
previous->next=NULL; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp; 
print(mem); 
} 
else 
{ 
current->state=0; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
print(mem); 
} 
} 
else if((current->next)->next==NULL) 
{ 
if(previous->state==0&&(current->next)->state==0&&((previous->address+previous->size)==current->address)&&((current->size+current->address)==(current->next)->address)) 
{ 
MEMORY *temp1,*temp2; 
temp1=current; 
temp2=current->next; 
previous->size=previous->size+current->size+(current->next)->size; 
previous->next=NULL; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp1; 
delete temp2; 
print(mem); 
} 
else if(previous->state==0&&((previous->address+previous->size)==current->address))//釋放的地址空間前面有空閑塊則把它和前面的合并 
{ 
MEMORY *temp; 
temp=current; 
previous->size=previous->size+current->size; 
(current->next)->former=previous; 
previous->next=current->next; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp; 
print(mem); 
} 
else if((current->next)->state==0&&((current->size+current->address)==(current->next)->address))//釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并 
{ 
MEMORY *temp; 
temp=current->next; 
current->size=current->size+(current->next)->size; 
current->state=0; 
current->next=NULL; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 

delete temp; 
print(mem); 
} 
} 
else 
{ 
if(previous->state==0&&(current->next)->state==0&&((previous->address+previous->size)==current->address)&&((current->size+current->address)==(current->next)->address)) 
{ 
MEMORY *temp1,*temp2; 
temp1=current; 
temp2=current->next; 
previous->size=previous->size+current->size+(current->next)->size; 
((current->next)->next)->former=previous; 
previous->next=(current->next)->next; 

cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp1; 
delete temp2; 
print(mem); 
} 
else if(previous->state==0&&(previous->address+previous->size)==current->address)//釋放的地址空間前面有空閑塊則把它和前面的合并 
{ 
MEMORY *temp; 
temp=current; 
previous->size=previous->size+current->size; 
previous->state=0; 
(current->next)->former=previous; 
previous->next=current->next; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
delete temp; 
print(mem); 
} 
else if((current->next)->state==0&&((current->size+current->address)==(current->next)->address))//釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并 
{ 
MEMORY *temp; 
temp=current->next; 
current->size=current->size+(current->next)->size; 
current->state=0; 
((current->next)->next)->former=current; 
current->next=(current->next)->next; 

cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 

delete temp; 
print(mem); 

} 
else//處理完的作業前后都沒有空閑塊時直接把它的狀態改為沒分配 
{ 
current->state=0; 
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; 
print(mem); 
} 
} 
if((ptr->next)->next!=NULL) 
sort(ptr);//排序由空閑塊從小到大 
} 
void print(MEMORY *ptr) 
{ 
MEMORY *temp; 
temp=ptr->next; 
cout<<"\n內存鏈的狀態為："<<endl; 
while(temp!=NULL) 
{ 
cout<<"分配的地址為："<<temp->address<<" 分配的空間："<<temp->size<<"k" 
<<" 運行的作業號:"<<temp->num; 
if(temp->state==0) 
{ 
cout<<" 內存空閑"; 
} 
else 
{ 
cout<<" 內存已分配"; 
} 
cout<<endl; 
temp=temp->next; 
} 
}