首頁  >  文章  >  後端開發  >  使用C++在鍊錶中搜尋元素

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

WBOY
WBOY轉載
2023-09-10 15:01:02852瀏覽

使用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中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除