Compter l'occurrence de la valeur de recherche dans une liste liée en C ++

En informatique, compter les instances d'une certaine valeur dans une liste liée est une opération typique. Trouver la fréquence d'un élément dans une liste est fréquemment effectué afin qu'il puisse être utilisé pour l'analyse des données, la recherche et le tri, entre autres. Dans une liste liée, le calcul du nombre de fois où une valeur apparaît signifie souvent traverser la liste et déterminer si la valeur de chaque nœud correspond à la valeur cible. Chaque fois qu'une correspondance est découverte, le nombre d'occurrences de comptage est ensuite augmentée. Les algorithmes itératifs, récursifs et à base de hachage peuvent tous être utilisés pour effectuer cette procédure, chacune avec ses propres avantages et inconvénients.

En C ++, il existe de nombreuses façons de déterminer la fréquence à laquelle un élément apparaît dans une liste liée, y compris ce qui suit:

Méthode itérative: La technique itérative vérifie le champ de données de chaque nœud car il traverse la liste liée pour compter les répétitions de la valeur souhaitée.

Méthode récursive: La liste liée est itérée en utilisant une fonction récursive pour compter les répétitions de la valeur cible.

Méthode de table de hachage: La fréquence de la valeur cible est renvoyée à l'aide de la technique de la table de hachage qui stocke la fréquence de chaque élément dans la liste liée dans une table de hachage.

Approche 1: méthode itérative

La méthode itérative est une approche pour résoudre un problème où une tâche est répétée jusqu'à ce qu'une certaine condition soit remplie. Il implique une séquence d'instructions qui sont exécutées à plusieurs reprises, soit un nombre spécifié de fois ou jusqu'à ce qu'une condition spécifique soit satisfaite. Dans cette méthode, la solution est obtenue en effectuant une séquence de calculs, chacun s'appuyant sur les résultats du calcul précédent.

La méthode itérative peut être utilisée pour résoudre un large éventail de problèmes, des calculs arithmétiques simples aux algorithmes complexes. Il est souvent préféré à la méthode récursive car il est plus simple, plus facile à comprendre et nécessite moins de frais généraux en termes d'utilisation de la mémoire.

// Programme complet pour l'insertion dans une liste liée en C++
#inclure
Utilisation de Namespace Std;
nœud de classe

public:
données int;
Nœud * suivant;
;
int countoccurrences (node ​​** headnode, int item)
int count = 0;
Nœud * current = * headnode;
pendant que (actuel != Null)
if (current-> data == item)
Count ++;

Current = Current-> Suivant;

Return Count;

void insertAtBeginningLinkedList (Node ** headnode, int data)
// Créer dynamiquement de la mémoire pour ce newnode
Node * newNode = new node ();
newNode-> data = data;
newNode-> next = * headnode;
* headnode = newNode;
couter << newNode->données << " inserted data successfully"
"dans la liste liée" << endl;

void printLinkedList (nœud * nœud)
couter << "\n";
// tandis que la condition s'arrêtera quand nœud == null
while (nœud!= Null)
couter << node->données << " "; node = node->suivant;

couter << "\n" << endl;

int main()

Nœud * 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;
couter<<"The number of times "<couter<retour 0;

Sortir:

10 Données insérées Liste liée avec succès
9 Données insérées Liste liée avec succès
8 Données insérées Liste liée avec succès
12 Données insérées Liste liée avec succès
19 Données insérées Liste liée avec succès
8 Données insérées Liste liée avec succès
8 19 12 8 9 10
Le nombre de fois 8 se produit est 2

Explication:

Une méthode itérative pour compter les occurrences d'un élément spécifique dans une liste liée est implémentée dans le code précédent.

La première étape consiste à définir la classe «nœud» qui a deux variables de membre: «données» qui est utilisée pour maintenir la valeur de chaque nœud et «suivant» qui est une référence au nœud après elle dans la liste.

Une donnée entière et un double pointeur vers le nœud de tête de la liste liée sont transmis à la fonction insertatbeginningLinkedList (). En utilisant le nouveau nœud (), la mémoire d'un nouveau nœud est créée dynamiquement, et les données sont ensuite affectées au nouveau nœud. Plus tard, il met à jour le nœud de tête afin qu'il s'agisse du nouveau nœud en définissant le prochain pointeur du nouveau nœud vers le nœud de tête précédent.

Le pointeur du nœud de tête de la liste liée et l'élément à rechercher sont les deux entrées qui sont données à la fonction CountOccurrences (). La fonction renvoie combien de fois l'élément apparaît dans la liste liée. La fonction commence par définir la variable de nombre sur 0 et la référence de la variable actuelle au nœud de tête de la liste liée. La méthode commence alors une boucle. La fonction détermine si le champ de données du nœud actuel est égal à la valeur d'objectif pour chaque itération de la boucle (élément). La variable de comptage est augmentée. Si c'est le cas, la boucle continue alors jusqu'à ce que nous ayons visité tous les nœuds de la liste, date à laquelle le «courant» est modifié pour pointer vers le nœud suivant. La fonction renvoie la valeur finale du nombre, qui indique le nombre de fois que l'élément apparaît dans la liste, lorsque la boucle a terminé.

PrintLinkedList (): imprime les valeurs de tous les nœuds dans la liste liée. Il prend un pointeur vers le premier nœud de la liste comme entrée.

Dans la fonction Main (), une liste liée vide est créée en initialisant le nœud de tête vers null. La fonction utilise ensuite la fonction insertatbeginningLinkedList pour insérer plusieurs valeurs dans la liste. Enfin, la liste est imprimée et le nombre d'occurrences du numéro 8 est compté et affiché à l'aide des fonctions de comptes et de plateaux PrintLinkedList.

Nous traversons la liste complète une seule fois. Par conséquent, la complexité temporelle de notre méthode est O (n), où n est le nombre de nœuds dans la liste.

Approche 2: méthode récursive

Une méthode récursive est une fonction qui s'appelle comme un sous-programme. L'idée derrière la récursivité est de décomposer un problème en sous-problèmes plus petits jusqu'à ce qu'il devienne assez simple pour être résolu directement. La fonction récursive combine ensuite les solutions aux sous-problèmes pour former la solution au problème d'origine. En informatique, la récursivité est largement utilisée dans de nombreux algorithmes et structures de données, telles que le tri et la recherche, pour réduire la complexité de la résolution de gros problèmes en les divisant en sous-problèmes plus petits et plus faciles à résoudre.

#inclure
Utilisation de Namespace Std;
nœud de classe

public:
données int;
Nœud * suivant;
;
int countOccurrencesRecursive (node ​​* headnode, int item)
if (headnode == null)
retour 0;

int count = countOccurrencesRecursive (headnode-> Suivant, item);
if (headnode-> data == item)
Count ++;

Return Count;

int main()
Nœud * headnode = nouveau nœud;
Nœud * secondNode = nouveau nœud;
Node * tiers-Node = nouveau nœud;
headnode-> data = 11;
headnode-> next = secondNode;
secondNode-> data = 12;
secondNode-> next = tiersnode;
ThirdNode-> data = 11;
ThirdNode-> next = null;
int cible = 11;
int count = countOccurrencesRecursive (headnode, cible);
couter << "Count of " << target << " is: " << count << endl;
retour 0;

Sortir:

Le nombre de 11 est: 2

Explication:

1. La classe de nœuds, qui a les données des membres et ensuite, est utilisée pour définir une liste liée.
2. Une référence à la tête de la liste liée et l'élément à compter sont les deux entrées de la méthode CountOccurrencesRecursive ().
3. Lorsque la tête est nul, le cas initial de la récursivité, qui le fait revenir 0, renvoie 0.
4. Récursivement, la fonction s'appelle en utilisant le nœud consécutif de la liste liée.
5. Si les données du nœud actuel correspondent à la cible après l'appel récursif, le nombre est augmenté.
6. La fonction renvoie le nombre total.
7. L'élément cible est défini sur 11 et une liste liée à trois nœuds est construite dans la fonction principale.
8. Appeler le compte CountOccurrencesRecursive () avec la tête de la liste liée et l'élément cible en tant que paramètres donne le nombre de l'élément cible.

Approche 3: Méthode de la table de hachage

Une structure de données appelée un tableau de hachage permet de réaliser les recherches de paires de valeurs clés à case moyenne à temps constant o (1). Il fonctionne à l'aide d'une clé pour calculer un index dans un tableau de créneaux ou de seaux, à partir de laquelle la valeur nécessaire peut être trouvée. La table de hachage stocke les paires de valeurs clés, qui sont ensuite divisées en fonction de la fonction de hachage à travers une variété de seaux.

Une implémentation de table de hachage pour C ++ est rendue possible par la carte non ordonnée de la bibliothèque de modèle standard (STL). Le stockage et la récupération de la paire de valeurs clés peuvent être réalisés avec cela rapidement et efficacement. Avec la syntaxe suivante, un non ordonné_map est déclaré:

#inclure
non ordonné_map hashtable;

Où la «clé» désigne le type de clés dans une table de hachage, et la «valeur» indique le type de valeurs qui sont stockées dans. À l'aide de l'opérateur de carré de support [], le non ordonné_map permet l'insertion, la suppression et la recherche de la paire de valeurs clés rapide et efficace. Par exemple, vous pouvez effectuer ce qui suit pour ajouter une paire de valeurs clés à un non ordonné_map:

hashtable [key] = valeur;

Le calcul de la valeur de hachage et le placement de la paire de valeurs clés dans le seau approprié sont tous deux gérés automatiquement par le non ordonné_map.

#inclure
#inclure
Utilisation de Namespace Std;
nœud de classe

public:
données int;
Nœud * suivant;
;
int countoccurrenshash (nœud * tête, cible int)
std :: non ordonné_map fréquence;
Nœud * courant = tête;
pendant que (actuel != Null)
fréquence [actuel-> données] ++;
Current = Current-> Suivant;

Fréquence de retour [cible];

int main()
Nœud * headnode = nouveau nœud;
Nœud * secondNode = nouveau nœud;
Node * tiers-Node = nouveau nœud;
headnode-> data = 11;
headnode-> next = secondNode;
secondNode-> data = 12;
secondNode-> next = tiersnode;
ThirdNode-> data = 11;
ThirdNode-> next = null;
int cible = 11;
int count = countoccurrenshash (headnode, cible);
couter << "Count of " << target << " is: " << count << endl;
retour 0;

Sortir:

Le nombre de 11 est: 2

Explication:
L'approche de la table de hachage pour compter les occurrences est mise en œuvre par la fonction CountOccurrenShash (). Il crée une fréquence non ordonnée_map et définit son état initial sur une carte vide. La fonction met ensuite à jour le nombre de chaque valeur de données dans la carte de fréquence tout en itérant via la liste liée. Le nombre de la valeur cible dans la carte de fréquence est ensuite retourné.

La fonction déclare alors un pointeur appelé «courant» et l'initialise à la tête de la liste liée. Tant que le «courant» n'est pas nul, une boucle de temps est ajoutée dans la fonction. La fonction définit le «courant» sur actuel-> Suivant pour passer au nœud suivant dans la liste liée après avoir augmenté le nombre de données actuelles dans la carte de fréquence pour chaque itération de la boucle.

La fonction renvoie ensuite le nombre de la valeur cible dans la carte de fréquence, ce qui est égal au nombre de fois où la valeur cible apparaît dans la liste liée, une fois que la boucle while a terminée.

La fonction principale crée trois objets de nœud, chacun représentant un nœud dans la liste liée. Le premier nœud est attribué avec la valeur 11, et son prochain pointeur est défini sur le deuxième nœud. De même, le deuxième nœud est attribué avec la valeur 12, et son prochain pointeur est défini sur le troisième nœud. Le troisième nœud est attribué avec la valeur 11 et son prochain pointeur est défini sur NULL pour indiquer la fin de la liste liée.

Ensuite, la tête de la liste liée et la valeur cible sont passées sous forme de paramètres lors de l'appel du CountOccurrenShash () pour récupérer le nombre de la valeur 11. La sortie est ensuite imprimée à la console.

Conclusion

Itérative, table de hachage et récursivité sont les trois façons les plus populaires de compter les instances d'une valeur particulière dans une liste liée en C++. Dans l'approche itérative, la liste liée est en boucle et une variable de nombre est augmentée à chaque fois qu'un nœud qui contient la valeur souhaitée est découverte. La fréquence des éléments de la liste liée est stockée sous forme de paires de valeurs clés en utilisant la technique de la table de hachage qui utilise une structure de données de carte non ordonnée. La méthode de la table de hachage est appropriée pour les listes liées plus grandes et offre des vitesses de recherche rapides. La méthode de récursivité comprend invoquer une fonction sur chaque nœud de la liste liée à plusieurs reprises pour diviser le problème en sous-problèmes plus petits. Lorsque la fin de la liste liée est atteinte, un décompte qui est collecté sur tous les appels à la fonction est retourné.