4

私はダウニーの「コンピューター科学者のように考える方法」を研究していますが、リンクリストの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

print_backwardの値として「list.next」を呼び出すと、単に「bc」が得られませんか？

注：以下の何人かの人々は、この関数は不適切に設計されていると指摘しています。これは、どのリストでも、常に基本ケースに到達することを示すことができないためです。ダウニーはまた、同じ章の後半でこの問題を指摘しています。

4

7 に答える 7

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

print_backwardの値として「list.next」を呼び出すと、単に「bc」が得られませんか？

いいえ; a-> b-> cがprint_backwardに渡されたときに何が起こるかを想像してください：

「[bc]」がprint_backwardに渡され、「a」が出力されます。ただし、「a」が出力される前の「print_backward」は、それ自体を呼び出します。それで：

  • [abc]はNoneではないため、b->cはprint_backwardに渡されます
    • [bc]がprint_backwardに渡されます
      • [c]はprint_backwardに渡されます
      • print_backwardには何も渡されません
        • これは
      • 次に「c」が出力されます
    • 次に「b」が出力されます
  • 次に「a」が出力されます
  • 終了する。
于 2012-07-19T21:21:49.617 に答える
2

順方向印刷バージョンでは、再帰呼び出しを実行する前に各ノードを印刷します。逆方向印刷バージョンでは、再帰呼び出しを行った後に各ノードを印刷します。

これは偶然ではありません。

両方の関数は、リストの最後に到達するまで繰り返されます。違いは、印刷がこのプロセス中に行われるか、その後に行われるかです。

関数呼び出しはスタックを使用します。これは、関数呼び出しが行われたときにコンピューターがコードを実行していた場所を記憶する後入れ先出しのデータ構造です。ある順序でスタックに置かれたものは、逆の順序で外れます。したがって、再帰は元の呼び出しの逆の順序で「巻き戻され」ます。印刷は、巻き戻しプロセス中、つまり、各再帰呼び出しが完了した後に行われます。

于 2012-07-19T21:29:57.077 に答える
1

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-19T21:20:34.493 に答える
1

再帰は、特定の順序で行われる呼び出しのリストを作成するだけであると考える方が簡単な場合があります。関数が続行すると、最終的にベースケースに到達するまで、一連の呼び出しが蓄積されます。基本的なケースは、プログラムをさらに細かく分割する必要がない状況です。この関数の基本ケースは、印刷するものがない場合です。この場合、。を使用せずにそのままにしreturnます。

関数呼び出しの再帰的なスタックを巻き戻すときに、通常、クールなことが発生します。現在、print_backwardリストの各要素で呼び出されており、「アンワインド」され、最新の呼び出しが最初に終了し、以前の呼び出しが最後に終了します。これは、最後の要素で呼び出したときに作成された「インスタンス」がprint_backward最初に終了することを意味します。したがって、最後の要素が最初に印刷され、次に最後から2番目、最後から3番目などになります。 、元の関数が最終的に終了するまで。

何が起こったかのこの表現を見てください：

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-19T21:29:54.317 に答える
0

再帰を使用しています。最後まで「ジッパー」で閉じてから、呼び出しが戻るたびにすべての要素を出力します。最初に印刷するのは最後に呼び出されたものなので、リストを逆方向に印刷します。

于 2012-07-19T21:14:49.900 に答える
0

いいえ。再帰には2種類あります。

  1. 末尾再帰：関数が戻った後、値を返す以外に何もすることがない場合。関数呼び出しはスタックされません。
  2. 最初に基本ケースを見つける再帰（この場合、、、null次にリストを逆方向に処理します）。各関数呼び出しは、後で処理するためにスタックにプッシュされます。あなたの例では、関数はと'a'->'b'->'c'->nullしてスタックされ、スタックがポップされると、作者は逆方向に印刷することによって次のことを示しました： `if null return：print'c'-> print'b'-> print'a'

あなたの場合、作者は再帰の異なる概念を示しただけで、それを使用してリストを逆方向に印刷しました。

于 2012-07-19T21:16:26.587 に答える
0

ノードは次のようになります。

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

の最初の呼び出しでprint_backwardは、変数listの値はであり'a'、その後の呼び出しでは、print_backwardさらに1つ下に移動します。ガード（）に当たるまで、それらは何も出力しないことに注意してください。受信したノードが印刷する前に、受信したノードが戻る必要Noneがあるため、物事は後ろから前に印刷されます（printステートメントは関数呼び出しの後にあるため） ） 等々。print_backward'c'print_backward'b'

これは他の誰かのコードであると私は認識していますが、ここには悪い習慣がいくつかあります。後でではなく、学習している間に今お話しするのが最善です。listまず、 Pythonの組み込み関数/型の名前であるため、変数名として使用しないでください。次に、等式テストif obj == Noneは、によってより適切に実行されます。最後に、クラスを（ ）if obj is Noneから継承することをお勧めします。これにより、新しいスタイルのクラスになります。objectclass node(object):

于 2012-07-19T21:16:47.170 に答える