Re: Será que eu sou muito burro, ou isso é difícil mesmo.

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Tiago M. Silveira writes:
 > Daniel Cukier wrote:
 > > Estou lendo o EP4 a um tempão, já li um monte de vezes, consegui entender o
 > > que é a árvore de huff. Porém, quando vou ler o código huff.c, a partir da
 > > parte dos "for":
 > > for (i=0; i<520;i++) coount[i]=0; ... etc ... até o final, eu não consigo
 > > entender. Nos outros programas que o Yoshi fez, ele usava o CWeb e ia
 > > explicando o que cada parte do programa fazia. Agora, no EP4, não tem nada
 > > que explique nada! Eu olho para a lista de discussão e fico pensando comigo
 > > mesmo: até agora, só vi uma meia dúzia de alunos participar da lista. Será
 > > que todo mundo entendeu o EP4, e eu que estou meio por fora?
 > 
 > Pior. Gente como eu ficou estudando pras provas, subs, etc. e só foi mexer no
 > EP4 quinta à tarde. Ninguém entendeu (salvo algumas exceções) exatamente todo o
 > HUFF.C. Mas eu posso te mostrar alguma coisa (e junto com isso, perguntar se eu
 > pensei certo):
 > 
 > --- CUT HERE --- : )
 >  for (i=0; i<520; i++) count[i]=0; // Inicializa o count[];
 >  for (k=0; k<520; k++) dad[k]=heap[k]=0; // Inicializa o dad[] e o heap[];
 >  for (j=0; j<n_chars; j++) count[texto[j]]++; // conta as ocorrencias;
 >  for (i=h_size=0; i<=256; i++)
 >   if (count[i]) heap[++h_size]=i; // mede o tamanho do heap.
 >  for (k=h_size/2; k>0; k--)
 >   pqdownheap(heap, h_size, count, k); // transforma o heap[] em heap;
 >  while (h_size>1) {
 >   t=heap[1];              // removemos o menor elemento...
 >   heap[1]=heap[h_size--]; // ...e colocamos o maior em seu lugar.
 >   pqdownheap(heap, h_size, count, 1); // restabelecemos o heap;
 > /* Aqui, a maior posicao do count[] recebe o numero de ocorrencias do maior
 >  * elemento (t) + o no. de ocorrencias do segundo maior (heap[1]): */

Agora sabemos quais das duas subarvores tem maior peso (=prioridade).
Devemos junta-las:

 >   count[256+h_size]=count[heap[1]]+count[t];
 > // Essa posicao e' o pai do t:
 >   dad[t]=256+h_size;

perfeito.

 > // o pai do heap[1] fica negativo:
 >   dad[heap[1]]=-256-h_size;

256+h_size 'e tambem o pai de heap[1].

Para que saibamos quem 'e filho direito e filho esquerdo, usamos o
sinal.  Isto aparece explicado no Sedgewick: "The sign of dad[t]
indicates whether the node is a left or right child of its parent." 

 > /* o heap[1], agora o maior elemento do heap[], rebece um valor aparentemente
 >  * aleatorio, e o heap e restabelecido: */
 >   heap[1]=256+h_size; pqdownheap(heap, h_size, count, 1);

Inserimos esta nova subarvore no heap.  Yoshi

 >  }
 > --- CUT HERE ---
 > 
 > Bom, os meus comentários estão aí, mas a partir da parte q usa a segunda metade
 > do count[] e do dad[] eu boiei legal...
 > 
 > > Porém, pelo que percebi (também não sei se está certo), preciso, antes de
 > > imprimir esses caracteres, imprimir no arquivo compactado qual código de
 > > zeros e uns pertence a cada caractere, para que na hora de descompactar,
 > > conseguir reconstruir o arquivo.
 > >
 > > Se isso que penso for verdade, então, não preciso entender o huff.c por
 > > inteiro para fazer o EP4, certo? basta apenas saber como gravar uma
 > > sequencia de zeros e uns, um vetor com 256 posições, que seria a tabela com
 > > os caracteres e seus respectivos códigos.
 > 
 > Tomara q c tenha razão, pq eu já desencanei de entender o huff inteiro. Quanto
 > ao problema das notas, pensa assim: C tem uma azul e duas vermelhas. Precisar de
 > nota é natural. se a média (7.0) é justa ou alta ou baixa para aprovar ou
 > reprovar (EM MAC) alguém do BCC, isso é um pouco do critério do professor.
 > Realmente, concordo com vc quanto à demora na devolução dos EPs, especialmente
 > se for verdade o boato q rola sobre o monitor só ter pego o ep3 pra corrigir
 > sexta-feira. Aconteceu comigo em 110, e provavelmente aconteceu em 122 tb.
 > 
 > te+!
 > 
 > --
 > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 > Tiago Minchillo da Silveira
 > Kiron Multimídia - http://www.kiron.com.br
 > Homepage pessoal em construção!!! Em breve divulgo o endreço.
 > Nick no IRC/ICQ: Duke Jeffrie - UIN: 9350490
 > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~