給定一個雙向循環鍊錶和一個關鍵字，我們需要在鍊錶中搜尋關鍵字，並在找到時給出適當的訊息。假設我們有一個具有特定字元的鍊錶，並且我們需要在其中搜尋一個元素。所以讓我們從下面的鍊錶開始 -
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.
以下是在雙向鍊錶中執行搜尋操作的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;
}
Element present
關鍵字4存在於雙向鍊錶中。
在一個雙向循環鍊錶中，我們可以從任何位置開始，因為沒有固定的頭部和尾部。在上述方法中，我們有一個“頭部”，它是一個偽頭部，我們從這裡開始搜尋。上述演算法的時間複雜度是O(n)，因為是線性搜尋。
以上是在C++中搜尋雙向循環鍊錶中的元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！
