此功能爲什麼向後打印鏈接列表？

我正在通過唐尼的如何像計算機科學家一樣思考，我對Linked List有一個關於他的print_backward（）函數的問題。此功能爲什麼向後打印鏈接列表？

首先，這裏唐尼在Python實現鏈表：

class Node: 
    #initialize with cargo (stores the value of the node) 
    #and the link. These are set to None initially. 
    def __init__(self, cargo = None, next = None): 
     self.cargo = cargo 
     self.next = next 

    def __str__(self): 
     return str(self.cargo)

我們給這個類中的下列貨物和鏈接值：

#cargo 
node1 = Node('a') 
node2 = Node('b') 
node3 = Node('c') 
#link them 
node1.next = node2 
node2.next = node3

要打印的鏈表，我們用另一種唐尼的職能。

def printList(node): 
    while node: 
     print node, 
     node = node.next 

>>>printList(node1) 
>>>a b c

所有非常簡單。但我不明白如何在以下函數中的遞歸調用允許向後打印鏈表。

def print_backward(list): 
    if list == None : return 
    print_backward(list.next) 
    print list, 

>>>print_backward(node1) 
>>>c b a

不會調用「list.next」作爲print_backward的值只是給你「b c」？

注意：下面幾個人指出，這個函數設計的很糟糕，因爲給定任何列表，我們不能表明它總是會達到基本情況。唐尼在同一章的後面也指出了這個問題。

來源

2012-07-19 Renklauf

正如其他答案所指出的那樣，這個函數是遞歸的說明，但是也有一些缺陷：不是尾遞歸（會在長列表上導致堆棧溢出錯誤），類節點應該從'object'繼承，'' list'不應該被用作變量名稱。 – jrouquie 2012-07-19 21:26:00

在正向打印版本中，它會在進行遞歸調用之前打印每個節點。在後向打印版本中，它在之後打印每個節點進行遞歸調用。

這不是巧合。

這兩個函數都會遞歸到列表末尾。不同之處在於在此過程中還是之後發生打印。

函數調用使用棧，後進先出的數據結構，它記住了函數調用時計算機執行代碼的位置。以一種順序放入堆棧的內容以相反順序排列。因此，遞歸按照原始調用的相反順序「解開」。打印發生在退繞過程期間，即在每次遞歸調用完成之後。

來源

2012-07-19 21:29:57 kindall

關於LIFO的觀點正是我需要了解唐尼的功能如何運作的。謝謝您的幫助：-） – Renklauf 2012-07-19 21:34:33

它使用遞歸。它一直「拉」到最後，然後在每次調用返回時打印每個元素。由於第一個打印是最近被打印的，所以它向後打印列表。

來源

2012-07-19 21:14:49 Wug

號有2種遞歸：

尾遞歸：如果有什麼不同之處返回其值的函數返回後做。函數調用不會堆疊。
遞歸首先找到基本案例（在這種情況下，null，然後向後處理列表）。每個函數調用都被推入堆棧中，以供後續處理。在你的例子中，函數被堆疊爲'a'->'b'->'c'->null，然後當堆棧彈出時，作者顯示反向打印：`如果null返回：打印'c' - >打印'b' - >打印'a'

就你而言，作者只演示了遞歸的不同概念，並用它向後打印列表。

來源

2012-07-19 21:16:26 cybertextron

你的節點是這個樣子：

node1 node2 node3 
'a' => 'b' => 'c' => None

在第一次調用print_backward，變量list具有價值'a'，以print_backward招一個進一步向下行後續調用。請注意，他們沒有任何打印任何東西，直到你打到警衛（None）在哪個時間，事情得到打印從前到後作爲print_backward收到節點'c'必須返回之前print_backward那接收節點'b'可以打印（因爲打印語句在函數調用之後）等等。

雖然我認識到這是別人的代碼，但在這裏有幾件事是不好的做法 - 最好我現在告訴你，而你在學習，而不是在以後。首先，不要使用list作爲變量名稱，因爲它是python中內置函數/類型的名稱。第二，平等測試if obj == None最好由if obj is None完成，最後，讓你的類繼承object（class node(object):），這是一個好主意，因爲它使它成爲一種新風格的類。

來源

2012-07-19 21:16:47 mgilson

如果list不是None，它會調用print_backward，然後打印列表的第一個成員。展開，這實際上是發生了什麼。您可以看到，當電話開始返回時，會打印'c'，然後'b'，然後'a'。

它看起來在實際打印列表一樣，它打印的第一個節點

print_backward(list='a','b','c') 
    print_backward(list='b','c') 
    print_backward(list='c') 
     print_backward(list=None) 
     list is None, so return 
     print 'c' 
    print 'b','c' 
    print 'a','b','c'

來源

2012-07-19 21:20:34 MStodd

def print_backward(list): 
    if list == None : return 
    print_backward(list.next) 
    print list,

會不會叫「list.next」爲print_backward的價值簡單地給你「BC」？

否;圖片當a-> b-> c傳遞給print_backward時發生了什麼：

「[b c]」被傳遞給print_backward，然後打印出「a」。但打印「a」之前的「print_backward」會自行調用。所以：

[ABC]不是無，那麼B->Ç被傳遞給print_backward
- [BC]傳遞給print_backward
  - [C]被傳遞到print_backward
  - 無被傳遞到print_backward
    - 返回
  - 然後「C 「打印
- 然後」b「被印刷
然後」a「被印刷
退出。

來源

2012-07-19 21:21:49 LSerni

有時我覺得將遞歸看作僅僅構造一個按特定順序調用的列表更容易。隨着函數的繼續，它會建立一堆調用，直到它最終到達基本情況。基本情況是不需要進一步分解程序的情況;在這個函數中，基本情況是什麼時候什麼都不打印，在這種情況下，我們只是在return之前不做任何事情。

很酷的東西通常發生在我們展開函數調用的遞歸堆棧的路上。目前，print_backward已在列表中的每個元素上調用，並且現在將「展開」，先完成最近的調用，然後再調用最近的調用。這意味着當您在最後一個元素上調用print_backward時創建的「實例」是第一個要完成的元素，因此最後一個元素是第一個要打印的元素，接着是倒數第二個，倒數第三個等等。直到原來的函數最終退出。

在發生了什麼這表示請看：

print_backward(node1)   #first call to print_backward 
    print_backward(node2)  #calls itself on next node 
     print_backward(node3) #calls itself on next node 
      print_backward(None) #calls itself on None. We can now start unwinding as this is the base case: 
     print Node3    #now the third invocation finishes... 
    print Node2     #and the second... 
print Node1      #and the first.

雖然功能首先是在較早的元素調用時，實際打印該元素來遞歸調用之後的部分，所以不會實際執行直到遞歸調用完成。在這種情況下，這意味着print list部分將不會執行，直到所有後面的元素都先打印完（按相反順序），這樣就可以向後打印列表元素。：D

來源

2012-07-19 21:29:54

此功能爲什麼向後打印鏈接列表？

回答

相關問題