数据结构 C7 查找（上）

2022-12-10 125

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构 C7 查找

7.1查找的基本概念

查找：在数据集合上寻找满足某种条件的数据元素的过程称之为查找
查找表（查找结果）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成
关键字：数据结构中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

也就是说你查到哪个数据结构，那么这个数据结构记忆是你的查找表。关键字是唯一的，需要可区分性，唯一性；

如看下图：

对查找表的常见操作

1.查找符合条件的数据元素

2.插入删除某个数据元素

只需要进行操作1的是静态查找表。两者都要进行操作的是动态查找表

如下图：

评价指标

查找长度–在查找运算中，需要对比的关键词的次数称之为查找长度

平均查找长度（ASL）–所有查找过程中进行关键字的比较次数的平均值

公式如下：

举个例子：二叉排序树的成功/失败的ASL

ASL的数量级反应了查找算法的时间复杂度.

7.2顺序查找和折半查找

7.2.1顺序查找

顺序查找，又叫线性查找，通常用于线性表

算法思想：

从头到脚挨个查找（或者反过来欸个查找）

如下图：查找43，逆从头开始到尾部查找就行或者反过来

代码实现

查找成功：

查找失败：

typedef struct{
  elemtype *elem;
  int tablelen;
}SStable;
int search_seq(sstable ST,elemtype key){
  int i;
  for(i=0;i<ST.Tablelen&&ST.elem[i]!=key;++i);
  return i==ST.TableLen?-1:i;
}

类似算法：哨兵算法

查找成功：

查找失败：

typedef struct{
 elemtype *elem;
 int tablelen;
}SStable;
int search_seq(sstable ST,elemtype key){
ST.elem[0]=key;
 int i;
 for(i=ST.Tablelen;ST.elem[i]!=key;--i);
 return i;
}

查找效率分析

基于这个算法的效率，这个算法是否可以优化呢？

对表进行有序排列，再进行查找，如下图：

由此引申了查找判定树，上图的查找判定树如下

另外一种优化方法：当你的每一个结点的查找概率不一样的时候，按照概率由大到小排序。

这样成功的几率会增大。

7.2.2折半查找

折半查找，又称之为二分查找，仅仅适用于有序的顺序表。

算法思想

设置两个指针，分别指向数组的头部与数组的尾部，在设置一个指针指向前两者除以二取整的地方。

然后三个指针分别指向了最大值，最小值，中间值。然后拿现在查找的数字和中间值比较，如果大于只能在右边，设置low=mid+1;如果小于，只能在左边,设置high=mid-1;

重复上面过程直到查找成功low=high=mid=该查找的数值。

如果low=high还没有查找成功，那么下面就会变成low>high,查找失败.

具体过程如下图。

上面的例子是查找成功的例子，那咱们看一看一个查找失败的例子；

以上就是算法的基本思想。

算法实现

代码实现：

typedef struct{
  elemtype *elem;//顺序表拥有随机访问的特性，链表没有
  int tablelen;
}sstable;
int binary_search(sstable l,elemtype key){
  int low=0,high=l.tablelen-1,mid;
  while(low<=high){
  mid=(low+high)/2;
  if(l.elem[mid]==key)
    return mid;
  else if(l.elem[mid]>key)
    high=mid-1;
  else 
    low=mid+1;
  }
  return -1;
}