堆变量作用域

Question

我正在实现一个堆，但我无法理解为什么变量 'int hole' 不在我的插入方法的范围内。我已经尝试了很多事情，例如，在方法和 class 中声明它。我的插入中的 for 循环是引发错误的原因。

template <class Comparable>
class BinaryHeap
{
    public:
        explicit BinaryHeap( int capacity = 100 );
        bool isEmpty( ) const;
        bool isFull( ) const;
        const Comparable & findMin( ) const;
        void insert( const Comparable & x );
        void deleteMin( );
        void deleteMin( Comparable & minItem );
        void makeEmpty( );
    private:
        int currentSize; // Number of elements in heap
        vector<Comparable> array; // The heap array
        void buildHeap( );
        void percolateDown( int hole );
 };

template <class Comparable>
void BinaryHeap<Comparable>::insert( const Comparable & x )
{
    if( isFull( ) ) //throw Overflow( );
    // Percolate up
        int hole = ++currentSize;
    **for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )**
        array[ hole ] = array[ hole / 2 ];
        array[ hole ] = x;
}

Answer 1

array[ hole ] = x; 在 for 循环之外。
hole 仅在 if( isFull( ) ).

它应该看起来更像这样：

int hole = /* initial value */;

if( isFull( ) )
{
    //throw Overflow( );
    // Percolate up
    hole = ++currentSize;
}

for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
{
    array[ hole ] = array[ hole / 2 ];
    array[ hole ] = x;
}

Answer 2

注释掉 throw 后，if 语句看起来像

if( isFull( ) )
{
    int hole = ++currentSize;
}

变量hole仅在if语句中"in scope"。

Answer 3

这是因为变量 hole 是在 if 子句的 "then" 分支内声明的。您可能遗漏了一些大括号。

Answer 4

没有花括号 ({})，if 和 for 块只包含一个语句。因此，如果我们为了清楚起见添加它们，您的代码实际上将等同于以下内容：

if( isFull( ) ) {
    int hole = ++currentSize;
}
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 ) {
    array[ hole ] = array[ hole / 2 ];
}
array[ hole ] = x;

当这样写时，很明显为什么代码无法编译。相反，您应该自己添加花括号，以便它们正确地表示您想要的块：

if (isFull()) {
    int hole = ++currentSize;
    for (; hole > 1 && x < array[ hole / 2 ]; hole /= 2) {
        array[ hole ] = array[ hole / 2 ];
        array[ hole ] = x;
    }
}

Answer 5

你写的地方

if( isFull( ) ) //throw Overflow( );

我认为你的意图是

if( isFull( ) ) {
 //throw Overflow( );
}

其他人解释了以下行与 if 相关联时会发生什么，因为您遗漏了那些 { }

顺便说一句，我注意到您使用的是基于 1 的索引。大多数堆算法文档都假定基于 1 的索引，所以我希望这就是原因。但是 std::vector 使用基于 0 的索引。如果您的意图是浪费矢量的元素 0，请记住在将矢量大小时调整为 capacity+1 而不仅仅是 capacity。当我编写堆算法代码时，我总是重新定义基于 0 的索引的规则。我使用规则 H[i]<=H[2*i+1] && h[i]<=h[2*i+2]

而不是 H[i]<=H[2*i] && h[i]<=h[2*i+1]

堆变量作用域

Heap variable scope

c++

variables

templates

scope

syntax-error