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 -
1 2 |
|
Considérons un autre scénario avec la clé 5 -
1 2 |
|
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.
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 -
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
1 |
|
Nous allons maintenant utiliser la méthode récursive pour résoudre le même problème -
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
1 |
|
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!