实现动态分区分配 模拟程序

#include
#include
#define BUSY 1 //忙碌状态
#define FREE 0 //空闲状态

using namespace std;


int Init(int KB); //创建内存空间
int Show();//显示内存分配情况
int First_fit(int ID,int KB);//首次适应算法
int Best_fit(int ID,int KB);//最佳适应算法
int Worst_fit(int ID,int KB);//最坏适应算法
int Alloc(int alg); //申请空间
int Receive(); //释放空间

struct Data
{
int ID; //进程ID
int size; //空间大小 KB
int add; //分区地址
int state; //状态 BUSY 和 FREE
};

struct Node
{
Data data; //数据
Node* pre; //前驱指针
Node* next; //后继指针
};

string ary[5]={"","首次适应","最佳适应","最坏适应"};
int lenth;
Node* head; //头结点


//-----------创建内存空间-------------
int Init(int KB)//空间大小KB KB
{
Node* temp=new Node();
temp->data.size=KB;
temp->data.ID=0;
temp->data.add=0;
temp->data.state=FREE;


head=new Node();
head->pre=NULL;
head->next=temp;

temp->pre=head;
temp->next=NULL;

cout<<"您创建了"<
return 1;
}


//-------------------显示内存分配情况----------------
int Show()
{
Node* p=head->next;
cout<<"==========内存分配情况========================"<while(p!=NULL)
{
cout<<"起始地址:";
printf("%3d",p->data.add);
cout<<" 空间大小:";
printf("%3dKB",p->data.size);
cout<<" 状态:";
if(p->data.state == FREE)
{
cout<<"空闲"<}
else
{
cout<<"占用";
cout<<" 进程"<data.ID<}
p=p->next;
}
cout<<"=============================================="<return 1;
}

//----------------首次适应算法--------------------
int First_fit(int ID,int KB)
{

Node *p=head->next;
while(p)
{
if(p->data.state == FREE && p->data.size >= KB)
{
if(p->data.size == KB) //空间大小正好适合
{
p->data.ID=ID;
p->data.state=BUSY;
}
else //有空间大于申请空间的，即有剩余空间
{
Node* temp=new Node();
temp->data.ID=ID;
temp->data.size=KB;
temp->data.state=BUSY;
temp->data.add=p->data.add;

temp->next=p;
temp->pre=p->pre;

p->pre->next=temp;
p->pre=temp;

p->data.size -= temp->data.size;
p->data.add = temp->data.size + temp->data.add;

}
return 1;
}
else
{
p=p->next;
}
}

return 0;


}



//----------------最佳适应算法--------------------
int Best_fit(int ID,int KB)
{
int min=2*lenth;
Node *best=NULL;
Node *p=head->next;
while(p)
{
if(p->data.state == FREE && p->data.size >= KB && min > (p->data.size-KB) )
{
min=p->data.size-KB;
best=p;
if(min==0) break;
}
p=p->next;
}

if(best == NULL)
{
cout<<"没有空间可以申请！"<return 0;
}

if(min==0)
{//空间大小正好适合
best->data.ID=ID;
bes

t->data.state=BUSY;
}
else
{//空间还有剩余
Node* temp=new Node();
temp->data.ID=ID;
temp->data.size=KB;
temp->data.state=BUSY;
temp->data.add=best->data.add;

temp->next=best;
temp->pre=best->pre;

best->pre->next=temp;
best->pre=temp;

best->data.size -= temp->data.size;
best->data.add = temp->data.size + temp->data.add;
}



return 1;

}


//----------------最坏适应算法--------------------
int Worst_fit(int ID,int KB)
{
int max=-1;
Node *worst=NULL;
Node *p=head->next;
while(p)
{
if(p->data.state == FREE && p->data.size >= KB && max < (p->data.size-KB) )
{
max=p->data.size-KB;
worst=p;
}
p=p->next;
}

if(worst == NULL)
{
cout<<"没有空间可以申请！"<return 0;
}

if(max==0)
{//空间大小正好适合
worst->data.ID=ID;
worst->data.state=BUSY;
}
else
{//空间还有剩余
Node* temp=new Node();
temp->data.ID=ID;
temp->data.size=KB;
temp->data.state=BUSY;
temp->data.add=worst->data.add;

temp->next=worst;
temp->pre=worst->pre;

worst->pre->next=temp;
worst->pre=temp;

worst->data.size -= temp->data.size;
worst->data.add = temp->data.size + temp->data.add;
}



return 1;

}

//------------申请空间-------------
int Alloc(int alg)
{
int ID,KB;
cout<<"请输入进程ID和申请空间大小：";
cin>>ID;
while(cin>>KB)
{
if(KB == 0 || KB <= 0 )
{
cout<<"分配大小不合适，请重试！";
cout<<"请输入进程申请空间大小：";
}
else break;
}

if(alg == 1)
{
if(First_fit(ID,KB))
cout<<"分配内存成功！"<else
cout<<"分配内存失败！"<}
else if(alg == 2)
{
if(Best_fit(ID,KB))
cout<<"分配内存成功！"<else
cout<<"分配内存失败！"<}
else if(alg == 3)
{
if(Worst_fit(ID,KB))
cout<<"分配内存成功！"<else
cout<<"分配内存失败！"<}
cout<return 1;
}


//------------释放空间-------------
int Receive()
{
int ID,KB;
cout<<"请输入进程ID和释放空间大小：";
cin>>ID>>KB;

Node *p=head->next;
Node *qt;

while(p)
{
if(p->data.ID == ID)
{
qt=p;//找到释放空间的内存块了
break;
}
else
p=p->next;
}

if(p==NULL)
{
cout<<"该进程没有申请空间，无法释放！"<return 0;
}

if(qt->data.size != KB)
{
cout<<"必须释放进程所占有的所有空间！请重新输入！"<return 0;
}


Node *pre,*next;
pre=qt->pre;
next=qt->next;

if(pre!=head)
{
if(pre->data.state == FREE)
{//释放结点的前结点是空闲，则聚合
pre->data.size += qt->data.size;
pre->data.ID=0;
pre->data.state=FREE;
pre->next=next;
if(next!=NULL) next->pre=pre;

free(qt);
}
else
{//释放结点的前结点被占用，则只更改释放结点的信

息
qt->data.ID=0;
qt->data.state=FREE;
}
}

if(next!=NULL)
{
pre=next->pre;
if(next->data.state == FREE)
{//释放结点的后结点是空闲，则聚合
pre->data.size+=next->data.size;
pre->data.ID=0;
pre->data.state=FREE;
pre->next=next->next;
if(next->next != NULL) next->next->pre=pre;

free(next);
}
else
{//释放结点的后结点被占用
if(qt!=NULL)
{
qt->data.ID=0;
qt->data.state=FREE;
}

}
}

return 1;
}

int main()
{
int alg; //算法选择标记
cout<<" 请选择算法 \n";
cout<<"********************************************\n";
cout<<"****(1)首次适应 (2)最佳适应 (3)最坏适应*****\n";
cout<<"********************************************\n";
while(cin>>alg)
{
if(alg<=3 && alg>=1)
break;
}

cout<<"您选择了"<
cout<<"请输入初始状态下可用内存空间大小"<cin>>lenth;

Init(lenth);//创建初始内存空间大小


int choice; //操作标记

cout<<"————————————————"<cout<<"| 1：申请内存 2：释放内存 |"<cout<<"| 3：查看分配 4：退出 |"<cout<<"————————————————"<cout<<"请输入您的操作：";
while(cin>>choice)
{
if(choice>4 || choice < 1)
{
cout<<"输入错误，请重新输入!"<cout<<"请输入您的操作：";
continue;
}
if(choice == 4) break;

if(choice == 1 )
{
Alloc(alg);
}
else if(choice==2)
{
if(Receive())
{
cout<<"释放空间成功！"<}
else
{
cout<<"释放空间失败！"<}
}
else if(choice == 3)
{
Show();
}

cout<<"请输入您的操作：";
}

return 0;
}