使用 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 次檢視

啟動你的職業生涯

完成課程獲得認證

開始學習
廣告