数据结构与算法——查找算法
2020-05-17 本文已影响0人
A慢慢懂
一、定义
查找：根据给定的某一个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找表:是有同一类型的数据元素构成的集合。
关键字：是数据元素中某一个数据项值，又称为键值。用它可以表示一个数据元素，也可以标识一个记录的某一个数据项(字段)
若关键字可以唯⼀地标识⼀个记录, 则称此关键字为关键字
(Primary Key)
对于那些可以识别多个属于元素(记录)的关键字,我们称为次关键
字(Secondary Key)
二、查找表操作方式分类
1.静态查找表：只作查找操作的查找表
a.查询某个”特定的”数据元素是否在查找表中
b. 检索某个"特定的"数据元素和各种属性;
2.动态查找表(Dynamic Search Table): 在查找过程中同时插⼊查找表中不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素; 显然动态查找表的操作就是2个动作
a. 查找时插⼊数据元素;
b. 查找时删除数据元素;
三、查找的算法
-
3.1顺序查找:又称为线性查找，是最基本的查找技术。查找过程:从表中的第一个或者做后一个记录开始，逐个进行记录关键字和给定值比较。
1.若某一个记录的关键字和给定值相等，则查找成功，找到所查记录。
2.若到最后一个或者第一个两者都不相等，则查不到所查记录，查找不成功。
代码实现:
#include <stdio.h>
#include <string.h>
#include <math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Elemtype;
//a表示数组，n代表个数、key代表所查的记录
Status Sequential_Search(int *a,int n,int key){
for (int i = 1; i < n-1; i++) {
if (a[i] == key) {
//如果有返回OK
return i;
}
}
return ERROR;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("顺序查找!\n");
int a[10] = {9,1,3,5,7,9,10,11,13,17};
int n = 10,key = 15;
printf("顺序查找啦\n");
printf("数组a中是否有key = %d的记录------下标为%d(0代表无)\n",key,Sequential_Search(a, n, key));
return 0;
}
-
3.2折半查找:又称为二分查找。
1、前提是线性表中的记录必须是关键码有序，线性表必须采用的是顺序存储。
2、基本思想：
a.在有序表中，取中间记录作为比较对象。若给定值与中间记录的关键字相等，则查找成功。
b.若给定值⼩于中间的记录关键字,则在中间记录的左半区继续查找;
c.若给定的值⼤于中间记录的关键字,则在中间记录的右半区继续查找;
d.不断重复以上的过程,直到查找成功,或所以查找区域⽆记录,查找失败为⽌.
代码实现:
int Binary_Search(int *a,int n,int key){
int minIndex,maxIndex,mid = 0;
mid = n;
minIndex = 1;
maxIndex = n -1;
while (minIndex<mid) {
//每次取中间
mid = (maxIndex+minIndex)/2;
if (a[mid]== key) {
//相等，返回下标
return mid;
}else if (a[mid]<key){
//中间记录值小于key，使最小下标等于mid的下一个下标
minIndex = mid+1;
}else{
//中间记录值大于key，使最小下标等于mid的上一个下标
maxIndex = mid-1;
}
}
return 0;;
}
-
3.3插值查找:是根据查找的关键字key 与查找表中最⼤最⼩记录的关键字⽐较后的查找⽅法, 其核⼼就是在于插值的计算公式:( key - a[low])/ (a[high] - a[low] )
代码实现:
//插值查找
int Interpolate_Search(int *a,int n,int key){
int low,hight,mid = 0;
mid = n;
low = 1;
hight = n -1;
while (low<hight) {
mid = low + (hight - low)*(key - a[low])/(a[hight]-a[low]);
if (a[mid]== key) {
//相等，返回下标
return mid;
}else if (a[mid]<key){
//记录值小于key，使最小下标等于mid的下一个下标
low = mid+1;
}else{
//记录值大于key，使最小下标等于mid的上一个下标
hight = mid-1;
}
}
return 0;
}
3.3插值查找:
斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）
在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
代码实现:
//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;
}
