使用C++在鍊錶中搜尋元素

要在鍊錶中搜尋元素，我們必須迭代整個鍊錶，將每個節點與所需資料進行比較，並繼續搜尋直到獲得匹配。因為鍊錶不提供隨機訪問，所以我們必須從第一個節點開始搜尋。

我們得到一個整數鍊錶和一個整數鍵。我們需要尋找這個鍵是否存在於我們的鍊錶中。我們可以在鍊錶中做一個簡單的線性搜索，找到key。如果存在，我們可以返回“Yes”；否則，“否”

讓我們來看看一些輸入輸出場景 -

我們已經獲取了一個列表，我們需要在該列表中查找該元素是否存在於該列表中，並使用提供的鍵為 3 獲取相應的輸出 -

Input Data: [ 10, 4, 5, 4, 10, 1, 3, 5]
Output: Yes

讓我們考慮另一個場景，金鑰為 5 -

Input Data: [ 1, 4, 9, 4, 10, 1, 3, 6]
Output: No

演算法（步驟）

以下是執行所需任務所需遵循的演算法/步驟 -

• 將頭部設定為空。

• 為連結清單新增一些項目

• 取得使用者輸入的要搜尋的項目。

• 從頭到尾線性遍歷鍊錶，直到到達空節點。

• 檢查每個節點，看看資料值是否與要搜尋的項目相符。

• 傳回找到資料的節點的索引。如果沒有找到，則轉到下一個節點。

範例

例如，我們有一個鍊錶，如“52->4651->42->5->12587->874->8->null”，其鍵為 12587。實作該範例的 C 程式下面給出 -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   while(head) {
      if(head->val == key) {
         cout << "Yes";
         return;
      }
      head = head->next;
   }
   cout << "No";
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

輸出

Yes

範例

現在我們將使用遞歸方法來解決相同的問題 -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   if(head == NULL) {
      cout << "No";
   } else if(head->val == key) {
      cout << "Yes";
   } else {
      solve(head->next, key);
   }
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

輸出

Yes

結論

時間複雜度為O(n)。我們使用迭代方法來解決這個問題。用遞歸方法嘗試這個問題。

以上是使用C++在鍊錶中搜尋元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！