严蔚敏数据结构c语言版习题集复习资料动态存储管理文库.docx

《严蔚敏数据结构c语言版习题集复习资料动态存储管理文库.docx》由会员分享，可在线阅读，更多相关《严蔚敏数据结构c语言版习题集复习资料动态存储管理文库.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 动态存储管理 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(!StackEm

2、pty(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.startsize; f=p+n-1; /f指向空闲块底部 if(p-1)-tag&(f+1)-tag)

3、/回收块上下邻块均为占用块 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

4、; 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)/伙伴系统的空

5、闲块回收算法 buddy=addr%(2*n)?(addr-n):(addr+n); /求回收块的伙伴地址 addr-tag=0; addr-kval=n; for(i=0;availi.nodesizellink=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;/伙伴是此大小的唯一

6、空闲块 else p-llink-rlink=p-rlink; p-rlink-llink=p-llink; /从空闲块链中删去伙伴 new=addrp?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)/把堆结构存储的的所有空

7、闲块链接成可利用空间表,并返回表头指针 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.listi.length; p=H.listi.stadr; for(k=0;ks;k+) *(q+)=*(p+); /紧缩内存空间 H.listj.stadr=q; H.listj.length=s; /紧缩占用空间表 j+; /Mem_Contract