《数据结构题集》答案第8章动态存储管理.docVIP

第八章 动态存储管理 8.11 typedef struct {?????????? ?????? char *start; ???????????????? int size; ????????????? } fmblock; //空闲块类型 char *Malloc_Fdlf(int n)//遵循最后分配者最先释放规则的内存分配算法{??while(Gettop(S,b)b.sizen)??{????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.startaddr)??{????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=ad