给定一个双向循环链表和一个关键字，我们需要在链表中搜索关键字，并在找到时给出适当的消息。假设我们有一个具有特定字符的链表，并且我们需要在其中搜索一个元素。所以让我们从下面的链表开始 –
5 8 9 2 4
我们将使用4作为寻找给定问题解决方案的关键。双向链表没有固定的头部，所以我们将从任意节点开始，然后将该节点标记为头部，直到我们再次遇到这个头部，我们对链表进行线性搜索，并搜索关键字。
让我们看一些输入输出的场景 –
立即学习“C++免费学习笔记（深入）”；
假设我们有一个双向循环链表，其中有5个节点 3 4 5 6 7，要查找的元素是6。
Input = 3 4 5 6 7 key=6Output = Element found
登录后复制
让我们考虑另一种情况，即在双向循环链表中没有要搜索的元素。
Input = 1020304050 key=100Output = Element not found
登录后复制
算法
以下是接近的步骤。
实现一个链表，并通过在链表的每个节点中分配前向节点来传递值。
将节点的前一部分分配给最后一个节点的下一部分。
将节点的每个前一部分分配给节点的下一部分。
将关键元素传递给检查它是否存在于双向循环链表中的关键元素。
如果键存在于双向循环链表中，则返回true。
Else, it returns false.
Example
的中文翻译为：
示例
以下是在双向链表中执行搜索操作的C++实现代码：
#include #include 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 Output
Element present
登录后复制
Explanation
的中文翻译为：
解释
关键字4存在于双向链表中。
结论
在一个双向循环链表中，我们可以从任何位置开始，因为没有固定的头部和尾部。在上述方法中，我们有一个“头部”，它是一个伪头部，我们从这里开始搜索。上述算法的时间复杂度是O(n)，因为是线性搜索。
以上就是在C++中搜索双向循环链表中的元素的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2584897.html
