4

Alguém poderia me ajudar em implementar uma lista encadeada para realizar operações de conjuntos? Sem utilizar funções nativas do Java, como ArrayList.

O algoritmo já gera uma lista encadeada e adiciona novos nós, mas como faço para fazer uma operação como a união?

No Main, estou instanciando duas classes, cada uma seria uma lista com valores, mas como chamo uma função de união que receba como parâmetro essas duas listas e como percorre-las simultaneamente? (Sei percorrer uma por vez)

Código - Main

public class TrabalhoListas {

public static void main(String[] args) {
    ListaDinamica teste = new ListaDinamica();
    ListaDinamica teste2 = new ListaDinamica();
    teste.add(1);
    teste.add(2);
    teste.add(3);
    teste.imprimeLista();
    System.out.println("Segunda lista");
    teste2.add(1);
    teste2.add(6);
    teste2.add(3);
    teste2.imprimeLista();
    System.out.println("Primeira de novo");
    teste.imprimeLista();
}
}

--- Lista ---

public class Lista {

private int valor;
private Lista prox;

public Lista() {
}

public int getValor() {
    return valor;
}

public void setValor(int valor) {
    this.valor = valor;
}

public Lista getProx() {
    return prox;
}

public void setProx(Lista prox) {
    this.prox = prox;
}
}

Lista Dinâmica

public class ListaDinamica {

Lista primeiro;
Lista ultimo;
int tamanho = 0;

public ListaDinamica() {
    primeiro = null;
    ultimo = primeiro;
}

public void add(int valor) {
    Lista novo = new Lista();
    novo.setValor(valor);
    tamanho++;
    if (primeiro == null) {
        primeiro = novo;
        ultimo = novo;
        novo.setProx(null);
    } else {
        novo.setProx(primeiro);
        primeiro = novo;
    }
}

public void imprimeLista() {
    Lista atual = primeiro;
    for(int i = 0; i < tamanho; i++){
        System.out.println(atual.getValor());
        atual = atual.getProx();
    }
}

public void uniao(){

}
}
2
  • Posta o código do que tentou, mesmo que esteja errado ou incompleto. 28/03/2015 às 15:23
  • Certo, estarei colocando o Main e o arquivo que estou adicionando.
    – Natalia
    28/03/2015 às 16:03

3 Respostas 3

0

Acho que seria isso, que simplesmente modifica uma ListaDinamica concatenando nela uma outra ListaDinamica:

public void uniao(ListaDinamica outraLista) {
    ultimo.setProx(outraLista.primeiro);
    ultimo = outraLista.ultimo;
    tamanho += outraLista.tamanho;
    removeDuplicatas();
}

E para remover duplicatas, você acaba percorrendo a mesma lista duas vezes, uma dentro da outra:

private void removeDuplicatas() {
    for (Lista a = primeiro; a != null; a = a.getProx()) {
        for (Lista b = a.getProx(); b != null; b = b.getProx()) {
            if (a.getValor() == b.getValor()) {
                a.setProx(b.getProx());
                tamanho--;
            }
        }
    }
}

Este algoritmo de remover duplicatas não é lá muito eficiente (tem complexidade de tempo quadrática), mas deve funcionar corretamente e deve servir para os seus propósitos. Bolar um algoritmo eficiente para isso seria bem mais complicado, e neste caso seria melhor usar as classes que o java já lhe dá (como HashSet ou TreeSet).

Convém também colocar uma chamada a removeDuplicatas() no fim do método add(int). Ou então criar um método de busca e usá-lo no método add(int) para evitar adicionar um elemento que já exista.

E então, você usa este método no final do método main:

teste.uniao(teste2);
teste.imprimeLista();

Se preferir fazer a união sem modificar nenhuma das duas listas, o melhor então é seguir a abordagem da minha outra resposta.

6
  • Mas neste caso ele concatenaria tudo, entretanto uma união de conjuntos, só agrega valores inexistentes em um conjunto mas que contenham no outro. Ou seja, ele não pode repetir os valores.
    – Natalia
    28/03/2015 às 16:55
  • @Natalia Editei a minha resposta para remover as duplicatas. 28/03/2015 às 17:02
  • agora fiquei na dúvida, sobre matemática mesmo, caso A[1, 2, 1] e B[3, 4, 5] a união não seria C[1, 2, 1, 3, 4, 5]? Ou os números de um conjunto não podem se repetir dentro dele?
    – Natalia
    28/03/2015 às 17:19
  • @Natalia Conjuntos, tais como definidos na matemática, não têm elementos repetidos e nem ordem bem definida dos elementos. Exemplo: seja A o conjunto de países da Europa e B o conjunto de países que começam com a letra E. No conjunto que é a união de A e B temos a Espanha, mas não temos duas Espanhas. Também não existe nada dizendo se Espanha vem antes de Eslovênia ou não (a menos que nós venhamos a definir algum critério de ordenação). O mesmo se aplica para a intersecção. 28/03/2015 às 17:28
  • Entendi e em qual local eu invoco este metodo de união, e como passo para eles os valores das lista A e B?
    – Natalia
    28/03/2015 às 17:32
0

Para fazer a união entre duas listas, basta percorrer a lista 1 até o último "elemento válido"( !=null) e adicionar a lista 2 como o próximo deste elemento.

public static void uniaoLista(Lista l1, Lista l2){

    //Lista auxiliar que vai percorrer a lista 1
    Lista lAux = l1;


    //Percorre a lista l1 até chegar ao ultimo "elemento válido", ou seja, != de null
    while(lAux.getProx()!=null){

        lAux = lAux.getProx();
    }

    //Quando este elemento é achado, dizemos que seu próximo elemento será a lista l2
    lAux.prox = l2;
}

Dessa maneira, não teria a necessidade de criar uma classe "Lista Dinâmica", bastaria ter um objeto Lista que recebe a primeira lista e depois fazer a união entre esta lista e uma outra qualquer. Exemplo:

Suponha as listas:

Lista l1 = 1->2->3->4

Lista l2 = 5->6->7->8

Para realizar a união sem acabar com a lista l1, uma vez que os objetos são passados por referência, faça:

...
Lista lUniao = l1.clone();
uniaoLista(lUniao,l2);

//lUniao = 1->2->3->4->5->6->7->8
3
  • Certo, mas como passo as listas como parametro? Na Main, minhas listas seriam teste e teste2, como eu mandaria para o método uniaoLista? E também eu preciso fazer uma verificação, por exemplo, caso a l1 = 1->2->3 e a l2 = 2->3->4, apenas o 4 será inserido na nova lista, os valores não se repetem entre os conjuntos.
    – Natalia
    28/03/2015 às 16:58
  • Acho que o problema que vocês está tendo é que o método uniaoLista() está dentro de uma classe, então voce precisaria fazer teste1.uniaoLista() ou teste2.uniaoLista(). Faça o seguinte, coloque o método união lista na Main, não esquecendo de colocar o método como estático
    – regmoraes
    28/03/2015 às 17:01
  • Certo colocando no Main, da para passar por paramêtro, mas surge outro problema, como preciso verificar as igualdades, preciso percorrer a lista, e minhas variaveis globais, como primeiro e ultimo estão na classe ListaDinamica, e para adicionar valores na lista também é realizado na listaDinamica.
    – Natalia
    28/03/2015 às 17:08
0

Você pode acrescentar um método para descobrir se um elemento existe na ListaDinamica:

public boolean existe(int elemento) {
    for (Lista a = primeiro; a != null; a = a.getProx()) {
        if (a.getValor() == elemento) return true;
    }
    return false;
}

Modificar o método add(int) para não deixar adicionar duplicatas:

public void add(int valor) {
    if (existe(valor)) return; // Não deixa adicionar duplicatas.
    Lista novo = new Lista();
    novo.setValor(valor);
    tamanho++;
    if (primeiro == null) {
        primeiro = novo;
        ultimo = novo;
        novo.setProx(null);
    } else {
        novo.setProx(primeiro);
        primeiro = novo;
    }
}

E na união, é só acrescentar todos os elementos da outra lista:

public void uniao(ListaDinamica outraLista) {
    for (Lista a = outraLista.primeiro; a != null; a = a.getProx()) {
        add(a.getValor());
    }
}

E então, você usa este método no final do método main:

teste.uniao(teste2);
teste.imprimeLista();

Talvez você não goste do fato do método uniao modificar a lista. Se for este o caso, e você quiser na verdade criar uma nova lista sem modificar nenhuma das duas, então faça isso:

public ListaDinamica uniao(ListaDinamica outraLista) {
    ListaDinamica novaLista = new ListaDinamica();
    for (Lista a = primeiro; a != null; a = a.getProx()) {
        novaLista.add(a.getValor());
    }
    for (Lista a = outraLista.primeiro; a != null; a = a.getProx()) {
        novaLista.add(a.getValor());
    }
    return novaLista;
}

E então no seu método main:

ListaDinamica teste3 = teste.uniao(teste2);
teste3.imprimeLista();
8
  • Certo e onde eu invoco este método, e como passo os valores das listas adicionadas?
    – Natalia
    28/03/2015 às 17:31
  • @Natalia Resposta editada. 28/03/2015 às 17:39
  • Ele não permite atribuir teste.uniao, reporta como incompatibilidade, você teria um outro tipo de contato com o hangout ou algo do genêro? Preciso entender como percorrer estas duas listas simultaneamente para fazer algumas verificações, e tentar solucionar meu problema da união. Claro que se não tiver essa possibilidade eu irei entender.
    – Natalia
    28/03/2015 às 17:43
  • @Natalia O primeiro método uniao que dei é void. Ele modifica a lista teste ao invés de criar uma lista nova. O segundo método uniao que dei usa a abordagem de criar uma lista nova. As duas abordagens são mutuamente incompatíveis entre si e você provavelmente só vai querer escolher uma delas. A forma como você vai colocá-las no main depende da abordagem que você escolher. 28/03/2015 às 17:50
  • @Natalia Quanto a contato comigo, você pode pegar o meu e-mail na minha página de usuário (é só clicar no link com o meu nome e "scrollar" o quadro à direita até o fim). Mas aqui no StackOverflow há várias pessoas que podem te ajudar, sendo que eu sou apenas um. 28/03/2015 às 17:50

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .