Knowing the highest repetition code in a data structure (list)

Question

Knowing the highest repetition code in a data structure (list)

Navigation

#1 by (3 votes)

5

I'm doing a Java Data Structures project and I have a list that is simply chained that receives the code, name, sex, and course of each person. I need only validate which code (integer type) that repeats more often and show the last value of the list with that code. In case of a tie in the number of repetitions, I show the last one that was inserted with this code. The logic is SIMPLE, but I'm not able to develop it in this type (lists).

This is my code, remembering that aux and comp are the nodes. The tamanho() is a method that returns the number of people in the list, and the mostra_noh method is to show the value I want.

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);
}

java lista-encadeada

asked by anonymous 18.04.2014 / 05:43

1 answer

Join a number of people without repeating the combination with the maximum stipulated Creating an array with variables with different correlations in R?

score 3 · Accepted Answer

Your problem is that you have a single variable ( cont ) that is incremented every time two codes are the same. Whenever any codes are the same. If code a repeats% with% times and 10 repeats% with% times, b will 2 . This does not tell you anything about which one repeats more, nor which node has this code repeated.

To solve this, I suggest storing a list with the following values in another data structure:

repeated code
how many times is repeated
the last node that has this code

Since this structure can start empty - or with all the codes in the list, repeated zero times, with the last node cont (it is at your discretion). Clarifying: These values must exist for each code . The data structure is for you to decide, but as you are studying threaded lists, I suggest using another threaded list to store those values (and duplicate your suffering rsrs).

I'll give you an example using 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;
}

Additionally, there are other issues in your code that may be making it difficult to get a response:

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

What happens if I only have 12 element on your list? It will not even enter the loop ... I think this is what you want (because if you only have one element, you do not have to compare it to anyone else), but remember that other variables - such as null - will not have been initialized in this case (ie they will still have the initial value of 1 ).

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

The problem here is that it will always start from the second element forward - even if q is the second! The ideal is to start from the next element of the list - the one that is in front of 0

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

That is, the aux element will compare with aux , 1 , 2 ... element 3 will compare with 4 , 2 ... and so on, down to the last element - which will compare with no one.

aux.mostra_noh(q);

Here, what you want to show is not 3 (since this will always be 4 or q ), but rather the last element with more repetitions. If in this code snippet you update the suggested data structure at the beginning of the response:

        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);
        }

Then in the end you have to go through this structure to get the highest value, and print the corresponding node (or sort the list in descending order and get the first value, at your discretion).

aux.mostra_noh(maiorRepeticao());