Suchelement in einer verknüpften Liste mit C++

Um nach einem Element in einer verknüpften Liste zu suchen, müssen wir die gesamte verknüpfte Liste durchlaufen, jeden Knoten mit den erforderlichen Daten vergleichen und weiter suchen, bis wir eine Übereinstimmung erhalten. Da verknüpfte Listen keinen Direktzugriff ermöglichen, müssen wir mit der Suche beim ersten Knoten beginnen.

Wir erhalten eine verknüpfte Liste von Ganzzahlen und einen Ganzzahlschlüssel. Wir müssen herausfinden, ob dieser Schlüssel in unserer verknüpften Liste vorhanden ist. Wir können eine einfache lineare Suche in der verknüpften Liste durchführen, um den Schlüssel zu finden. Wenn es existiert, können wir „Ja“ zurückgeben, andernfalls „Nein“

Schauen wir uns einige Eingabe- und Ausgabeszenarien an -

Wir haben eine Liste abgerufen, in der wir herausfinden müssen, ob das Element in der Liste vorhanden ist, und die entsprechende Ausgabe mit dem bereitgestellten Schlüssel 3 erhalten müssen -

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

Betrachten wir ein anderes Szenario mit Schlüssel 5 -

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

Algorithmus (Schritte)

Hier sind die Algorithmen/Schritte, die befolgt werden müssen, um die erforderliche Aufgabe auszuführen -

• Setzen Sie die Kopfzeile auf leer.

• Fügen Sie einige Elemente zur verknüpften Liste hinzu

• Rufen Sie die vom Benutzer eingegebenen Elemente zur Suche ab.

• Durchlaufen Sie die verknüpfte Liste linear vom Anfang bis zum Ende, bis Sie einen leeren Knoten erreichen.

• Überprüfen Sie jeden Knoten, um zu sehen, ob der Datenwert mit dem gesuchten Element übereinstimmt.

• Gibt den Index des Knotens zurück, auf dem die Daten gefunden wurden. Wenn nicht gefunden, gehen Sie zum nächsten Knoten.

Beispiel

Zum Beispiel haben wir eine verknüpfte Liste wie „52->4651->42->5->12587->874->8->null“, deren Schlüssel 12587 ist. Das C++-Programm, das dieses Beispiel implementiert, ist unten angegeben -

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

Ausgabe

Yes

Beispiel

Jetzt werden wir die rekursive Methode verwenden, um dasselbe Problem zu lösen -

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

Ausgabe

Yes

Fazit

Die Zeitkomplexität ist O(n). Zur Lösung dieses Problems verwenden wir einen iterativen Ansatz. Versuchen Sie dieses Problem rekursiv.

Das obige ist der detaillierte Inhalt vonSuchelement in einer verknüpften Liste mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!