本文共 2678 字,大约阅读时间需要 8 分钟。
在数据集合中寻找满足所给条件的数据元素的过程
,称之为查找;查找的结果有且只有两种:成功和失败
,换句话就是:要么从集合中找到至少一个满足条件的元素,要么在集合一个也找不到满足条件的元素
。查找结构
。确定某个值是否在查找表中
; ② 从查找表中筛选出满足特定条件的元素的各种属性
; ③ 从查找表中确定一个用于进行元素插入操作的位置
; ④ 从查找表中寻找满足删除条件的元素进行删除操作
。元素确定
,也即是上面的 ①②,那么这种查找表就称为静态查找表。适合静态查找表的查找算法有:顺序查找、折半查找和散列查找
。元素修改
,即上面的 ③④,那么这种查找表就称之为动态查找表;适合动态查找表的查找算法有:二叉排序树查找、散列查找等
。数据元素中能够唯一标识该数据元素的数据项的值
,例如学生信息表中的学号就是一个具体的学生信息的关键字;基于关键字的查找,其查找成功的结果往往是唯一确定的。一次查找的长度指需要比较的关键字的次数
,平均查找长度则是指整个查找过程中进行关键字比较的次数的平均值
: 平均查找长度,往往用于衡量一个算法是否高效。
顺序查找、折半查找和分块查找
。线性查找
,分为对一般无序线性表的顺序查找和针对关键字有序的顺序表进行查找。int SimpleSeqSearch(int arr[], int len, int keyValue){ for(int i=0;i
哨兵
的实现,如下:int SeqSearch(int arr[], int len, int keyValue){ arr[0] = keyValue; // 哨兵, 此时的数组是从下标 1 开始赋值的,即参数数组的下标 0是空 int i; for(i=len; arr[i]!=keyValue; i--); return i;}
前者小于等于目标值,后者大于目标值;或者反过来
。当取不到等号时,便可以判断目标值在查找表中不存在;这段描述可以用如下图的判定树来表示: int OrderSearch(int arr[], int len, int keyValue){ for(int i=0; ikeyvalue) return -1; }}
二分查找
。折半查找是针对有序序列的查找算法
。// 二分查找,针对有序序列的查找算法int BinSearch(int arr[], int len, int keyValue){ int low = 0, high = len - 1, mid; while (low <= high) { mid = (low + high) / 2; if (arr[mid] == keyValue) return mid; else if (arr[mid] > keyValue) high = mid - 1; else low = mid + 1; } return -1;}
分块查找又称为索引查找,吸取了顺序查找和折半查找各自的优点,既有动态结构,又适于快速查找
。即第一块的最大关键字小于第二块中所有的关键字
,以此类推; ② 建立一个索引表,索引表中的每个元素含有各块的最大关键字和各块的第一个元素的地址,索引表按关键字有序排列。 ③ 先确定待查关键字所在的块,然后再在块内进行搜索。转载地址:http://khqgn.baihongyu.com/