Elemen carian dalam senarai terpaut menggunakan C++

Untuk mencari elemen dalam senarai terpaut, kami perlu mengulangi keseluruhan senarai terpaut, membandingkan setiap nod dengan data yang diperlukan dan teruskan mencari sehingga kami mendapat padanan. Oleh kerana senarai terpaut tidak menyediakan akses rawak, kita mesti mula mencari dari nod pertama.

Kami mendapat senarai terpaut integer dan kunci integer. Kami perlu mencari sama ada kunci ini wujud dalam senarai terpaut kami. Kita boleh melakukan carian linear mudah dalam senarai terpaut untuk mencari kunci. Jika ia wujud, kita boleh membalas "Ya"; jika tidak, "Tidak"

Mari kita lihat beberapa senario input dan output -

Kami telah mengambil senarai di mana kami perlu mencari jika elemen itu ada dalam senarai dan mendapatkan output yang sepadan menggunakan kunci 3 yang disediakan -

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

Mari kita pertimbangkan senario lain dengan kunci 5 -

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

Algoritma (langkah)

Berikut adalah algoritma/langkah yang perlu diikuti untuk melaksanakan tugas yang diperlukan -

• Tetapkan pengepala kepada kosong.

• Tambahkan beberapa item pada senarai terpaut

• Dapatkan item untuk carian yang dimasukkan oleh pengguna.

• Melintasi senarai terpaut dari awal hingga akhir sehingga mencapai nod kosong.

• Semak setiap nod untuk melihat sama ada nilai data sepadan dengan item yang anda cari.

• Mengembalikan indeks nod tempat data ditemui. Jika tidak ditemui, pergi ke nod seterusnya.

Contoh

Sebagai contoh, kami mempunyai senarai terpaut seperti "52->4651->42->5->12587->874->8->null" yang kuncinya ialah 12587. Program C++ yang melaksanakan contoh ini diberikan di bawah -

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

Output

Yes

Contoh

Kini kami akan menggunakan kaedah rekursif untuk menyelesaikan masalah yang sama -

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

Output

Yes

Kesimpulan

Kerumitan masa ialah O(n). Kami menggunakan pendekatan berulang untuk menyelesaikan masalah ini. Cuba masalah ini secara rekursif.

Atas ialah kandungan terperinci Elemen carian dalam senarai terpaut menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!