허프 먼 코드, 트리의 초기 입력에 문제가 발생했습니다.

Question

"abracadabra"와 같은 단어를 사용하여이를 허프만 트리로 만드는 코드를 작성하고 있습니다. 나는 호프만 나무의 원리를 이해하지만, 지금 당장은 내가 아브라카 다브라를 어떻게 구현할 것인가에 대한 것입니다.

선생님이 우리에게 간다고 말한 접근 방식은 2 개의 개별 대기열/배열을 갖는 것입니다. 첫 번째 문자는 각 문자의 양을 저장하고 다른 문자는 양 (가장 높은 값부터 가장 낮은 값)의 순서로 문자를 저장하고 문자가 같은 값을 가질 때 알파벳 순으로 정렬됩니다.

그래서 결과는 다음과 같습니다 : 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; 
} 

없이, 아마 실제로 그것을 써서 방법