给定一个双向循环链表和一个关键字，我们需要在链表中搜索关键字，并在找到时给出适当的消息。假设我们有一个具有特定字符的链表，并且我们需要在其中搜索一个元素。所以让我们从下面的链表开始 -
<-> 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
算法
以下是接近的步骤。
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存在于双向链表中。
结论
在一个双向循环链表中，我ߤ
.........................................................