0

CLRSに従ってCでヒープソートアルゴリズムを実装していました。ただし、ソートされた出力を取得できません。見て、私のコードの何が問題なのか教えてください。機能maxheapとbuildmaxheap働き。コードの何が問題なのかわかりません。

コードは、配列要素をヒープソートすることになっています。heapsort()関数にエラーがあると感じ、正常maxheapにbuildmaxheap動作します。

私が得ている最終的な出力は

1 1 1 1 2 1 2 2 1 1

しかし、期待される出力は

1 2 3 4 7 8 9 10 14 16

コード：

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

#define maxn 11
int n=10;

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

int left(int i)
{
    return 2*i+0;
}

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

void  max_heap(int x[],int i,int heapsize)
{
    int largest;
    int l=left(i);
    int r=right(i);

    if (l<=heapsize &&  x[l]>x[i]){
        largest=l;
    }
    else
    {
        largest=i;
    }
    if (r<=heapsize && x[r]>x[largest]){
        largest=r;
    }
    if (largest!=i)
    {
        int s=x[i];x[i]=x[largest];x[largest]=s;
        max_heap(x,largest,heapsize);
    }
}

void buildmaxheap(int x[],int heapsize)
{

    int i;
    for(i=5;i>=1;i--)
        max_heap(x,i,heapsize);

}

void heapsort(int x[])
{
    buildmaxheap(x,10);
    int i,t,heapsize=10;
    for(i=10;i>=2;i--)
    {
        int s=x[i];x[1]=x[i];x[i]=s;

        heapsize--;
        /*
         printf("%d",heapsize);
         */
        max_heap(x,i,heapsize);
    }
    for(i=1;i<=10;i++)
        printf("%d\t",x[i]);

}

int main()
{
    int x[maxn],i;
    x[1]=16;
    x[2]=4;
    x[3]=10;
    x[4]=14;
    x[5]=7;
    x[6]=9;
    x[7]=3;
    x[8]=2;
    x[9]=8;
    x[10]=1;
    heapsort(x);
    /*
     for(i=1;i<=10;i++)
     printf("%d\t",x[i]);
     */
}
4

2 に答える 2

0

この行：

int s=x[i];x[1]=x[i];x[i]=s;

スワップをしようとしているように見えますが、混乱しています。インデックスを見て、順序を考えてください。

それを修正した後、まだ別のバグがあります。私は本を​​持っていないので、何をするように言われたのか正確にはわかりませんが、要素を削除した後、ルートからヒープ プロパティを修正する必要があると思いますが、コードはそれを行いません。 .

于 2015-06-17T23:35:29.587 に答える
0

ヒープソートにはロジックがありません。任意のソート アルゴリズムは、2 つの値を比較し、より小さい場合は 1 つ、大きい場合は別のことを行い、同じ場合はそのままにしておく必要があります。現在、コンパレータをインデックス 1 で複数回自動的に交換します。

数値が失われてランダムな 1 と 2 になる理由がはっきりとわかりませんが、あまりにも壊れているように見えるので、再試行するまで時間がありません。

C では、配列インデックスは 0 から始まります。この小さな 10 ノードの難問では、それを避けないでください。それは大したことではありません。しかし、ゼロが最初であると自動的に考え始めなければ、大きな代償を払うことになります。

于 2015-06-17T23:06:25.273 に答える