數(shù)據(jù)結(jié)構(gòu)教學講義：第8章 動態(tài)存儲管理

1、第八章 動態(tài)存儲管理 8.11 typedef struct char *start; int size; fmblock; /空閑塊類型 char *Malloc_Fdlf(int n)/遵循最后分配者最先釋放規(guī)則的內(nèi)存分配算法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)Po

2、p(T,a);Push(S,a); /恢復原來次序return b.start;/Malloc_Fdlf mem_init()/初始化過程.InitStack(S);InitStack(T); /S和T的元素都是fmblock類型Push(S,MemStart,MemLen); /一開始,棧中只有一個內(nèi)存整塊./main 8.12 void Free_Fdlf(char *addr,int n)/與上一題對應(yīng)的釋放算法while(Gettop(S,b)&b.startsize;f=p+n-1; /f指向空閑塊底部if(p-1)-tag&(f+1)-tag) /回收塊上下鄰塊均為占用塊p-tag

3、=0;f-tag=0;f-uplink=p;if(!pav)p-llink=p;p-rlink=p;elseq=pav-llink;p-llink=q;p-rlink=pav;q-rlink=p;pav-llink=p;pav=p;/ifelse 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-llin

4、k=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)/伙伴系統(tǒng)的空閑塊回收算法buddy=addr%(2*n)?(addr-n):(addr+n); /求回收塊的伙伴

5、地址addr-tag=0;addr-kval=n;for(i=0;availi.nodesizellink=addr; addr-rlink=addr; availi.first=addr; /作為唯一一個該大小的空閑塊elsefor(p=availi.first;p!=buddy&p!=availi.first;p=p-rlink);/尋找伙伴if(p=buddy) /伙伴為空閑塊,此時進行合并if(p-rlink=p) availi.first=NULL;/伙伴是此大小的唯一空閑塊elsep-llink-rlink=p-rlink;p-rlink-llink=p-llink; /從空閑塊鏈

6、中刪去伙伴new=addrp?p:addr; /合并后的新塊首址Free_BS(avail,new,2*n); /遞歸地回收新塊/ifelse /伙伴為占用塊,此時插入空閑塊鏈頭部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)/把堆結(jié)構(gòu)存儲的的所有空閑塊鏈接成可利用空間表,并返回表頭指針p=lowbound;while(p-tag&p=highbound) return NULL; /沒有空閑塊head=p;for(q=p;ptag)q-next=p;q=p;/ifp-next=NULL;return head; /返回頭指針/MakeList 8.16 void Mem_Contract(Heap &H)/對堆H執(zhí)行存儲緊縮q=MemStart;j=0;for(i=0;itag)s=H.listi.length;p=H.li