给每个递归调用一个清楚的契约,较容易理解链表操作。我们会删除所有数值等于目标的节点,并保持其余节点的身份和相对次序。
契约和所有权
定义 10.2.1
(removeAll 的契约)
输入 head 是 null,或指向有限、无环的单向链。节点有 value 和 next 两个字段。调用者授权此程序独占地修改链接及释放被删节点;外部指针不得在节点被释放后再解引用它,而仍指向存活节点的别名会看到链接的改变。链表拥有其节点:dispose(p) 只释放节点 p,不检查或释放 p.next 所指的后缀。假设相等测试、指针赋值和释放各需常数时间。调用者必须用返回值更新旧表头;若链表对象另存尾指针或长度,也须另行更新。
输出:由存活节点按原顺序组成的链的表头;若没有节点存活则为 null。
removeAll(p, target):
if p == null:
return null
rest = removeAll(p.next, target)
if p.value == target:
dispose(p) // rest 仍然存活
return rest
p.next = rest
return p
递归调用先处理原本的后缀,然后才决定如何处理 p。若删除 p,其调用者得到 rest;否则将 p.next 接到筛选后的后缀。释放 p 后绝不能再通过它写入。因为这里的释放操作不遍历 p.next,释放前不必清除被删节点的旧链接。若语言使用递归析构器或共享所有权,便需要另一套释放规则,不能直接套用此假设。
概念视角算法
同一个筛选,改为单次向前扫描
从左到右扫描一次,并记住最后一个幸存节点,也会得到相同的结果。先保存 p.next,然后释放 p,或把 p 接在最后一个幸存节点之后(若尚无幸存节点,它就成为新的头)。返回的链和被释放的节点集合相同,但释放改为从前到后进行,额外空间也是常数。
常见错误
(调用之后仍使用旧表头)
取 A(2) -> B(5) -> null,目标为 。调用返回 B,并释放 A。若调用者继续使用变量 head(仍等于 A),就会读取已释放的节点。调用并不会改变表头变量,因为程序是返回新表头,而不是给调用者的变量赋值。调用者必须写成 head = removeAll(head, 2)。
常见错误
(忘记为存活节点重新连接)
若存活分支返回 p 时没有执行 p.next = rest,则在 B(5) -> C(2) -> D(7)、目标 的情况下,节点 B 仍然指向已释放的节点 C,尽管 C 已被删除。p.next = rest 这一步,才会把 p 之后被删的节点接掉,每个存活节点都必须执行它。
为什么正确
定理 10.2.2
(递归删除的正确性与成本)
设 head 是 null,或是含 个节点的有限、无环链的表头。则 removeAll(head, target) 返回一条链的表头,该链恰由数值不等于 target 的节点组成,顺序及节点身份均保持原样。每个被删节点恰好释放一次,存活节点均不释放。此调用需要 时间和 栈空间,且不分配任何节点。
证明
(对链的长度归纳)
每次非空调用都递归处理少一个节点的链。长度是非负整数,故最后必到 null。按原链长度作归纳:空链的结果正确。假设递归调用返回原后缀中删去所有匹配节点后的链,而且保留存活节点的身份和次序。若 p 匹配,释放它并返回该后缀,恰好删去所需节点;若不匹配,将 p 接到该后缀之前,便保留了整条链中应存活节点的原次序。因此整个契约成立,每个被删节点恰好释放一次,存活节点均不释放。
原链有 n 个节点时,共有 n 个非空调用及一个基础调用,每个只做常数工作,所以时间为 ,调用栈占 空间;没有分配新节点。即使全部节点都被删除,删除前仍已递归下降到链尾,因此仍有此栈成本。
证明透视
归纳假设必须说什么
归纳假设是针对后缀本身这条链来陈述的:对 p.next 的调用,返回删去匹配节点后该后缀的表头。证明用了两次这个假设。若 p 匹配,答案就是该返回的表头,别处不需修补。若 p 存活,只改 p 自己的链接,并令它指向该返回的表头,所以存活节点保持顺序。递归发生在碰 p 之前,所以读取 p.next 时 p 仍然存活。转到较短的链这一步,需要链有限且无环:这样长度才会递减,基础情形才可到达,下面的反例说明了这一点。
反例模式
有环的链没有基础情形
去掉链无环的假设。设 A(1) -> B(2) -> A,其中 B.next 指回 A,调用 removeAll(A, 7)。对 A 的调用递归到 B,再递归回 A,如此类推:调用 永远到不了 null,没有任何调用返回,栈不断增长直至溢出。长度论证失效,因为 A 之后的“后缀”并不更短。契约要求链有限且无环;可能含环的链表须先检查,例如用 Floyd 方法。
练习:跟踪返回值
例题 10.2.3
(返回时的返回值)
不同节点 A(2) -> B(5) -> C(2) -> D(7) -> null 组成链表。执行 removeAll(head, 2)。我们列出每个非空调用在返回时的返回值、被释放的节点及结果,并说明为何调用者要把返回值赋给表头。
从链尾返回:D 存活,设置 D.next = null,返回 D;C 匹配,释放后返回 D;B 存活,设置 B.next = D,返回 B;A 匹配,释放后返回 B。结果为 B(5) -> D(7) -> null,存活节点相对顺序不变;A、C 各释放一次。旧表头 A 已不存活,若继续使用会成为悬空指针,因此必须以返回的 B 更新。此例旧尾 D 恰好仍存活,但一般不能假设旧尾不会被删。
例题 10.2.4
(开头连续出现匹配节点)
对 X(3) -> Y(3) -> Z(1) -> null 执行 removeAll(head, 3)。最内层的非空调用是 Z:它存活,设置 Z.next = null 并返回 Z。Y 匹配,释放后返回 Z。X 匹配,释放后返回 Z。返回的表头是 Z,最后的链是 Z(1) -> null。两个相邻的匹配节点不构成困难,因为每个匹配节点只是把筛选后后缀的表头向上转交。
练习:边界情形与附加数据
例题 10.2.5
(全部或没有节点被删除时的附加数据)
链表对象保存 head、tail 和 length,节点为 P(4) -> Q(4) -> R(4) -> null,长度 3。用此程序删除目标 4,给出返回表头及调用者修正后的数据。再对 U(1) -> V(3) -> null 删除目标 4,给出结果及成本,并说明如何在一般情况下安全地修正这些数据,而不使用已释放指针。
第一个例子中,返回时依次释放 R、Q、P,各调用均返回 null。修正后表头和尾指针均为 null,长度为 0。第二个例子中,两个节点以原身份和顺序保留,返回 U,尾指针为 V,长度为 2。即使没有匹配,程序仍访问两个节点,一般时间为 、栈空间为 。一般做法是先赋值返回的表头,再遍历返回的存活链,计数并记住最后节点;空链的尾指针为 null。此额外步骤需 时间和 迭代额外空间,总时间仍为 。除非独立确认旧表头或旧尾指针仍存活,否则不可在调用后检查它们。
练习与解答
快速检查
(对 P(5) -> Q(5) -> R(8) -> S(5) -> null 执行 removeAll(head, 5)。给出每个非空调用在返回时的返回值、被释放的节点及最后的链。)
解答 · 答案
调用从链尾返回。S 匹配,释放后返回 null。R 存活,设置 R.next = null 并返回 R。Q 匹配,释放后返回 R。P 匹配,释放后返回 R。被释放的节点是 S、Q、P,最后的链是 R(8) -> null,返回的表头是 R。
快速检查
(在递归程序中,为何递归调用要在 dispose(p) 之前,而不是之后?)
解答 · 答案
调用要读取 p.next,而这个读取必须在 p 仍然存活时进行。dispose(p) 之后不可再解引用该节点,所以其后才读 p.next 就是使用已释放的节点。先作调用也使 rest 在释放 p 时已经可用,于是可一步以 rest 取代 p。
快速检查
(一条含 个节点的链表,每个节点的值都是目标值。removeAll 共作多少次调用?在递归深度受限的语言中,哪种资源可能耗尽?)
解答 · 答案
共有 个非空调用加一个基础调用,即 次调用,在最深处全部同时在栈上,因为释放要到递归返回时才开始。调用栈占 空间,即使没有节点保留,也可能溢出。用指向前一个存活节点的指针的迭代版本,只需 额外空间。