Программа Heapsort не возвращает результат - PullRequest
Новая
       4

Программа Heapsort не возвращает результат

0 голосов
/ 12 февраля 2020

Я реализую программу Heapsort на языке C, который сортируется с помощью двоичного дерева. Когда я запускаю эту программу, все в порядке, пока она не встретит функцию heapsort в программе. Я также пытаюсь отладить это, но это все равно не так при выполнении функции heapsort.

Что касается некоторых алгоритмов на Inte rnet, я нахожу их похожими на мой исходный код, но они работают правильно, поэтому мне очень трудно обнаружить ошибки в моем исходном коде 

#include <stdio.h>
#define MAX 2100
void downheap(int a[], int n, int k)
{
    int i=0;
    int temp = a[0];
    while (k <= n/2)
    {
        i = k + k;
        if(i<n && a[i] <= a[i+1]) i++;
        if(temp < a[i]) break;
        a[k] = a[i]; k = i;
    }
    a[k] = temp;
}
void heapsort(int a[], int n)
{
    int i, j;
    for(i=0; i<=n; i++) downheap(a, n, i);
    while(n>=0)
    {
        j = a[0]; a[0] = a[n]; a[n] = j;
        downheap(a, --n, 0);
    }
}

int main()
{
    int n, a[MAX], i;
    printf("Enter your number of elements: ");
    scanf("%d", &n);
    for(i=0; i<n; i++) printf("%d: ", i), scanf("%d", &a[i]);
    heapsort(a, n-1);
    for(i=0; i<n; i++) printf("%d ", a[i]);
    return 0;
}

1 Ответ

1 голос
/ 12 февраля 2020

В вашем коде есть несколько проблем, которые я перечислю ниже:

Вы должны придерживаться общего соглашения, что n - это количество элементов. В вашем коде это количество элементов минус один, что неудобно. В этом случае вы должны вызвать heapsort(a, n).

. В функции heapsort значение for(i=0; i<=n; i++) downheap(a, n, i) должно быть for(i=n/2-1; i>=0; i--) downheap(a, n, i).

Далее, поскольку n - это число элементов в a, l oop должно быть while(--n > 0). Итерация, в которой n = 0, не имеет смысла, так как она затем поменяет местами a [0] с a [0]. Наконец вы звоните downheap(a, n, 0).

Функция downheap, где у вас самая большая проблема. Функция должна сравнить элемент по индексу i с двумя его потомками и сохранить максимум дерева по индексу i. Если произошел обмен с ребенком, возобновите замену этого ребенка. Ваша функция полностью неверна. Вот правильная реализация. 

void downheap(int *a, int n, int k){
    int l = 2*k+1, r = 2*k+2, max = k;
    if (l < n && a[l] > a[max])
        max = l;
    if (r < n &d a[r] > a[max])
        max = r;
    if (max != k) {
        int j = a[k]; a[k] = a[max]; a[max] = j;
        downheap(a, n, max);
    }
}

Как видите, этот код сильно отличается от вашего, что совершенно неверно.

Для вашего удобства приведен код функции heapsort. Этот код был не так плох, но все же неверен. 

void heapsort(int *a, int n){
    int i, j;
    for(i=n/2-1; i>=0; i--)
        downheap(a, n, i);
    while(--n > 0){
        j = a[0]; a[0] = a[n]; a[n] = j;
        downheap(a, n, 0);
    }
}

РЕДАКТИРОВАТЬ

Не рекурсивная реализация downheap: 

void downheap(int *a, int n, int k){
    while (1) {
        int l = 2*k+1, r = 2*k+2, max = k;
        if (l < n && a[l] > a[max])
            max = l;
        if (r < n &d a[r] > a[max])
            max = r;
        if (max == k)
            break;
        int j = a[k]; a[k] = a[max]; a[max] = j;
        k = max;
    }
}
...