c - 为什么这里会出现段错误？

Question

GDB 为我提供以下信息:

程序收到信号EXC_BAD_ACCESS，无法访问内存。 原因:KERN_INVALID_ADDRESS，地址:0x0000000000000000 minHeapify()中的0x0000000100000a3f

作为引用，图表是一个指针数组。

//all info for a vertex
typedef struct Vertex{
    float key;
    struct Vertex *prev;
    float loc[4];
} Vertex;

//using the pointer
typedef Vertex *VertexPointer;

VertexPointer *
createGraph(int numpoints, int dimension){
    //seed the psuedo-random number generator
    srand(time(NULL));

    //declare an array for the vertices
    VertexPointer *graph = malloc(numpoints * sizeof(*graph));

    //create the vertices in the array
    int x;
    int z;
    for(x = 0; x < numpoints; x++){
        //create the vertex
        VertexPointer v;
        v = (VertexPointer)malloc(sizeof(Vertex));
        (*v).key = 100;
        //(*v).prev = 0;
        //multiple dimensions
        for(z=0; z < dimension; z++){
            (*v).loc[z] = rand_float();
        }
        //put the pointer in the array
        graph[x] = v;
    }
    return graph;
} 


void
extractMin(VertexPointer *graph, int size){
    printf("We've stepped into extractMin");
    (*graph[0]).key = 100;
    minHeapify(graph, size, 1);
}




void
minHeapify(VertexPointer *graph, int size, int i) { 
    printf("We've stepped into minHeapify");
    //get the indexes of the left and right children.  readjust indices to start at 0.
    int l = 2i -1;
    int r = 2i;
    i = i - 1;

    //following the algorithm on p. 154 of CLRS  
    int smallest;
    if((l < size) && ((*graph[l]).key < (*graph[i]).key) ){
        smallest = l;
    }
    else{
        smallest = i;
    }
    if( (r < size) && ((*graph[r]).key < (*graph[smallest]).key) ){
        smallest = r;
    }
    if(smallest != i) {
        float exchange = (*graph[i]).key;
        (*graph[i]).key = (*graph[smallest]).key;
        (*graph[smallest]).key = exchange;
        minHeapify(graph, size, smallest);
    }
}

Answer 1

崩溃的可能原因在于您的索引调整:第一次，您将 i 从 1 调整为 0。然而，在随后的调用中，您无法再次向上调整，因此例如如果 i 第一次是最小元素，则第二次调用的结果是 i = -1。该调整代码使得很难推断算法的正确性。

另一个问题是您将 2*i 错误地输入为 2i。

第三个问题是，交换 key 不足以让算法提供正确的结果，您必须交换整个顶点(或者实际上是它们的指针)。