二叉排序树查找算法 基本概念顺序查找二分查找分块索引查找二叉排序树的查找.ppt

? 基本概念基本概念顺序查找顺序查找二分查找二分查找分块索引查找分块索引查找二叉排序树的查找二叉排序树的查找B树与B+树的查找B树与B+树的查找Hash散列查找Hash散列查找9.1 基本概念9.1 基本概念查找表:由具有同一类型的数据元素(或查找表:由具有同一类型的数据元素(或记录)组成的集合称为查找表。记录)组成的集合称为查找表。关键字: 关键字是记录中某个项或组合项关键字: 关键字是记录中某个项或组合项的值,用它可以标识一个记录。能唯一确的值,用它可以标识一个记录。能唯一确定一个记录的关键字,称为主关键字;而定一个记录的关键字,称为主关键字;而不能唯一确定一个记录的关键字,称为次不能唯一确定一个记录的关键字,称为次关键字.关键字 查找是指按给定的某个值k,在查找表中查找是指按给定的某个值k,在查找表中查找关键字为给定值k的记录。查找关键字为给定值k的记录。查找是计算机中经常遇到的操作。二叉排序树查找算法特别是查找是计算机中经常遇到的操作。特别是当问题所涉及到的数据量相当大时,查找当问题所涉及到的数据量相当大时,查找的效率就显得格外重要。的效率就显得格外重要。 查找运算的主要操作是关键字的比较,所以,通查找运算的主要操作是关键字的比较,所以,通常把查找过程中对关键字需要执行的平均比较次常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。

法效率优劣的标准。* 查找结果:成功、失败* 查找算法的性能指标 时间复杂性平均查找长度: 平均比较次数平均查找长度定义为:nA SLp ci ii ?1其中,n是元素的个数;p 是查找第i个元i素的概率,p p p 1/n;c 是找到1 2 n i第i个元素所需要的比较次数*常用的查找算法顺序查找顺序查找二分查找折半查找二分查找折半查找分块索引查找分块索引查找二叉排序树的查找二叉排序树的查找B树与B+树的查找B树与B+树的查找Hash散列查找Hash散列查找9.2 顺序查找struct Recordint key;……;Record r[n];无监视哨的顺序查找:int SeqSearchRecord r[], int n, int kint i0;while in&&r[i].key!k i++;if in return i;else return -1;有监视哨的顺序查找int SeqSearch2Record r[], int n, int kint i0;r[n].keyk;while r[i].key!k i++;if in return i;else return -1;? 顺序查找的平均查找长度为:n nA SLp c i / n n ?1 / 2s qi ii ?1 i ?1?顺序查找的特点:算法简单,但查找效率低。

? 二分查找又称为折半查找。9.3 二分查找9.3 二分查找二分查找要求顺序表是有序的。二分查找的基本思想是:首先将待查的K值与有 序表R[0]到R[n-1]的中间位置mid上的结点的关键 字进行比较,若相等,则查找完成;否则,若 R[mid].keyK,则说明待查找的结点只可能在左 子表R[0]到R[mid-1]中,只需在左子表中继续查 找;否则在右子表R[mid+1]到R[n-1]中继续查找。这样,经过一次关键字的比较就缩小了一半的查找区间。如此进行下去,直到找到为止(当然也存在最后找不到的可能)。例:[0513192137566475808892][0513192137]566475808892051319 [2137] 566475808892查找K21的过程(查找成功)[0513192137566475808892]051319213756 [6475808892]051319213756647580 [8892]051319213756647580[8892 ]查找K85的过程(查找失败)二分查找算法非递归int BiSearchRecord r[ ], int n, int klow0,highn-1;while lowhighmidlow+high/2;if r[mid].keyk return mid;else if r[mid].keyklowmid+1;else highmid-1;return -1;二分查找算法递归int BiSearch2Record r[],int low,int high,intkif lowhighreturn -1;elsemidlow+high/2;if r[mid].keyk return mid;else if r[mid].keykreturn BiSearch2r,mid+1,high,k;else return BiSearch2r,low,mid-1,k;算法分析算法分析如果把当前查找位置上的结点作为根,左子表和右子表的结点分别作为根的左子树和右子树,由此得到的二叉树称为描述二分查找的判定树。二叉排序树查找算法

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26491-1.html