《数据结构》-第八章 动态存储管理
第八章 动态存储管理 8.11
typedef struct {
char *start;
int size;
} fmblock; //空闲块类型
char *Malloc_Fdlf(int n)//遵循最后分配者最先释放规则的内存分配算法 {
while(Gettop(S,b)&&b.size
size;
f=p+n-1; //f指向空闲块底部
if((p-1)->tag&&(f+1)->tag) //回收块上下邻块均为占用块
{
p->tag=0;f->tag=0;
f->uplink=p;
if(!pav)
{
p->llink=p;
p->rlink=p;
}
else
{
q=pav->llink;
p->llink=q;p->rlink=pav;
q->rlink=p;pav->llink=p;
}
pav=p;
}//if
else if(!(p-1)->tag&&(f+1)->tag) //上邻块为空闲块
{
q=(p-1)->uplink;
q->size+=n;
f->uplink=q;
f->tag=0;
}
else if((p-1)->tag&&!(f+1)->tag) //下邻块为空闲块
{
q=f+1;
s=q->llink;t=q->rlink;
p->llink=s;p->rlink=t;
s->rlink=p;t->llink=p;
p->size+=q->size;
(q+q->size-1)->uplink=p;
p->tag=0;
}
else //上下邻块均为空闲块
{
s=(p-1)->uplink;
t=f+1;
s->size+=n+t->size;
t->llink->rlink=t->rlink;
t->rlink->llink=t->llink;
(t+t->size-1)->uplink=s;
}
}//Free_BT,该算法在课本里有详细的描述.
8.14
void Free_BS(freelist &avail,char *addr,int n)//伙伴系统的空闲块回收算法 {
buddy=addr%(2*n)?(addr-n):(addr+n); //求回收块的伙伴地址
addr->tag=0;
addr->kval=n;
for(i=0;avail[i].nodesizellink=addr;
addr->rlink=addr;
avail[i].first=addr; //作为唯一一个该大小的空闲块
}
else
{
for(p=avail[i].first;p!=buddy&&p!=avail[i].first;p=p->rlink);//寻找伙伴
if(p==buddy) //伙伴为空闲块,此时进行合并
{
if(p->rlink==p) avail[i].first=NULL;//伙伴是此大小的唯一空闲块
else
{
p->llink->rlink=p->rlink;
p->rlink->llink=p->llink;
} //从空闲块链中删去伙伴
new=addr>p?p:addr; //合并后的新块首址
Free_BS(avail,new,2*n); //递归地回收新块
}//if
else //伙伴为占用块,此时插入空闲块链头部
{
q=p->rlink;
p->rlink=addr;addr->llink=p;
q->llink=addr;addr->rlink=q;
}
}//else
}//Free_BS
8.15
FBList *MakeList(char *highbound,char *lowbound)//把堆结构存储的的所有空闲块链接成可利用空间表,并返回表头指针
{
p=lowbound;
while(p->tag&&p=highbound) return NULL; //没有空闲块
head=p;
for(q=p;ptag)
{
q->next=p;
q=p;
}//if
p->next=NULL;
return head; //返回头指针
}//MakeList
8.16
void Mem_Contract(Heap &H)//对堆H执行存储紧缩 {
q=MemStart;j=0;
for(i=0;itag)
{
s=H.list[i].length;
p=H.list[i].stadr;
for(k=0;k
本文档为【《数据结构》-第八章 动态存储管理】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483