0

「abracadabra」などの単語をハフマンツリーにするコードを書いています。私はハフマンツリーの原理を理解していますが、今私が引っ掛かっているのは、最初にアブラカダブラを実装する方法です。

私の先生が私たちに行くように言ったアプローチは、2つの別々のキュー/配列を持つことです。1つ目は各文字の金額を格納し、もう1つは金額の順に（最大から最小）文字を格納し、文字の値が同じ場合はアルファベット順に並べ替えられます。

したがって、結果は次のようになります。5,2,2,1,1およびa、b、r、c、d彼は私たちにキューの使用を望んでいると確信していますが、この単純な部分にアプローチする方法がわかりません。コード..

どんな助けでも最もありがたいです。

4

1 に答える 1

0

なぜあなたがそれをまったくその形で書くように求められているのか私には考えられませんが、私の頭のてっぺんから、私はこれをします：

カウントと文字の2つのキューを初期化します。

入力の各文字について：
 レターキューでレターを検索します。
 見つかった場合
   countをcount-queue+1からの対応する値に設定します
   両方のキューから削除します
 そうしないと
   カウントを1に設定
 文字を追加し、正しい場所で両方のキューに数えます

完了すると、ツリーを構築するための正しい順序のキューができます。

私には待ち行列の乱用のように感じますが、それがあなたに求められたのであれば...

編集：キューなどを使わずに、おそらく実際にそれを書く方法は次のとおりです。

unsigned char input[]="abracadabra";
int counts[256];
memset(counts, 0, 256 * sizeof(int));

unsigned char i;
unsigned char *pt = input;
int max = 0;
while(i = *pt++)
{
    counts[i]++;
    if(counts[i] > max) max = counts[i];
}

while(max)
{
    int nmax = 0;
    for(int c = 0 ; c < 256 ; c++)
    {
        if(counts[c] < max && counts[c] > nmax) nmax = counts[c];
        if(counts[c] == max)
        {
            printf("%c: %d\n", c, max);
        }
    }
    max = nmax;
}
于 2012-12-03T22:46:44.313 に答える