使用C++在链表中搜索元素

WBOY

发布时间：2023-09-10 15:01:02

1223人浏览过

来源于tutorialspoint

转载

使用c++在链表中搜索元素

要在链表中搜索元素，我们必须迭代整个链表，将每个节点与所需数据进行比较，并继续搜索直到获得匹配。因为链表不提供随机访问，所以我们必须从第一个节点开始搜索。

我们得到一个整数链表和一个整数键。我们需要查找这个键是否存在于我们的链表中。我们可以在链表中做一个简单的线性搜索，找到key。如果存在，我们可以返回“Yes”；否则，“否”

让我们看看一些输入输出场景 -

我们已经获取了一个列表，我们需要在该列表中查找该元素是否存在于该列表中，并使用提供的键为 3 获取相应的输出 -

立即学习“C++免费学习笔记（深入）”；

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

算法（步骤）

以下是执行所需任务所需遵循的算法/步骤 -

将头部设置为空。
向链接列表添加一些项目

Yes!SUN企业网站系统 3.5 Build 20100303
Yes!Sun基于PHP+MYSQL技术，体积小巧、应用灵活、功能强大，是一款为企业网站量身打造的WEB系统。其创新的设计理念，为企业网的开发设计及使用带来了全新的体验：支持前沿技术：动态缓存、伪静态、静态生成、友好URL、SEO设置等提升网站性能、用户体验、搜索引擎友好度的技术均为Yes!Sun所支持。易于二次开发：采用独创的平台化理念，按需定制项目中的各种元素，如：产品属性、产品相册、新闻列表

下载
获取用户输入的要搜索的项目。
从头到尾线性遍历链表，直到到达空节点。
检查每个节点，看看数据值是否与要搜索的项目匹配。
返回找到数据的节点的索引。如果没有找到，则转到下一个节点。

示例

例如，我们有一个链表，如“52->4651->42->5->12587->874->8->null”，其键为 12587。实现该示例的 C++ 程序下面给出 -

#include 
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 
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;
}