单元的收集与集中.ppt

无用单元无用单元:指没有被用户使用又指没有被用户使用又 不在可用空间表控制不在可用空间表控制 下的废弃单元下的废弃单元.一、共享表和递归表的删一、共享表和递归表的删 除问题除问题 1 引用计数的广义表引用计数的广义表第第 七七 节节 无用单元的收无用单元的收 集与集中集与集中 TYPE nodetype=RECORD tag:(0,1,2);link:nodetype;CASE data1:tag OF0:(data:elementtype);1:(data:nodetype)2:(data:integer)END;lists,position=nodetype;A 2 3 0 a 1 0 2 1 0 b 0 c 0 B A=(a,(b,c)2 1 1 1 1 0 0 B=(A,A,()2 2 0 a 1 0 C C=(a,c)2 删除广义表的递归算法删除广义表的递归算法 PROCEDURE lerase (VAR x:lists);VAR y:position;BEGIN x .data:=x .data-1 IF x .data 0 THEN RETURN;y:=x;WHILE y .link 0 DO y:=y .link;IF y .tag=1 THEN CALL lerase(y .data);y .link:=av;av:=x END;lerase 三、无用单元的收集三、无用单元的收集 1 定长结点收集无用单元定长结点收集无用单元进行标记后的可用内存情况进行标记后的可用内存情况：0n1 1n2 0n3 1n4 0n5 1n6 1n7 0n8定长无用结点链成可用空间表定长无用结点链成可用空间表 n8 n5 n3 n1 0 定长结点收集算法定长结点收集算法CONST size=定长结点尺寸定长结点尺寸;PROCEDURE collection (av,i:position;m:integer);BEGIN av:=0;i:=1;WHILE i m DO IF i .mark=0 THEN i .link:=av;av:=i ;i:=i+size END;collection 2 用存储压缩技术收集无用单元用存储压缩技术收集无用单元（1）压缩方法）压缩方法：进行标记后的可用内存情况进行标记后的可用内存情况：0n1 1n2 0n3 1n4 0n5 1n6 1n7 0n8内存压缩后的情况内存压缩后的情况：空闲区空闲区 n2 n4 n6 n7-n1+n2+n3+n4（2）压缩算法的基本思想）压缩算法的基本思想：为使用结点确定出新的起始地址。为使用结点确定出新的起始地址。更新有用结点的所有链接域更新有用结点的所有链接域。按预分配地址移动结点，使之集按预分配地址移动结点，使之集中于存储器的一端。中于存储器的一端。结点结构定义如下结点结构定义如下：TYPE nodetype=RECORD mark :(0,1);new-addr :integer;link1,link2:integer;size :integer END;PROCEDURE compact (A:ARRAY1;M;av:integer);BEGIN 阶段阶段 1av:=1;i:=1;WHILE i=m DO IF i.mark=1 THEN i.new-addr:=av;av:=av+i.size;i:=i+i.size;阶段阶段 2 i:=1;WHILE i=m DO IF i.mark=1 THEN i.link1:=i.link1.new-addr;i.link2:=i.link2.new-addr ;i:=i+i.size;阶段阶段 3 i:=1;WHILE i=m DO IF i.mark=1 THEN k:=i.new-addr;L:=k;FOR j:=i TO i+i.size-1 DO Ak:=Aj;k:=k+1 ;i:=i+L.size ELSE i:=i+i.size END;compact