Projeto para MAC324 - VIP

MAC324 - Estruturas de Dados para Engenharia

Poli/Elétrica - 1o. Semestre de 1999

Observações

1. Você pode entregar duas versões do vip1.
   • Você pode entregar uma versão preliminar de vip1, que usa árvores de busca binária sem balanceamento para implementar a tabela de símbolos (veja observação sobre tabela de símbolos abaixo). O prazo de entrega é o estabelecido incialmente para a primeira fase do projeto.
   • Se você optar por fazer isto, você pode entregar a versão definitiva de seu vip1 até as 15:00 do dia 24 de maio de 1999. Esta versão definitiva deve usar árvores com balanceamento. Nada além da implementação da tabela de símbolos deve mudar de uma versão para outra. Isto será verificado pelo monitor!!!
   • Aqueles que optarem por entregar duas versões do vip1 (que eu recomendo), terão a oportunidade de entregar um relatório comparando o desempenho de suas duas versões até as 15:00 do dia 14/6/99. Um relatório bem feito valerá um ponto extra na nota final do projeto.
2. Dicas sobre linhas e texto de comprimento arbitrário. Você pode encontrar neste diretório dois programas que ilustram como alocar memória dinamicamente de forma que
   • possamos ler linhas de comprimento arbitrário (função GetLine() em leia_linha_C.c) e
   • possamos ler um texto de comprimento arbitrário para a memória (a única limitação é a quantidade de memória disponível). O programa leia_linha2.c também usa a técnica de alocar blocos de caracteres por vez, para diminuir o número de chamadas ao sistema (malloc()), que são demoradas.
   • Note que o GetLine() faz uso de malloc() e free() sem muita preocupação. Se você quiser, você pode pensar em como implementar uma versão de GetLine() que faz menos uso de chamadas ao sistema.
3. Tabela de símbolos. Uma parte importante do projeto consiste na implementação de uma tabela de símbolos (veja o Capítulo 12 do Sedgewick). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em listas ligadas (que é uma forma muito primitiva de implementação). Preste atenção na modularização seguida neste exemplo.

   Lembre-se de que você pode entregar a primeira fase do projeto (vip1) usando árvores de busca binária sem balanceamento. A modularização apresentada neste exemplo facilitará a entrega da versão definitiva de seu vip1.

4. A técnica do vetor ord[] de wordtest. A técnica de Knuth que usa o vetor ord[] para identificar letras maiúsculas e minúsculas, para distinguir caracteres de quebra de palavra, etc parece-me que vale a sua atenção. Inclusive, com este vetor, você pode provavelmente dar uma solução simples para problemas ligados com caracteres acentuados, cedilha, etc.
5. Ordem alfabética. A ordem alfabética do dicionário não é a ordem lexicográfica que é derivada da ordem numérica dos caracteres quando levamos em conta a tabela ASCII. Para resolver este problema, você pode considerar como a chave que identifica uma palavra p um par ordenado (a(p), b(p)), onde a(p) seria a palavra p levando em conta o vetor ord[] que identifica as várias variantes de uma letra (maiúscula, minúscula, acentuada, etc). O componente b(p) levaria em conta, por exemplo, o código ASCII. Uma palavra p viria antes uma outra palavra q se a(p) < a(q) ou a(p) = a(q) e b(p) < b(q) (ordem lexicográfica nos pares).

   Note que o uso desta técnica implica em gerar uma variante dos dicionários fornecidos. Note também que esta técnica torna possível detectar palavras do tipo "abraão" (deveria ser "Abraão").

6. Tabela de símbolos (bis). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em ABBs. Note que a modularização que estamos usando faz com que a substituição da implementação com listas ligadas (veja este diretório) por esta nova implementação seja extremamente simples. Este é o poder de noções básicas como modularização e encapsulamento.
7. Tabela de símbolos (bisbis). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em ABBs aleatórias. Note que a modularização que estamos usando faz com que a substituição da implementação com listas ligadas (veja este diretório) ou com ABBs (veja este diretório) por esta nova implementação seja extremamente simples. Novamente, este é o poder de noções básicas como modularização e encapsulamento.
8. Tabela de símbolos (bisbisbis). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em ABBs do tipo splay.
9. Tabela de símbolos (bis^4). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em ABBs rubro-negras.
10. Tabela de símbolos (bis^5). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em tabelas de hashing. Usamos aqui resolução de colisões por encadeamento.
11. Tabela de símbolos (bis^6). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em tabelas de hashing. Usamos aqui resolução de colisões por linear probing.
12. Tabela de símbolos (bis^7). Você encontra neste diretório uma implementação de uma tabela de símbolos baseada em tabelas de hashing. Usamos aqui resolução de colisões por double hashing.

Last modified: Sun May 23 19:59:20 EST 1999