锐客网

  1. 首页 > 睿知 > it技术 > >

浅谈全方位查找

IT知识查找

农村四月闲人少，勤学苦攻把名扬。这篇文章主要讲述浅谈全方位查找相关的知识，希望能为你提供帮助。
如有不足或错误，欢迎大家在评论区给我留言哟

让我们一起开启学习之旅吧Happy



（一）顺序查找

I.算法思想
从表的一端开始，依次将记录的关键字与给定的值进行比较，若某个记录的关键字与给定值相等，则查找成功；反之，若扫描整个表后，仍未找到和给定值相等的记录，则查找失败
II.具体代码
//适用了线性表的链式存储结构，详细代码在最后
LinkList Search_Seq(LNode *L, int key)//顺序查找

LinkList p = L;
int i;
while(p-> next)

i++;
p = p-> next;
//printf("查找次数为%d！\\n",i);
if(p-> info == key)

printf("查找次数为%d \\n",i);
return p;





III.复杂度分析查找一个关键字，最少查找一次成功，最多查找n次成功

时间复杂度为：O（n）
空间复杂度为：O（1）
IV.适用范围  既适用线性表的顺序存储结构，也适用与线性表的链式存储结构


V.优缺点分析Advantage：算法简单，对存储结构无要求，关键字有无序均可应用
Disadvantage:查找效率低，如果n较大，不宜使用顺查找


（二）折半查找

I.算法思想
关键字有序排列后，从表的中间记录开始，如果给定值与中间记录相等，则查找成功；如果给定值大于或小于记录的关键字，则在表中大于或小于中间记录的那一半中查找，重复操作，直到查找成功，如果在某一步查找空间为空，则查找失败
II.具体代码
//折半查找
void Search_Bin(int S[],int key,int n)

//在有序表中折半查找其关键字等于key的元素。如果找到，则函数值为该元素在表中所在位置，否则为0
int low=0; //置查找取件初值
int high=n-1;
int mid;
int flag=0;
int times=1;
while(low< =high)

mid=(low+high)/2;
if(key==S[mid])

printf("查找成功，查找位置为：%d\\n",mid+1);
flag=1;
break;

else if(key < S[mid])

high=mid-1; //继续在前一子表中进行查找
times++;

else

low=mid+1; //继续在后一子表中进行查找
times++;



printf("查找次数为：%d\\n",times);
if(flag==0)

printf("查找失败！\\n");


III.复杂度分析二叉判定树（二叉排序树）



    假设每个记录的查找概率相等（Pi=1/n）
// j为深度，2^（j-1）的为深度为j时判定树的总结点数
时间复杂度为：O(log2^n)
IV.适用范围
      有序的顺序表，不经常做插入和删除


V.优缺点分析
Advantage:比较次数少，查找效率高
【浅谈全方位查找】Disadvantage:表必须是有序表，对表的要求高
（三）二叉查找
  二叉排序树（Binary Sort Tree）：又称二叉排序树（可为空树）
具体定义如下：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
（3）它的左右子树也分别为二叉排序树
如果二叉树满足上述定义，就是一棵二叉排序树
I.算法思想
      给定值从根结点开始比较，如果大于根结点，寻找右子树，反之，寻找左子树，重复此步骤，直到查找成功为止，反之，查找失败


II.具体代码
//查找
int SearchBST(BSTree T,int key,int ci)


if(!T) return 0; //查找失败
else if(key == T-> data) ci++; printf("查找次数为%d\\n",ci); return 1; //查找成功
else if(key> T-> data) ci++; return SearchBST(T-> rchild,key,ci); // 查找右子树
else if(key< T-> data) ci++; return SearchBST(T-> lchild,key,ci); // 查找左子树

III.复杂度分析
  时间复杂度和二分查找时间度原理类似，均使用了二叉判定树
      时间复杂度为：O(log2^n)
IV.适用范围
    经常做插入和删除的动态查找表
V.优点分析
    插入和删除操作无需移动元素，只需要修改指针
（四）哈希查找
I.哈希表
      一种储存结构，通过某种函数（哈希函数），   使得其元素的储存位置与它的关键码之间能够建立一种映射关系，那么在查找时通过该函数很快找到相应元素。
II.哈希函数
      散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。



III.冲突的产生与解决  （1）冲突分析    以除余函数法的哈希函数为例
例： 现有 （1 ，3，4，5，6，9，13）几个数进行储存，将n%10求模运算的结果作为哈希地址进行元素插入。

在存储 13 的过程中 ，hash（地址） = 13%10=3,但空间 3已经被占用 ，冲突产生
冲突产生原因：插入一个元素，其根据哈希函数计算出的地址，已经被其他元素占用的情况。
（2）冲突的解决I.开放地址法
    产生冲突，将变化地址下标，找寻空地址进行插入
如下图：

II.开散列（链式结构）
通过链式存储结构，如果产生冲突，新生成结点，插入冲突地址后
IV.ASL（Average Search Length）
      平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度
定义如下：

其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。
当然，有查找成功，就有查找不成功，即要查找元素不在查找表中。
一个算法的ASL越大，说明时间性能差，反之，时间性能好，这也是显而易见的。
在顺序查找(Sequence Search)表中，查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。所以说，Ci（第i个元素的比较次数）在于这个元素在查找表中的位置，如第0号元素就需要比较一次，第一号元素比较2次......第n号元素要比较n+1次。所以Ci=i；所以

在哈希查找（Hash Search）表中，根据哈希函数，如果根据下标直接找到元素，则查找成功次数为1，如果在下一位找到，则查找成功次数依次递增，将各个元素的“查找成功次数的和”除于“元素总个数”就是ASL（success）,ASL(unsuccess)的求解是根据入口（哈希函数的除数M）进行的，M类似于通道入口，从每一个通道开始如果为空为查找失败，“所有通道失败的总数” 除于“通道入口个数（即M）”就是ASL
实例如下：

V.具体代码
//哈希表搜索关键字
void SearchHash(HashTable *HT,int key,int M)

//再散列表HT中查找关键字为key的元素，如果查找成功，返回散列表的单元符号，否则返回-1
int H0 = HashFunction(M,key); //根据散列表函数H（key）计算散列地址
int flag = 0;
HashTable *q; //定义了一个指针
q= HT+H0; //将指针指向该地址
if ((q-> data)==key)//如果单元H0中元素的关键字为key,则查找成功

printf("该单元位置为：%d ",H0);
flag=1;


else

while(q-> next

    推荐阅读


    上一篇：生产环境定时任务解注释

    下一篇：使用 React 和 Next.js 构建博客