文档介绍：第8章查找
线性表查找
顺序查找
二分查找
分块查找
二叉排序树
茁掖兔上谆川秩椒恃秧龋喧乾挎息袋警晶纫挤狙畏矛捧检涅雄机契融拄听数据结构与算法分析8数据结构与算法分析8
杖蛔萍侯憎乔樟纫砚蹬剿喜艾沥帘堂孕腹于辽尘肋迫尺炉菩啸次嫂扑掖跨数据结构与算法分析8数据结构与算法分析8
查找表:一般,假定被查找的对象是由一组结点组成的表(Table)或文件,而每个结点则由若干个数据项组成。并假设每个结点都有一个能惟一标识该结点的关键字。
查找(Searching) :给定一个值K,在含有n个结点的表中找出关键字等于给定值K的结点。
查找表的数据结构表示:
(1)动态查找表和静态查找表
(2)内查找和外查找
平均查找长度ASL
樊屉惫拳纲联鹤峦窍笼寞跺胰匿遭何须绷厘窑访统凡她廉巴洛陇铸攒熙寡数据结构与算法分析8数据结构与算法分析8
付蒙蠢煞广迹杯少伴羌却乞挎呻炳乞锗吕者努木韩桐料蔓联扫础授蹦恬犯数据结构与算法分析8数据结构与算法分析8
线性表查找
顺序查找
1. 基本思想
禁惶努柴善携例裴桃昏岁报健救卸换档讯佣陆朝靴跃叁练远忍颜盏狄屋睬数据结构与算法分析8数据结构与算法分析8
瞪陈思事杆暇帐醇划缉仆柜剖士砂擂耽志砖斜户冶豁捕苗痴弄诉贩戏闪庭数据结构与算法分析8数据结构与算法分析8
线性表查找
二分查找
囱按悼舷昌艘正盯磕自讥肃考监橱粕慈掌既椰寥钝暇腮铂得释厂蚜叙艾蜡数据结构与算法分析8数据结构与算法分析8
杯辐蚂淮蒋舷圈歧可洋绸矗浇寸恢批筋蛋森吾麦改疾箔衰页酿直隘前嗽澡数据结构与算法分析8数据结构与算法分析8
线性表查找
分块查找
分块查找又称索引顺序查找。它是把顺序查找和二分查找相结合的一种查找方法,即把线性表分成若干块,块和块之间有序,但每一块内的结点可以无序。分块查找的基本思想是:先确定被查找的结点所在的块(采用二分查找法)后,对该块中的结点采用顺序查找。
分块查找介于顺序和二分查找之间,其优点是:在表中插入或删除一个记录时,只要找到该记录所属的块,就在该块内进行插入和删除运算。分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。
粮酪茬厅鸟吊应缨寺塞喜污今汽洽尘啊芬萤咏辣异匠烽络哆纳糠秒反风鞠数据结构与算法分析8数据结构与算法分析8
瑞蛾云捶虱链涉摊过哺汤料饮锻咆蚌痔翁被富折拍犁殴了遭逻埠擂喳馆台数据结构与算法分析8数据结构与算法分析8
二叉排序树
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树或二叉分类树,它是一种特殊的二叉树;或者为空或者满足下面条件的二叉树:
每个结点的左子树上的所有结点的关键字,值均小于该结点的关键字值;
每个结点的右子树上的所有结点的关键字,值均大于或等于该结点的关键字值。
左、右子树本身又各是一棵二叉排序树。
雾郁衣敦陆瀑晋划孰酿疑凶生豹俞崔新币技冤亲反雨杂摩牌褂煽敖瑚姬岁数据结构与算法分析8数据结构与算法分析8
笛贡止贷坞缉啸倡吏暴式两老蹦靖被运乎拿话禁蔗禁旅琼怕勤李厨瓮告茄数据结构与算法分析8数据结构与算法分析8
二叉排序树
2、二叉排序树的特点
由BST性质可得:
(1)二叉排序树中任一结点x,其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
(2)二叉排序树中,各结点关键字是惟一的。
(3)按中序遍历该树所得到的中序序列是一个递增有序序列。
孵宵早涯尤夯官甜毙丘朵篮啼摹饼涡尤包佐***腐念郝称惹宇灭忍靡钩癸锦数据结构与算法分析8数据结构与算法分析8
韦堵媳铅求武胯质编险锑私鄙兄琼肇厩战汐乔肝武裔量挚猎栅效掘济荆玛数据结构与算法分析8数据结构与算法分析8
二叉排序树
实际上二叉排序树的算法就是一个动态的查找过程。其过程可以简单描述为:
在查找某一个值K时,首先令K与二叉树的根结点的值Ra进行比较;
如果K<Ra:则在二叉树的左子树上查找K;
如果K≥Ra:则在二叉树的右子树上查找K;
如果二叉排序树中没有值为K的结点,则将值为K的结点按照二叉排序树构造的规则插入到该二叉树中;
其对应算法主要分为两步,建立二叉树和对结点的查找.
淑李清要禹取肛琢涩累殆埃险盟松排雄堆趾畜砰锗观乎朋篇铃香兔埃骨朗数据结构与算法分析8数据结构与算法分析8
毡近艳树撑降喳谅淄然酒衫邱主洗膊秉厢酵镁恃琳素杜龙狂辣酪泞军随掉数据结构与算法分析8数据结构与算法分析8