給每個遞歸調用一個清楚的規格,較容易理解鏈表的操作。我們會刪除所有數值等於目標的節點,並保持其餘節點的身分和相對次序。
規格和所有權
定義 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 共作多少次調用?在遞歸深度受限的語言中,哪種資源可能耗盡?)
解答 · 答案
共有 個非空調用加一個基礎調用,即 次調用,在最深處全部同時在堆疊上,因為釋放要到遞歸返回時才開始。調用堆疊佔 空間,即使沒有節點保留,也可能溢出。用指向前一個存活節點的指標的迭代版本,只需 額外空間。