8.5无用单元收集(2) 8.5无用单元收集(3) 。如何解决广义表结构中的“无用单元”或“悬挂访问”问题？ ·如何解决广义表结构中的“无用单元”或悬挂访问”问愿？ 。使用访问计数悬 。收集无用单元 在所有子表成广义表上增加一个表头结点，并设立 在程序运行中，所有的能表站点不管是否还有用， 国难 都不被回收，直到整个可利用空间表为空。此时中断 一个“计数城”，它的值为指向过子表减广义表的指针 执行准序，收集无用单元，分两步进行： 数目。当读计数城的值为0时，此于表或广义表中的站 1)对所有占用站点加上标志(0-未用，1-占用) 点才被释放。 2》对整个可利用存储空间顺序扫描一造，将标志为0 的站点能成一个新的可利用空间袁， 25/35 回 26/35 图 8.5无用单元收集(4) 8.5无用单元收集(5) 。标志(mark)算法：加标志的操作实质上是通历广义表，将 。非递归标志算法 广义表中所有结点的标志战(mark)赋值为“1”. 。程序中附设栈成队列实现广义表的遍历。 。假设广义表采用头尾链表示： 。类似于图的深度优先薄历或广度优先遭历 原子结，点(mark,tag,atom:表结点(mark,tag,hp,tp) 。评价：栈或队列的空间同样是不确定的 。递归算法： ,利用表结点本身的指针城标记墙历路径的标志算法 盖本项：1)表为空，则无须迪历： ·前述的递归和非递归标志算法，设栈的目的是： 2)若是一个敢据元囊，则标志元套结点 )记录谴历时所走的略径，以使在速历表头之后沿原路 归销项：首先标志表结点，再分别速历表头和表尾 逃圈，娘而对表见进行通历。 评价：需要一个较大的卖现遂归用的栈的铺动内存，黄内存不能 用于动本分家。由于表的层次不定，使得找的容量不易确定中可 ,利用已经标志过的表结点中的tag,hp和t中p域代普栈记 能会找逆出 27/35 录遗历过程中的路径，震8.10，P208209)图 8.5无用单元收集(6) 8.5无用单元收集(7) 。利用表结点本身的指针域标记速历路径的标志算法 。利用表结点本身的指针罐标记塘历路径的标志算法 。算法思想 银设印指向刚加上兼态的某个表布底时，指向p的举兼站点，q 氧流即指向侧加上标志的莱个表塘点时，指向p的章表结燕， 指向p的兼头或表见.（如因8.1(ab).P2I0 q指向p的表头成表见.（加图8.11(ab,P210 当q指向的表头结点时，可能有三种情况出现： 当q粉向的表头结点时，可能有三种情况出现： 3)设即的表头为来加桥志的于表， 1)设p的表头只是一个元素体点(mark,tag。.atom), 则橘先遭历表头子表，即1=p;P=q: 则墙历表头仅需对该是头结点打上标志后即◆推向的是品： 为丁记下指针移动的路径，以便在印递回原结点时同时找到 2)设p的表头为空表或是巴加上桥志的于章(mark,tag.tp.hp), 的母表结点，则庄能壶t之前，应先记下整动的路径，即全所推 则无需速历表头只要令指向的麦是： 德点的b卫望的值为t2且ta蝶的值为0”， 29/35 图 3035 图 55 25/35 8.5 无用单元收集(2) „ 如何解决广义表结构中的“无用单元”或“悬挂访问”问题？ „ 使用访问计数器 在所有子表或广义表上增加一个表头结点，并设立 一个“计数域”，它的值为指向该子表或广义表的指针 数目。当该计数域的值为0时,此子表或广义表中的结 点才被释放。 26/35 8.5 无用单元收集(3) „ 如何解决广义表结构中的“无用单元”或“悬挂访问”问题？ „ 收集无用单元 在程序运行中，所有的链表结点不管是否还有用， 都不被回收，直到整个可利用空间表为空。此时中断 执行程序，收集无用单元，分两步进行: 1)对所有占用结点加上标志(0-未用，1-占用) 2)对整个可利用存储空间顺序扫描一遍，将标志为0 的结点链成一个新的可利用空间表。 困难 27/35 8.5 无用单元收集(4) „ 标志(mark)算法: 加标志的操作实质上是遍历广义表，将 广义表中所有结点的标志域(mark)赋值为“1”。 „ 假设广义表采用头尾链表示： 原子结点(mark, tag,atom); 表结点(mark, tag,hp,tp) „ 递归算法： 基本项：1）表为空，则无须遍历； 2）若是一个数据元素，则标志元素结点 归纳项：首先标志表结点，再分别遍历表头和表尾 评价：需要一个较大的实现递归用的栈的辅助内存，该内存不能 用于动态分配。由于表的层次不定，使得栈的容量不易确定Î可 能会栈溢出 28/35 8.5 无用单元收集(5) „ 非递归标志算法 „ 程序中附设栈或队列实现广义表的遍历。 „ 类似于图的深度优先遍历或广度优先遍历 „ 评价：栈或队列的空间同样是不确定的 „ 利用表结点本身的指针域标记遍历路径的标志算法 „ 前述的递归和非递归标志算法，设栈的目的是： Æ记录遍历时所走的路径，以便在遍历表头之后沿原路 退回，继而对表尾进行遍历。 „ 利用已经标志过的表结点中的tag, hp和tp域代替栈记 录遍历过程中的路径。(图8.10, P208~209) 29/35 8.5 无用单元收集(6) „ 利用表结点本身的指针域标记遍历路径的标志算法 „ 算法思想 假设p指向刚加上标志的某个表结点时，t指向p的母表结点， q指向p的表头或表尾。(如图8.11(a)(b),P210) 当q指向p的表头结点时，可能有三种情况出现： 1）设p的表头只是一个元素结点(mark, tag, atom)， 则遍历表头仅需对该表头结点打上标志后即令q指向p的表尾； 2）设p的表头为空表或是已加上标志的子表(mark, tag, tp, hp) ， 则无需遍历表头只要令q指向p的表尾； 30/35 8.5 无用单元收集(7) „ 利用表结点本身的指针域标记遍历路径的标志算法 假设p指向刚加上标志的某个表结点时，t指向p的母表结点，q 指向p的表头或表尾。(如图8.11(a)(b),P210) 当q指向p的表头结点时，可能有三种情况出现： 3）设p的表头为未加标志的子表， 则需先遍历表头子表，即t = p; p = q； 为了记下t指针移动的路径，以便在p退回原结点时同时找到p 的母表结点，则在修改t 之前，应先记下t移动的路径，即令p所指 结点的hp域的值为t，且tag域的值为“0