数据结构第四讲ppt课件.ppt

文档介绍：第四讲查找和排序
1
本章出题特点
在历年统考里,大多以客观题的形式出现,具体如下:
年份
内容
客观
主观
2009
查找
1(2分)
排序
2(4分)
2010
查找
1(2分)
1(10分)
排序
2(4分)
2011
查找
1(2分)
排序
2(4分)
2012
查找
1(2分)
排序
2(4分)
2
一、查找
查找的基本概念
顺序查找
折半查找
B树查找
散列表
3
基本概念
在查找表上进行的基本操作有:查询,检索,插入和删除。若只是前两种操作的查找表则称为静态查找表,若兼有后面两种,则称为动态查找表。
查找的基本操作是关键字间的比较,查找每一个元素所需比较次数的平均值称为平均查找长度,即
通常用平均查找长度来衡量查找算法的好坏。
4
例如,在关键字序列为{3,9,1,5,8,10,6,7,2,4}的线性表查找关键字为6的元素。
顺序查找过程如下:
顺序查找
5
二分查找
二分查找也称为折半查找,要求线性表中的结点必须己按关键字值的递增或递减顺序排列。
思路:首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。
8
例如,在关键字有序序列{2,4,7,9,10,14,18,26,32,40}中采用二分查找法查找关键字为7的元素。
二分查找过程如下:
9
开始: 2 4 7 9 10 14 18 26 32 40
low=0 high=9
mid=(0+9)/2=4
第1次比较: 2 4 7 9 10 14 18 26 32 40
low=0 high=3 mid=(0+3)/2=1
第2次比较: 2 4 7 9 10 14 18 26 32 40
low=2 high=3 mid=(2+3)/2=2
第3次比较: 2 4 7 9 10 14 18 26 32 40
R[2].key=7
查找成功,返回序号2
10