单元的收集与集中

无用单元:指没有被用户使用又 不在可用空间表控制 下的废弃单元. 一、共享表和递归表的删 除问题 1引用计数的广义表

第七节无用单元的收 集与集中 TYPE nodetype=RECORD tag:(0,1,2); link:nodetype; CASEdata1:tagOF 0:(data:elementtype); 1:(data: nodetype) 2:(data:integer) END; lists,position=nodetype;

A 230a10 210b0c0B A=(a,(b,c)) 2111100 B=(A,A,()) 220a10 CC=(a,c)2删除广义表的递归算法 PROCEDURElerase (VARx:lists); VAR y:position; BEGIN x.data:=x.data-1 IFx.data<>0THEN RETURN; y:=x;

WHILEy.link<>0DO [y:=y.link; IFy.tag=1THEN CALLlerase(y.data)]; y.link:=av; av:=x END;{lerase} 三、无用单元的收集 1定长结点收集无用单元 进行标记后的可用内存情况： 0n11n20n31n40n51n61n70n8 定长无用结点链成可用空间表 n8 n5n3n10定长结点收集算法

CONST size=定长结点尺寸; PROCEDUREcollection (av,i:position;m:integer); BEGIN av:=0;i:=1; WHILEi<mDO [IFi.mark=0THEN [i.link:=av;av:=i]; i:=i+size] END;{collection}2用存储压缩技术收集无用单元 （1）压缩方法： 进行标记后的可用内存情况：0n11n20n31n40n51n61n70n8 内存压缩后的情况： 空闲区 n2n4n6n7 -------------------- n1+n2+n3+n4（2）压缩算法的基本思想： 为使用结点确定出新的起始地址。 更新有用结点的所有链接域。 按预分配地址移动结点，使之集 中于存储器的一端。结点结构定义如下： TYPE nodetype=RECORD mark:(0,1); new-addr:integer; link1,link2:integer; size:integer END; PROCEDUREcompact (A:ARRAY[1;M];av:integer); BEGIN {阶段1} av:=1;i:=1; WHILEi<=mDO [IF[i].mark=1 THEN [[i].new-addr:=av; av:=av+[i].size]; i:=i+[i].size];{阶段2} i:=1; WHILEi<=mDO [IF[i].mark=1 THEN [[i].link1:=[[i].link1].new-addr;[i].link2:=[[i].link2].new-addr]; i:=i+[i].size]; {阶段3} i:=1; WHILEi<=mDO [IF[i].mark=1 THEN [k:=[i].new-addr;L:=k; FORj:=iTOi+[i].s