脚踢数据结构查找
- (꒪ꇴ꒪ ),Hello我是祐言QAQ
- 我的博客主页:C/C 语言,Linux基础,ARM开发板,软件配置等领域博主🌍
- 快上🚘,一起学习,让我们成为一个强大的攻城狮!
- 送给自己和读者的一句鸡汤🤔:集中起来的意志可以击穿顽石!
- 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏
数据结构中的查找是指在一个数据集合(例如数组、列表、树等)中,根据给定的某个值或条件,寻找目标元素或符合条件的元素。查找操作旨在确定特定元素是否存在于数据集合中,并在存在时获取其位置或值。在算法和数据结构领域,查找是一项基础操作,它对于许多应用程序的性能和效率至关重要。不同类型的查找方法适用于不同的数据集合和操作需求,涵盖了顺序查找、二分查找、插值查找、树表查找、哈希表查找等。那么接下来我们就讲讲这些查找的实现吧。
一、顺序查找(线性查找)
1.概念
顺序查找是一种基本查找方法,它一般为从头开始逐个遍历数据集合,直到找到目标元素或遍历完整个集合。
2.算法
(1) 从数据集合的起始位置开始,逐个比较元素与目标元素;
(2)如果找到目标元素,返回其位置(索引);
(3)如果遍历完整个数据集合仍未找到目标元素,返回查找失败。
3.实现
此程序是一个完整的可执行程序,执行结果如上图所示,接下来的其他代码我将只给查找的核心代码,感兴趣的同学可以尝试自己完成其余的代码使之运行,或自行练习编写代码。
-
#include <stdio.h>
-
-
int linear_search(int arr[], int n, int target) {
-
for (int i = 0; i < n; i ) {
-
if (arr[i] == target) {
-
return i; // 返回目标元素的索引
-
}
-
}
-
return -1; // 目标元素未找到
-
}
-
-
// 遍历
-
void display(int arr[], int n) {
-
for (int i = 0; i < n; i ) {
-
printf("%d ", arr[i]);
-
}
-
printf("\n");
-
}
-
-
int main() {
-
int data[] = {2, 3, 5, 7, 9, 11};
-
int n = sizeof(data) / sizeof(data[0]);
-
display(data, 6);
-
int target;
-
printf("请输入要查找的元素。\n");
-
scanf("%d",&target);
-
int result = linear_search(data, n, target);
-
if (result != -1) {
-
printf("元素 %d 在索引 %d(下标)处找到。\n", target, result);
-
} else {
-
printf("未找到目标元素。\n");
-
}
-
-
return 0;
-
}
二、二分查找(折半查找)
1.概念
二分查找适用于有序数据集合,它通过重复将数据集划分为两半并比较目标元素与中间元素的大小,从而快速定位目标元素。
2.算法
(1)在有序数据集合中,确定左右边界;
(2)计算中间位置 mid = (left right) / 2;
(3)比较目标元素与中间元素的大小关系;
(4)如果目标元素等于中间元素,查找成功;
(5)如果目标元素小于中间元素,继续在左半部分查找;
(6)如果目标元素大于中间元素,继续在右半部分查找;
(7)重复步骤2-3,直到找到目标元素或左边界大于右边界。
3.实现
-
int binary_search(int arr[], int n, int target) {
-
int left = 0, right = n - 1;
-
while (left <= right) {
-
int mid = left (right - left) / 2;
-
if (arr[mid] == target) {
-
return mid; // 返回目标元素的索引
-
} else if (arr[mid] < target) {
-
left = mid 1;
-
} else {
-
right = mid - 1;
-
}
-
}
-
return -1; // 目标元素未找到
-
}
三、 插值查找
1.概念
插值查找是在有序数据集合中通过插值计算来估计目标元素的位置,从而加快查找速度。
2.算法
(1)在有序数据集合中,确定左右边界;
(2)计算插值位置 mid = left (target - arr[left]) * (right - left) / (arr[right] - arr[left]);
(3)比较目标元素与插值位置处元素的大小关系;
(4)如果目标元素等于插值位置处元素,查找成功;
(5)如果目标元素小于插值位置处元素,继续在左半部分查找;
(6) 如果目标元素大于插值位置处元素,继续在右半部分查找;
(7)重复步骤2-3,直到找到目标元素或左边界大于右边界。
3.实现
插值查找的实现与二分查找类似,但计算插值位置时使用了插值公式。
-
int interpolation_search(int arr[], int n, int target) {
-
int left = 0, right = n - 1;
-
while (left <= right && target >= arr[left] && target <= arr[right]) {
-
int pos = left ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);
-
if (arr[pos] == target) {
-
return pos; // 返回目标元素的索引
-
} else if (arr[pos] < target) {
-
left = pos 1;
-
} else {
-
right = pos - 1;
-
}
-
}
-
return -1; // 目标元素未找到
-
}
四、 树表查找(二叉树查找)
树表查找方法包括各种基于树结构的查找,其中二叉树查找是最简单的一种。
1.概念
二叉树查找是基于二叉搜索树的查找方法,利用树结构将元素组织起来以支持高效的查找操作。它是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。 这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。
2.算法
(1)从根节点开始,比较目标元素与当前节点的值;
(2)如果目标元素等于当前节点的值,查找成功;
(3)如果目标元素小于当前节点的值,继续在左子树中查找;
(4)如果目标元素大于当前节点的值,继续在右子树中查找;
(5)如果到达叶子节点仍未找到目标元素,查找失败。
3.实现
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
// 定义二叉树结点
-
struct TreeNode {
-
int value;
-
struct TreeNode* left;
-
struct TreeNode* right;
-
};
-
-
// 二叉树查找函数
-
struct TreeNode* binary_tree_search(struct TreeNode* root, int target) {
-
// 当根节点为空或者根节点的值等于目标值时,返回根节点
-
if (root == NULL || root->value == target) {
-
return root;
-
}
-
-
// 如果目标值小于根节点的值,则在左子树中查找
-
if (target < root->value) {
-
return binary_tree_search(root->left, target);
-
}
-
// 如果目标值大于根节点的值,则在右子树中查找
-
return binary_tree_search(root->right, target);
-
}
-
-
int main() {
-
// 构建二叉搜索树
-
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
-
root->value = 5;
-
root->left = NULL;
-
root->right = NULL;
-
-
root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
-
root->left->value = 3;
-
root->left->left = NULL;
-
root->left->right = NULL;
-
-
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
-
root->right->value = 8;
-
root->right->left = NULL;
-
root->right->right = NULL;
-
-
// 要查找的目标值
-
int target = 3;
-
-
// 调用二叉树查找函数
-
struct TreeNode* result_node = binary_tree_search(root, target);
-
if (result_node) {
-
printf("元素 %d 找到了。\n", target);
-
} else {
-
printf("未找到目标元素。\n");
-
}
-
-
// 释放动态分配的内存
-
free(root->left);
-
free(root->right);
-
free(root);
-
-
return 0;
-
}
更多C语言、Linux系统、ARM板实战和数据结构相关文章,关注专栏:
📢写在最后
- 今天的分享就到这啦~
- 觉得博主写的还不错的烦劳
一键三连喔
~ - 🎉感谢关注🎉
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhiefkie
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
excel下划线不显示怎么办
PHP中文网 06-23 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22