0

「アルゴリズムの紹介」で説明されているアルゴリズムを使用して最大ヒープを構築しようとしていますが、うまく動作しません。まず、関数間で配列を渡す際に興味深い問題が発生しています。私の理解では、配列はC++で参照によって渡されますが、配列を渡した後、引数とパラメーターのアドレスが一致しないことを確認します。パラメータである配列で sizeof() を使用しようとすると、正しい値が返されません。

第二に、アルゴリズムが機能していないようです。配列にいくつかの変更を加え、数値をヒープに近づけますが、まだ先があります。私はコードを何十回もチェックしましたが、テキストに記載されている疑似コードにスポットを当てているようです。私は何が欠けていますか？

#include <iostream>
#include <ctime>

#define N 10
#define DISPLAY

using namespace std;


// Display an array
void display(double p[]) {
#ifdef DISPLAY
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << endl;
#endif
}


inline int parent(int i)
{return i/2;}

inline int left(int i)
{return 2*i;}

inline int right(int i)
{return 2*i+1;}

void maxHeapify(double p[], int i)
{
    int largest;

   int l = left(i);
   int r = right(i);

   if (l <= N && (p[l] > p[i]))
        largest = l;

    else
        largest = i;

    if (r <= N && (p[r] > p[largest]))
        largest = r;

    if (largest != i)
    {
        double temp = p[i];

        p[i] = p[largest];

        p[largest] = temp;

        maxHeapify(p, largest);
    }
}   

void buildMaxHeap(double p[])
{
    for (int i=N/2; i>0; i--)
        maxHeapify(p, i);
}

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

1 に答える 1

0

私はあなたのコードを以下のように修正しました：

#include <iostream>
#include <ctime>

#define N 10
#define DISPLAY

using namespace std;


// Display an array
void display(double p[]) {
#ifdef DISPLAY
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << endl;
#endif
}


inline int parent(int i)
{return i/2;}

inline int left(int i)
{return 2*i;}

inline int right(int i)
{return 2*i+1;}

void maxHeapify(double p[], int i)
{
    int largest;

   int l = left(i)-1;
   int r = right(i)-1;
   i=i-1;

   if (l <= N && (p[l] > p[i]))
        largest = l;

    else
        largest = i;

    if (r <= N && (p[r] > p[largest]))
        largest = r;

    if (largest != i)
    {
        double temp = p[i];

        p[i] = p[largest];

        p[largest] = temp;

        maxHeapify(p, largest+1);
    }
}   

void buildMaxHeap(double p[])
{
    for (int i=N/2; i>0; i--)
        maxHeapify(p, i);
}

int main() {
 double a[] = {4,1,3,2,16,9,10,14,8,7};
 buildMaxHeap(a);
 display(a);
}
于 2013-02-23T22:12:44.210 に答える