严蔚敏《数据结构(c语言版)习题集》答案第八章-动态存储管理文库.docx

第八章 动态存储管理 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=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; 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;availi.nodesize<n;i+); /找到这一大小的空闲块链 if(!availi.first) /尚没有该大小的空闲块 addr->llink=addr; addr->rlink=addr; availi.first=addr; /作为唯一一个该大小的空闲块 else for(p=availi.first;p!=buddy&&p!=availi.first;p=p->rlink);/找寻伙伴 if(p=buddy) /伙伴为空闲块,此时进行合并 if(p->rlink=p) availi.first=NULL;/伙伴是此大小的唯一空闲块 else p->llink->rlink=p->rlink; p->rlink->llink=p->llink; /从空闲块链中删去伙伴 new=addr>pp: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) p+; /查找第一个空闲块 if(p>=highbound) return NULL; /没有空闲块 head=p; for(q=p;p<highbound;p+=cellsize) /建立链表 if(!p->tag) 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;i<Max_ListLen;i+) if(H.listi.stadr->tag) s=H.listi.length; p=H.listi.stadr; for(k=0;k<s;k+) *(q+)=*(p+); /紧缩内存空间 H.listj.stadr=q; H.listj.length=s; /紧缩占用空间表 j+;/Mem_Contract第 5 页