Tecnologia

Disponível somente no TrabalhosFeitos
  • Páginas : 11 (2514 palavras )
  • Download(s) : 0
  • Publicado : 1 de abril de 2013
Ler documento completo
Amostra do texto
Universidade Federal de Ouro Preto
Instituo de Ciências Exatas e Aplicadas (ICEA)
Campus João Monlevade

Algoritmos e Estruturas de Dados II
Segundo Trabalho Prático
Algoritmos de Pesquisa/Busca


Sumário

1- Introdução 3
1.1 - Considerações Iniciais 3
1.2 – Especificações do Problema 3
2 – Algoritmos e Estruturas de Dados 4
2.1 (TAD LISTA) Lista.h 4
2.1.2 Função BuscaBinária: 5
2.1.3 Função Busca Sequencial: 5
2.2 (TAD HASH) hash.h 6
2.3 (TAD Arvore AVL) arvAvl.h 7
2.5 Função Principal (main.c) 8
3 – Conclusão 11
4 – Referências 12

1- Introdução

O seguinte trabalho visou realizar a implementação de algoritmos de pesquisa/Busca. Estes algoritmos foram desenvolvidos por meio de estruturas de dados como Arvore Binária de Busca, Arvore AVL e tabelaHash. Também foi utilizado como estrutura de dados uma Lista encadeada a fim de armazenar dados para o desenvolvimento do trabalho. Após a inserção de elementos nas estruturas citadas foi disponibilizado algoritmos que permitem a busca em cada uma das estruturas para posteriormente realizar as comparações necessárias.
A seguir serão apresentados os principais conceitos do desenvolvimento daaplicação.
1.1 - Considerações Iniciais
Ambiente de desenvolvimento do código fonte: Code Blocks
<Disponível em: http://www.codeblocks.org/Acesso em: 28/03/2013>
Ambiente de desenvolvimento do código fonte: QT Creator
<Disponível em: http://qt-project.org/doc/qtcreator-2.6/Acesso em: 28/03/2013>
Linguagem de Programação Utilizada: Linguagem C.

1.2 – Especificações do ProblemaFaça um programa que leia um texto qualquer (arquivo no formato .txt) e imprima, em
ordem alfabética, as palavras e a sua frequência no texto. Por exemplo, no texto “dois mais dois são quatro” o seu programa deverá imprimir:
dois 2
mais 1
quatro 1
são 1
A leitura do arquivo deverá desprezar espaços em branco e sinais de pontuação, que serão considerados separadores de palavras. Além disso, aleitura deverá converter todas as letras maiúsculas em minúsculas. Você pode considerar que existem no máximo 1024 palavras diferentes no texto (de fato, considere as primeiras 1024 diferentes palavras que aparecerem no texto e despreze as seguintes novas palavras), e que cada palavra contém no máximo 20 letras.
A pesquisa e inserção das palavras do texto deverão ser implementadas com asseguintes estruturas:
1. Pesquisa Sequencial.
2. Pesquisa Binária.
3. Árvore Binária de Pesquisa sem balanceamento.
4. Árvore Binária de Pesquisa com balanceamento.
5. Hash – endereçamento aberto.
Coloque contadores no seu programa para determinar o número de comparações de chaves e atribuições de registros necessárias para montar a tabela de freqüências em cada uma das estruturas acima (Apenas onúmero de comparações para montar a estrutura. Não é necessário considerar as comparações e atribuições para a impressão ordenada).
Calcule também o tempo que cada estrutura leva apara montar a tabela. Análise através dos dados coletados o desempenho / eficiência de cada estrutura. Use parâmetros de linha de comando para fazer sua chamada. Esse tipo de execução é bastante comum em sistemas Unix /Linux e no antigo DOS. Por exemplo, se o seu programa chama-se Freq e você quiser contar a frequência do arquivo texto.txt utilizando um hash, sua chamada deve ser:
> Freq hash texto.txt
Descubra como ler os parâmetros da linha de comando (da mesma forma como foi feita no trabalho prático 3) e defina (e documente) a sintaxe a ser utilizada. Também faz parte do trabalho descobrir como fazer aleitura de um arquivo texto e a manipulação adequada
de strings.
2 – Algoritmos e Estruturas de Dados
Para criação e estruturação do trabalho, foram utilizados aos tipos abstratos de dados Hash, Arvore Binária de Busca sem Balanceamento, Árvore Binária com Balanceamento (AVL) e Lista Dinâmica. As estruturas e as funções que compõem o trabalho serão descritas abaixo:

2.1 (TAD LISTA)...
tracking img