使用 C++ 在連結串列中搜索元素

要在連結串列中搜索一個元素，我們必須遍歷整個列表，將每個節點與所需資料進行比較，並持續搜尋直到找到匹配項。由於連結串列不提供隨機訪問，因此我們必須從第一個節點開始搜尋。

給定一個整數連結串列和一個整數鍵。我們需要找到這個鍵是否存在於我們的連結串列中。我們可以在連結串列中進行簡單的線性搜尋並找到鍵。如果存在，則返回“是”；否則，返回“否”。

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

我們建立了一個列表，我們需要找到元素是否在該列表中，並根據提供的鍵（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

演算法（步驟）

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

• 將頭部設定為 null。

• 向連結串列中新增一些項

• 獲取使用者要搜尋的專案的輸入。

• 從頭到尾線性遍歷連結串列，直到到達 null 節點。

• 檢查每個節點以檢視資料值是否與要搜尋的專案匹配。

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

示例

例如，讓我們有一個這樣的連結串列：“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)。我們使用了迭代方法來解決這個問題。嘗試使用遞迴方法解決此問題。

Prateek Jangid

更新於: 2022年8月10日

5K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始