Maison > développement back-end > C++ > Rechercher un élément dans une liste chaînée en utilisant C++

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

WBOY
Libérer: 2023-09-10 15:01:02
avant
883 Les gens l'ont consulté

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 -

1

2

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

Output: Yes

Copier après la connexion

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

1

2

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

Output: No

Copier après la connexion

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 -

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

#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;

}

Copier après la connexion

Sortie

1

Yes

Copier après la connexion
Copier après la connexion

Exemple

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

#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;

}

Copier après la connexion

Sortie

1

Yes

Copier après la connexion
Copier après la connexion

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!

source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal