1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Procura em listas ordenadas

Discussão em 'Programação' iniciada por lilcrazy, 17 de Março de 2007. (Respostas: 9; Visualizações: 1060)

  1. lilcrazy

    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[]
     
  2. legerdemain

    legerdemain Power Member

    implementa um algoritmo de pesquisa dicotómica.. http://en.wikipedia.org/wiki/Dichotomic_search
     
  3. Tuaregue

    Tuaregue Power Member

    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.
     
  4. wolftec

    wolftec Power Member

    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].
     
  5. Hipnoted

    Hipnoted Power Member

    Linguagem? Já agora listas simples ou duplamente ligadas?
     
  6. MadOnion

    MadOnion Folding Member

    Para o efeito é usar um ciclo:

    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: 18 de Março de 2007
  7. Rui_Carlos

    Rui_Carlos 1st Folding then Sex

    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.
     
  8. lilcrazy

    lilcrazy Power Member

    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
     
  9. liquido

    liquido Power Member

    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.
     
  10. PrOdG

    PrOdG Power Member

    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.
     

Partilhar esta Página