C语言请我想改变Maxheap删除和插入堆使用为使用递归[关闭]

已关闭，此问题需要details or clarity。目前不接受答复。
**想改善这个问题吗？**通过editing this post添加详细信息并澄清问题。

5天前关闭。
Improve this question
我想知道这段代码是如何递归工作的。但我不知道从哪里开始修复这个代码。我请求你的帮助..！
臀部的创作部分比较长，所以省略了

void insert_max_heap(HeapType* h, element item) { // max heap's insert function
    int i;

    i = ++(h->heap_size);

    while ((item.key > h->heap[i / 2].key) && (i != 1)) {
        h->heap[i] = h->heap[i / 2];
        i = i / 2;
    }

    h->heap[i] = item;
}

element delete_max_heap(HeapType* h) { // max heap's delete function
    element item, temp;
    item = h->heap[1];
    temp = h->heap[h->heap_size];

    h->heap_size = h->heap_size - 1;

    int parent, child;
    parent = 1;
    child = 2;

    while (child <= h->heap_size) {
        if ((child < h->heap_size) && (h->heap[child].key < h->heap[child + 1].key))
            child++; 
        if (temp.key >= h->heap[child].key)
            break;

        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    h->heap[parent] = temp;
    return item;
}

您有：

void insert_max_heap( HeapType *h, element item ) {
   int i = ++( h->heap_size );

   while ( i != 1 && item.key > h->heap[ i / 2 ].key ) {
      h->heap[ i ] = h->heap[ i / 2 ];
      i = i / 2;
   }

   h->heap[ i ] = item;
}

这里有个窃听器
如果h->heap_size是堆中元素的数量，那么你最终可以赋值给h->heap[ h->heap_size ]，这是错误的。
如果h->heap_size是堆上最后一个元素的索引，那么当i == 0时只剩下一个槽。但当i == 1时，循环结束。
我假设h->heap_size是堆的大小，我将使用n作为变量名，这是大小的习惯。

void insert_max_heap( HeapType *h, element item ) {
   int n = ++( h->heap_size );

   while ( n != 1 && item.key > h->heap[ n / 2 - 1 ].key ) {
      h->heap[ n - 1 ] = h->heap[ n / 2 - 1 ];
      n = n / 2;
   }

   h->heap[ n - 1 ] = item;
}

递归是一种重复执行代码的方式，因此我们需要识别重复的代码。这是显而易见的。
重复的部分有参数HeapType *h, element item, int n，并返回int。所以我们的递归函数看起来像这样：

int insert_max_heap_body( HeapType *h, element item, int i ) {
   ...
}

让我们从移动循环开始。

int insert_max_heap_helper( HeapType *h, element item, int n ) {
   while ( n != 1 && item.key > h->heap[ n / 2 - 1 ].key ) {
      h->heap[ n - 1 ] = h->heap[ n / 2 - 1 ];
      n = n / 2;
   }

   return n - 1;
}

void insert_max_heap( HeapType *h, element item ) {
   int n = ++( h->heap_size );
   int i = insert_max_heap_helper( h, item, n );
   h->heap[ i ] = item;
}

现在让它递归。

int insert_max_heap_helper( HeapType* h, element item, int i ) {
   if ( n == 1 || item.key <= h->heap[ n / 2 - 1 ].key )
      return n - 1;

   h->heap[ n - 1 ] = h->heap[ n / 2 - 1 ];
   n = n / 2;

   return insert_max_heap_helper( h, item, n );
}

void insert_max_heap( HeapType* h, element item ) {
   int n = ++( h->heap_size );
   int i = insert_max_heap_helper( h, item, n );
   h->heap[ i ] = item;
}

让我们把最后一个赋值移到助手中。这种变化纯粹是主观的，但我认为它们更好地说明了函数实现了什么。

void insert_max_heap_helper( HeapType* h, element item, int n ) {
   int half = n / 2;
   if ( n == 1 || item.key <= h->heap[ half - 1 ].key ) {
      h->heap[ i ] = item;
      return;
   }

   h->heap[ n - 1 ] = h->heap[ half - 1 ];

   return insert_max_heap_helper( h, item, half );
}

void insert_max_heap( HeapType* h, element item ) {
   insert_max_heap_helper( h, item, ++( h->heap_size ) );
}

现在我们有了一个递归的解决方案。但是为什么呢！？！这会占用更多的堆栈空间，而且由于额外的函数调用，它会变慢。

C语言请我想改变Maxheap删除和插入堆使用为使用递归[关闭]

1条答案

相关问题

热门标签

最新问答

C语言 请我想改变Maxheap删除和插入堆使用为使用递归[关闭]

1条答案

相关问题

热门标签

最新问答

C语言请我想改变Maxheap删除和插入堆使用为使用递归[关闭]