Ir para o conteúdo
esec.rom

[Resolvido] ordenar listas ligadas

Mensagens Recomendadas

esec.rom    2
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

}

Editado por Rui Carlos
GeSHi

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    312
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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
esec.rom    2
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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
esec.rom    2
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;

}
}

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    312
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 :)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.