練習 13：單鏈表 · 笨辦法學 Python · 續中文版

# 練習 13：單鏈表 > 原文：[Exercise 13: Single Linked Lists](https://learncodethehardway.org/more-python-book/ex13.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 你將實現的第一個數據結構是單鏈表。我將描述數據結構，列出你應該實現的所有操作，并給你實現需要通過的單個測試。你應該首先嘗試使用此數據結構，然后再觀看我的實現和審計視頻，以便你了解該過程。 > 警告 > 這些都不是數據結構的高效實現。它們故意做成樸素和緩慢的，以便我們可以在練習 18 和 19 中講解度量和優化。如果你在行業工作中嘗試使用這些數據結構，就會有性能問題。 ## 描述在面向對象語言（如 Python）中處理許多數據結構時，你需要理解三個常見概念： + “節點”，通常是數據結構的容器或存儲單元。你的值保存在這里。 + “邊”，但我們會叫它“指針”或“鏈接”，它指向其他節點。這些都放在每個節點內，通常作為實例變量。 + “控制器”，它是一些類，知道如何使用節點中的指針來正確構造數據。在 Python 中，我們將映射這些概念，如下所示： + 節點只是一個類定義的對象。 + 指針（邊）只是節點對象中的實例變量。 + 控制器是另一個簡單的類，它使用節點存儲所有內容并構建數據。這是所有的操作（`push`，`pop`，`list`等）的地方，通常控制器的使用者從來沒有真正處理節點或指針。在一些關于算法的書中，你將看到這樣的實現，將節點和控制器組合成一個類，但這是非常混亂的，也違反了設計中的問題分離。最好將節點與控制類分開，以便只做一件事并且把它做好，以及你知道錯誤在哪里。想象一下，我們想要存儲一系列汽車。我們有第一輛車，后面是第二輛，直到最后一輛。想象這個列表，我們可以開始設想一個節點/指針/控制器設計： + 節點包含每個車的描述。也許這只是一個`Car`類的`node.value`變量。如果你很懶，我們可以調用這個`SingleLinkedListNode`或`SLLNode`。 + 然后，每個`SLLNode`具有一個鏈接，指向鏈表中下一個節點。訪問`node.next`可以讓你訪問下一輛車。 + 控制器，簡單地稱為`SingleLinkedList`，具有諸如`push`，`pop`，`first`或`count`之類的操作，它們接受`Car`，并且使用節點在內部進行存儲。當你將汽車`push`到`SingleLinkedList`控制器上時，它將處理在一個節點的內部鏈表，來將其存儲在最后。 > 注 > 當 Python 有個相當好用并且快速的`list`時，為什么我們要這么做呢？完全是為了學習數據結構。在真實世界中，你可以使用 Python 的`list`并繼續。為了實現`SingleLinkedListNode`，我們需要一個簡單的類，如下： ```py class SingleLinkedListNode(object): def __init__(self, value, nxt, prev): self.value = value self.next = nxt def __repr__(self): nval = self.next and self.next.value or None return f"[{self.value}:{repr(nval)}]" ``` 我們必須使用單詞`nxt`，因為`next`是 Python 中的保留字。除此之外，這是一個非常簡單的課程。最復雜的是`__repr__`函數。當你使用`%r`格式或在節點上調用`repr()`時，這會打印調試輸出。它應該返回一個字符串。 > 注 > 現在花時間了解如何使用`SingleLinkedListNode`類手動構建列表，然后手動遍歷它。這是一個很好的45分鐘 hack spike，嘗試練習它。 ## 控制器一旦我們在`SingleLinkedListNode`類中定義了我們的節點，我們可以確切地知道控制器應該做什么。每個數據結構都有所需的常用操作列表，使其有用。不同的操作花費不同的內存（空間）和時間，一些是昂貴的，另一些是快速的。`SingleLinkedListNode`的結構使得一些操作非常快，但是許多其他操作非常慢。在實現過程中，你將會了解到它。查看操作的最簡單方法是，查看`SingleLinkedList`類的框架版本： ```py class SingleLinkedList(object): def __init__(self): self.begin = None self.end = None def push(self, obj): """將新的值附加到鏈表尾部。""" def pop(self): """移除最后一個元素并返回它。""" def shift(self, obj): """將新的值附加到鏈表頭部。""" def unshift(self): """移除第一個元素并返回它。""" def remove(self, obj): """尋找匹配的元素并從中移除。""" def first(self): """返回第一個元素的*引用*，不要移除。""" def last(self): """返回最后一個元素的*引用*，不要移除。""" def count(self): """計算鏈表中的元素數量。""" def get(self, index): """獲取下標處的值。""" def dump(self, mark): """轉儲鏈表內容的調試函數。""" ``` 在其他練習中，我只會告訴你這些操作，并留給你來弄清楚，但是對于這個練習，我會指導你實現。查看`SingleLinkedList`中的函數列表，來查看每個操作以及如何使用的注釋。 ## 測試我現在要向你提供測試，實現這個類時，你必須使其能夠工作。你會看到我已經遍歷了每一個操作，并試圖覆蓋大部分的邊界情況，但是當我進行審計時，你會發現實際上我可能錯過了一些。人們常常不會對一些案例進行測試，例如“零個元素”和“一個元素”。 ```py from sllist import * def test_push(): colors = SingleLinkedList() colors.push("Pthalo Blue") assert colors.count() == 1 colors.push("Ultramarine Blue") assert colors.count() == 2 def test_pop(): colors = SingleLinkedList() colors.push("Magenta") colors.push("Alizarin") assert colors.pop() == "Alizarin" assert colors.pop() == "Magenta" assert colors.pop() == None def test_unshift(): colors = SingleLinkedList() colors.push("Viridian") colors.push("Sap Green") colors.push("Van Dyke") assert colors.unshift() == "Viridian" assert colors.unshift() == "Sap Green" assert colors.unshift() == "Van Dyke" assert colors.unshift() == None def test_shift(): colors = SingleLinkedList() colors.shift("Cadmium Orange") assert colors.count() == 1 colors.shift("Carbazole Violet") assert colors.count() == 2 assert colors.pop() == "Cadmium Orange" assert colors.count() == 1 assert colors.pop() == "Carbazole Violet" assert colors.count() == 0 def test_remove(): colors = SingleLinkedList() colors.push("Cobalt") colors.push("Zinc White") colors.push("Nickle Yellow") colors.push("Perinone") assert colors.remove("Cobalt") == 0 colors.dump("before perinone") assert colors.remove("Perinone") == 2 colors.dump("after perinone") assert colors.remove("Nickle Yellow") == 1 assert colors.remove("Zinc White") == 0 def test_first(): colors = SingleLinkedList() colors.push("Cadmium Red Light") assert colors.first() == "Cadmium Red Light" colors.push("Hansa Yellow") assert colors.first() == "Cadmium Red Light" colors.shift("Pthalo Green") assert colors.first() == "Pthalo Green" def test_last(): colors = SingleLinkedList() colors.push("Cadmium Red Light") assert colors.last() == "Cadmium Red Light" colors.push("Hansa Yellow") assert colors.last() == "Hansa Yellow" colors.shift("Pthalo Green") assert colors.last() == "Hansa Yellow" def test_get(): colors = SingleLinkedList() colors.push("Vermillion") assert colors.get(0) == "Vermillion" colors.push("Sap Green") assert colors.get(0) == "Vermillion" assert colors.get(1) == "Sap Green" colors.push("Cadmium Yellow Light") assert colors.get(0) == "Vermillion" assert colors.get(1) == "Sap Green" assert colors.get(2) == "Cadmium Yellow Light" assert colors.pop() == "Cadmium Yellow Light" assert colors.get(0) == "Vermillion" assert colors.get(1) == "Sap Green" assert colors.get(2) == None colors.pop() assert colors.get(0) == "Vermillion" colors.pop() assert colors.get(0) == None ``` 仔細研究此測試，以便你在嘗試實現之前，先了解每個操作應如何工作。我不會一次將所有這些代碼寫入文件。相反，最好每次只做一個測試，并使其小部分能夠工作。 > 注 > 這里，如果你不熟悉自動化測試，你可能想要觀看視頻，來看我怎么做。 ## 審計入門當你執行每個測試時，你將審計代碼來找到缺陷。最終，你將跟蹤你在審計中找到的缺陷數量，但現在你需要在寫完代碼之后執行審計。“審計”類似于政府認為你偷稅漏稅的時候，稅務局所做的工作。他們遍歷每筆交易，每筆收入金額，所有支出金額，以及你為什么這樣來花費。代碼審核與之類似，因為你遍歷每個函數，并分析所有輸入參數，以及所有輸出值。要進行基本的審計，你將執行此操作： + 從你的測試用例開始。在這個例子中我們來審計`test_push`。 + 查看第一行代碼，并確定正在調用什么以及正在創建什么。在這種情況下，它的`colors = SingleLinkeList()`。這意味著我們正在創建`colors`變量，并調用`SingleLinkeList.__ init__`函數。 + 跳到`__init__`函數的頂部，保持測試用例和目標函數（`__init__`）并排。確認你已經這樣做了。然后，確認你使用數值和類型正確的函數參數來調用它。在這種情況下`__init__`只需要`self`，它應該是正確的類型。 + 然后進入`__init__`并逐行審計，以相同的方式確認每個函數調用和變量。它的參數數量正確嗎？類型正確嗎？ + 在每個分支（`if`語句，`for`循環，`while`循環）中，確認邏輯是正確的，并且它處理邏輯中的任何可能的條件。`if`語句的`else`子句有錯誤嗎？循環能結束嗎？然后潛入每個分支，以相同方式跟蹤函數，潛入，檢查變量，回來，并檢查返回值。 + 當你到達一個函數結尾或任何`return`的時候，跳回到`test_push`調用者，來檢查返回值是否匹配期望值，當你調用它的時候。記住，盡管如此，你也可以對`__init__`中的每個調用搞這么做。 + 最后，當你到達`test_push`函數的末尾時，你就完成了，并且已經完成了它調用的每個函數的遞歸檢查。這個流程一開始似乎很乏味，是的，但是你會越來越快，在視頻中你會看到，在運行每個測試之前我都這么做（或至少我真的努力嘗試這么做）。我按照以下流程： + 寫一些測試代碼。 + 編寫代碼使測試工作。 + 審計二者。 + 運行測試，看看我是否正確。 ## 挑戰練習我們現在到達了這個部分，你已經準備好嘗試它了。首先，瀏覽測試并研究它的作用，并研究`sllist.py`中的代碼，來弄清楚你需要做什么。我建議當你嘗試在`SingleLinkeList`中實現一個函數時，首先寫一些注釋來描述它做了什么，然后填充 Python 代碼來使這些注釋工作。你會看到我在視頻中這樣做。當你花了一兩個 45 分鐘的會話來 Hack 它并試圖讓它工作時，現在是觀看視頻的時候了。你首先需要嘗試它，以便更好地了解我正在嘗試的事情，這樣可以使視頻更容易理解。視頻中我只是編程而不說話，但我會做一個旁白來討論發生了什么。視頻也更快來節省時間，我會剪切掉任何無聊的錯誤或時間的浪費。一旦你看到我是怎么做的，你已經做了筆記（對嗎？），然后去嘗試更嚴格的東西，并盡可能仔細地執行代碼審核過程。 ## 審計編寫代碼后，請確保執行第三部分中描述的審計流程。如果你不太確定如何完成，我也將在視頻中為這個練習執行審計。 ## 深入學習為這次練習準備的深入學習是，完全根據我在第三部分的介紹中描述的方式，嘗試再次實現該算法。你還應該嘗試思考，這個數據結構中的哪些操作最有可能很慢。完成后，對你創建的內容執行審計。