在C++中搜尋雙向循環鍊錶中的元素

給定一個雙向循環鍊錶和一個關鍵字，我們需要在鍊錶中搜尋關鍵字，並在找到時給出適當的訊息。假設我們有一個具有特定字元的鍊錶，並且我們需要在其中搜尋一個元素。所以讓我們從下面的鍊錶開始 -

5 8 9 2 4

我們將使用4作為尋找給定問題解決方案的關鍵。雙向鍊錶沒有固定的頭部，所以我們將從任意節點開始，然後將該節點標記為頭部，直到我們再次遇到這個頭部，我們對鍊錶進行線性搜索，並蒐索關鍵字。

讓我們來看一些輸入輸出的場景 -

假設我們有一個雙向循環鍊錶，其中有5個節點 3 4 5 6 7，要找的元素是6。

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

讓我們考慮另一種情況，即在雙向循環鍊錶中沒有要搜尋的元素。

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

演算法

以下是接近的步驟。

• 實作一個鍊錶，並透過在鍊錶的每個節點中分配前向節點來傳遞值。

• 將節點的前一部分指派給最後一個節點的下一部分。

• 將節點的每個前一部分分配給節點的下一部分。

• 將關鍵元素傳遞給檢查它是否存在於雙向循環鍊錶中的關鍵元素。

• 如果鍵存在於雙向循環鍊錶中，則傳回true。

• Else, it returns false.

#Example

的中文翻譯為：

範例

以下是在雙向鍊錶中執行搜尋操作的C 實作程式碼：

#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

Explanation

的中文翻譯為：

解釋

關鍵字4存在於雙向鍊錶中。

結論

在一個雙向循環鍊錶中，我們可以從任何位置開始，因為沒有固定的頭部和尾部。在上述方法中，我們有一個“頭部”，它是一個偽頭部，我們從這裡開始搜尋。上述演算法的時間複雜度是O(n)，因為是線性搜尋。

以上是在C++中搜尋雙向循環鍊錶中的元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！