使用 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。

  • 否则，返回 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)，因为它是一种线性搜索。

更新于：2022年8月10日

229 次查看

启动你的职业生涯

完成课程获得认证

开始学习
广告