Cuente la ocurrencia del valor de búsqueda en una lista vinculada en C ++

En informática, contar las instancias de un cierto valor en una lista vinculada es una operación típica. Encontrar la frecuencia de un elemento en una lista se realiza con frecuencia para que pueda usarse para el análisis de datos, la búsqueda y la clasificación, entre otras cosas. En una lista vinculada, calcular el número de veces que aparece un valor a menudo significa atravesar la lista y determinar si el valor de cada nodo coincide con el valor de destino. Cada vez que se descubre un partido, el número de ocurrencias de recuentos aumenta entonces. Los algoritmos iterativos, recursivos y basados ​​en hash se pueden utilizar para llevar a cabo este procedimiento, cada uno con sus propios beneficios y inconvenientes.

En C ++, hay numerosas formas de determinar con qué frecuencia aparece un elemento en una lista vinculada que incluye lo siguiente:

Método iterativo: La técnica iterativa verifica el campo de datos de cada nodo a medida que atraviesa la lista vinculada para contar las repeticiones del valor deseado.

Método recursivo: La lista vinculada se itera mediante el uso de una función recursiva para contar las repeticiones del valor de destino.

Método de tabla hash: La frecuencia del valor objetivo se devuelve utilizando la técnica de tabla hash que almacena la frecuencia de cada elemento en la lista vinculada en una tabla hash.

Enfoque 1: Método iterativo

El método iterativo es un enfoque para resolver un problema en el que se repite una tarea hasta que se cumpla una determinada condición. Implica una secuencia de instrucciones que se ejecutan repetidamente, ya sea un número especificado de veces o hasta que se cumpla una condición específica. En este método, la solución se obtiene realizando una secuencia de cálculos, cada uno basándose en los resultados del cálculo anterior.

El método iterativo se puede utilizar para resolver una amplia gama de problemas, desde cálculos aritméticos simples hasta algoritmos complejos. A menudo se prefiere sobre el método recursivo porque es más sencillo, más fácil de entender y requiere menos gastos generales en términos de uso de la memoria.

// Complete el programa para la inserción en una lista vinculada en C++
#incluir
usando el espacio de nombres STD;
nodo de clase

público:
datos int;
Nodo *siguiente;
;
int CountOccurrences (nodo ** headNode, int item)
int count = 0;
Nodo *actual = *headNode;
mientras (actual != Nulo)
if (current-> data == item)
contar ++;

corriente = corriente-> Next;

recuento de retorno;

void insertAtBeginningLinkedList (nodo ** headNode, int data)
// crear dinámicamente memoria para este nuevonode
Nodo* newnode = new Node ();
newnode-> data = data;
newnode-> next = *headNode;
*headNode = newnode;
cout << newNode->datos << " inserted data successfully"
"En la lista vinculada" << endl;

void printLinkedList (nodo* nodo)
cout << "\n";
// mientras que la condición se detendrá cuando nodo == nulo
mientras (nodo!= Nulo)
cout << node->datos << " "; node = node->próximo;

cout << "\n" << endl;

int main ()

Nodo* headNode = null;
insertAtBeginningLinkedList (y HeadNode, 10);
insertAtBeginningLinkedList (y HeadNode, 9);
insertAtBeginningLinkedList (& HeadNode, 8);
insertAtBeginningLinkedList (y HeadNode, 12);
insertAtBeginninglinkedList (y HeadNode, 19);
insertAtBeginningLinkedList (& HeadNode, 8);
printLinkedList (nodo de cabeza);
int search_item = 8;
cout<<"The number of times "<cout<regresar 0;

Producción:

10 datos insertados con éxito en la lista vinculada
9 datos insertados con éxito en la lista vinculada
8 datos insertados con éxito en la lista vinculada
12 datos insertados con éxito en la lista vinculada
19 datos insertados con éxito en la lista vinculada
8 datos insertados con éxito en la lista vinculada
8 19 12 8 9 10
El número de veces 8 ocurre es 2

Explicación:

Un método iterativo para contar las ocurrencias de un elemento específico en una lista vinculada se implementa en el código anterior.

El primer paso es definir la clase "nodo" que tiene dos variables miembros: "datos" que se usan para contener el valor de cada nodo y "siguiente", que es una referencia al nodo después de él en la lista.

Un datos enteros y un doble puntero al nodo principal de la lista vinculada se pasan a la función InsertATBeginningLinkedList (). Usando el nuevo nodo (), la memoria de un nuevo nodo se crea dinámicamente y los datos se asignan al nuevo nodo. Más tarde, actualiza el nodo principal para que sea el nuevo nodo configurando el siguiente puntero del nuevo nodo en el nodo anterior anterior.

El puntero del nodo principal de la lista vinculada y el elemento para buscar son las dos entradas que se dan a la función CountOccurrences (). La función devuelve cuántas veces aparece el elemento en la lista vinculada. La función comienza configurando la variable de recuento en 0 y la referencia de la variable actual al nodo principal de la lista vinculada. Luego, el método comienza un bucle de tiempo, que se ejecuta siempre que la "corriente" no sea nula, una señal de que el final de la lista todavía está en alcance. La función determina si el campo de datos del nodo actual es igual al valor de objetivo para cada iteración del bucle (elemento). La variable de recuento aumenta. Si es así, el bucle continúa hasta que hayamos visitado cada nodo en la lista, momento en el que se modifica la "corriente" para apuntar al siguiente nodo. La función devuelve el valor final del recuento, que denota el número de veces que el elemento aparece en la lista, cuando el bucle se ha completado.

PrintLinkedList (): imprime los valores de todos los nodos en la lista vinculada. Se necesita un puntero al primer nodo en la lista como una entrada.

En la función Main (), se crea una lista vinculada vacía inicializando el nodo principal a NULL. La función luego usa la función InsertATBeginningLinkedList para insertar varios valores en la lista. Finalmente, la lista se imprime y el número de ocurrencias del número 8 se cuenta y se muestra utilizando las funciones de CountOccurrencias y PrintLinkedList.

Atravesamos la lista completa solo una vez. Por lo tanto, la complejidad temporal de nuestro método es o (n), donde n es el número de nodos en la lista.

Enfoque 2: Método recursivo

Un método recursivo es una función que se llama a sí mismo como una subrutina. La idea detrás de la recursión es romper un problema en subproblemas más pequeños hasta que sea lo suficientemente simple como para resolverlo directamente. La función recursiva luego combina las soluciones a los subproblemas para formar la solución al problema original. En la informática, la recursión se usa ampliamente en muchos algoritmos y estructuras de datos, como la clasificación y la búsqueda, para reducir la complejidad de resolver grandes problemas dividiéndolos en subproblemas más pequeños y más fáciles de resolver.

#incluir
usando el espacio de nombres STD;
nodo de clase

público:
datos int;
Nodo *siguiente;
;
int CountOccurrencesRecursive (nodo *headNode, int item)
if (headNode == null)
regresar 0;

int count = CountOccurrencesRecursive (HeadNode-> Next, item);
if (headNode-> data == item)
contar ++;

recuento de retorno;

int main ()
Nodo *headNode = nuevo nodo;
Nodo *SecondNode = nuevo nodo;
Nodo *tercero = nuevo nodo;
headNode-> data = 11;
HeadNode-> next = SecondNode;
SecondNode-> data = 12;
SecondNode-> next = ThirdNode;
ThirdNode-> data = 11;
ThirdNode-> next = null;
int Target = 11;
int count = CountOccurrencesRecursive (HeadNode, Target);
cout << "Count of " << target << " is: " << count << endl;
regresar 0;

Producción:

El recuento de 11 es: 2

Explicación:

1. La clase de nodo, que tiene los datos de los miembros y el siguiente, se usa para definir una lista vinculada.
2. Una referencia a la cabeza de la lista vinculada y el elemento para contar son las dos entradas del método CountocurrencesRecursive ().
3. Cuando la cabeza es igual a nula, el caso inicial de la recursión, que hace que devuelva 0, devuelve 0.
4. Recursivamente, la función se llama a sí misma utilizando el nodo consecutivo de la lista vinculada.
5. Si los datos del nodo actual coinciden con el objetivo después de la llamada recursiva, el recuento aumenta.
6. La función devuelve el recuento total.
7. El elemento de destino se establece en 11 y se construye una lista vinculada con tres nodos en la función principal.
8. Llamar a CountOccurrenceRecursive () con el cabezal de la lista vinculada y el elemento objetivo como parámetros produce el recuento del elemento de destino.

Enfoque 3: método de tabla hash

Una estructura de datos llamada tabla hash permite que las búsquedas de pares de clave de caso promedio se realicen en tiempo constante o (1). Funciona utilizando una clave para calcular un índice en una matriz de ranuras o cubos, desde el cual se puede encontrar el valor necesario. La tabla hash almacena los pares de valor clave, que luego se dividen de acuerdo con la función hash en una variedad de cubos.

La implementación de la tabla hash para C ++ es posible por el mapa desordenado de la biblioteca de plantillas estándar (STL). El almacenamiento y la recuperación del par de valores clave se pueden hacer con esto de manera rápida y efectiva. Con la siguiente sintaxis, se declara un_map undered_map:

#incluir
desordenable_map tabla de picadillo;

Donde "clave" denota el tipo de claves en una tabla hash, y "valor" denota el tipo de valores que se almacenan dentro. Usando el operador de soporte cuadrado [], el Mapered_MAP habilita la inserción, eliminación y búsqueda del par de valores de clave rápida y efectiva. Por ejemplo, puede hacer lo siguiente para agregar un par de valores clave a un solered_map:

hashtable [clave] = valor;

El cálculo del valor hash y la colocación del par de valores clave en el cubo apropiado son manejados automáticamente por undered_map.

#incluir
#incluir
usando el espacio de nombres STD;
nodo de clase

público:
datos int;
Nodo *siguiente;
;
int countOccurrenceshash (nodo *head, int Target)
std :: unordered_map frecuencia;
Nodo *actual = head;
mientras (actual != Nulo)
frecuencia [actual-> data] ++;
corriente = corriente-> Next;

frecuencia de retorno [objetivo];

int main ()
Nodo *headNode = nuevo nodo;
Nodo *SecondNode = nuevo nodo;
Nodo *tercero = nuevo nodo;
headNode-> data = 11;
HeadNode-> next = SecondNode;
SecondNode-> data = 12;
SecondNode-> next = ThirdNode;
ThirdNode-> data = 11;
ThirdNode-> next = null;
int Target = 11;
int count = CountOccurrenceshash (HeadNode, Target);
cout << "Count of " << target << " is: " << count << endl;
regresar 0;

Producción:

El recuento de 11 es: 2

Explicación:
El enfoque de tabla hash para contar las ocurrencias es implementado por la función CountOccurrenceshash (). Crea una frecuencia desordenada_map y establece su estado inicial en un mapa vacío. La función luego actualiza el recuento de cada valor de datos en el mapa de frecuencia mientras se itera a través de la lista vinculada. Luego se devuelve el recuento del valor objetivo en el mapa de frecuencia.

La función luego declara un puntero llamado "actual" y lo inicializa a la cabeza de la lista vinculada. Mientras la "corriente" no sea nula, se agrega un bucle de tiempo en la función. La función establece la "corriente" a la corriente y se avanza al siguiente nodo en la lista vinculada después de aumentar el recuento de datos de corriente en el mapa de frecuencia para cada iteración del bucle.

La función luego devuelve el recuento del valor de destino en el mapa de frecuencia, que es igual al número de veces que el valor de destino aparece en la lista vinculada, una vez que el bucle se ha completado.

La función principal crea tres objetos de nodo, cada uno que representa un nodo en la lista vinculada. El primer nodo se asigna con el valor 11, y su siguiente puntero se establece para apuntar al segundo nodo. Del mismo modo, el segundo nodo se asigna con el valor 12, y su siguiente puntero se establece para apuntar al tercer nodo. El tercer nodo se asigna con el valor 11 y su siguiente puntero se establece en NULL para indicar el final de la lista vinculada.

A continuación, el jefe de la lista vinculada y el valor de destino se pasan como parámetros al llamar al countocrenceshash () para recuperar el recuento del valor 11. La salida se imprime en la consola.

Conclusión

Iterativo, tabla hash y recursión son las tres formas más populares de contar las instancias de un valor particular en una lista vinculada en c++. En el enfoque iterativo, la lista vinculada se giran y se incrementa una variable de conteo cada vez que se descubre un nodo que contiene el valor deseado. La frecuencia de los elementos en la lista vinculada se almacenan como pares de valor clave utilizando la técnica de tabla hash que utiliza una estructura de datos de mapa desordenada. El método de tabla hash es apropiado para listas vinculadas más grandes y ofrece velocidades de búsqueda rápidas. El método de recursión incluye invocar una función en cada nodo en la lista vinculada repetidamente para dividir el problema en subproblemas más pequeños. Cuando se alcanza el final de la lista vinculada, se devuelve un recuento que se recopila en todas las llamadas a la función.