在C++中搜索双向循环链表中的元素

给定一个双向循环链表和一个关键字，我们需要在链表中搜索关键字，并在找到时给出适当的消息。假设我们有一个具有特定字符的链表，并且我们需要在其中搜索一个元素。所以让我们从下面的链表开始 -

5 8 9 2 4

我们将使用4作为寻找给定问题解决方案的关键。双向链表没有固定的头部，所以我们将从任意节点开始，然后将该节点标记为头部，直到我们再次遇到这个头部，我们对链表进行线性搜索，并搜索关键字。

让我们看一些输入输出的场景 -

立即学习“C++免费学习笔记（深入）”；

假设我们有一个双向循环链表，其中有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

算法

以下是接近的步骤。

• 实现一个链表，并通过在链表的每个节点中分配前向节点来传递值。

  

  DALL·E 2

  OpenAI基于GPT-3模型开发的AI绘图生成工具，可以根据自然语言的描述创建逼真的图像和艺术。

  下载

• 将节点的前一部分分配给最后一个节点的下一部分。

• 将节点的每个前一部分分配给节点的下一部分。

• 将关键元素传递给检查它是否存在于双向循环链表中的关键元素。

• 如果键存在于双向循环链表中，则返回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 << "Element present"; else cout << "Element not present";
   return 0;
}

Output

Element present

Explanation

解释

关键字4存在于双向链表中。

结论

在一个双向循环链表中，我们可以从任何位置开始，因为没有固定的头部和尾部。在上述方法中，我们有一个“头部”，它是一个伪头部，我们从这里开始搜索。上述算法的时间复杂度是O(n)，因为是线性搜索。