要在鍊錶中搜尋元素,我們必須迭代整個鍊錶,將每個節點與所需資料進行比較,並繼續搜尋直到獲得匹配。因為鍊錶不提供隨機訪問,所以我們必須從第一個節點開始搜尋。
我們得到一個整數鍊錶和一個整數鍵。我們需要尋找這個鍵是否存在於我們的鍊錶中。我們可以在鍊錶中做一個簡單的線性搜索,找到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中文網其他相關文章!