动态分区分配方式的模拟C语言代码和C++代码Word文档格式.doc
《动态分区分配方式的模拟C语言代码和C++代码Word文档格式.doc》由会员分享，可在线阅读，更多相关《动态分区分配方式的模拟C语言代码和C++代码Word文档格式.doc（17页珍藏版）》请在冰点文库上搜索。
state=0;
L.after=p;
L.before=NULL;
L.size=0;
U.next=NULL;
n=&
U;
}
node*search（inta）
node*p=L.after;
if（p==NULL）
{
printf（"
没有空闲的区域!
"
）;
p=NULL;
returnp;
}
else
while（p!
=NULL&
&
a>
p->
size）
p=p->
after;
if（p==NULL）
{
printf（"
没有找到合适的空闲空间!
p=NULL;
returnp;
}
else
returnp;
voidrecovery（inta,intb）//内存回收算法
node*c,*s,*r=L.after;
node*d=L.after,*e;
usenode*k=U.next,*h=&
while（k!
a!
=k->
num）
h=k;
k=k->
next;
if（k==NULL）
没有找到这样的作业!
h->
next=k->
if（h->
next==NULL）
n=h;
while（r!
=NULL）//若回收得到的空闲块的前方有空闲块合并此空闲块
if（k->
add==r->
address+r->
r->
size=r->
size+k->
size;
break;
r=r->
if（r==NULL）//若回收得到的空闲块的后面有空闲块合并此空闲块
r=L.after;
while（r!
=NULL）
{
add+k->
size==r->
address）
address=k->
add;
r=r->
}
while（d!
=NULL）//保证空闲链表中没有相邻的空闲空间
if（d->
after!
e=d->
address+d->
size==e->
d->
after=e->
while（e->
e->
after->
before=d;
size=d->
size+e->
free（e）;
d=d->
if（r==NULL）
r=L.after;
c=（node*）malloc（sizeof（node））;
c->
size=b;
if（L.after==NULL）
c->
after=L.after;
L.after=c;
else
{
r=L.after;
while（r!
{
if（r->
address>
c->
{
c->
after=r;
before=r->
before;
r->
before->
after=c;
before=c;
free（k）;
return;
}
else
r=r->
}
free（k）;
voidalloc（inta,intb）//分配内存算法
node*p,*q=L.after;
usenode*m;
p=search（b）;
if（p==NULL）
return;
m=（usenode*）malloc（sizeof（usenode））;
//生成一个被占用链表的结点,并插入到该链表的尾部
m->
add=p->
address;
num=a;
next=n->
n->
next=m;
n=m;
//保证n始终指向被占用链表的尾部，方便以后新生成结点的插入
if（p->
size>
b）//如果申请空间的大小小于找到空闲空间的大小的处理
p->
size=p->
size-b;
address=p->
address+b;
else//如果申请空间的大小等于找到空闲空间的大小的处理
p->
after=p->
if（p->
p->
before=p->
free（p）;
voidsort（）//对空闲链表进行排序
intmax;
node*p,*q,*r,*s;
nodea;
p=L.after;
while（p!
=NULL）//让指针q指向链表的最后一个结点
q=p;
p=p->
if（L.after->
after==NULL）
return;
while（p!
=q）
{
s=r=p=L.after;
max=r->
while（s!
=q->
after）
if（s->
max）
{
max=s->
r=s;
s=s->
}
else
s=s->
a.size=q->
a.address=q->
q->
address=r->
r->
size=a.size;
address=a.address;
if（q->
before==&
L）
return;
else
q=q->
voidPrint（）
usenode*q=U.next;
inti=1;
printf（"
\n空闲区域列表:
\n"
FREEIDaddresssize\n"
%-10d"
i）;
p->
address）;
%d\n"
size）;
i++;
if（q==NULL）
\n已分配区域列表:
WORKIDaddresssize\n"
while（q!
q->
num）;
add）;
q=q->
voidfirstfit（）//首次适应算法
inta,b,i;
Init（）;
Print（）;
while
（1）
{printf（"
\n1、申请空间\n"
printf（"
2、释放空间\n"
3、退出首次适应算法\n"
请输入你的选择:
scanf（"
%d"
&
i）;
switch（i）
{
case1:
{
printf（"
请输入申请空间的作业号:
scanf（"
a）;
printf（"
请输入申请空间的大小:
scanf（"
b）;
alloc（a,b）;
Print（）;
break;
}
case2:
printf（"
请输入释放空间的作业号:
请输入释放空间的大小:
recovery（a,b）;
case3:
printf（"
return;
}
voidbestfit（）
3、退出最佳适应算法\n"
sort（）;
voidmain（）
inti;
while
（1）
{
printf（"
1、首次适应算法\n"
2、最佳适应算法\n"
3、退出\n"
scanf（"
switch（i）
case1:
firstfit（）;
break;
case2:
bestfit（）;
case3:
}
运行结果
①开始界面
②首次适应算法
③最佳适应算法
程序代码——C++语言实现
//***************************************************************
//********
动态分区分配方式的模拟
*********
iostream.h>
#defineFree0//空闲状态
#defineBusy1//已用状态
#defineOK1
//完成
#defineERROR0//出错
#defineMAX_length640//最大内存空间为640KB
typedefintStatus;
typedefstructfreearea//定义一个空闲区说明表结构
intID;
//分区号
longsize;
//分区大小
longaddress;
//分区地址
intstate;
//状态
}ElemType;
//----------
线性表的双向链表存储结构
------------
typedefstructDuLNode//doublelinkedlist
ElemTypedata;
structDuLNode*prior;
//前趋指针
structDuLNode*next;
//后继指针
}DuLNode,*DuLinkList;
DuLinkListblock_first;
//头结点
DuLinkListblock_last;
//尾结点
Statusalloc（int）;
//内存分配
Statusfree（int）;
//内存回收
StatusFirst_fit（int,int）;
//首次适应算法
StatusBest_fit（int,int）;
//最佳适应算法
voidshow（）;
//查看分配
StatusInitblock（）;
//开创空间表
StatusInitblock（）//开创带头结点的内存空间链表
block_first=（DuLinkList）malloc（sizeof（DuLNode））;
block_last=（DuLinkList）malloc（sizeof（DuLNode））;
block_first->
prior=NULL;
next=block_last;
block_last->
prior=block_first;
next=NULL;
data.address=0;
data.size=MAX_length;
data.ID=0;
data.state=Free;
returnOK;
//-----------------------
分配主存
-------------------------
Statusalloc（intch）
intID,request;
cout<
<
请输入作业（分区号）：
;
cin>
>
ID;
请输入需要分配的主存大小（单位:
KB）：
request;
if（request<
0||request==0）
分配大小不合适，请重试！
endl;
returnERROR;
if（ch==2）//选择最佳适应算法
if（Best_fit（ID,request）==OK）cout<
分配成功！
elsecout<
内存不足，分配失败！
else//默认首次适应算法
if（First_fit（ID,request）==OK）cout<
//------------------
首次适应算法
-----------------------
StatusFirst_fit（intID,intrequest）//传入作业名及申请量
//为申请作业开辟新空间且初始化
DuLinkListtemp=（DuLinkList）malloc（sizeof（DuLNode））;
temp->
data.ID=ID;
data.size=request;
data.state=Busy;
DuLNode*p=block_first->
while（p）
if（p->
data.state==Free&
p->
data.size==request）
{//有大小恰好合适的空闲块
data.size>
request）
{//有空闲块能满足需求且有剩余"
prior=p->
prior;
next=p;
data.address=p->
data.address;
prior->
next=temp;
prior=temp;
data.address=temp->
data.address+temp->
data.size;
data.size-=request;
p=p->
//--------------------
最佳适应算法
------------------------
StatusBest_fit（intID,intrequest）
intch;
//记录最小剩余空间
DuLNode*q=NULL;
//记录最佳插入位置
while（p）//初始化最小空间和最佳位置
（p->
request||p->
data.size==request））
q=p;
ch=p->
data.size-request;
{//空闲块大小恰好合适
升级会员 