Rechercher un élément dans une liste chaînée en utilisant C++

Pour rechercher un élément dans une liste chaînée, nous devons parcourir toute la liste chaînée, comparer chaque nœud avec les données requises et continuer la recherche jusqu'à ce que nous obtenions une correspondance. Étant donné que les listes chaînées ne fournissent pas d'accès aléatoire, nous devons commencer la recherche à partir du premier nœud.

Nous obtenons une liste chaînée d'entiers et une clé entière. Nous devons savoir si cette clé existe dans notre liste chaînée. Nous pouvons faire une simple recherche linéaire dans la liste chaînée pour trouver la clé. S'il existe, on peut renvoyer « Oui » sinon, « Non »

;

Examinons quelques scénarios d'entrée et de sortie -

Nous avons récupéré une liste dans laquelle nous devons trouver si l'élément est présent dans la liste et obtenir le résultat correspondant en utilisant la clé fournie de 3 -

Input Data: [ 10, 4, 5, 4, 10, 1, 3, 5]
Output: Yes

Considérons un autre scénario avec la clé 5 -

Input Data: [ 1, 4, 9, 4, 10, 1, 3, 6]
Output: No

Algorithme (étapes)

Voici les algorithmes/étapes à suivre pour effectuer la tâche requise -

• Définissez l'en-tête sur vide.

• Ajoutez quelques éléments à la liste chaînée

• Récupérez les éléments saisis par l'utilisateur à rechercher.

• Parcourez linéairement la liste chaînée du début à la fin jusqu'à atteindre un nœud vide.

• Vérifiez chaque nœud pour voir si la valeur des données correspond à l'élément que vous recherchez.

• Renvoie l'index du nœud où les données ont été trouvées. S'il n'est pas trouvé, passez au nœud suivant.

Exemple

Par exemple, nous avons une liste chaînée telle que "52->4651->42->5->12587->874->8->null" dont la clé est 12587. Le programme C++ qui implémente cet exemple est donné ci-dessous -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   while(head) {
      if(head->val == key) {
         cout << "Yes";
         return;
      }
      head = head->next;
   }
   cout << "No";
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

Sortie

Yes

Exemple

Nous allons maintenant utiliser la méthode récursive pour résoudre le même problème -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   if(head == NULL) {
      cout << "No";
   } else if(head->val == key) {
      cout << "Yes";
   } else {
      solve(head->next, key);
   }
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

Sortie

Yes

Conclusion

La complexité temporelle est O(n). Nous utilisons une approche itérative pour résoudre ce problème. Essayez ce problème de manière récursive.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!