Procura em listas ordenadas

L

lilcrazy

Power Member
Boas pessoal.

1) Alguém me pode ajudar como se procura um elemento X de uma lista ordenada?

por exemplo searchElement(int x);

se encontrar X devolve true, se não encontra devolve false.

2) E como se faz para devolver o elemento na posição pos.

returnElement(int pos);

OBRIGADO

abraços[]
 
Pesquisa binária(pesquisa dicotómica), é o melhor. O resto é básico, lembra-te que só podes utilizar a pesquisa binária se a lista estiver mesmo ordenada.
 
Não sei que linguagem estas a utilizar, mas em python tens a função FIND que te devolve a posição da primeira ocurrencia na lista se não a encontrar devolve -1.

Pela tua segunda pergunta deduzo mesmo que não estás a utilizar python, pois para teres isso basta var=lista[n].
 
lilcrazy disse:
Boas pessoal.

1) Alguém me pode ajudar como se procura um elemento X de uma lista ordenada?

por exemplo searchElement(int x);

se encontrar X devolve true, se não encontra devolve false.

2) E como se faz para devolver o elemento na posição pos.

returnElement(int pos);

OBRIGADO

abraços[]
Clicar para expandir...

Para o efeito é usar um ciclo:

Ciclo que vai da posição 0 até ao tamanho da lista (exclusivé).
Para cada valor da lista, compara com o elemento.
Se o valor da lista == elemento, devolve verdadeiro, senão devolve falso.
Clicar para expandir...

Para devolver a posição devolver um boolean, devolve um int:
É usar o mesmo ciclo, mas em vez de devolver verdadeiro ou falso, devolve "indice".

Cumps

Edit: Saber o tipo de lista é fulcral.
 
Última edição:
legerdemain disse:
implementa um algoritmo de pesquisa dicotómica.. http://en.wikipedia.org/wiki/Dichotomic_search
Clicar para expandir...

parece-me que esse algoritmo só faz sentido se tiveres acesso directo às posições da lista (nos arrays por exemplo). em lista ligadas pouco melhor se poderá fazer do que um busca sequêncial em que terminamos quando aparecer um valor maior do que o procurado.

para devolver o elemento de uma determinada posição é só fazer um ciclo que vai contando os elementos (mais uma vez estou a admitir que são usadas listas ligadas, no caso de array's o acesso é directo).

PS: convém dizer que tipo de lista estão a ser usadas.
 
Realmente saber a linguagem e o tipo de lista usada é fulcral!!

Escapou-se me, sorry :/

A linguagem utilizada é java. O tipo de lista ligada é lista ligada ordenada. Uma vez que o programa recebe um ficheiro de comandos do tipo "insert x", "del x", exists "x", "print y".
Ou seja quando eu leio uma linha divido a linha em tokens, e só faz operações se existirem apenas 2 tokens. O primeiro token é o tipo de comando, e o segundo token é o valor que o comando utilizará. No caso do insert, del e exists, os valores dados são por exemplo 100, 90, etc. A minha ideia é à medida que se lê o valor, faz-se a procura na lista. Se existir não executa o comando, se não existir executa o comando e coloca o valor correspondente na lista. Eu já consegui implementar o algoritmo que coloca os elementos na lista por ordem. Ou seja, daí ser uma lista ligada ordenada. Preciso apenas de umas luzes para desenvolver um método boolean que procura na lista o elemento, se existir devolve true, se nao existir devolve false.
O comando print recebe as posições e não o valor em si. Como a lista tem de estar por ordem, se for "print 2", ele devolve o elemento na posição 2 da lista. Mas não o segundo elemento, devolve o elemento na ordem. Por exemplo se entrar na lista 120, 90, 100. E se fizer "print 2" ele não devolve 90. Devolve 100 (ordem crescente).

Any help?

tnks
 
admitindo que usas uma estrutura do genero:

Código: 
typedef struct _No {
  struct _instante *next;        /* ponteiro para o proximo nó da lista*/
} No;

para procurares usas qualquer coisa do género:

Código: 
no * procuraNo(int t, No *no) {
 no*aux;
 
 for(aux=no; aux!=NULL; aux=aux->next){
  if(aux->t == t) return aux;
 }

 return NULL;
}

que te retorna NULL caso não encontre e retorna um ponteiro para esse nó que procuras na lista caso o encontre.
 
Pesquisas dicotómicas em listas não fazem grande sentido, já que (como já disse o Rui_Carlos) não se tem acesso directo a uma determinada posição. A melhor solução é mesmo a que já deram, pesquisa iterativa.
 
Inicie sessão ou registe-se para poder participar.
Back
Topo