5

Estou fazendo um projeto em Java de estruturas de dados e tenho uma lista simplesmente encadeada que recebe o código, nome, sexo e curso de cada pessoa. Eu preciso somente validar qual o código (tipo inteiro) que repete mais vezes e mostrar o último valor da lista com esse código. Em caso de empate na quantidade de repetições, eu mostro o último que foi inserido com esse código. A lógica é SIMPLES, mas não estou conseguindo desenvolvê-la nesse tipo (listas).

Esse é o meu código, lembrando que aux e comp são os nós. O tamanho() é um método que retorna a quantidade de pessoas da lista, e o método mostra_noh é pra mostrar o valor que eu quero.

public void consultar_repeticao()
{

    Noh aux = null;
    Noh comp = null;
    int p = 0;
    int q = 0;
    int cont = 0;

    for (aux = this.primeiro, p = 1;
         aux != null && p <tamanho();
         aux = aux.getProximo(), p++) {

        for (comp = this.primeiro.getProximo(), q = 2;
             comp != null &&  q <=tamanho();
             comp = comp.getProximo(), q++) {

            if(aux.getCodigo()==comp.getCodigo()){
                cont++;
            }

         };
    };
    aux.mostra_noh(q);
}

1 Resposta 1

3

Seu problema é que você tem uma única variável (cont) que é incrementada toda vez que dois códigos forem iguais. Toda vez que quaisquer códigos forem iguais. Se o código a repetir 10 vezes e o b repetir 2 vezes, cont será 12. Isso não te diz nada sobre qual deles se repete mais, nem qual nó possui esse código repetido.

Para resolver isso, sugiro guardar em outra estrutura de dados uma lista com os seguintes valores:

  • código repetido
  • quantas vezes se repete
  • qual o último nó que possui esse código

Sendo que essa estrutura pode começar vazia - ou com todos os códigos da lista, repetidos zero vezes, com último nó null (fica a seu critério). Esclarecendo: esses valores devem existir para cada código. A estrutura de dados é você que decide, mas como está estudando listas encadeadas, sugiro usar uma outra lista encadeada para guardar esses valores (e duplicar seu sofrimento rsrs).

Vou dar um exemplo usando arrays:

class Repeticao {
    int codigo;
    int quantasVezes = 0;
    int ultimoNoh = -1;
}

Repeticao[] repeticoes = new Repeticao[max_nos];
// Popular o array com objetos Repeticao, um para cada código

void incrementarRepeticao(int codigo, int ultimoNoh) {
    for ( int i = 0 ; i < repeticoes.length ; i++ )
        if ( repeticoes[i].codigo == codigo ) {
            repeticoes[i].quantasVezes++;
            if ( ultimoNoh > repeticoes[i].ultimoNoh )
                repeticoes[i].ultimoNoh = ultimoNoh;
        }
}

int maiorRepeticao() {
    Repeticoes maior = repeticoes[0];
    for ( int i = 1 ; i < repeticoes.length ; i++ )
        if ( repeticoes[i].quantasVezes > maior.quantasVezes )
            maior = repeticoes[i];
    return maior.ultimoNoh;
}

Além disso, há outros problemas no seu código que podem estar dificultando a chegada numa resposta:

for (aux = this.primeiro, p = 1;
        aux != null && p <tamanho();

O que acontece se só tiver 1 elemento na sua lista? Ele nem vai entrar no loop... Acho que é isso mesmo que você quer (pois se só tiver um elemento, não precisa comparar ele com ninguém), mas é bom lembrar que outras variáveis - como q - não terão sido inicializadas nesse caso (i.e. ainda terão o valor inicial de 0).

    for (comp = this.primeiro.getProximo(), q = 2;
        comp != null &&  q <=tamanho();

O problema aqui é que ele sempre vai começar do segundo elemento pra frente - mesmo se aux for o próprio segundo! O ideal é começar do próximo elemento da lista - aquele que está na frente do aux

// Sugestão: modificar o código acima para:
    for (comp = aux.getProximo(), q = p + 1;
        comp != null &&  q <=tamanho();

Ou seja, o elemento 1 vai se comparar com o 2, 3, 4... o elemento 2 vai se comparar com o 3, 4... e assim por diante, até o último elemento - que não vai se comparar com ninguém.

aux.mostra_noh(q);

Aqui, o que você quer mostrar não é o q (pois esse sempre será 0 ou tamanho()), mas sim o último elemento com mais repetições. Se nesse trecho de código você atualizar a estrutura de dados sugerida no início da resposta:

        if(aux.getCodigo()==comp.getCodigo()){
            //cont++;

            // Procura `aux.getCodigo()` na estrutura de dados
            // Incrementa o número de repetições
            // Atribui o último nó, que nesse caso é `comp` (o de maior índice)
            incrementarRepeticao(aux.getCodigo(), q);
        }

Então no final você tem que percorrer essa estrutura para obter o maior valor, e imprimir o nó correspondente (ou ordenar a lista em ordem decrescente e pegar o primeiro valor, a seu critério).

aux.mostra_noh(maiorRepeticao());
5
  • Ainda não entendi como vou fazer pra mostrar o nó correspondente. Ele vai ser o comp? Mas como vou mostrá-lo, e esse número de repetições... como deve ser incrementado? Pode me ajudar com isso ainda, por favor? 18/04/2014 às 16:10
  • if(cont>=maior){ maior = cont; teste = q; } }; cont = 0; }; aux.mostra_noh(teste); Eu estou fazendo isso, mas como você disse só me retorna o último elemento de todos. Eu quero só o último que mais repetiu e não consigo colocar isso no meu código... 18/04/2014 às 17:25
  • @yeahifoundit Atualizei a resposta. O número de repetições, já tinha falado como fazer, coloquei mais ênfase agora (se ainda tiver dúvida, favor explicar melhor o que não ficou claro). Seu método de achar o maior está quase ok, só que o cont não deve ser resetado pra zero - e sim mantido como está (para cada nó). Dei também um exemplo do que precisa ser feito usando arrays, de fato não dá pra usar uma única variável (tipo o comp ou o cont) porque você precisa dos valores distintos pra cada código distinto - e isso exige a criação de uma outra lista (ou talvez um Map).
    – mgibsonbr
    18/04/2014 às 20:18
  • @yeahifoundit Não sei se me expliquei direito, se ainda tiver dúvidas pode perguntar. Não está claro pra mim se o que está te trazendo dificuldades é: 1) a lógica do algoritmo; ou 2) como expressar essa lógica em código.
    – mgibsonbr
    18/04/2014 às 20:19
  • Consegui entender sim!! Muito obrigada mesmo!! 18/04/2014 às 20:57

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 .