Suchen Sie nach Elementen in einer doppelt zirkulär verknüpften Liste in C++

Angesichts einer doppelt zirkulär verknüpften Liste und eines Schlüsselworts müssen wir die verknüpfte Liste nach dem Schlüsselwort durchsuchen und beim Finden eine entsprechende Meldung ausgeben. Angenommen, wir haben eine verknüpfte Liste mit einem bestimmten Zeichen und müssen darin nach einem Element suchen. Beginnen wir also mit der unten verlinkten Liste -

8 2 Wir verwenden 4 als Schlüssel, um die Lösung für das gegebene Problem zu finden. Doppelt verknüpfte Listen haben keinen festen Kopf, daher beginnen wir an einem beliebigen Knoten und markieren diesen Knoten als Kopf, bis wir erneut auf den Kopf stoßen, wo wir eine lineare Suche in der verknüpften Liste durchführen und nach dem Schlüsselwort suchen.

Angenommen, wir haben eine bidirektionale verknüpfte Liste mit 5 Knoten 5 gefunden Es ist 6.

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

Betrachten wir einen anderen Fall, in dem es in einer doppelt zirkulär verknüpften Liste kein zu durchsuchendes Element gibt.

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

Algorithmus

Hier sind die Schritte, um näher zu kommen.

Implementieren Sie eine verknüpfte Liste und übergeben Sie Werte, indem Sie jedem Knoten der verknüpften Liste Vorwärtsknoten zuweisen.
Weisen Sie den vorherigen Teil des Knotens dem nächsten Teil des letzten Knotens zu.
Weisen Sie jeden vorherigen Teil des Knotens dem nächsten Teil des Knotens zu.
Übergeben Sie das Schlüsselelement an das Schlüsselelement, das prüft, ob es in der doppelt zirkulär verknüpften Liste vorhanden ist.
Gibt „true“ zurück, wenn der Schlüssel in einer doppelt zirkulär verknüpften Liste vorhanden ist.
Andernfalls wird false zurückgegeben.

• Die chinesische Übersetzung von
Beispiel

Beispiel

Das Folgende ist der C++-Implementierungscode zum Durchführen einer Suchoperation in einer doppelt verknüpften Liste:

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

Ausgabe

Element present

Erklärung

Erklärung

Schlüsselwort 4 ist in der doppelt verknüpften Liste vorhanden.

Fazit

In einer doppelt zirkulär verknüpften Liste können wir an jeder Position beginnen, da es keinen festen Kopf und Ende gibt. In der obigen Methode haben wir einen „Kopf“, der ein Pseudokopf ist, und wir beginnen unsere Suche von hier aus. Die zeitliche Komplexität des obigen Algorithmus beträgt O(n), da es sich um eine lineare Suche handelt.

Das obige ist der detaillierte Inhalt vonSuchen Sie nach Elementen in einer doppelt zirkulär verknüpften Liste in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!