《数据结构》课程教学资源：答案_第八章 动态存储管理

第八章动态存储管理 8.11 typedef struct i har *start enblock,∥空闲块类型 char* Malloc_Fdlf( int n)遵循最后分配者最先释放规则的内存分配算法 while( Gettop(s, b)&&b size<n) Pop(s, b) Push(T,b),∥从栈顶逐个取出空闲块进行比较 if( Stack Empty(S) return NULL,∥没有大小足够的空闲块 Pop(s, b) bsize. if(b size)Push(S,b. start+n b size})/分割空闲块 while(!stack Empty T) Popt Push(s, a }/恢复原来次序 eturn b start i//Malloc ldIf mem inito/初始化过程 Init Stack(S) InitStack(T,/S和T的元素都是 enblock类型 Push(S,{ MemStart emlEn}),∥一开始栈中只有一个内存整块 nain 8.12 void Free FdIf(char* addr int n)/与上一题对应的释放算法 while(Gettop(s, b )&&b start <addr) Pop(s, b); Push(t, b)

第八章 动态存储管理 8.11 typedef struct { char *start; int size; } fmblock; //空闲块类型 char *Malloc_Fdlf(int n)//遵循最后分配者最先释放规则的内存分配算法 { while(Gettop(S,b)&&b.size<n) { Pop(S,b); Push(T,b); //从栈顶逐个取出空闲块进行比较 } if(StackEmpty(S)) return NULL; //没有大小足够的空闲块 Pop(S,b); b.size-=n; if(b.size) Push(S,{b.start+n,b.size});//分割空闲块 while(!StackEmpty(T)) { Pop(T,a); Push(S,a); } //恢复原来次序 return b.start; }//Malloc_Fdlf mem_init()//初始化过程 { ... InitStack(S);InitStack(T); //S 和 T 的元素都是 fmblock 类型 Push(S,{MemStart,MemLen}); //一开始,栈中只有一个内存整块 ... }//main 8.12 void Free_Fdlf(char *addr,int n)//与上一题对应的释放算法 { while(Gettop(S,b)&&b.start<addr) { Pop(S,b); Push(T,b);

}∥在按地址排序的栈中找到合适的插入位置 if( Gettop(T.b&&( b start +b.size=addr)/可以与上邻块合并 Pop(T, b); addr. start n+=b size if( Gettop(s,b&&(adr+n= b start)/可以与下邻块合并 Pop(S, b) n+=b size Push(S,{addr,n}),/插入到空闲块栈中 while(!stackEmpty(D) Pop(T, b); Push(s, b): }/恢复原来次序 i//Free LdIf 8.13 void Free BT( Space& pav, Space p》∥/在边界标识法的动态存储管理系统中回收空 闲块p np->sIze f=p+n-1;∥f指向空闲块底部 if(p-1)tag&&(f+1)>tag)∥回收块上下邻块均为占用块 p->tag=0 f->tag=0 f->uplink=p p→link=p; nk p->link=q: p->rlinkpav H->rlink=p pav->link=p: pav-p, else if(p-1)>tag&&(f+1)>ag)∥上邻块为空闲块

} //在按地址排序的栈中找到合适的插入位置 if(Gettop(T,b)&&(b.start+b.size==addr)) //可以与上邻块合并 { Pop(T,b); addr=b.start;n+=b.size; } if(Gettop(S,b)&&(addr+n==b.start)) //可以与下邻块合并 { Pop(S,b); n+=b.size; } Push(S,{addr,n}); //插入到空闲块栈中 while(!StackEmpty(T)) { Pop(T,b); Push(S,b); } //恢复原来次序 }//Free_Fdlf 8.13 void Free_BT(Space &pav,Space p)//在边界标识法的动态存储管理系统中回收空 闲块 p { n=p->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; f->uplink=q else if(p-1)>tag&&l(f+1)>ag)/下邻块为空闲块 q=f+1; s=q->link t=q->rlink; p->ink=s p->rlink=t S->rlink=p: t->llink p->sIze+=q->sIze (q+q->size-1)->uplink=p p->tag=0 else∥上下邻块均为空闲块 s=(p-1)->uplink; t=f+1 t->llink->rlink=t->rlink t->rlink ->llink=t->llink (t+t->size-1)->uplink }/ Free bt,该算法在课本里有详细的描述 8.14 void free_BS( freelist& Avail,char*addr,ntny伙伴系统的空闲块回收算法 buddy=addr%(2*n)?( addr-n)(addr+n,/求回收块的伙伴地址 addr->kvaln for(i=0; avail[ i]. nodesizellinkeadd addr->rlink-addr aval]fist=addr,∥作为唯一一个该大小的空闲块 else for(p=aval[ first; p!- buddy&&pl= avail[D] first; p=p>rink/寻找伙伴 flp= buddy)/伙伴为空闲块,此时进行合并

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) //伙伴为空闲块,此时进行合并 {

ifp→rik=p)aval[]frst=NUL/伙伴是此大小的唯一空闲块 else p->llink->rlink=p->rlink link→p->li }∥从空闲块链中删去伙伴 new=adrp? p: addr,∥合并后的新块首址 Free Bs( availe,2*n);∥递归地回收新块 i/if else∥伙伴为占用块此时插入空闲块链头部 q→p-> rlink p->rlink-addr; addr->link=p q->llink=addr addr->rlink=q ilelse i//Free Bs 8.15 FBList* MakeList(char* highbound,char+ snowbound别∥把堆结构存储的的所有空闲 块链接成可利用空间表并返回表头指针 p=lowbound while(p->tag&&p= highbound) return NULL;∥没有空闲块 -p, for(q→pptag q→p, i/if p->next=NULL return head;/返回头指针 3//Makelist 8.16 void Mem Contract(Heap&Hy对堆H执行存储紧缩 q=MemStart; =0; for(=0; i tag)

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-Hlist[]. length p=Hlist[].stadr for(k=0k<sk+)*(q++)*(p++),∥紧缩内存空间 H list[]. stadr=q list[length=s,紧缩占用空间表 i//Mem Contract

s=H.list[i].length; p=H.list[i].stadr; for(k=0;k<s;k++) *(q++)=*(p++); //紧缩内存空间 H.list[j].stadr=q; H.list[j].length=s; //紧缩占用空间表 j++; } }//Mem_Contract