Cari elemen dalam senarai terpaut dua kali ganda dalam C++

Memandangkan senarai terpaut dua kali ganda dan kata kunci, kami perlu mencari senarai terpaut untuk kata kunci dan memberikan mesej yang sesuai apabila ditemui. Katakan kita mempunyai senarai terpaut dengan watak tertentu dan kita perlu mencari elemen di dalamnya. Jadi mari kita mulakan dengan senarai terpaut di bawah -

5 8 2

Kami akan menggunakan 4 sebagai kunci untuk mencari penyelesaian kepada masalah yang diberikan. Senarai terpaut berganda tidak mempunyai kepala tetap, jadi kami akan bermula pada nod sewenang-wenangnya dan menandakan nod itu sebagai kepala sehingga kami menemui kepala semula, di mana kami melakukan carian linear senarai terpaut dan mencari kata kunci.

Mari kita lihat beberapa senario input dan output -

Andaikan kita mempunyai senarai terpaut pekeliling dua hala dengan 5 nod 4 6 didapati Ia 6.

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

Mari kita pertimbangkan satu lagi kes di mana tiada unsur untuk dicari dalam senarai pautan dua bulatan.

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

Algoritma

Berikut adalah langkah-langkah untuk mendekati.

• Laksanakan senarai terpaut dan lulus nilai dengan menetapkan nod hadapan dalam setiap nod senarai terpaut.

• Tugaskan bahagian sebelumnya nod ke bahagian seterusnya nod terakhir.

• Tugaskan setiap bahagian nod sebelumnya ke bahagian nod seterusnya.

• Hantar elemen kunci kepada elemen utama yang menyemak sama ada ia wujud dalam senarai pautan dua bulatan.

• Kembalikan benar jika kunci wujud dalam senarai pautan dua bulatan.

• Jika tidak, ia kembali palsu.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut ialah kod pelaksanaan C++ untuk melaksanakan operasi carian dalam senarai berganda:

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

Output

Element present

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Kata kunci 4 wujud dalam senarai berganda.

Kesimpulan

Dalam senarai pautan dua bulatan, kita boleh bermula dari mana-mana kedudukan kerana tiada kepala dan ekor yang tetap. Dalam kaedah di atas, kami mempunyai "kepala", yang merupakan pseudo-kepala, dan kami memulakan carian kami dari sini. Kerumitan masa bagi algoritma di atas ialah O(n) kerana ia adalah carian linear.

Atas ialah kandungan terperinci Cari elemen dalam senarai terpaut dua kali ganda dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!