我是靠谱客的博主 动人煎蛋,这篇文章主要介绍关于查找的有哪些常见算法?,现在分享给大家,希望可以做个参考。

查找专题

    • 查找的概念
      • 查找表操作⽅方式分类(静态/动态)
        • 顺序表查找(Sequential Search)
          • 代码实现
          • 优化(增加哨兵,将key存储在a[0])
        • 折半查找(Binary Search)
          • 代码实现
          • 查找范围优化(插值查找)
        • 斐波拉契查找(Fibonacci Search)
          • 代码实现
        • 有序查找-总结
      • 动态查找表
        • 二叉排序树(Binary Sort Tree)
          • ⼆叉排序树(Binary Sort Tree) — 树结构定义
          • 二叉排序树(Binary Sort Tree) — 查找操作代码实现
          • 二叉排序树(Binary Sort Tree) — 插入操作代码实现
          • 二叉排序树(Binary Sort Tree) — 删除操作
          • 插入删除代码综合

查找的概念

查找(Searching): 就是根据给定的某个值,在查找表中确定⼀一个其关键字等于给定值 的数据元素。
**查找表(Search Table)**是由同一类型的数据元素(记录)构成的集合。
**关键字(Key)**是数据元素中某个数据项的值.又称为键值. ⽤用它可 以表示一个数据元素,也可以标识一个记录的某个数据项(字段). 我们称为关键码。
若关键字可以唯一地标识一个记录, 则称此关键字为主关键字 (Primary Key)。
对于那些可以识别多个属于元素(记录)的关键字,我们称为次关键 字(Secondary Key)。

查找表操作⽅方式分类(静态/动态)

静态查找表(Static Search Table): 只作查找操作的查找表;

  1. 查询某个”特定的”数据元素是否在查找表中;

  2. 检索某个"特定的"数据元素和各种属性;

动态查找表(Dynamic Search Table): 在查找过程中同时插⼊入查找表中不不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素; 显然动态查找表的操作就是2个动作。

  1. 查找时插⼊数据元素;
  2. 查找时删除数据元素;

顺序表查找(Sequential Search)

顺序查找(Sequential Search), 又称为线性查找. 是最基本的查找技术. 它的查找过程: 从表中的第一个(或最后一个)记录开始,逐个进行记录关键 字和给定值比较;

  1. 若某个记录的关键字和给定值相等,则查找成功,找到所查记录;
  2. 如果直到最后一个(或第一个)记录, 其关键字和给定值比较都不等 时, 则表中没有所查的记录,查找不成功;
代码实现
复制代码
1
2
3
4
5
6
7
8
9
10
//1.顺序查找 //a为数组,n为查找的数组个数,key为要查找的关键字; int Sequential_Search(int *a,int n,int key){ for (int i = 1; i <= n ; i++) if (a[i] == key) return i; return 0; }
优化(增加哨兵,将key存储在a[0])
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//2.顺序查找_哨兵 int Sequential_Search2(int *a,int n,int key){ int i; //设置a[0]为关键字值,称为'哨兵' a[0] = key; //循环从数组尾部开始 i = n; while (a[i] != key) { i--; } //返回0,则说明查找失败 return i; }

折半查找(Binary Search)

折半查找(Binary Search)技术,又称为二分查找.
它的前提是线性表中的记录必须是关键码有序(通常是从小到⼤有序),线性表必须采⽤用顺序存储;

折半查找的基本思想是:

  1. 在有序表中,取中间记录作为⽐较对象,若给定值与中间记录的关键字相 等则查找成功;
  2. 若给定值小于中间的记录关键字,则在中间记录的左半区继续查找;
  3. 若给定的值大于中间记录的关键字,则在中间记录的右半区继续查找;
  4. 不断重复以上的过程,直到查找成功,或所以查找区域⽆记录,查找失败为止.
代码实现
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//假设数组a,已经是有序的(从小到大) int Binary_Search(int *a,int n,int key){ int low,high,mid; //定义最低下标为记录首位 low = 1; //定义最高下标为记录末位 high = n; while (low <= high) { //折半计算 mid = (low + high) /2; if (key < a[mid]) { //若key比a[mid] 小,则将最高下标调整到中位下标小一位; high = mid-1; }else if(key > a[mid]){ //若key比a[mid] 大,则将最低下标调整到中位下标大一位; low = mid+1; }else //若相等则说明mid即为查找到的位置; return mid; } return 0; }
查找范围优化(插值查找)

插值查找(Interpolation Search):是根据查找的关键字key 与查找表中最大最⼩记录的关键字⽐比较后的查找方法, 其核心 就是在于插值的计算公式:
在这里插入图片描述
#####代码实现

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Interpolation_Search(int *a,int n,int key){ int low,high,mid; low = 1; high = n; while (low <= high) { //插值 mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]); if (key < a[mid]) { //若key比a[mid]插值小,则将最高下标调整到插值下标小一位; high = mid-1; }else if(key > a[mid]){ //若key比a[mid]插值 大,则将最低下标调整到插值下标大一位; low = mid+1; }else //若相等则说明mid即为查找到的位置; return mid; } return 0; }

斐波拉契查找(Fibonacci Search)

代码实现
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//5.斐波拉契查找 int F[100]; /* 斐波那契数列 */ int Fibonacci_Search(int *a,int n,int key){ int low,high,mid,i,k; //最低下标为记录的首位; low = 1; //最高下标为记录的末位; high = n; k = 0; //1.计算n为斐波拉契数列的位置; while (n > F[k]-1) { k++; } //2.将数组a不满的位置补全值; for(i = n;i < F[k]-1;i++) a[i] = a[n]; //3. while (low <= high) { //计算当前分隔的下标; mid = low+F[k-1]-1; if (key < a[mid]) { //若查找的记录小于当前分隔记录; //将最高下标调整到分隔下标mid-1处; high = mid-1; //斐波拉契数列下标减1位; k = k-1; }else if(key > a[mid]){ //若查找的记录大于当前的分隔记录; //最低下标调整到分隔下标mid+1处 low = mid+1; //斐波拉契数列下标减2位; k = k-2; }else{ if (mid <= n) { //若相等则说明,mid即为查找的位置; return mid; }else { //若mid>n,说明是补全数值,返回n; return n; } } } return 0; }

有序查找-总结

这几种查找方式只是每次选择的范围不同,其公式总结如下:
在这里插入图片描述

动态查找表

二叉排序树(Binary Sort Tree)

二叉排序树(Binary Sort Tree),又称为二叉查找树. 它或者是一颗空树.或者是一颗具有下列性质的二叉树;

  1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结构的值;
  2. 若它的右子树不空,则右子树上的所有结点的值均大于它的根结点的值;
  3. 它的左右子树也分别是二叉排序树;
⼆叉排序树(Binary Sort Tree) — 树结构定义

在这里插入图片描述

二叉排序树(Binary Sort Tree) — 查找操作代码实现
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//1.二叉排序树--查找 /* 递归查找二叉排序树T中,是否存在key; 指针f指向T的双亲,器初始值为NULL; 若查找成功,则指针p指向该数据元素的结点,并且返回TRUE; 若指针p指向查找路径上访问的最后一个结点则返回FALSE; */ Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){ if (!T) /* 查找不成功 */ { *p = f; return FALSE; } else if (key==T->data) /* 查找成功 */ { *p = T; return TRUE; } else if (key<T->data) return SearchBST(T->lchild, key, T, p); /* 在左子树中继续查找 */ else return SearchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */ }
二叉排序树(Binary Sort Tree) — 插入操作代码实现
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//2.二叉排序树-插入 /* 当二叉排序树T中不存在关键字等于key的数据元素时, */ /* 插入key并返回TRUE,否则返回FALSE */ Status InsertBST(BiTree *T, int key) { BiTree p,s; //1.查找插入的值是否存在二叉树中;查找失败则-> if (!SearchBST(*T, key, NULL, &p)) { //2.初始化结点s,并将key赋值给s,将s的左右孩子结点暂时设置为NULL s = (BiTree)malloc(sizeof(BiTNode)); s->data = key; s->lchild = s->rchild = NULL; //3. if (!p) { //如果p为空,则将s作为二叉树新的根结点; *T = s; }else if(key < p->data){ //如果key<p->data,则将s插入为左孩子; p->lchild = s; }else //如果key>p->data,则将s插入为右孩子; p->rchild = s; return TRUE; } return FALSE; }
二叉排序树(Binary Sort Tree) — 删除操作
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//3.从二叉排序树中删除结点p,并重接它的左或者右子树; Status Delete(BiTree *p){ BiTree temp,s; if((*p)->rchild == NULL){ //情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树; //①将结点p临时存储到temp中; temp = *p; //②将p指向到p的左子树上; *p = (*p)->lchild; //③释放需要删除的temp结点; free(temp); }else if((*p)->lchild == NULL){ //情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树; //①将结点p存储到temp中; temp = *p; //②将p指向到p的右子树上; *p = (*p)->rchild; //③释放需要删除的temp结点 free(temp); }else{ //情况③:删除的当前结点的左右子树均不为空; //①将结点p存储到临时变量temp, 并且让结点s指向p的左子树 temp = *p; s = (*p)->lchild; //②将s指针,向右到尽头(目的是找到待删结点的前驱) //-在待删除的结点的左子树中,从右边找到直接前驱 //-使用`temp`保存好直接前驱的双亲结点 while (s->rchild) { temp = s; s = s->rchild; } //③将要删除的结点p数据赋值成s->data; (*p)->data = s->data; //④重连子树 //-如果temp 不等于p,则将S->lchild 赋值给temp->rchild //-如果temp 等于p,则将S->lchild 赋值给temp->lchild if(temp != *p) temp->rchild = s->lchild; else temp->lchild = s->lchild; //⑤删除s指向的结点; free(s) free(s); } return TRUE; }
插入删除代码综合
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//4.查找结点,并将其在二叉排序中删除; /* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */ /* 并返回TRUE;否则返回FALSE。 */ Status DeleteBST(BiTree *T,int key) { //不存在关键字等于key的数据元素 if(!*T) return FALSE; else { //找到关键字等于key的数据元素 if (key==(*T)->data) return Delete(T); else if (key<(*T)->data) //关键字key小于当前结点,则缩小查找范围到它的左子树; return DeleteBST(&(*T)->lchild,key); else //关键字key大于当前结点,则缩小查找范围到它的右子树; return DeleteBST(&(*T)->rchild,key); } }

最后

以上就是动人煎蛋最近收集整理的关于关于查找的有哪些常见算法?的全部内容,更多相关关于查找内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(94)

评论列表共有 0 条评论

立即
投稿
返回
顶部