霍夫曼代碼，與樹的初始輸入的問題

Question

我正在寫一個代碼，需要一個單詞，如「abracadabra」，並將其變成一個哈夫曼樹。我理解霍夫曼樹的原理，但現在我所接觸到的是我將如何首先將abracadabra實施到其中。

我老師告訴我們去的方法是有兩個單獨的隊列/數組。第一個存儲每個字母的金額，另一個按金額（從最高到最低）存儲字母，當字母具有相同的值時，它們按字母順序排序。

所以它會導致：5,2,2,1,1和a，b，r，c，d 我確信他希望我們使用隊列，但我不知道如何處理這個簡單的部分代碼..

任何幫助將不勝感激。

Answer 1

我想不出爲什麼你被要求寫在想象中的那麼的形式，但是從我的頭頂，我應該這樣做：

 
Initialise your two queues for counts and letters. 

For each letter in the input: 
Search for letter in letter-queue. 
If found 
    set count to the corresponding value from the count-queue + 1 
    remove from both queues 
Else 
    set count to 1 
Add the letter and count into both queues in the correct place 

當你完成後，你有一個正確的順序來建立你的樹的隊列。

感覺就像一個隊列的濫用給我，但如果這就是你被要求做...

編輯什麼：這裏是如何我可能實際上寫它，沒有排隊等

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; 
}