Jump to content

Ordenar listas ligadas


Bartude

Recommended Posts

Boas, eu queria ordenar uma lista ligada, só que ta a dar mal. A minha lista ligada chama-se atletas e é do tipo Atleta(uma instancia). La dentro tem os atributos ouro, prata e bronze. E queria ordenar primeiro por ouro, depois prata e depois bronze. O codigo seguinte é so o de ouro, depois é so alterar para os outros.

Atleta temp;
for (int i = 0; i < atletas.size() - 1; i++) {
		for (int j = i + 1; j < atletas.size() - 1; j++) {
			Atleta temp2 = atletas.get(j);
			if (atletas.get(i).getOuro() < atletas.get(j).getOuro()) {
				temp = atletas.get(i);
				atletas.removesem(i);
				atletas.add(i, atletas.get(j));
				atletas.removesem(j);
				atletas.add(j, temp);
			}
		}
	}

O removesem é um metodo da classe lista ligada, que quando remove, em vez de retroceder todos os elementos, deixa ali um espaço em branco, pa depois inserir.

public int removesem(int index){
	assert(index >= 0 && index < size()); //force valid index
	temp = head; //start at the beginning of the list

	if(index == 0){
			head = null;
			counter--;
			return 0;

	}
	else if(index == size()){
			tail = null;
			counter--;
			return 0;
	}

	//iterate to the position before the index
	for(int i = 0; i < index; i++) temp = temp.next;

	//set temp.next to point to the Node next to the Node to be removed
	temp = null;
	counter--;
	return 0;
}

O problema é que a partir dum certo ponto, começa a inserir tudo igual, e acaba por ficar 3/4 da lista ligada igual.

Alguem sabe qual o problema? Brigado

Link to comment
Share on other sites

Boas,

  1. Não usas a variavel temp2
  2. Tu removes a posição i e tudo passa a estar 1 index atrás e pegas no j (depois de remover é j+1).
  3. 3ª linha do if é: atletas.add(i, temp2); agora j já é j e nºao j+1 porque existe mais uma posição.

O que estás a fazer neste algoritmo é trocar o valor de i com j sempre que encontras 1 menor (corrigido nos 3 pontos acima) até chegares ao fim. (Esta linha é mais um aparte.

Penso que a maneira que expliquei e corrigi está correta mas posso me ter enganado.

Espero ter ajudado 😉

Tiago Tavares

Link to comment
Share on other sites

Boas, isso dito assim, é um bocado confuso pa mim.

Pelo que eu percebi, o codigo atao vai ficar assim:

for (int i = 0; i < atletas.size() - 1; i++) {
	    for (int j = i + 1; j < atletas.size() - 1; j++) {
		    Atleta temp2 = atletas.get(j);
		    if (atletas.get(i).getOuro() < atletas.get(j).getOuro()) {
			    temp = atletas.get(i);
			    atletas.removesem(i);
			    j++;
			    atletas.add(i, temp2);
			    atletas.removesem(j);
			    atletas.add(j, temp);
		    }
	    }
    }

É assim que deveria de tar?

Link to comment
Share on other sites

Creio que será sem o j++

for (int i = 0; i < atletas.size() - 1; i++) {
 for (int j = i + 1; j < atletas.size() - 1; j++) {
		Atleta temp2 = atletas.get(j);
		if (atletas.get(i).getOuro() < atletas.get(j).getOuro()) {
				temp = atletas.get(i);
				atletas.removesem(i);
				atletas.add(i, temp2);
				atletas.removesem(j);
				atletas.add(j, temp);
		  }
  }
}

Depois diz se funciona 😉

Edited by tiagotavares

Tiago Tavares

Link to comment
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.