脚踢数据结构查找

• (꒪ꇴ꒪ )，Hello我是祐言QAQ
• 我的博客主页：C/C 语言，Linux基础，ARM开发板，软件配置等领域博主🌍
• 快上🚘，一起学习，让我们成为一个强大的攻城狮！
• 送给自己和读者的一句鸡汤🤔：集中起来的意志可以击穿顽石!
• 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏

        数据结构中的查找是指在一个数据集合（例如数组、列表、树等）中，根据给定的某个值或条件，寻找目标元素或符合条件的元素。查找操作旨在确定特定元素是否存在于数据集合中，并在存在时获取其位置或值。在算法和数据结构领域，查找是一项基础操作，它对于许多应用程序的性能和效率至关重要。不同类型的查找方法适用于不同的数据集合和操作需求，涵盖了顺序查找、二分查找、插值查找、树表查找、哈希表查找等。那么接下来我们就讲讲这些查找的实现吧。

一、顺序查找（线性查找）

1.概念

         顺序查找是一种基本查找方法，它一般为从头开始逐个遍历数据集合，直到找到目标元素或遍历完整个集合。

2.算法

        （1） 从数据集合的起始位置开始，逐个比较元素与目标元素；
        （2）如果找到目标元素，返回其位置（索引）；
        （3）如果遍历完整个数据集合仍未找到目标元素，返回查找失败。

3.实现

         此程序是一个完整的可执行程序，执行结果如上图所示，接下来的其他代码我将只给查找的核心代码，感兴趣的同学可以尝试自己完成其余的代码使之运行，或自行练习编写代码。

1.  
   #include <stdio.h>
2.  
    
3.  
   int linear_search(int arr[], int n, int target) {
4.  
   for (int i = 0; i < n; i ) {
5.  
   if (arr[i] == target) {
6.  
   return i; // 返回目标元素的索引
7.  
   }
8.  
   }
9.  
   return -1; // 目标元素未找到
10.  
    }
11.  
     
12.  
    // 遍历
13.  
    void display(int arr[], int n) {
14.  
    for (int i = 0; i < n; i ) {
15.  
    printf("%d ", arr[i]);
16.  
    }
17.  
    printf("\n");
18.  
    }
19.  
     
20.  
    int main() {
21.  
    int data[] = {2, 3, 5, 7, 9, 11};
22.  
    int n = sizeof(data) / sizeof(data[0]);
23.  
    display(data, 6);
24.  
    int target;
25.  
    printf("请输入要查找的元素。\n");
26.  
    scanf("%d",&target);
27.  
    int result = linear_search(data, n, target);
28.  
    if (result != -1) {
29.  
    printf("元素 %d 在索引 %d（下标）处找到。\n", target, result);
30.  
    } else {
31.  
    printf("未找到目标元素。\n");
32.  
    }
33.  
     
34.  
    return 0;
35.  
    }

二、二分查找（折半查找）

1.概念

        二分查找适用于有序数据集合，它通过重复将数据集划分为两半并比较目标元素与中间元素的大小，从而快速定位目标元素。

2.算法

        （1）在有序数据集合中，确定左右边界；
        （2）计算中间位置 mid = (left right) / 2；
        （3）比较目标元素与中间元素的大小关系；
        （4）如果目标元素等于中间元素，查找成功；
        （5）如果目标元素小于中间元素，继续在左半部分查找；
        （6）如果目标元素大于中间元素，继续在右半部分查找；
        （7）重复步骤2-3，直到找到目标元素或左边界大于右边界。

3.实现

1.  
   int binary_search(int arr[], int n, int target) {
2.  
   int left = 0, right = n - 1;
3.  
   while (left <= right) {
4.  
   int mid = left (right - left) / 2;
5.  
   if (arr[mid] == target) {
6.  
   return mid; // 返回目标元素的索引
7.  
   } else if (arr[mid] < target) {
8.  
   left = mid 1;
9.  
   } else {
10.  
    right = mid - 1;
11.  
    }
12.  
    }
13.  
    return -1; // 目标元素未找到
14.  
    }

三、 插值查找

1.概念

         插值查找是在有序数据集合中通过插值计算来估计目标元素的位置，从而加快查找速度。

2.算法

        （1）在有序数据集合中，确定左右边界；
        （2）计算插值位置 mid = left (target - arr[left]) * (right - left) / (arr[right] - arr[left])；
        （3）比较目标元素与插值位置处元素的大小关系；
        （4）如果目标元素等于插值位置处元素，查找成功；
        （5）如果目标元素小于插值位置处元素，继续在左半部分查找；
        （6） 如果目标元素大于插值位置处元素，继续在右半部分查找；
        （7）重复步骤2-3，直到找到目标元素或左边界大于右边界。

3.实现

        插值查找的实现与二分查找类似，但计算插值位置时使用了插值公式。

1.  
   int interpolation_search(int arr[], int n, int target) {
2.  
   int left = 0, right = n - 1;
3.  
   while (left <= right && target >= arr[left] && target <= arr[right]) {
4.  
   int pos = left ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);
5.  
   if (arr[pos] == target) {
6.  
   return pos; // 返回目标元素的索引
7.  
   } else if (arr[pos] < target) {
8.  
   left = pos 1;
9.  
   } else {
10.  
    right = pos - 1;
11.  
    }
12.  
    }
13.  
    return -1; // 目标元素未找到
14.  
    }

四、 树表查找（二叉树查找）

        树表查找方法包括各种基于树结构的查找，其中二叉树查找是最简单的一种。

1.概念

         二叉树查找是基于二叉搜索树的查找方法，利用树结构将元素组织起来以支持高效的查找操作。它是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。 

2.算法

        （1）从根节点开始，比较目标元素与当前节点的值；
        （2）如果目标元素等于当前节点的值，查找成功；
        （3）如果目标元素小于当前节点的值，继续在左子树中查找；
        （4）如果目标元素大于当前节点的值，继续在右子树中查找；
        （5）如果到达叶子节点仍未找到目标元素，查找失败。

3.实现

1.  
   #include <stdio.h>
2.  
   #include <stdlib.h>
3.  
    
4.  
   // 定义二叉树结点
5.  
   struct TreeNode {
6.  
   int value;
7.  
   struct TreeNode* left;
8.  
   struct TreeNode* right;
9.  
   };
10.  
     
11.  
    // 二叉树查找函数
12.  
    struct TreeNode* binary_tree_search(struct TreeNode* root, int target) {
13.  
    // 当根节点为空或者根节点的值等于目标值时，返回根节点
14.  
    if (root == NULL || root->value == target) {
15.  
    return root;
16.  
    }
17.  
     
18.  
    // 如果目标值小于根节点的值，则在左子树中查找
19.  
    if (target < root->value) {
20.  
    return binary_tree_search(root->left, target);
21.  
    }
22.  
    // 如果目标值大于根节点的值，则在右子树中查找
23.  
    return binary_tree_search(root->right, target);
24.  
    }
25.  
     
26.  
    int main() {
27.  
    // 构建二叉搜索树
28.  
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
29.  
    root->value = 5;
30.  
    root->left = NULL;
31.  
    root->right = NULL;
32.  
     
33.  
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
34.  
    root->left->value = 3;
35.  
    root->left->left = NULL;
36.  
    root->left->right = NULL;
37.  
     
38.  
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
39.  
    root->right->value = 8;
40.  
    root->right->left = NULL;
41.  
    root->right->right = NULL;
42.  
     
43.  
    // 要查找的目标值
44.  
    int target = 3;
45.  
     
46.  
    // 调用二叉树查找函数
47.  
    struct TreeNode* result_node = binary_tree_search(root, target);
48.  
    if (result_node) {
49.  
    printf("元素 %d 找到了。\n", target);
50.  
    } else {
51.  
    printf("未找到目标元素。\n");
52.  
    }
53.  
     
54.  
    // 释放动态分配的内存
55.  
    free(root->left);
56.  
    free(root->right);
57.  
    free(root);
58.  
     
59.  
    return 0;
60.  
    }

        更多C语言、Linux系统、ARM板实战和数据结构相关文章，关注专栏：

   手撕C语言

            玩转linux

                    脚踢数据结构

                            6818（ARM）开发板实战

📢写在最后

• 今天的分享就到这啦~
• 觉得博主写的还不错的烦劳 一键三连喔~
• 🎉感谢关注🎉

这篇好文章是转载于：学新通技术网