C语言extract_max实现中指针类型不兼容警告及输出错误问题

问题现象 #

实现extract_max函数时，尝试以指针形式传递堆的size变量，编译出现指针类型不兼容警告：

extract_max.c: In function ‘max_heapify’:
extract_max.c:26:20: warning: passing argument 2 of ‘max_heapify’ from incompatible pointer type [-Wincompatible-pointer-types]
   26 |   max_heapify(arr, &new_size, largest);
      |                    ^~~~~~~~~
      |                    |
      |                    int **
extract_max.c:6:33: note: expected ‘int *’ but argument is of type ‘int **’
   6 | void max_heapify(int *arr, int *new_size, int i)
      |                            ~~~~~^~~~~~~~
extract_max.c: In function ‘extract_max’:
extract_max.c:41:20: warning: passing argument 2 of ‘max_heapify’ from incompatible pointer type [-Wincompatible-pointer-types]
   41 |   max_heapify(arr, &size, 0);
      |                    ^~~~~
      |                    |
      |                    int **
extract_max.c:6:33: note: expected ‘int *’ but argument is of type ‘int **’
   6 | void max_heapify(int *arr, int *new_size, int i)

编译后程序输出结果错误。改用值传递size并将循环条件改为size-1时，程序能输出正确结果：

printf("
The elements of the heap after extract_max are:
");  
for(int i=0; i<size-1; i++)
    printf("%d ", arr[i]);

完整可复现代码：

#include<stdio.h>
#include<stdlib.h>

void max_heapify(int *arr, int *new_size, int i)
{
    int l = 2*i+1;
    int r = 2*i+2;
    int largest = i, temp;
    
    if(l<*new_size && arr[largest]<arr[l])
        largest = l;
            
    if(r<*new_size && arr[largest]<arr[r])
        largest = r;    
        
    if(largest != i)
    {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        
        max_heapify(arr, &new_size, largest);
    }   
}

void extract_max(int *arr, int *size)
{
    int max;
    if(*size < 1)
        printf("
No element in the heap !");
        
    else
    {
        max = arr[0];
        arr[0] = arr[*size-1];
        *size = *size-1;
        max_heapify(arr, &size, 0);
        printf("
The extracted max elemnt is: %d", max);
    }   
}

int main()
{
    int i;
    int arr[] = {12, -8, 20, 2, 3, 89, 71, -6, 11, 10};
    int size = 10;
            
    //build_max heap
    for(i=size/2-1; i>=0; i--)
        max_heapify(arr, &size, i);
    
    printf("The elements of the heap after max heapification are:
");  
    for(int i=0; i<size; i++)
        printf("%d ", arr[i]);
    printf("
");   
        
    extract_max(arr, &size);
    
    printf("
The elements of the heap after extract_max are:
");  
    for(int i=0; i<size; i++)
        printf("%d ", arr[i]);
    printf("
");
    
    return 0;
}

问题分析 #

警告的核心是指针类型不匹配：

• max_heapify的第二个参数要求是int *（指向int的指针）
• 两处调用时传递的&new_size和&size都是int **类型：
  • max_heapify里的new_size本身已经是int *，取地址后变成指向指针的指针
  • extract_max里的size同样是int *，取地址后类型不兼容

这种类型错误会导致程序访问错误的内存地址，最终输出异常。

修复方案 #

直接传递指针变量本身，而非它的地址即可解决类型不兼容问题，同时修正一处拼写错误：

修改后的完整代码 #

#include<stdio.h>
#include<stdlib.h>

void max_heapify(int *arr, int *new_size, int i)
{
    int l = 2*i+1;
    int r = 2*i+2;
    int largest = i, temp;
    
    if(l<*new_size && arr[largest]<arr[l])
        largest = l;
            
    if(r<*new_size && arr[largest]<arr[r])
        largest = r;    
        
    if(largest != i)
    {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        
        // 直接传递new_size，而非&new_size
        max_heapify(arr, new_size, largest);
    }   
}

void extract_max(int *arr, int *size)
{
    int max;
    if(*size < 1)
        printf("
No element in the heap !");
        
    else
    {
        max = arr[0];
        arr[0] = arr[*size-1];
        *size = *size-1;
        // 直接传递size，而非&size
        max_heapify(arr, size, 0);
        printf("
The extracted max element is: %d", max);
    }   
}

int main()
{
    int i;
    int arr[] = {12, -8, 20, 2, 3, 89, 71, -6, 11, 10};
    int size = 10;
            
    //build_max heap
    for(i=size/2-1; i>=0; i--)
        max_heapify(arr, &size, i);
    
    printf("The elements of the heap after max heapification are:
");  
    for(int i=0; i<size; i++)
        printf("%d ", arr[i]);
    printf("
");   
        
    extract_max(arr, &size);
    
    printf("
The elements of the heap after extract_max are:
");  
    for(int i=0; i<size; i++)
        printf("%d ", arr[i]);
    printf("
");
    
    return 0;
}

修复要点 #

1. 将max_heapify递归调用中的&new_size改为new_size
2. 将extract_max中调用max_heapify的&size改为size
3. 修正extract_max中的拼写错误：elemnt改为element

修改后程序可正确编译运行，main函数中的循环无需修改为size-1，直接使用i<size即可输出正确结果。

内容的提问来源于stack exchange，提问作者Debbie