MC 202 - EF - Atividade de Laboratório no. 7

Descrição do Problema: Avaliação prática de Árvores Binárias de Busca

• árvores binárias de busca não balanceadas 
• árvores binárias de busca perfeitamente balanceadas
• árvores binárias de busca 'ponderadas' pela freqúência de ocorrências

O texto de entrada

O que deve ser feito

1. Construção da 'primeira árvore': ler o arquivo de entrada e criar uma árvore binária de busca com as palavras contidas no mesmo (sem repetições). Nessa árvore, as palavras devem ser inseridas à medida em que ocorrem no texto, sem nenhuma preocupação com o balanceamento da mesma. 
2. Avaliação da 'primeira árvore': ler o arquivo de entrada e procurar cada palavra que ocorre no mesmo na árvore criada no passo 1.  As ocorrências de cada palavra devem ser contadas nesta fase.  Ao se fazer a busca por uma palavra na árvore, o programa deve contar as comparações de palavras ('strings') e de caracteres. Ao final, o programa deverá listar o número total de comparações de palavras e de caracteres (essas mesmas informações deverão ser apresentadas para cada um dos tipos de busca analisadas nesta atividade.).
3. Avaliação da 'árvore perfeitamente balanceada': como a busca numa árvore perfeitamente balanceada é equivalente à busca binária num vetor, para fazer esta medição o seu programa pode fazer o seguinte: construir um vetor com as palavras do texto, percorrendo a árvore construída no passo 1 em in-ordem,  e em seguida ler o arquivo de entrada fazendo a busca (binária) de cada palavra que ocorre no mesmo. Ao se fazer a busca binária por cada palavra no vetor, o programa deverá contar as comparações de palavras e de caracteres. Esses valores serão parte do resultado final a ser apresentado pelo programa. Caso você queira, por uma questão de rigor, fazer uso de uma árvore perfeitamente balanceada, esta pode ser construída facilmente a partir do vetor ordenado.
4. Avaliação da 'árvore ponderada pelas freqüências': Para esta fase, o seu programa deverá ordenar o vetor construído no passo 3 por ordem decrescente das freqüências (número de ocorrências) das palavras. Uma vez ordenado o vetor, inserir os nomes numa árvore binária de busca não balanceada, por ordem decrescente das freqüências (usando as mesmas funções utilizadas para a construção da árvore no passo 1).  Nessa árvore, a raiz irá conter a palavra mais freqüente (o mesmo acontecendo com cada sub-árvore). Tendo construído essa árvore, ler o arquivo de entrada, fazendo a busca na árvore por cada palavra que ocorre no mesmo. Ao se fazer essa busca, o programa deverá contar as comparações de palavras e de caracteres. Esses valores deverão ser apresentados como parte do resultado final do programa. 
5. Conclusões: além do programa, deverá ser entregue um arquivo texto explicando o porquê dos resultados obtidos. Importante: o objetivo das conclusões é procurar explicações para os fatos observados - elas não devem se resumir à descreve-los.

Funções auxiliares

#define GT 1
#define EQ 0
#define LT -1

/***** contadores de comparações ********/
int compCount = 0;
int chCompCount = 0;

/***** (re)inicialização dos contadores de comparações *****/
void resetCounters(){ 
  compCount = 0; 
  chCompCount = 0; 
}
    
/******* comparação de strings ********/
/****  e contagem das comparações  ****/
int strComp(char *a, char*b){
  compCount++;
  for(;;){
    chCompCount++;
    if(*a == '\0')  if(*b == '\0') return EQ; else return LT;
    if(*b == '\0')  return GT;
    if(*a < *b)     return LT;
    if(*a++ > *b++) return GT;
  }    
}    

/****************************************************
  funções auxiliares para acesso ao arquivo texto
*****************************************************/

char lastCh = '\0';      /* último caracter lido */
FILE* inputFile = NULL;  /* arquivo de entrada   */
int wordCount = 0;       /* contador de palavras */

/*** habilita o arquivo para leitura ***/
void initInputFile(char* fName){
  inputFile = fopen(fName,"r");
  lastCh = tolower(fgetc(inputFile));
  wordCount = 0;
}

/*** encerra a sessão de leitura do arquivo ***/
void closeInputFile() { close(inputFile); }

/*  'pega' o próximo nome do arquivo de entrada. */
/*  Devolve NULL se chegar ao final do arquivo   */
char* getName() {
  char name[30];
  int  idx = 0;
  char * res = NULL;
  /* pular caracteres que não interessam */
  while((lastCh != EOF) && ((lastCh < 'a') || (lastCh > 'z'))) lastCh = tolower(fgetc(inputFile));
  while((lastCh >='a') && (lastCh <='z')){
    name[idx++] = lastCh;
    lastCh = tolower(fgetc(inputFile));
  }
  if(idx == 0) return NULL;
  res = (char*)malloc(idx+1);
  name[idx]='\0';
  wordCount++;
  strcpy(res,name);
  return res;
}

  initInputFile("arquivo.txt");
  name = getName();
  while(name != NULL){
    printf("nome:[%s]\n",name);
    name = getName();
  }
  closeInputFile();

Os Resultados

• número total de palavras encontradas no texto (incluindo as repetições)
• número de palavras diferentes encontradas no texto
• para cada um dos três tipos de busca realizados
• número total de comparações 'palavra a palavra' 
• número total de comparações 'caracter a caracter'

Item Opcional

Data de Entrega: 13/10/07