Rechercher des éléments dans une liste chaînée doublement circulaire en C++

Étant donné une liste chaînée doublement circulaire et un mot-clé, nous devons rechercher le mot-clé dans la liste chaînée et donner un message approprié une fois trouvé. Supposons que nous ayons une liste chaînée avec un caractère spécifique et que nous devions y rechercher un élément. Commençons donc par la liste ci-dessous -

5 8 Nous utiliserons 4 comme clé pour trouver la solution au problème donné. Les listes doublement chaînées n'ont pas de tête fixe, nous allons donc commencer à un nœud arbitraire et marquer ce nœud comme tête jusqu'à ce que nous rencontrions à nouveau la tête, où nous effectuons une recherche linéaire de la liste chaînée et recherchons le mot-clé.

Supposons que nous ayons une liste chaînée circulaire bidirectionnelle avec 5 nœuds 3 4 5 trouvé Il est 6 heures.

Input = <-> 3 <-> 4<-> 5<-> 6<-> 7<-> key=6
Output = Element found

Considérons un autre cas où il n'y a aucun élément à rechercher dans une liste chaînée doublement circulaire.

Input = <-> 10<->20<->30<->40<->50<-> key=100
Output = Element not found

Algorithme

Voici les étapes pour vous en rapprocher.

Implémentez une liste chaînée et transmettez des valeurs en attribuant des nœuds avant dans chaque nœud de la liste chaînée.
Attribuez la partie précédente du nœud à la partie suivante du dernier nœud.
Attribuez chaque partie précédente du nœud à la partie suivante du nœud.
Passez l'élément clé à l'élément clé qui vérifie s'il existe dans la liste chaînée doublement circulaire.
Renvoie vrai si la clé existe dans une liste chaînée doublement circulaire.
Sinon, il renvoie faux.

• La traduction chinoise de
Exemple

Exemple

Voici le code d'implémentation C++ pour effectuer une opération de recherche dans une liste doublement chaînée :

#include <iostream>
#include <vector>
using namespace std;
class Node {
   public:
   int val;
   Node *left, *right;
   Node(int val) {
      this->val = val;
   }
};
bool solve(Node* root, int key) {
   Node* copy = root;
   do {
      if(copy->val == key) return true;
      copy = copy->right;
   }while(copy!=root);
   return false;
}
int main() {
   // assigning the forward node in each node of the linked list
   Node* phead = new Node(5);
   phead->right = new Node(8);
   phead->right->right = new Node(9);
   phead->right->right->right = new Node(2);
   phead->right->right->right->right = new Node(4);
   phead->right->right->right->right->right = phead;
 
   // assignment of the previous node in each node in the linked list
 
   // assigning the previous of the head to the last element
   phead->left = phead->right->right->right->right;

   // assigning the left node in each node of the linked list
   phead->right->left = phead;
   phead->right->right->left = phead->right;
   phead->right->right->right->left = phead->right->right;
   phead->right->right->right->right->left = phead->right->right->right;
   if(solve(phead, 4)) cout << "Element present"; else cout << "Element not present";
   return 0;
}

Sortie

Element present

Explication

Explication

Le mot-clé 4 existe dans la liste doublement chaînée.

Conclusion

Dans une liste chaînée doublement circulaire, nous pouvons partir de n'importe quelle position car il n'y a pas de tête ni de queue fixes. Dans la méthode ci-dessus, nous avons une « tête », qui est une pseudo-tête, et nous commençons notre recherche à partir d’ici. La complexité temporelle de l'algorithme ci-dessus est O(n) car il s'agit d'une recherche linéaire.

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!