文档介绍：软件技术基础
制作
主讲
jjyang
检索和排序
第五章检索
检索的基本方法
检索
检索是依据元素的关键字,在结构中找寻元素的方法
关键字:元素的标志,检索的依据
一般情况下,关键字是一个元素的唯一标识
检索
检索的方法与数据结构的关系
数据结构决定了检索的方法
有时为提高检索效率,需要对数据结构采用特殊的实现方式
例,按成绩检索学生,检索一个学生成绩递增的表格比杂乱的表格效率高
检索效率的一般评价依据:
比较次数
最多、最少和平均比较次数
检索顺序检索
顺序检索顺序查找
从头开始逐个检索直到找到需要的结点
i = 0;
while( i < table->length){
if( table->a[i].key == our_key)
break;
i = i+1; }
找到所需的结点
if (i < table->length )
return i;
else
error(“ no such item ”);
平均查找次数
= ∑PiCi
i = 1
n
=
n+1
2
检索二分检索
折半(二分)检索
方法描述:
元素按关键字大小排列,每次查询查找范围内的“中间位置”结点。
若该结点不是所需,则缩小查找范围为前半部分或后半部分
m
m = length / 2
(要求元素按关键字大小排列)
a[i].key < a[m].key
a[j].key > a[m].key
检索二分检索
算法框架
每次将检索范围缩小一半,直到范围中结点的个数为0
while(L <= h){
核心算法:
判断是否找到所需结点;
否则,将范围减半;
}
检索二分检索
核心算法
确定检索范围:
L:上限;h:下限所以L ≤ h
确定“中间位置”的节点:
m =(L +h)/2
若key大于m的关键字
L = m + 1;缩小查询范围为后半部分
若key小于m的关键字
h = m - 1;缩小查询范围为前半部分
若key与m的关键字相同,则找到结点
mid = ( L + h )/ 2;
if(key > a[mid].key )
L = m + 1;
else if ( a[mid].key < key )
h = mid – 1;
else find item,break;
m
L
h
mid = ( L + h ) / 2;
if( table->data[mid].key == key)
break;
else if( key > table->data[ mid].key )
else
检索二分检索
int binary_search( key , table ){
L = 0;
h = table->length –1;
while ( ){
}
return mid;
}
L <= h
h = mid –1;
L = mid +1;
if ( L < = h )
else return –1;
L
h
平均查找次数
检索二分检索
n
1
( 1 + 2 × 2 + 4 × 3 + ... + 2k × (log 2n +1))
≈log2 (n + 1) - 1
9
7
5
1
16
18
10
1层
2层
3层