§1  FREQ ABB  INTRODUCAO 1

September 30, 1998 at 09:34

1. Introducao. Este programa ilustra um uso de árvores binárias de busca. Como no caso do programa , o usuário fornece como entrada uma lista de palavras, uma palavra por linha, e a saída devolvida por é uma lista das palavras que ocorrem na entrada, sem repetição, uma por linha, com cada uma delas seguida do número de vezes que ela ocorre na entrada.

Por simplicidade, assumimos que a entrada vem no stdin e que a saída é devolvida no stdout . Mensagens de erro são enviadas para stderr e se encontramos algum erro terminamos a execução e devolvemos um código de erro negativo.

Executaremos a nossa tarefa da seguinte forma. Manteremos uma árvore binária de busca contendo o conjunto corrente de palavras. Isto é, em um dado instante, já lemos um certo número de palavras, e elas estão armazenadas em nossa árvore, com as respectivas freqüências até o momento registradas. Ao lermos uma nova palavra, nós a procuramos em nossa árvore. Se a encontramos, incrementamos o contador dela, e caso contrário nós a inserimos em nossa árvore.

Esta é uma versão “minimal” deste exemplo, equivalente ao programa . Vale a pena comparar e

conferir os programas em si e também o desempenho de  e  .

2. A organização de é típica de programas em C. #include #include

⟨ Typedefs 3 ⟩

⟨ Funções 14 ⟩

int main( )

{ ⟨ Variáveis locais a main 4 ⟩; ⟨ Inicialize a árvore binária de busca 6 ⟩; ⟨ Leia a entrada palavra por palavra e as processe uma por vez 7 ⟩; ⟨ Imprima a lista de palavras e seu número de ocorrências 12 ⟩; ⟨ Imprima o número de palavras lidas e o número de comparações feitas 17 ⟩; return 0;

}

3. Usaremos as estruturas no struct como os nós de nossa árvore binária de busca. Por simplicidade, definimos o tipo No através de um typedef . ⟨ Typedefs 3 ⟩ ≡

typedef struct no struct { char ∗palavra; /∗ a palavra ∗/ int n ocorrencias ; /∗ número de ocorrências da palavra ∗/ struct no struct ∗f esq , ∗f dir ; /∗ para os filhos esquerdo e direito ∗/

} No; /∗ células das listas ligadas ∗/

This code is used in section 2.

4. Assumiremos que as palavras da entrada têm no máximo caracteres.

#define  50

⟨ Variáveis locais a main 4 ⟩ ≡ char s[ ]; /∗ a palavra corrente ∗/ long n pals = 0; /∗ número de palavras lidas ∗/ long n pals dist = 0; /∗ número de palavras lidas distintas ∗/

See also sections 5, 13, and 16. This code is used in section 2.

2  ARVORES BINARIAS DE BUSCA  FREQ ABB §5

5. Arvores Binarias de Busca. A única rotina de manipulação de árvores de que precisamos é a de busca e inserção, visto em sala. ⟨ Variáveis locais a main 4 ⟩ +≡

No ∗t; /∗ o ponteiro para a raiz da árvore ∗/

6. ⟨ Inicialize a árvore binária de busca 6 ⟩ ≡ t = Λ;

This code is used in section 2.

7. ⟨ Leia a entrada palavra por palavra e as processe uma por vez 7 ⟩ ≡

while (gets (s)) { n pals^{++}; ⟨ Procure s na árvore t; insira um novo nó caso não a encontre 8 ⟩;

}

This code is used in section 2.

8. ⟨ Procure s na árvore t; insira um novo nó caso não a encontre 8 ⟩ ≡

if (¬t) /∗ a árvore está vazia ∗/

⟨ Construa uma árvore com um único nó para s 9 ⟩ else /∗ a árvore não está vazia ∗/

⟨ Busque s em t 10 ⟩;

This code is used in section 7.

9. Começamos com o mais fácil. ⟨ Construa uma árvore com um único nó para s 9 ⟩ ≡

{ char ∗s aux ; t = (No ∗) malloc(sizeof (No)); if (¬t) {

fprintf (stderr , ␣ ␣ ␣ ␣ ␣ ␣ ); return −1;

} s aux = (char ∗) malloc(strlen(s) + 1); /∗ +1 para o ∗/ if (¬s aux ) {

fprintf (stderr , ␣ ␣ ␣ ␣ ); return −2;

} strcpy (s aux , s); /∗ fazemos uma cópia de s em s aux ∗/ t palavra = s aux ; t n ocorrencias = 1; t f esq = t f dir = Λ; n pals = n pals dist = 1;

}

This code is used in section 8.

§10  FREQ ABB  ARVORES BINARIAS DE BUSCA 3

10. Agora sabemos que estamos lidando com uma árvore não vazia. Procuramos s da segunte forma: primeiro comparamos s com a palavra na raiz da árvore (i.e., t palavra). Se s < t palavra, continuamos a busca na subárvore esquerda de t, cuja raiz é t f esq . Analogamente, se s > t palavra, continuamos a busca na subárvore direita de t, cuja raiz é t f dir . Se s = t palavra, encontramos s! Quando descemos nas subárvores esquerda ou direita, continuamos o mesmo processo. Para este procedimento, usamos um ponteiro para nós p que percorre a árvore (vai “descendo” na árvore). Temos ainda um ponteiro auxiliar p anterior , que aponta para o nó visitado logo antes de visitar p. ⟨ Busque s em t 10 ⟩ ≡

{ int achou = 0; int comp res ; /∗ resultado da comparação entre s e p palavra ∗/ No ∗p = t; No ∗p anterior ; while (¬achou ∧ p)

if (o, (comp res = strcmp(s, p palavra)) < 0) { p anterior = p; p = p f esq ;

}

else if (comp res > 0) { p anterior = p; p = p f dir ;

}

else achou = 1; if (achou) p n ocorrencias^{++}; else ⟨ Insira um novo nó para a palavra s 11 ⟩;

}

This code is used in section 8.

11. ⟨ Insira um novo nó para a palavra s 11 ⟩ ≡

{ No ∗no novo; char ∗s aux ; no novo = (No ∗) malloc(sizeof (No)); if (¬no novo) {

fprintf (stderr , ␣ ␣ ␣ ␣ ); return −1;

} s aux = (char ∗) malloc(strlen(s) + 1); /∗ +1 para o ∗/ if (¬s aux ) {

fprintf (stderr , ␣ ␣ ␣ ␣ ); return −2;

} strcpy (s aux , s); no novo palavra = s aux ; no novo n ocorrencias = 1; no novo f esq = no novo f dir = Λ; n pals dist^{++}; if (comp res < 0) p anterior f esq = no novo; else p anterior f dir = no novo;

}

This code is used in section 10.

12. Percorremos a árvore em in-ordem para imprimir as palavras que encontramos na entrada, sem repetição e em ordem alfabética. A função in ordem( ) abaixo é trivialmente implementada recursivamente.

Na realidade, fazemos mais que simplesmente imprimir as palavras e suas respectivas ocorrências. Vamos determinar a profundidade da árvore e também a profundidade média dos nós da árvore. Recordemos que a profundidade de um nó na árvore é o comprimento do caminho da raiz até ele. A profundidade da árvore é o máximo das profundidades dos nós que ocorrem na árvore. A função in ordem( ) também determina o número de nós na árvore; naturalmente, isto deve bater com o número de palavras distintas na entrada. ⟨ Imprima a lista de palavras e seu número de ocorrências 12 ⟩ ≡

in ordem(t, &n nos , &profdd , &profdd media); if (n pals dist ≠ n nos ) {

fprintf (stderr , ␣ ␣ ␣ ␣ ␣ ␣␣ ␣ ␣ ); return −3;

}

This code is used in section 2.

13. ⟨ Variáveis locais a main 4 ⟩ +≡ long profdd ; /∗ a profundidade da árvore ∗/ double profdd media; /∗ a profundidade média dos nós da árvore ∗/ long n nos ; /∗ o número de nós na árvore ∗/

14. ⟨ Funções 14 ⟩ ≡ void in ordem(No ∗p, long ∗n nos , long ∗profdd , double ∗profdd media) { long profdd esq , profdd dir ;

double profdd media esq , profdd media dir ;

long n nos esq , n nos dir ;

if (p) { in ordem(p f esq , &n nos esq , &profdd esq , &profdd media esq ); ⟨ Visite p 15 ⟩; in ordem(p f dir , &n nos dir , &profdd dir , &profdd media dir ); ∗n nos = n nos esq + n nos dir + 1; if (∗n nos ≡ 1) ∗profdd = ∗profdd media = 0; else {

∗profdd media = 1 + (profdd media esq ∗ n nos esq + profdd media dir ∗ n nos dir − 1)/(∗n nos ); ∗profdd = 1 + ((profdd esq > profdd dir ) ? profdd esq : profdd dir );

} } else { /∗ a árvore está vazia ∗/

∗n nos = 0;

∗profdd = ∗profdd media = −1; /∗ apenas por convenção ∗/ }

}

This code is used in section 2.

15. ⟨ Visite p 15 ⟩ ≡ printf ( ␣ , p palavra, p n ocorrencias );

This code is used in section 14.

16. Faremos uma contagem do número de comparações que são feitas entre palavras. Usaremos um contador n comp para isto.

#define o n comp^{++}

⟨ Variáveis locais a main 4 ⟩ +≡ long n comp = 0;

17. ⟨ Imprima o número de palavras lidas e o número de comparações feitas 17 ⟩ ≡

printf (  ␣  ␣         ␣     ␣ ␣  , n pals );
printf (  ␣  ␣           ␣      ␣ ␣  , n comp);
printf (  ␣     ␣  ␣           ␣      ␣   ␣        ␣    ␣ ␣  , (double)

n comp/n pals );

printf (  ␣  ␣         ␣         ␣ ␣  , n pals dist );
printf (  ␣  ␣       ␣ ␣  , profdd );
printf (  ␣     ␣    ␣   ␣  ␣      ␣ ␣  , profdd media);

This code is used in section 2.

6  INDICE  FREQ ABB §18

18. Indice. Aqui está uma lista de identificadores que são usados, com indicação de onde eles aparecem. As entradas sublinhadas indicam onde eles aparecem.

achou: \underline{10}. : \underline{4}. comp res : \underline{10}, 11. f dir : \underline{3}, 9, 10, 11, 14. f esq : \underline{3}, 9, 10, 11, 14. fprintf : 9, 11, 12. gets : 7. in ordem: 12, \underline{14}. main: \underline{2}. malloc: 9, 11. n comp: \underline{16}, 17. n nos : 12, \underline{13}, \underline{14}. n nos dir : \underline{14}. n nos esq : \underline{14}. n ocorrencias : \underline{3}, 9, 10, 11, 15. n pals : \underline{4}, 7, 9, 17. n pals dist : \underline{4}, 9, 11, 12, 17. No: \underline{3}, 5, 9, 10, 11, 14. no novo: \underline{11}. no struct: \underline{3}. o: \underline{16}. p: \underline{10}, \underline{14}. p anterior : \underline{10}, 11. palavra: \underline{3}, 9, 10, 11, 15. printf : 15, 17. profdd : 12, \underline{13}, \underline{14}, 17. profdd dir : \underline{14}. profdd esq : \underline{14}. profdd media: 12, \underline{13}, \underline{14}, 17. profdd media dir : \underline{14}. profdd media esq : \underline{14}. s: \underline{4}. s aux : \underline{9}, \underline{11}. stderr : 1, 9, 11, 12. stdin: 1. stdout : 1. strcmp: 10. strcpy : 9, 11. strlen: 9, 11. t: \underline{5}.

FREQ ABB NAMES OF THE SECTIONS 7

⟨ Busque s em t 10 ⟩ Used in section 8.

⟨ Construa uma árvore com um único nó para s 9 ⟩ Used in section 8.

⟨ Funções 14 ⟩ Used in section 2.

⟨ Imprima a lista de palavras e seu número de ocorrências 12 ⟩ Used in section 2. ⟨ Imprima o número de palavras lidas e o número de comparações feitas 17 ⟩ Used in section 2. ⟨ Inicialize a árvore binária de busca 6 ⟩ Used in section 2. ⟨ Insira um novo nó para a palavra s 11 ⟩ Used in section 10. ⟨ Leia a entrada palavra por palavra e as processe uma por vez 7 ⟩ Used in section 2. ⟨ Procure s na árvore t; insira um novo nó caso não a encontre 8 ⟩ Used in section 7.

⟨ Typedefs 3 ⟩ Used in section 2. ⟨ Variáveis locais a main 4, 5, 13, 16 ⟩ Used in section 2. ⟨ Visite p 15 ⟩ Used in section 14.