1

私はこれを何時間も見ていて、これを理解することはできません。heapify関数の比較がより大きい値に変更された場合、出力は本来あるべき昇順になります。リストを降順で並べ替えたいのですが、次のコードを使用しても正しい出力が得られません。

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

typedef struct stuff {
    char *str;
}stuff_t;

void heapify(stuff_t *stuff_array, int i, int n) 
{
    stuff_t temp;
    int left, right, max;

    left = 2*i;
    right = left + 1;
    max = i;
    if (left < n)
        if (strtod(stuff_array[left].str, NULL) < strtod(stuff_array[i].str, NULL))
            max = left;
    if (right < n)
        if (strtod(stuff_array[right].str, NULL) < strtod(stuff_array[max].str, NULL))
            max = right;

    if (max != i)
    {
        temp = stuff_array[i];
        stuff_array[i] = stuff_array[max];
        stuff_array[max] = temp;
        heapify(stuff_array, max, n);
    }
}

void heapsort(stuff_t *stuff_array)
{
    short i,N;
    stuff_t temp; 

    N = 0;
    while (stuff_array[N].str)
        N++;

    for (i = (N/2)-1; i >= 0; i--)
        heapify(stuff_array, i, N);

    for (i = N-1; i >= 1; i--) {
        temp = stuff_array[0];
        stuff_array[0] = stuff_array[i];
        stuff_array[i] = temp;
        heapify(stuff_array, 0, i);
    }
}

int main (int argc, char* argv[])
{
    int i;
    stuff_t *s_list = calloc(4, sizeof(stuff_t));
    stuff_t *s_list1 = calloc(8, sizeof(stuff_t));
    s_list[0].str = "9.3";
    s_list[1].str = "9.3";
    s_list[2].str = "7.8";

    printf("before: ");
    for (i = 0; i < 3; i++)
        printf("%s, ", s_list[i]);
    printf("\n");

    heapsort(s_list);

    printf("after: ");
    for (i = 0; i < 3; i++)
        printf("%s, ", s_list[i]);
    printf("\n");

    s_list1[0].str = "7.5";
    s_list1[1].str = "10.0";
    s_list1[2].str = "10.0";
    s_list1[3].str = "8.3";
    s_list1[4].str = "6.5";
    s_list1[5].str = "5.0";
    s_list1[6].str = "4.6";

    printf("before: ");
    for (i = 0; i < 3; i++)
        printf("%s, ", s_list1[i]);
    printf("\n");

    heapsort(s_list1);

    printf("after: ");
    for (i = 0; i < 7; i++)
        printf("%s, ", s_list1[i]);
    printf("\n");
    return 0;
}

プログラム出力：

// using less than comparison
before: 9.3, 9.3, 7.8,
after: 9.3, 7.8, 9.3,
before: 7.5, 10.0, 10.0,
after: 10.0, 10.0, 8.3, 7.5, 6.5, 4.6, 5.0,

// using greator than comparison
before: 9.3, 9.3, 7.8,
after: 7.8, 9.3, 9.3,
before: 7.5, 10.0, 10.0,
after: 4.6, 5.0, 6.5, 7.5, 8.3, 10.0, 10.0,
4

1 に答える 1

4

0から数え始めると、i*2とi*2 + 1を子のアドレスとして使用できません。問題は、2 * 0 = 0です（左の子は親と同じになります）。

于 2010-07-01T17:24:19.193 に答える