Conte a ocorrência do valor da pesquisa em uma lista vinculada em C ++

Na ciência da computação, contar as instâncias de um determinado valor em uma lista vinculada é uma operação típica. Encontrar a frequência de um elemento em uma lista é frequentemente feita para que ela possa ser usada para análise de dados, pesquisa e classificação, entre outras coisas. Em uma lista vinculada, calculando o número de vezes que um valor aparece geralmente significa atravessar a lista e determinar se o valor de cada nó corresponde ao valor alvo. Toda vez que uma partida é descoberta, o número de ocorrências de contagem é então aumentado. Algoritmos iterativos, recursivos e baseados em hash podem ser usados ​​para realizar este procedimento, cada um com seus próprios benefícios e desvantagens.

Em C ++, existem inúmeras maneiras de determinar com que frequência um elemento aparece em uma lista vinculada, incluindo o seguinte:

Método iterativo: A técnica iterativa verifica o campo de dados de cada nó, pois atravessa a lista vinculada para contar as repetições do valor desejado.

Método recursivo: A lista vinculada é iterada usando uma função recursiva para contar as repetições do valor alvo.

Método da tabela de hash: A frequência do valor alvo é retornada usando a técnica da tabela de hash que armazena a frequência de cada elemento na lista vinculada em uma tabela de hash.

Abordagem 1: Método iterativo

O método iterativo é uma abordagem para resolver um problema em que uma tarefa é repetida até que uma certa condição seja atendida. Envolve uma sequência de instruções que são executadas repetidamente, um número especificado de vezes ou até que uma condição específica seja satisfeita. Neste método, a solução é obtida realizando uma sequência de cálculos, cada um com base nos resultados do cálculo anterior.

O método iterativo pode ser usado para resolver uma ampla gama de problemas, desde cálculos aritméticos simples até algoritmos complexos. É frequentemente preferido sobre o método recursivo, porque é mais direto, mais fácil de entender e requer menos sobrecarga em termos de uso de memória.

// Programa completo para inserção em uma lista vinculada em C++
#incluir
usando namespace std;
Nó da classe

público:
int dados;
Nó *a seguir;
;
int contouccurrences (nó ** headNode, int item)
int conting = 0;
Nó *atual = *headNode;
while (atual != Null)
if (current-> data == item)
contagem ++;

Current = Current-> Next;

contagem de retorno;

void insertatbeginningLinkedList (nó ** headNode, int dados)
// Crie dinamicamente a memória para este newNode
Nó* newNode = new Node ();
newNode-> dados = dados;
newNode-> próximo = *headNode;
*headNode = newNode;
cout << newNode->dados << " inserted data successfully"
"Na lista vinculada" << endl;

void printlinkedlist (nó* nó)
cout << "\n";
// enquanto a condição vai parar quando nó == null
while (nó!= Null)
cout << node->dados << " "; node = node->próximo;

cout << "\n" << endl;

int main ()

Nó* headNode = null;
insertatbeginningLinkedList (& headnode, 10);
insertatbeginningLinkedList (& headnode, 9);
insertatbeginningLinkedList (& headnode, 8);
insertatbeginningLinkedList (& headnode, 12);
insertatbeginningLinkedList (& headnode, 19);
insertatbeginningLinkedList (& headnode, 8);
PrintLinkedList (HeadNode);
int search_item = 8;
cout<<"The number of times "<cout<retornar 0;

Saída:

10 dados inseridos com sucesso na lista vinculada
9 Dados inseridos com sucesso na lista vinculada
8 Dados inseridos com sucesso na lista vinculada
12 dados inseridos com sucesso na lista vinculada
19 Dados inseridos com sucesso na lista vinculada
8 Dados inseridos com sucesso na lista vinculada
8 19 12 8 9 10
O número de vezes 8 ocorre é 2

Explicação:

Um método iterativo para contar as ocorrências de um elemento específico em uma lista vinculada é implementada no código anterior.

A primeira etapa é definir a classe "nó", que possui duas variáveis ​​de membros: "dados" que são usados ​​para manter o valor de cada nó e "próximo", que é uma referência ao nó após a lista na lista.

Dados inteiros e um ponteiro duplo para o nó da lista da lista vinculado são passados ​​para a função insertatBeginningLinkedList (). Usando o novo node (), a memória de um novo nó é criada dinamicamente e os dados são atribuídos ao novo nó. Mais tarde, ele atualiza o nó da cabeça para que seja o novo nó, definindo o próximo ponteiro do novo nó para o nó da cabeça anterior.

O ponteiro do nó da cabeça da lista vinculada e o item a serem pesquisados ​​são as duas entradas que são dadas à função CountCurrences (). A função retorna quantas vezes o item aparece na lista vinculada. A função começa definindo a variável de contagem para 0 e a referência da variável atual ao nó da cabeça da lista vinculada. O método começa um loop de tempo, que funciona enquanto a "corrente" não for nula, um sinal de que o fim da lista ainda está ao alcance. A função determina se o campo de dados do nó atual é igual ao valor da meta para cada iteração do loop (item). A variável de contagem é aumentada. Se for, o loop continua até que visitemos todos os nó da lista, momento em que a “corrente” é modificada para apontar para o seguinte nó. A função retorna o valor final da contagem, que denota o número de vezes que o item aparece na lista, quando o loop foi concluído.

Printlinkedlist (): imprime os valores de todos os nós na lista vinculada. É preciso um ponteiro para o primeiro nó da lista como uma entrada.

Na função Main (), uma lista vinculada vazia é criada inicializando o nó da cabeça para nulo. A função usa então a função InsertatBeginningLinkedList para inserir vários valores na lista. Finalmente, a lista é impressa e o número de ocorrências do número 8 é contado e exibido usando as funções CountCurrences e PrintLinkedlist.

Nós atravessamos a lista completa apenas uma vez. Portanto, a complexidade temporal do nosso método é o (n), onde n é o número de nós na lista.

Abordagem 2: Método recursivo

Um método recursivo é uma função que se autodenomina como uma sub -rotina. A idéia por trás da recursão é quebrar um problema em subproblemas menores até que se torne simples o suficiente para ser resolvido diretamente. A função recursiva combina as soluções para os subproblemas para formar a solução para o problema original. Na ciência da computação, a recursão é amplamente usada em muitos algoritmos e estruturas de dados, como classificação e pesquisa, para reduzir a complexidade de resolver grandes problemas, dividindo-os em subproblemas menores e mais fáceis de solucionar.

#incluir
usando namespace std;
Nó da classe

público:
int dados;
Nó *a seguir;
;
int contouccurrencesrecursive (nó *h Headnode, int item)
if (headNode == null)
retornar 0;

int count = countCurrencesRecursive (HeadNode-> Next, item);
if (headNode-> dados == item)
contagem ++;

contagem de retorno;

int main ()
Nó *headNode = novo nó;
Nó *SecondNode = new Node;
Nó *terceironode = novo nó;
headNode-> dados = 11;
HeadNode-> Next = SecondNode;
SecondNode-> dados = 12;
SecondNode-> Next = ThirdNode;
terceiroNode-> dados = 11;
terceironode-> próximo = nulo;
int alvo = 11;
int count = countCurrencesRecursive (HeadNode, Target);
cout << "Count of " << target << " is: " << count << endl;
retornar 0;

Saída:

A contagem de 11 é: 2

Explicação:

1. A classe de nó, que possui os dados dos membros e, em seguida, é usada para definir uma lista vinculada.
2. Uma referência à cabeça da lista vinculada e ao elemento para contar são as duas entradas do método CountCurrencesRecursive ().
3. Quando a cabeça é igual a nulo, o caso inicial da recursão, que faz com que ele retorne 0, retorna 0.
4. Recursivamente, a função se chama usando o nó consecutivo da lista vinculada.
5. Se os dados do nó atual corresponderem ao alvo após a chamada recursiva, a contagem será aumentada.
6. A função retorna a contagem total.
7. O elemento de destino é definido como 11 e uma lista vinculada com três nós é construída na função principal.
8. Chamando o CountCurrencesRecursive () com a cabeça da lista vinculada e o elemento de destino como parâmetros produz a contagem do elemento de destino.

Abordagem 3: Método da tabela de hash

Uma estrutura de dados chamada tabela de hash permite que as pesquisas de par de valores-chave médios sejam executadas em tempo constante o (1). Ele funciona usando uma chave para calcular um índice em uma matriz de slots ou baldes, a partir da qual o valor necessário pode ser encontrado. A tabela de hash armazena os pares de valor-chave, que são divididos de acordo com a função de hash em vários baldes.

Uma implementação da tabela de hash para C ++ é possível pelo mapa não ordenado da Biblioteca de Modelos Padrão (STL). O par de pares de valores-chave e recuperação pode ser feito com isso de maneira rápida e eficaz. Com a seguinte sintaxe, é declarado um não -ordenado:

#incluir
UNODERED_MAP hashtable;

Onde “chave” indica o tipo de chaves em uma tabela de hash e “valor” denota o tipo de valores que são armazenados dentro. Usando o operador de suporte quadrado [], o UNODERED_MAP permite a inserção, exclusão e pesquisa rápidas e eficazes do valor-chave. Por exemplo, você pode fazer o seguinte para adicionar um par de valores-chave a um UNODERED_MAP:

hashtable [key] = value;

O cálculo do valor de hash e a colocação do par de valores-chave no balde apropriado são tratados automaticamente pelo UNODERED_MAP.

#incluir
#incluir
usando namespace std;
Nó da classe

público:
int dados;
Nó *a seguir;
;
int contouccurrenceshash (nó *cabeça, int alvo)
std :: UNODERED_MAP frequência;
Nó *atual = cabeça;
while (atual != Null)
Frequência [Current-> Data] ++;
Current = Current-> Next;

frequência de retorno [Target];

int main ()
Nó *headNode = novo nó;
Nó *SecondNode = new Node;
Nó *terceironode = novo nó;
headNode-> dados = 11;
HeadNode-> Next = SecondNode;
SecondNode-> dados = 12;
SecondNode-> Next = ThirdNode;
terceiroNode-> dados = 11;
terceironode-> próximo = nulo;
int alvo = 11;
int count = countCurrenceshash (HeadNode, Target);
cout << "Count of " << target << " is: " << count << endl;
retornar 0;

Saída:

A contagem de 11 é: 2

Explicação:
A abordagem da tabela de hash para contar as ocorrências é implementada pela função CountCurrenceshash (). Ele cria uma frequência não -ordered_map e define seu estado inicial para um mapa vazio. A função atualiza a contagem de cada valor de dados no mapa de frequência enquanto itera através da lista vinculada. A contagem do valor alvo no mapa de frequência é então retornada.

A função então declara um ponteiro chamado "atual" e a inicializa na cabeça da lista vinculada. Enquanto o "atual" não for nulo, um loop de tempo é adicionado à função. A função define o "atual" para a corrente-> próximo a avançar para o próximo nó na lista vinculada após aumentar a contagem de dados de corrente no mapa de frequência para cada iteração do loop.

A função retorna então a contagem do valor alvo no mapa de frequência, o que é igual ao número de vezes que o valor alvo aparece na lista vinculada, uma vez que o loop for concluído.

A função principal cria três objetos de nós, cada um representando um nó na lista vinculada. O primeiro nó é atribuído com o valor 11, e seu próximo ponteiro está definido para apontar para o segundo nó. Da mesma forma, o segundo nó é atribuído com o valor 12, e seu próximo ponteiro está definido para apontar para o terceiro nó. O terceiro nó é atribuído com o valor 11 e seu próximo ponteiro é definido como nulo para indicar o final da lista vinculada.

Em seguida, o chefe da lista vinculada e o valor alvo são passados ​​como parâmetros ao chamar o condeClurrenceshash () para recuperar a contagem do valor 11. A saída é então impressa no console.

Conclusão

Tabela iterativa, hash e recursão são as três maneiras mais populares de contar as instâncias de um valor específico em uma lista vinculada em c++. Na abordagem iterativa, a lista vinculada é emitida e uma variável de contagem é aumentada cada vez que um nó que contém o valor desejado é descoberto. A frequência dos elementos na lista vinculada é armazenada como pares de valor-chave usando a técnica da tabela de hash que utiliza uma estrutura de dados de mapa não ordenada. O método da tabela de hash é apropriado para listas maiores vinculadas e oferece velocidades rápidas de pesquisa. O método de recursão inclui invocar uma função em cada nó na lista vinculada repetidamente para dividir o problema em subproblemas menores. Quando a extremidade da lista vinculada é atingida, uma contagem que é coletada em todas as chamadas para a função é retornada.