Algoritmos e Estruturas de dados

Algoritmos e Estruturas de dados
Tabela Hash
Métodos de pesquisa (busca): Como podemos recuperar informações a partir de uma grande massa de informações previamente armazenada? Existem vários métodos e estruturas de dados podem ser empregados para se fazer busca.
Dependendo da situação, cada método poderá tornar a sua busca mais eficiente.

A escolha do método de busca poderá ser feita analisando:
- Quantidade de dados envolvidos
- Frequência com que operações de inserção e retirada são efetuadas

Diante da análise você poderá escolher os seguintes métodos ( memória interna ):
_ Busca (pesquisa) Seqüencial
_ Busca Binária
_ Busca por Interpolação
_ Busca em Árvores( com e sem balanceamento)
_ Hashing

Conceitos básicos:

Informação é dividida em registros.
Registrossão estruturas de dados capazes de agregar várias informações. structnome_do_registro { tipo campo1; tipo campo2;
...
tipocampon;
};

Registros ficam armazenados em um vetor (arranjo).
Uma tabela é um conjunto de elementos, chamados registros.
A tabela pode ser:
_ Um vetor de registros
_ Uma lista encadeada
_ Uma árvore
_ Etc.

A tabela pode ficar:
_ Totalmente na memória (busca interna)
_ Totalmente no armazenamento auxiliar (buscaexterna)
_ Dividida entre ambos

Qual é o objetivo da busca de dados?

“Dado um conjunto de elementos, onde cada um é identificado por uma chave, o objetivo da busca é localizar, nesse conjunto, o elemento que corresponde a uma chave específica”

Tipos de busca de dados:

Busca sequencial: Método de pesquisa mais simples: a partir do primeiro registro, pesquise seqüencialmente até encontrar achave procurada; então pare. Armazenamento de um conjunto de registros por meiode um array. (vetor ou como uma lista encadeada)

for (i=0; iitems[0].chave = x; /* sentinela */ for(i = T->tamanho; T->items[i].chave != chave; i--); return i;
}

Uma maneira de tornar o algoritmo mais eficiente é usar um sentinela