函数调用中的分段错误C

Question

我正在解决使用MaxHeap在数组中寻找第k个最小元素的问题。我的C代码如下：

#include <stdio.h> 
#include <stdlib.h> 
/** 
* @input A : Read only (DON'T MODIFY) Integer array 
* @input n1 : Integer array's (A) length 
* @input k : Integer 
* 
* @Output Integer 
*/ 
struct heap { 
    int *A; 
    int size; 
    int heapsize; 
}; 

void init_heap(struct heap*, int); 
void max_heapify(struct heap*, int); 
void add_heap(struct heap*, int); 
int extract_max(struct heap*); 
int get_max(struct heap*); 

int kthsmallest(const int* A, int n1, int k) { 
    struct heap* H = malloc(sizeof *H); 
    init_heap(H, k); 
    int i = 0; 
    for(i = 0; i < k; i++) { 
     add_heap(H, A[i]); 
    } 
    for(i = k; i < n1; i++) { 
     if (A[i] < get_max(H)) { 
      extract_max(H); 
      add_heap(H, A[i]); 
     } 
    } 
    return get_max(H); 
} 

//Initializes the heap array, heapsize and size 
void init_heap(struct heap* H, int n) { 
    H->A = malloc((n+1) * sizeof(int)); 
    H->heapsize = 0; 
    H->size = n; 
} 

//Makes the tree rooted at index i into a heap if the sub-trees at 2i and 2i+1 are heaps 
void max_heapify(struct heap* H, int index) { 
    int *arr = H->A; 
    int left = 2*index; 
    int right = 2*index+1; 
    int max = index; 
    if (left <= H->heapsize && arr[left] > arr[max]) max = left; 
    if (right <= H->heapsize && arr[right] > arr[max]) max = right; 
    if (max != index) { 
     int temp = arr[index]; 
     arr[index] = arr[max]; 
     arr[max] = temp; 
    } 
    max_heapify(H, max); 
} 

//Adds and element into the heap 
void add_heap(struct heap* H, int data) { 
    if(H->heapsize == H->size) { 
     return; 
    } 
    (H->heapsize)++; 
    int *arr = H->A; 
    arr[H->heapsize] = data; 
    int i = H->heapsize; 
    while(i > 1 && arr[i/2] < arr[i]) { 
     int temp = arr[i]; 
     arr[i] = arr[i/2]; 
     arr[i/2] = temp; 
     i = i/2; 
    } 
    //printf("Added %d\n", data); 
} 

int extract_max(struct heap* H) { 
    if (H->heapsize == 0) { 
     return -1; 
    } 
    int *arr = H->A; 
    int ret_val = arr[1]; 
    arr[1] = arr[H->heapsize]; 
    (H->heapsize)--; 
    max_heapify(H, 1); 
    //printf("Removed %d\n", ret_val); 
    return ret_val; 
} 

int get_max(struct heap* H) { 
    if (H->heapsize == 0) { 
     return -1; 
    } 
    return *((H->A)+1); 
} 

int main() { 
    int A[] = {8, 16, 80, 55, 32, 8, 38, 40, 65, 18, 15, 45, 50, 38, 54, 52, 23, 74, 81, 42, 28, 16, 66, 35, 91, 36, 44, 9, 85, 58, 59, 49, 75, 20, 87, 60, 17, 11, 39, 62, 20, 17, 46, 26, 81, 92}; 
    printf("Answer = %d\n", kthsmallest(A, 46, 9)); 
    return 0; 
} 

当我运行该程序时，出现分段错误。我试图调试，但我找不到原因。

这是我的gdb的输出：

Program received signal SIGSEGV, Segmentation fault. 
0x0000000100000cd8 in max_heapify (
    H=<error reading variable: Cannot access memory at address 0x7fff5f3ffff8>, index=<error reading variable: Cannot access memory at address 0x7fff5f3ffff4>) 
    at kthsmallest.c:49 
49 void max_heapify(heap* H, int index) { 

这是我的valgrind输出

==21378== Memcheck, a memory error detector 
==21378== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al. 
==21378== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info 
==21378== Command: ./a.out 
==21378== 
==21378== 
==21378== Process terminating with default action of signal 11 (SIGSEGV) 
==21378== Access not within mapped region at address 0x104002FF8 
==21378== at 0x100000DCE: max_heapify (kthsmallest.c:57) 
==21378== If you believe this happened as a result of a stack 
==21378== overflow in your program's main thread (unlikely but 
==21378== possible), you can try to increase the size of the 
==21378== main thread stack using the --main-stacksize= flag. 
==21378== The main thread stack size used in this run was 8388608. 

当我extract_max函数调用max_heapify功能分割故障发生。

Answer 1

这是一个堆栈溢出错误，因为max_heapify不断地递归调用它，并且它从不停止。 max_heapify应只在条件为(max != index)为真时递归调用。如果条件和代码现在按预期工作，我将递归调用移入上面的条件中。

这是最后的正确功能：

void max_heapify(struct heap* H, int index) { 
    int *arr = H->A; 
    int left = 2*index; 
    int right = 2*index+1; 
    int max = index; 
    if (left <= H->heapsize && arr[left] > arr[max]) max = left; 
    if (right <= H->heapsize && arr[right] > arr[max]) max = right; 
    if (max != index) { 
     int temp = arr[index]; 
     arr[index] = arr[max]; 
     arr[max] = temp; 
     max_heapify(H, max); 
    } 
}