#include <iostream.h>
int work[10][2]; //作业名字 大小
int idle[10][2]; //空闲区大小 地址
int free[10][3]; //已分配区域的名字 地址 大小
int num=0,b=1,d,ch1,ch2;
void init(){
idle[0][0]=1;idle[0][1]=100;
free[0][0]=0;free[1][1]=0;free[1][2]=0;
work[0][0]=0;work[0][1]=0;
for(int i=1;i <=9;i++){ //初始化数组
idle[i][0]=0;idle[i][1]=0;
free[i][0]=0;free[i][1]=0;free[i][2]=0;
work[i][0]=0;work[i][1]=0;
}
}
void jishu(){ //求空闲单元数
for(int i=0;i <9;i++)
if(idle[i][1]!=0)
num++;
}
void jishu1(){ //求作业数
for(int i=0;i <9;i++)
if(work[i][1]!=0)
b++;
}
void zuixian(){ //最先适应法
jishu();
for(int i=0;i <num;i++){
for(int j=i;j <num-i-1;j++){
if(idle[j][0]>idle[j+1][0]){
int temp=idle[j][0];
idle[j][0]=idle[j+1][0];
idle[j+1][0]=temp;
temp=idle[j][1];
idle[j][1]=idle[j+1][1];
idle[j+1][1]=temp;
}
}
}
}
void zuijia(){ //最佳适应法
num=0;
jishu();
for(int i=0;i <num;i++){
for(int j=i;j <num-i-1;j++){
if(idle[j][1]>idle[j+1][1]){
int temp=idle[j][0];
idle[j][0]=idle[j+1][0];
idle[j+1][0]=temp;
temp=idle[j][1];
idle[j][1]=idle[j+1][1];
idle[j+1][1]=temp;
}
}
}
}
void zuihuai(){ //最坏适应法
num=0;
jishu();
for(int i=0;i <num;i++){
for(int j=i;j <num-i-1;j++){
if(idle[j][1] <idle[j+1][1]){
int temp=idle[j][0];
idle[j][0]=idle[j+1][0];
idle[j+1][0]=temp;
temp=idle[j][1];
idle[j][1]=idle[j+1][1];
idle[j+1][1]=temp;
}
}
}
}
void huishou(int name){ //回收进程函数
num=0;
b=0;
jishu();
jishu1();
int c=-1;
for(int k=0;k <=b;k++){
if(free[k][0]==name){
c=k;
break;
}
}
if(c==-1)cout <<"要回收的作业不存在！" <<endl;
else{
for(int i=0;i <num;i++){ //将空闲单元排序{不包括新回收的}
for(int j=i;j <num-i-1;j++){
if(idle[j][0]>idle[j+1][0]){
int temp=idle[j][0];
idle[j][0]=idle[j+1][0];
idle[j+1][0]=temp;
temp=idle[j][1];
idle[j][1]=idle[j+1][1];
idle[j+1][1]=temp;
}
}
}
for(int q=0;q <num;q++){ //将空单元排序{包括新回收的}
if(free[c][1] <=idle[q][0]){


for(int j=num;j>=q;j--){
idle[j+1][0]=idle[j][0];
idle[j+1][1]=idle[j][1];
}
idle[j][0]=free[c][1];
idle[j][1]=free[c][2];
b++;
if(idle[j+1][0]==idle[j][0]+idle[j][1]){
idle[j][1]=idle[j][1]+idle[j+1][1];
for(int m=j+1;m <=num;m++){
idle[m][0]=idle[m+1][0];
idle[m][1]=idle[m+1][1];
}
idle[m][0]=0;
idle[m][1]=0;
b--;
}
if(idle[j-1][0]==idle[j][0]){
idle[j-1][1]=idle[j-1][1]+idle[j][1];
for(int n=j;j <=num;j++){
idle[n][0]=idle[n+1][0];
idle[n][1]=idle[n+1][1];
}
idle[n][0]=0;
idle[n][1]=0;
b--;
}
break;
}
}
if(ch2==1)zuixian();
if(ch2==2)zuijia();
if(ch2==3)zuihuai();
for(int p=c;c <b-1;c++){
free[c][0]=free[c+1][0];
free[c][1]=free[c+1][1];
free[c][2]=free[c+1][2];
work[c][0]=work[c+1][0];
work[c][1]=work[c+1][1];
}
cout<<"该进程已被成功回收！"<<endl;
}
}
void fp(){
int tag=0; //判断空闲区与请求区大小
num=0;
b=0;
jishu();
jishu1();
for(int j=0;j <num;j++){
if(work[b][1] <idle[j][1]){
free[b][0]=work[b][0];
free[b][1]=idle[j][0];
free[b][2]=work[b][1];
idle[j][0]=idle[j][0]+work[b][1];
idle[j][1]=idle[j][1]-work[b][1];
tag=1;
break;
}
else if(work[b][1]==idle[j][1]){
free[b][0]=work[b][0];
free[b][1]=idle[j][0];
free[b][2]=work[b][1];
tag=1;
for(int i=j;i <=num-1;i++){
idle[i][0]=idle[i+1][0];
idle[i][1]=idle[i+1][1];
}
break;
}
else tag=0;
}
if(tag==0)cout <<"作业过大没有足够存储空间！" <<endl;
}
void print(){
num=0;
b=1;
jishu();
jishu1();
cout <<"已分配表为:" <<endl;
for(int i=0;i <=b;i++)
if(free[i][2]!=0)
cout <<"作业名:" <<free[i][0] <<" 内存起始地址:" <<free[i][1] <<" 占用内存空间:" <<free[i][2] <<endl;
cout <<endl;
cout <<"空闲区表为:" <<endl;
for(int j=0;j <num;j++)
if(idle[j][1]!=0)
cout <<"起始地址:" <<idle[j][0] <<" 连续内存空间:" <<idle[j][1] <<endl;
cout <<endl;
}
void main(){ //主函数运行上面定义的函数
init();
int n;
cout <<"1.分配空间；2.回收空间；" <<endl;
cin>>ch1;
cout <<endl;
cout <<"1.最先适应法；2.最佳适应法；3.最坏适应法；" <<endl;
cin>>ch2;
cout <<endl;
if(ch1==1){
cout <<"请输入要分配内存的作业名及占用内存大小:";
cin>>work[b][0]>>work[b][1];
cout <<endl;
if(ch2==1){
zuixian();
fp();
}
else if(ch2==2){
zuijia();
fp();
}
else if(ch2==3){
zuihuai();
fp();
}
print();
}
cout <<"输入要回收的作业名：" <<endl;
cin>>n;
huishou(n);
}