1. Lucas José Kreutz Alves
  2. Trabalho Final de ED

Source

Trabalho Final de ED /

Filename Size Date modified Message
dicionarios
textos
49 B
251 B
3.2 KB
1.8 KB
6.2 KB
155 B
2.4 KB
234 B
3.8 KB
258 B
1.1 KB
3.5 KB
12.4 KB
1.0 KB
7.2 KB
1.0 KB
4.0 KB
465 B
4.4 KB
658 B
Trabalho Final de Estrutura de Dados (UFRGS, 2011/2)
- Adolfo Schneider
- Lucas Jose Kreutz Alves

-------------------------------------------------------------------------------
Objetivo:
    Dado um dicionario (somente palavras, sem definições), econtra erros 
  ortográficos em um arquivo texto.
  

Estruturas:
-Dicionário: AVL
-Texto: Pilha
-Erros: Lista Simplesmente Encadeada
-Palavra: Array


Justificativa da Escolha das Estruturas:
-Dicionário: Escolhemos utilizar AVL devido a sua rapidez para encontrar os
dados e altura reduzida em comparação a árvores como ABP e Rubro-Negras.
-Texto: facilidade de fazer inserções e de resgatar os items de sua estrutura.
Uma operação de POP, além de já liberar a memória ocupada, devolve o valor da
palavra.
-Erros: Pela simplicidade da estrutura e da possibilidade de termos um número
variado de itens, sendo o tamanho da memória a única limitação. Possibilidade
de ordenamento dos itens.
-Palavra: Pela otimização da alocação da memória, evitando a fragmentação dela.
Se torna uma estrutura mais rápida de lidar, aumentando a velocidade da execução
do programa.


Arquivos de Entrada:
- Arquivo dicionário (extensão .dic, codificação ANSI (Windows-1252);
- Arquivo texto (extesão .txt, codificação ANSI (Windows-1252)).


Vantagens:
- Estrutura fácil de ser compreendida, lógica simples;
- Utiliza estruturas básicas (AVL, Arrays, LSE e PILHA);
- Não utiliza árvores n-árias;
- Algoritmos de inserção e pesquisa simples;

Instruções:
- Coloque os arquivos de dicionário na pasta dicionarios
- Coloque os arquivos de texto na pasta dicionarios
- Rode o programa

Modificações para a Etapa 2:
- Criado campo 'linha' na estrutura do texto para salvar a linha no qual a
palavra se encontrava no arquivo. O motivo dessa modificação é que desse modo
a linha do qual a palavra foi lida fica registrada na pilha de palavras do texto;
- Criado campo 'linhas' na estrutura dos erros. É uma LSE em que cada elemento
representa uma linha em que o erro se encontra. Utilizamos uma LSE para representar
as linhas pela sua facilidade de implementação, velocidade e pela possibilidade
de não haver limitações quanto ao número de linhas que podem ser inseridas.


-------------------------------------------------------------------------------
Observações:
- Os arquivos devem estar em ANSI (não UTF8, nem ISO8859-1,nem ....);
- Os caracateres com acentos não serão impressos na tela corretamente em
terminais que não tenham codificação ISO8859-2 (a do prompt do Windows);
- Para exibir corretamente os acentos no Linux (testado no Ubuntu), mude a 
codificação do terminal para Europeu (ISO8859-2);
- Sabemos que utilizar uma Trie Tree ou uma B+ Tree seria mais eficiente para
armazenar o dicionário, mas a proposta da cadeira é de utilizar estruturas
mais básicas;
- Foi utilizado o Code::Blocks como IDE (por isso o arquivo .CBP no código) com
o GCC como compilador. Acreditamos que rode em outras IDE's e compiladores sem 
problemas;
- Foi desenvolvido no Windows, com foco nesse sistema. Rodá-lo em outros sistemas
requer modificações no código.