Semin rio de Estrutura de Dados B sica

Seminário de
Estrutura de
Dados Básica
PROFESSOR: ORLEWILSON MAIA

Busca Sequencial / Linear
Josias

Santos
Samuel Dantas
Gabriel Nery
Allan Silva

Busca Sequencial
É

uma das formas mais simples de busca.  Pode ser implementado em um vetor ordenado ou em uma lista encadeada.  Percorre-se registro por registro em busca da chave

Busca Sequencial
Chave buscada = 57
1

N = 10
7

25

31

39

57

60

68

71

83

94

Busca Sequencial –

Formas de

implementação

Algoritmo de busca sequencial em um vetor A, com n posições (0 até n – 1), sendo x a chave procurada: for ( i = 0 ; i < n ; i++ ) if(A[i] == x) return (i); /*chave encontrada*/ return (-1); /*chave não encontada*/

Busca Sequencial –

Formas de

implementação

Usa-se uma sentinela afim de melhorar o desempenho do algoritmo.
A[n]=x;
for (i=0; x != A[i]; i++); if (i < n) return(i);

//chave encontrada

else return(-1);

//chave não encontrada

Busca Sequencial
Algoritmo de busca sequencial em uma lista duplamente encadeada ordenada com head, onde buscar é a chave que se deseja encontrar. Lista *busca(Lista *l, int buscar){ if(buscar < l->next->matricula || buscar > l->prev->matricula) return l;
Lista *aux = l->next; for(aux; aux->matricula!=buscar && aux != l ;aux = aux>next); if(aux == l) return l;
//chave não encontrada else return aux;
// chave encontrada
}

Busca Sequencial
Se a chave n for encontrada, retornará o nó, em que foi encontrada, senão retornará a sentinela que no caso é o valor de l.
O primeiro if testa se o n é menor que o primeiro elemento da lista, ou maior que o último da lista. O laço while percorre a lista inteira, comparando a chave com o campo correspondente do registro. Busca Sequencial


Complexidade:

•

Se o registro for o primeiro: 1 comparação,

•

Se o registro procurado for o último: N comparações,

•

Se for igualmente provável que o argumento apareça em qualquer posição da tabela, em média: (n+1)/2 comparações, •

Se a busca for mal sucedida: N comparações.

•