2

2 つの質問があります。

1)最近、私はmax heapを構築しようとしています。CLRSを読んでも、実行してもバグが見つかりません。以下は私のコードです...

def maxHeapify(list, index):
    int = index
    left = (int+1) * 2 - 1
    right = (int+1) * 2
    largest = 0
    if left < len(list):
        if (left <= len(list)) & (list[left] >= list[int]):
            largest = left
        else: 
            largest = int
    if right < len(list):
        if (right <= len(list)) & (list[right] >= list[largest]):
            largest = right
    else:
        pass
    if largest != int:
        listNew = swapWithinList(list, int, largest)
        listNew = maxHeapify(listNew, largest)
    else:
        return listNew


def swapWithinList(list, id1, id2):
    num1 = list[id1]
    num2 = list[id2]
    listNew = list[:id1]
    listNew.append(num2)
    listNew = listNew + list[(id1+1):id2]
    listNew.append(num1)
    listNew = listNew + list[(id2+1):]
    return listNew

入力しますが、コンソールには次のように表示されます。

UnboundLocalError: local variable 'listNew' referenced before assignment

returnステートメントを間違った行に置いたということですか、それとも言及していないことがありますか?

2)反復とは何ですか?

質問をするとき、私は少し恥ずかしいです。しかし、反復とは何ですか？ウィキは、プロセスの各繰り返しがそれを意味すると言っているので、ループが各ラウンドを与える結果ですか?

イテレータはPythonの基本要素のようですが、イテレータとイテレーションの違いは何ですか?

4

2 に答える 2

6

1:

これ以上のコメントはありませんが、ウィキペディアから改作されたコードは次のとおりです。

def max_heapify(A, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    if left < len(A) and A[left] > A[largest]:
        largest = left
    if right < len(A) and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A) // 2, -1, -1):
        max_heapify(A, i)

例：

def ptree(A, i=0, indent=0):
    if i < len(A):
        print '  ' * indent, A[i]
        ptree(A, i * 2 + 1, indent + 1)
        ptree(A, i * 2 + 2, indent + 1)

A = range(9) 
build_max_heap(A)
ptree(A)

結果：

 8
   7
     3
       1
       0
     4
   6
     5
     2

ご不明な点がございましたら、お問い合わせください。

2:

Python での反復は、技術的には、例外next()が発生するまでオブジェクトのメソッドを繰り返し呼び出すプロセスです。StopIterationこのメソッドを持つオブジェクトをnextIterator と呼びます。呼び出し元のコードに Iterator を提供できるオブジェクトは、Iterable と呼ばれます。

于 2012-10-30T15:18:40.643 に答える
0

問題はここにあります：

if largest != int:
        listNew = swapWithinList(list, int, largest)
        listNew = maxHeapify(listNew, largest)
    else:
        return listNew

if ステートメントが false の場合、listNew を返そうとしますが、この時点では listNew が存在しない可能性があります (if ステートメントが true の場合にのみ割り当てられます)。

反復は、ループを通過するだけのパス、または一般的には、より大きなものを通過する単一のパスです。イテレータは、データ構造を反復処理するか、要素を 1 つずつ処理するオブジェクトです。

于 2012-10-30T15:19:36.267 に答える