Jump to content
esec.rom

[Resolvido] ordenar listas ligadas

Recommended Posts

esec.rom

alguém me pode ajudar a ordenar uma lista ligada, acho que o .NET ja tem metodos que fazem isso mas, tenho que criar o metodo

public void Sort()
{
 if (this.ListaVazia == true)
 {
	 return;
 }
 if (this.primeiro.next==null)
 {

	 return;
 }
 Nodo<T> aux = this.primeiro;
 //implementaçao da ordenaçao

}

Edited by Rui Carlos
GeSHi

Share this post


Link to post
Share on other sites
esec.rom

pode ser o quicksort ou outro qualquer;

nao quero que me façao o codigo todo, so quero uma ajuda para estruturar o codigo.

Share this post


Link to post
Share on other sites
Rui Carlos

Em duas respostas não te deste ao trabalho de fornecer a estrutura de dados que suporta a lista ligada. Dá pouca vontade de ajudar assim, ainda para mais quando se recebem respostas do tipo "pode ser qualquer um".

Se pode ser qualquer um, um bubble sort é capaz de ser mais simples de implementar. Algoritmo disponível aqui.

No teu caso, terás de adaptar as funções para listas em vez de arrays. Mas podes começar por tentar colocar a estrutura base do algoritmo na tua função, e depois coloca aqui o que fizeres, se não estiver a funcionar.

Share this post


Link to post
Share on other sites
esec.rom

eu estou a ficar baralhado com as listas, com arrays sei fazer mas com listas não, eu disse qualquer um porque depois de um implementado ja sei +- como implementar os outros.

com o link que mandaste nao consigo chegar a nenhum lado, ja estou todo baralhado

Share this post


Link to post
Share on other sites
esec.rom

ja fiz isto mas nao funciona

if (this.ListaVazia == true || this.Count == 1)
 {
	 return;
 }
Nodo<T> current = this.primeiro, current2 = this.primeiro;
Nodo<T> aux = current2;
current2 = current2.next;
//T[] vec = this.ToArray();

while (current != null)
{
while (current2 != null)

{
 if(current2.info.CompareTo(current.info)>0)
 {
 aux.info = current2.info;
 current2.info = current.info;
 current.info = aux.info;
 }
 current2 = current2.next;
}
current = current.next;

}
}

Share this post


Link to post
Share on other sites
Rui Carlos

Antes de mais, percebo pouco de C#. Adicionalmente, continuo sem saber a estrutura do tipo Nodo (e a mistura de termos em português com termos em inglês está uma boa confusão...).

Adaptando o teu código para o algoritmo descrito aqui, penso que ficas mais ou menos com isto:

if (this.ListaVazia == true || this.Count == 1)
{
   return;
}

Nodo<T> current;  // vamos deixar a inicialização para mais tarde; só precisas de uma variável, pois vais sempre trabalhar com o current, e com o current.next
T aux;  // a ideia é que precisas de uma variável auxiliar para fazeres swap da informação (T), não do nodo todo.
bool swapped = true;  // diz quando é que o algoritmo termina

while(swapped == true) // ou simplesmente, while(swapped)
{
   swapped = false;
   current = this.primeiro;
   while(current.next != null)  // enquanto houver próximo (para comparares com o current)
   {
        if(current.info.CompareTo(current.next.info)>0)
        {
            aux = current.info;
            current.info = current.info;
            current.info = aux;
            swapped = false;
        }
        current = current.next;
   }
}

No teu código anterior, tinhas um problema com o current2, que depois da primeira execução do ciclo interno, ficava a null, e como tal o ciclo interno nunca mais era executado.

Estavas também a seguir uma estratégia em que movias o elemento mais pequeno para o início, enquanto que na minha revisão é o maior que vai sendo movido para o fim (a menos de algum bug :D ). A condição de paragem é baseada no facto de haver ou não trocas na iteração anterior. Segui a estratégia apresentada no algoritmo da wikipédia.

Possivelmente, conseguias corrigir o teu código adicionando um current2 = current.next; no início do ciclo exterior.

Tanto a minha solução como a tua (depois de corrigida) podem ser optimizadas (mesmo mantendo o algoritmo bubble sort). Mas isso fica como um exercício :)

Share this post


Link to post
Share on other sites
esec.rom

obrigado por tudo, ja vi onde estava o erro,

faltava isto T aux; em vez Nodo<T> aux = current2;

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.