§1  FREQ  INTRODUCAO 1

September 30, 1998 at 07:16

1. Introducao. Este programa ilustra um uso de tabelas de espalhamentos. 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 tabela de espalhamento para o conjunto de palavras da entrada. Em um dado instante, já lemos um certo número de palavras, e elas estão armazenadas em uma tabela de espalhamento, com as respectivas freqüências até o momento registradas. Ao lermos uma nova palavra, nós a procuramos em nossa tabela. Se a encontramos, incrementamos o contador dela, e caso contrário nós a inserimos em nossa tabela.

Pretendo adicionar algumas coisas a este programa, para aumentar a flexibilidade de uso e eficiência. Espero que eu possa fazer isto em breve. Esta versão, entretanto, tem a vantagem de ser “minimal” e portanto possivelmente mais facil de entender

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

⟨ Typedefs 3 ⟩

⟨ Funções 6 ⟩

int main( )

{ ⟨ Variáveis locais a main 4 ⟩; ⟨ Inicialize a tabela de espalhamento 7 ⟩; ⟨ Leia a entrada palavra por palavra e as processe uma por vez 8 ⟩; ⟨ Imprima a lista de palavras e seu número de ocorrências 11 ⟩; ⟨ Imprima o número de palavras lidas e o número de comparações feitas 14 ⟩; return 0;

}

3. Usaremos resolução de colisões por encadeamento em nosso esquema de hashing. Os elementos das listas ligadas em nossa tabela de espalhamento vão ser as celulas , que são as estruturas definidas abaixo. ⟨ Typedefs 3 ⟩ ≡

typedef struct celula struct { char ∗palavra; /∗ a palavra ∗/ int n ocorrencias ; /∗ número de ocorrências da palavra ∗/ struct celula struct ∗prox ; /∗ para a lista ligada ∗/

} celula; /∗ 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 and 13. This code is used in section 2.

2  TABELAS DE ESPALHAMENTO  FREQ §5

5. Tabelas de espalhamento. Usaremos uma das funções de hashing vistas em sala, e usaremos resolução de colisões por encadeamento.

#define  1009

⟨ Variáveis locais a main 4 ⟩ +≡

celula ∗tab[  ];  /∗ a tabela de hashing ∗/

6. ⟨ Funções 6 ⟩ ≡ int hash div (char ∗s) { int h;

for (h = 0; ∗s ≠ ; s^{++}) h = (258 ∗ h + (unsigned char) ∗s) % ; return h;

}

This code is used in section 2.

7. ⟨ Inicialize a tabela de espalhamento 7 ⟩ ≡

{ int i;

for (i = 0; i < ; i^{++}) tab[i] = Λ; }

This code is used in section 2.

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

while (gets (s)) { int h valor ; n pals^{++}; h valor = hash div (s); ⟨ Procure s na lista tab[h valor ]; insira ou incremente contador 9 ⟩;

}

This code is used in section 2.

9. ⟨ Procure s na lista tab[h valor ]; insira ou incremente contador 9 ⟩ ≡

{ int achou = 0; celula ∗ptr = tab[h valor ]; while ((¬achou) ∧ ptr )

if (o, strcmp(s, ptr palavra) ≡ 0) achou = 1; else ptr = ptr prox ;

if (achou) ptr n ocorrencias^{++}; else ⟨ Insira nova célula na lista tab[h valor ] 10 ⟩;

}

This code is used in section 8.

§10  FREQ  TABELAS DE ESPALHAMENTO 3

10. ⟨ Insira nova célula na lista tab[h valor ] 10 ⟩ ≡

{ celula ∗cel nova; char ∗t; cel nova = (celula ∗) malloc(sizeof (celula)); if (cel nova ≡ Λ) {

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

} t = (char ∗) malloc(strlen(s) + 1); /∗ +1 para o ∗/ if (t ≡ Λ) {

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

} strcpy (t, s); cel nova palavra = t; cel nova n ocorrencias = 1; n pals dist^{++}; cel nova prox = tab[h valor ]; tab[h valor ] = cel nova;

}

This code is used in section 9.

11. ⟨ Imprima a lista de palavras e seu número de ocorrências 11 ⟩ ≡

{ int i;

for (i = 0; i < ; i^{++}) ⟨ Imprima as palavras na lista tab[i] 12 ⟩; }

This code is used in section 2.

12. ⟨ Imprima as palavras na lista tab[i] 12 ⟩ ≡

{ celula ∗ptr = tab[i];

for ( ; ptr ; ptr = ptr prox ) printf ( ␣ , ptr palavra, ptr n ocorrencias ); }

This code is used in section 11.

13. 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;

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

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

n comp/n pals );

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

printf (  ␣        ␣  ␣         ␣   ␣     ␣       ␣ ␣  ,

(double) n pals dist / );

This code is used in section 2.

4  INDICE  FREQ §15

15. 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{9}. cel nova: \underline{10}. celula: \underline{3}, 5, 9, 10, 12. celula struct: \underline{3}. celulas : 3. : \underline{4}. fprintf : 10. gets : 8. h: \underline{6}. h valor : \underline{8}, 9, 10. hash div : \underline{6}, 8. : \underline{5}, 6, 7, 11, 14. i: \underline{7}, \underline{11}. main: \underline{2}. malloc: 10. n comp: \underline{13}, 14. n ocorrencias : \underline{3}, 9, 10, 12. n pals : \underline{4}, 8, 14. n pals dist : \underline{4}, 10, 14. o: \underline{13}. palavra: \underline{3}, 9, 10, 12. printf : 12, 14. prox : \underline{3}, 9, 10, 12. ptr : \underline{9}, \underline{12}. s: \underline{4}, \underline{6}. stderr : 1, 10. stdin: 1. stdout : 1. strcmp: 9. strcpy : 10. strlen: 10. t: \underline{10}. tab: \underline{5}, 7, 9, 10, 12.

FREQ NAMES OF THE SECTIONS 5

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

⟨ Imprima a lista de palavras e seu número de ocorrências 11 ⟩ Used in section 2. ⟨ Imprima as palavras na lista tab[i] 12 ⟩ Used in section 11. ⟨ Imprima o número de palavras lidas e o número de comparações feitas 14 ⟩ Used in section 2. ⟨ Inicialize a tabela de espalhamento 7 ⟩ Used in section 2. ⟨ Insira nova célula na lista tab[h valor ] 10 ⟩ Used in section 9. ⟨ Leia a entrada palavra por palavra e as processe uma por vez 8 ⟩ Used in section 2. ⟨ Procure s na lista tab[h valor ]; insira ou incremente contador 9 ⟩ Used in section 8.

⟨ Typedefs 3 ⟩ Used in section 2. ⟨ Variáveis locais a main 4, 5, 13 ⟩ Used in section 2.