ListSimpleLinked

6 de maio de 2008 10 respostas

krvao 6 de maio de 2008

Boa noite…gostaria de ajuda para resolver o seguinte exercicio :

Implementar na classe ListSimpleLinked o método de ordenação sort() que foi adicionado à interface ListTAD. O método de ordenação
deverá utilizar o seguinte algoritmo de ordenação.

Classificação por seleção:

O algoritmo constrói a seqüência classificada com um elemento de cada vez adicionando os elementos na seqüência em ordem. A cada
passo, o elemento a ser adicionado à seqüência classificada é selecionado dos elementos restantes. Devido aos elementos serem
adicionados em ordem, eles são sempre inseridos em uma extremidade.

Para i de 0 até tamanho da lista-1 {

minPos = posição do menor elemento a partir da posição i;

troque de posição os elementos das posições minPos e i;

}

Ex.:

11,9,17,5,12 i=0

5,|9,17,11,12 i=1

5,9,|17,11,12 i=2

5,9,11,|17,12 i=3

5,9,11,12,|17 i=4

Dica I: a classe Pessoa deve implementar a interface Comparable e a classe ListSimpleLinked só pode receber elementos que
implementem esta interface.
Dica II: o método de ordenação deve utilizar o método de comparação de elementos compareTo().
Dica III: implemente um método private para retornar a posição do menor elemento a partir da posição i.

Alterar o tratamento de evento dos botões ?Listar Homens? e ?Listar Mulheres? de modo que a listagem de pessoa seja ordenada
alfabeticamente em ordem crescente.

Grato pela atenção

10 Respostas

Bruno_Laturner 6 de mai. de 2008

Sim, e cadê as classes Pessoa, SimpleLinkedList, a interface ListTAD?

E qual é a dúvida no teu código?

krvao 6 de mai. de 2008

renrutal:
Sim, e cadê as classes Pessoa, SimpleLinkedList, a interface ListTAD?

E qual é a dúvida no teu código?

PESSOA

public class Pessoa {

private String nome;

private char sexo;

public Pessoa(String umNome, boolean masculino) {
	nome = umNome;
	if(masculino) {
		sexo = 'M';
	}
	else {
		sexo = 'F';
	}
}

public String getNome() {
	return nome;
}

public char getSexo() {
	return sexo;
}

public String toString() {
	return "["+nome+","+sexo+"]";
}

 public boolean equals(Object o) {
     if(o == null) 
         return false;
     if(getClass() != o.getClass()) 
         return false;
     Pessoa outraPess = (Pessoa) o;
     if((nome.equals(outraPess.nome)))
         return true;
     else
         return false;        
 }

}

ListSimpleLinked

public class ListSimpleLinked implements ListTAD

{

// Referência para o primeiro elemento da lista encadeada.

private Nodo prim;

// Referência para o último elemento da lista encadeada.

private Nodo ult;

// Contabiliza o número de elementos da lista.

private int totalElementos;

// Classe interna Nodo
private class Nodo<T> {
    private T element;
    private Nodo<T> next;
    public Nodo(T e) {
        element = e;
        next = null;
    }
    public void setElement(T e) {
        element = e; 
    }
    public void setNext (Nodo<T> n) { 
        next = n; 
    }
    public T getElement() { 
        return element; 
    }
    public Nodo<T> getNext() { 
        return next; 
    }
}

public ListSimpleLinked () {
    prim = null;
    ult = null;
    totalElementos = 0;
}

ListTAD

public interface ListTAD

{

/**

* Adiciona um elemento ao final da lista

* @param element elemento a ser adicionado ao final da lista

<em>/	

public void add(E e);

/</em>*

* Insere um elemento em uma determinada posição da lista

* @param index a posição da lista onde o elemento será inserido

* @param element elemento a ser inserido

* @throws IndexOutOfBoundsException se (index < 0 || index > size())

<em>/

public void add (int index, E element);

/</em>*

* Esvazia a lista

<em>/

public void clear();

/</em>*

* Retorna true se a lista contém o elemento especificado

* @param element o elemento a ser testado

* @return true se a lista contém o elemento especificado

<em>/

public boolean contains(E e);

/</em>*

* Retorna o elemento de uma determinada posição da lista

* @param index a posição da lista

* @return o elemento da posição especificada

* @throws IndexOutOfBoundsException se (index < 0 || index >= size())

<em>/

public E get(int index);

/</em>*

* Retorna o índice da primeira ocorrência do elemento na lista, ou -1 se a lista não contém o elemento

* @param element o elemento a ser buscado

* @return o índice da primeira ocorrência do elemento na lista, ou -1 se a lista não contém o elemento

<em>/

public int indexOf (E e);

/</em>*

* Retorna true se a lista não contêm elementos

* @return true se a lista não contêm elementos

<em>/

public boolean isEmpty();

/</em>*

* Remove a primeira ocorrência do elemento na lista, se estiver presente

* @param element o elemento a ser removido

* @return true se a lista contém o elemento especificado

<em>/

public boolean remove(E e);

/</em>*

* Remove o elemento de uma determinada posição da lista

* @param index a posição da lista

* @return o elemento que foi removido da lista

* @throws IndexOutOfBoundsException se (index < 0 || index >= size())

<em>/

public E remove(int index);

/</em>*

* Retorna o número de elementos da lista

* @return o número de elementos da lista

<em>/

public int size();

/</em>*

* Substitui o elemento armanzenado em uma determinada posição da lista pelo elemento indicado

* @param index a posição da lista

* @param element o elemento a ser armazenado na lista

* @return o elemento anterior armazenado na posição da lista

* @throws IndexOutOfBoundsException se (index < 0 || index >= size())

<em>/

public E set(int index, E element);

public void addFirst(E e);

public E getFirst();

public E getLast();

public boolean removeFirst();

public boolean removeLast();

/</em>*

* Ordena a lista de acordo com a ordenação natural dos elementos, que devem implementar a interface Comparable

*/

public void sort();

}

***Minhas duvidas são quanto a implementação dos metodos que o exercicio pede…“sort, set E int(index, E element)…”

Bruno_Laturner 6 de mai. de 2008

Primeiro, implemente a interface Comparable na classe Pessoa. Tem uma explicação sobre ele aqui (na verdade é sobre o Comparator, que é quase a mesma coisa).

Sobre o sort, é exatamente como o exercício fala, para cada elemento à frente da sua posição na lista, encontre o menor de todos(usando o tal método private) e troque de lugar com ele.

Sobre o set, você vai até a posição indicada e sobreescreve o valor lá pelo novo que foi passado por parâmetro.

PS: pelamordedeus use a as tags [code] ao redor do seu código.

krvao 6 de mai. de 2008

cara…mto obrigado mas se eu soubesse como desenvolver n estaria aqui perguntando!!!

krvao 7 de mai. de 2008

Alguem poderia me ajudar?

Bruno_Laturner 7 de mai. de 2008

public class Pessoa implements Comparable<Pessoa>
{
  public int compareTo(Pessoa pessoa)
  {
    return this.nome.compareTo(pessoa.getNome());
  }
}

public class ListSimpleLinked<E> implements ListTAD<E>
{
  private Nodo<T> achaMenorAPartirDe(Nodo<T> nodo)
  {
    T menor = null;
    if (nodo != null)
    {
      menor = nodo;
    }
    while (nodo != null)
    {
      if (nodo.getElement().compareTo(menor.getElement()) < 0)
      {
        menor = nodo;
      }
      nodo = nodo.getNext();
    }
    return menor;
  }

  private void swap (Nodo<T> nodo1, Nodo<T> nodo2)
  {
    if (nodo1 != null && nodo2 != null)
    {
      T temp = nodo1.getElement();
      nodo1.setElement(nodo2.getElement());
      nodo2.setElement(temp);
    }
  }

  public void sort()
  {
    for (Node<E> nodo = prim; nodo != null; nodo = nodo.getNext())
    {
      Nodo<E> menor = achaMenorAPartirDe(nodo);
      if (nodo != menor)
        swap(nodo, menor);
    }
  }
}

Não testei, nem usei uma IDE pra fazer isso, e fiz na pressa, mas deve estar próximo de estar certo.

krvao 7 de mai. de 2008

renrutal…

obrigado novamente, só não entendi o meto swap mas ja ajudou bastante…vlw

Bruno_Laturner 7 de mai. de 2008

Swap pega dois nós e trocam os seus elementos entre si.

O mais indicado seria deixar os elementos como estão e trocar de lugar somente os nodos, mas isso dá muito trabalho numa lista simplesmente ligada, mais fácil numa em uma duplamente ligada(que aponta para o próximo e para o anterior).

krvao 7 de mai. de 2008

Este erro esta sendo gerado referente ao metodo “achaMenorAPartirDe”

found : ListSimpleLinked.Nodo
required: T
menor = minPos;

symbol  : method getElement()

location: class java.lang.Object

if (minPos.getElement().compareTo(menor.getElement()) < 0)

found : T
required: ListSimpleLinked.Nodo
return menor;

Bruno_Laturner 7 de mai. de 2008

Generics não é o meu forte. Tenta trocar T por E.

Criado 6 de maio de 2008

Ultima resposta 7 de mai. de 2008

Respostas 10

Participantes 2

10 Respostas

Topicos relacionados