#include<stdlib.h>
#include<iomanip.h>

#define n 10  //假定系統允許的最大進程數為n
#define m 2  //假定系統允許的空閑表最大為m
#define min 100 //空閑表被分配時，如果分配后剩余的空間小于min，則將該空閑表全部分配，若大于min，則切割分配

struct 
{ 
float address;  //空閑表起始地址
float length;  //空閑表長度，單位為字節
int sign;   //空閑表登記欄標志，用"0"表示空欄目，用"1"表示未分配
}free_table[m];  //空閑表

struct 
{ 
float address;  //分配表起始地址
float length;  //分配表長度，單位為字節
int sign;   //分配表登記欄標志，用"0"表示空欄目
}used_table[n];  //分配表

void allocate(char task,float size) //給進程(task)，采用最佳分配算法分配(size)大小的空間
{ 
 int i,k; 
 float ad; 
 k=-1; 
 for(i=0;i<m;i++)
  if(free_table[i].length>=size&&free_table[i].sign==1) 
   if(k==-1||free_table[i].length<free_table[k].length) 
   k=i; 
   if(k==-1)
   { 
	cout<<"無可用空閑區，請重新輸入!"<<endl;
    return; 
   } 

 if(free_table[k].length-size<=min) 
 { 
  free_table[k].sign=0; 
  ad=free_table[k].address; 
  size=free_table[k].length; 
 } 
 else 
 { 
  free_table[k].length=free_table[k].length-size; 
  ad=free_table[k].address+free_table[k].length; 
 } 
 
 //修改分配表
 i=0; 
 while(used_table[i].sign!=0&&i<n) //尋找空表目
  i++; 
 if(i>=n) 
 { 
  cout<<"無表目填寫已分分區，錯誤"<<endl;

  //修正空閑表
  if(free_table[k].sign==0) 
   free_table[k].sign=1; 
  else 
   {
    free_table[k].length=free_table[k].length+size; 
    return; 
   } 
 } 
 else 
 {//修改分配表
  used_table[i].address=ad; 
  used_table[i].length=size; 
  used_table[i].sign=task; 
 } 
 return; 
}//內存分配函數結束

void reclaim(char task) 
//釋放進程名為task的進程所占內存空間
{ 
 int i,k,j,s,t; 
 float S,L; 
 s=0; 
 while((used_table[s].sign!=task||used_table[s].sign==0)&&s<n) 
  s++; 
 if(s>=n)
 { 
  cout<<"找不到該進程，重新輸入!"<<endl;
  return; 
 } 

 //修改分配表 
 used_table[s].sign=0; 

 //取得歸還分區的起始地址S和長度L
 S=used_table[s].address; 
 L=used_table[s].length; 
 j=-1;k=-1;i=0; 

 while(i<m&&(j==-1||k==-1)) 
 { 
  if(free_table[i].sign==1) 
  { 
   if(free_table[i].address+free_table[i].length==S)k=i;//找到上鄰
   if(free_table[i].address==S+L)j=i;//找到下鄰
  } 
  i++; 
 } 

 if(k!=-1) 
  if(j!=-1) 
  { 
   free_table[k].length=free_table[j].length+free_table[k].length+L; 
   free_table[j].sign=0; 
  } 
  else 
   free_table[k].length=free_table[k].length+L; 
 else 
  if(j!=-1) 
  { 
   free_table[j].address=S; 
   free_table[j].length=free_table[j].length+L; 
  } 
  else 
  { 
   t=0; 
   while(free_table[t].sign==1&&t<m) 
    t++; 
   if(t>=m)//空閑表已滿,釋放內存失敗,將分配表復原
   { 
	cout<<"內存空閑表沒有空間,釋放內存失敗"<<endl;
    used_table[s].sign=task; 
    return; 
   } 
   free_table[t].address=S; 
   free_table[t].length=L; 
   free_table[t].sign=1; 
  } 
 return; 
}//釋放內存函數結束

int main( ) 
{ 
 int i,select; 
 float SIZE; 
 char task; 

 //空閑分配表初始化：
 free_table[0].address=10240; //起始地址假定為10240
 free_table[0].length=10240;  //長度假定為10240
 free_table[0].sign=1;   //初始空閑表為一個整體空閑表
 
 for(i=1;i<m;i++) 
  free_table[i].sign=0;  //其余空閑表項未被使用

 for(i=0;i<n;i++) 
  used_table[i].sign=0;  //初始時均未分配

 while(true) 
 { 
  cout<<"★★★★★★★★★★★★★★  驗證實現存儲器管理  ★★★★★★★★★★★★★"<<endl;
  cout<<endl;
  cout<<"          1、申請內存"<<endl;
  cout<<"          2、釋放內存"<<endl;
  cout<<"          3、顯示主存"<<endl;
  cout<<"          4、退出程序"<<endl;
  cout<<endl;
  cout<<"根據以上的提示，請選擇(1—4)： "; 
  cin>>select;
  switch(select) 
  { 
   case 1:   
	 cout<<endl;
     cout<<"申請內存空間的進程名task= ";
	 cin>>task;
	 cout<<endl;
	 cout<<"需要為該進程申請的空間size= ";
	 cin>>SIZE;
	 cout<<endl;
     allocate(task,SIZE); 
     break; 

   case 2:     
     cout<<endl;
	 cout<<"輸入要釋放內存的進程名task= ";
	 cin>>task;
     reclaim(task); 
     break; 

case 3:    
         //輸出內存空閑表和內存分配表
     cout<<endl;
	 cout<<"         ★內存空閑表情況★"<<endl;
	 cout<<"     起始地址  空間長度  標志"<<endl;
     for(i=0;i<m;i++)      
	 cout<<setw(10)<<free_table[i].address<<setw(10)<<free_table[i].length<<setw(7)<<free_table[i].sign<<endl;
	 cout<<"         ★內存分配表情況★："<<endl;
	 cout<<"     起始地址  申請長度  標志"<<endl;
     for(i=0;i<n;i++) 
      if(used_table[i].sign!=0)      
	   cout<<setw(10)<<used_table[i].address<<setw(10)<<used_table[i].length<<setw(7)<<(char) used_table[i].sign<<endl;
      else     
	  cout<<setw(10)<<used_table[i].address<<setw(10)<<used_table[i].length<<setw(7)<<used_table[i].sign<<endl;
     break; 
   case 4: exit(0); 
	   break;

   default:cout<<"沒有該選項，請重新輸入"<<endl;
  }/*case*/ 
 }/*while*/ 

 return 1;

}//主函數結束