c - 尝试 Cormen 的堆排序，但出现段错误

Question

我正在学习 Cormen 的堆排序。 当我尝试在数组上运行堆排序时，出现问题并且程序崩溃(段错误)。我尝试在堆排序函数中放入一些 printf 并打印 h->size 和 h->count 值，但它们似乎以某种方式从 10 更改为 3(!!!)，而没有我触摸它们(尝试在 heap_sort 循环之前和之后打印它们).. 我真的不明白有什么问题。请帮我。 在windows7上使用Eclipse。

ma​​in.c:

#include <stdio.h>
#include "heap.h"

void print_array2(int *a, int n)
{
    int *end = a + n;

    while (a < end)
        printf("%d ", *a++);

    printf("\n");
}

int main(void)
{
    int a[] =
    { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };

    print_array2(a, 10);

    heapsort(a, 10);

    print_array2(a, 10);

    return 0;
}

堆.c:

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

void heapify(heap *h, int i)
{
    int largest, left = LEFT(i), right = RIGHT(i);

    if (left < h->count && (*(h->a + left) > *(h->a + i)))
        largest = left;
    else
        largest = i;
    if (right < h->count && (*(h->a + right) > *(h->a + largest)))
        largest = right;

    if (largest != i)
    {
        swap(h->a + i, h->a + largest);
        heapify(h, largest);
    }
}

heap *build_heap(int *a, int size)
{
    heap h = (heap
            )
            { .size = size, .count = size, .a = a };

    heap *ph = &h;
    int i = size / 2;

    while (i >= 0)
        heapify(ph, i--);

    return ph;
}

void heapsort(int *a, int size)
{
    heap *h = build_heap(a, size);
    int i;

    for (i = h->size - 1; i >= 1; --i)
    {
        swap(h->a, h->a + i);
        h->count--;
        heapify(h, 0);
    }
}

void print_heap(heap *h)
{
    int *end = h->a + h->count, *arr = h->a;

    while (arr < end)
        printf("%d ", *arr++);

    printf("\n");
}

void print_array(heap *h)
{
    int *end = h->a + h->size, *arr = h->a;

    while (arr < end)
        printf("%d ", *arr++);

    printf("\n");
}

static void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

heap.h:

#ifndef HEAP_H_
#define HEAP_H_

typedef struct
{
    int size;   //array size
    int count;  //heap size
    int *a;     //int array
} heap;

#define PARENT(x) ((x + 1) / 2)
#define LEFT(x) (2 * (x) + 1)
#define RIGHT(x) (2 * ( (x) + 1) )

void heapify(heap* h, int i);
heap *build_heap(int *a, int size);
void heapsort(int *a, int size);
void print_heap(heap *h);
void print_array(heap *h);
static void swap(int *a, int *b);

#endif /* HEAP_H_ */

Answer 1

@mafso 是正确的。我更改了 build_heap 以返回堆的副本而不是指针，并且它有效。也许不是最好的方法，但它确实有效。这是代码:

heap.h

#ifndef HEAP_H_
#define HEAP_H_

typedef struct
{
    int size;   //array size
    int count;  //heap size
    int *a;     //int array
} heap;

#define PARENT(x) ((x + 1) / 2)
#define LEFT(x) (2 * (x) + 1)
#define RIGHT(x) (2 * ( (x) + 1) )

void heapify(heap* h, int i);
heap build_heap(int *a, int size);
void heapsort(int *a, int size);
void print_heap(heap *h);
void print_array(heap *h);
static void swap(int *a, int *b);

#endif /* HEAP_H_ */

heap.c

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

void heapify(heap *h, int i)
{
    int largest, left = LEFT(i), right = RIGHT(i);

    if (left < h->count && (*(h->a + left) > *(h->a + i)))
        largest = left;
    else
        largest = i;
    if (right < h->count && (*(h->a + right) > *(h->a + largest)))
        largest = right;

    if (largest != i)
    {
        swap(h->a + i, h->a + largest);
        heapify(h, largest);
    }
}

heap build_heap(int *a, int size)
{
    heap h;// = (heap) { .size = size, .count = size, .a = a };
    h.size = size;
    h.count = size;
    h.a = a;

    heap *ph = &h;
    int i = size / 2;

    while (i >= 0)
        heapify(ph, i--);

    return *ph;
}

void heapsort(int *a, int size)
{
    heap h = build_heap(a, size);
    int i;

    for (i = h.size - 1; i >= 1; --i)
    {
        swap(h.a, h.a + i);
        h.count--;
        heapify(&h, 0);
    }
}

void print_heap(heap *h)
{
    int *end = h->a + h->count, *arr = h->a;

    while (arr < end)
        printf("%d ", *arr++);

    printf("\n");
}

void print_array(heap *h)
{
    int *end = h->a + h->size, *arr = h->a;

    while (arr < end)
        printf("%d ", *arr++);

    printf("\n");
}

static void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

这是我的输出:

4 1 3 2 16 9 10 14 8 7 
1 2 3 4 7 8 9 10 14 16