算法-查找算法-线性表的查找（类C语言版）

算法-查找算法-线性表的查找（类C语言版）

文章目录

​​顺序查找​​

​​应用范围​​​​数据元素类型定义​​​​顺序查找算法​​​​改进后的顺序查找算法​​​​顺序查找时间效率分析​​​​顺序查找的性能分析​​​​顺序查找优缺点讨论​​

​​折半查找（二分或对分查找）​​

​​折半查找算法（非递归算法）​​​​折半查找——递归算法​​​​折半查找性能分析​​

​​判定树​​​​折半查找优缺点​​

​​分块查找（索引顺序查找）​​

​​分块查找过程​​​​分块查找性能分析​​​​分块查找优缺点​​

​​三种查找方法的比较​​

顺序查找

应用范围

顺序表或线性链表表示的静态查找表。表内元素之间无序。

数据元素类型定义

// 数据元素类型定义typedef struct { KeyType key; // 关键字域 InfoType otherinfo; // 其他域} ElemType; // 顺序表的定义typedef struct{ ElemType *R; // 存储空间基地址 int length; // 当前长度}SSTable; // Sequential Search TableSSTable ST; // 定义顺序表ST

顺序查找算法

int Search_Seq(SSTable ST, KeyType key){ // 若成功返回其位置信息，否则返回0 for(i=ST.length;i>=1;--i) if(ST.R[i].key==key) return i; return 0;}

改进后的顺序查找算法

把待查关键字key存入表头（哨兵、监视哨），可免去查找过程中每一步都要检测是否查找完毕，加快速度。

int Search_Seq(SSTable ST,KeyType key) { // 在顺序表 ST 中顺序查找其关键字等于 key 的数据元素。若找到，则函数值为该元素在表中的位置，否则为 0 ST.R[O].key=key; // ＂哨兵” for(i=ST.length;ST.R[i].key!=key;--i); // 从后往前找 return i; }

当ST.length较大时，此改进能使进行一次查找所需的平均时间几乎减少一半。

顺序查找时间效率分析

查找第 i 个元素，需要比较n - i + 1次。查找失败，需比较n + 1次。

顺序查找的性能分析

时间复杂度：O(n) 查找成功时的平均查找长度，设表中各记录查找概率相等 ASLs(n) = (1+2+…+n) / n = (n+1) / 2空间复杂度：一个辅助空间——O(1)。

顺序查找优缺点讨论

优点：算法简单，逻辑次序无要求，且不同存储结构均适用。 缺点：ASL太长，时间效率太低。

讨论：

1.记录的查找概率不相等时如何提高查找效率？ 查找表存储记录原则——按查找概率高低存储： （1）查找概率越高，比较次数越少； （2）查找概率越低，比较次数较多。

2.记录的查找概率无法测定时如何提高查找效率？ 方法——按查找概率动态调整记录顺序： （1）在每个记录中设一个访问频度域； （2）始终保持记录按非递增有序的次序排列； （3）每次查找后将刚查到的记录直接移至表头。

折半查找（二分或对分查找）

折半查找算法（非递归算法）

设表长为n，low、high和mid分别指向待查元素所在区间的上届、下届和中点，key为给定的要查找的值：初始时，令low=1，high=n，mid=(low+high) / 2让k与mid指向的记录比较

若key == R[mid].key，查找成功若key < R[mid].key，则high=mid - 1若key > R[mid].key，则low=mid + 1

重复上述操作，直至low>high时，查找失败。

int Search_Bin(SSTable ST,KeyType key) { // 在有序表ST 中折半查找其关键字等于key的数据元素。若找到， 则函数值为该元素在表中的位置， 否则为0 low= 1;high=ST.length; //置查找区间初值 while(low<=high) { mid=(low+high)/2; if{key==ST.R[mid].key) return mid; // 找到待查元素 else if{key

折半查找——递归算法

int Search_Bin(SSTable ST, keyType key, int low, int high){ if(low>high) return 0; // 差找不到时返回0 mid=(low+high)/2; if(key==ST.elem[mid].key) return mid; else if(key

折半查找性能分析

判定树

查找不成功： 比较次数 = 路径上的内部结点数 比较次数 ≤ log2n + 1

折半查找优缺点

优点：效率比顺序查找高。 缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效）。

分块查找（索引顺序查找）

1.将表分成几块，且表或者有序，或者分块有序；若 i < j，则第 j 块中所有记录的关键字均大于第 i 块中的最大关键字。 2.建立“索引表”（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）。

分块查找过程

分块查找性能分析

分块查找优缺点

优点：插入和删除比较容易，无需进行大量移动。 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。 适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

三种查找方法的比较

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。