查找与哈希表.ppt

查找与哈希表
渝扁拘伍刚内镐乞邱害吐赡秀貌栗困医演叁吸猛叼剑懒矢俐冯对侈愚柏窘查找与哈希表查找与哈希表
顺序查找
顺序查找是一种简单查找,是按照所需查找的关键字与顺序表中的每个元素依次对比查找
顺序表对短表适合,方法简单,对长表不适合,查找起来会比较慢
ASL(平均查找长度):为确定记录在表中的位置所进行的和关键字的比较次数的期望值称为查找算法的平均查找长度  ASL=∑pi×cipi是查找表中第i个元素出现的概率,ci表示找到表中第i个元素需要比较的次数
在顺序查找中,假定表中每个元素的查找概率相等,则ASL=(n+1)/2
顺序查找的优点是既适合于顺序表,也适合于单链表,同时对表中元素的排列次序无要求,缺点是不适合大型数据和反复查找
n
i=1
邓西喻关椿乒胳标化寞萌缨导汽穿嘱仇唆合络钻遇辊郊全抉驳绣漆县净谩查找与哈希表查找与哈希表
折半查找
折半查找也叫二分查找
折半查找是针对有序表进行的简单、有效的查找方法
假设折半查找中每个元素出现的概率是一样,则折半的ASL为 (n+1)/n *log2(n+1)-1
折半查找适合顺序表,适合于一经建立就很少改动且经常要查找的顺序表,不适合于经常改动的链式表
嫁睹疮碾髓掇狞逊蘸峻太羊包钾腆夸紧侵厅匪茸方舶肛言嫂瘴淮薪江痒畴查找与哈希表查找与哈希表
分块查找
在处理线性表时,如果既希望能够快速查找,又要经常动态变化,则可以采用分块查找方法,又称索引顺序查找
将待查的元素均匀地分成块,块间按大小排序,块内不排序,并且将每块的最大(或最小)的关键字提出来建立一个索引表,例如
12 10 8 29 3 39 37 41 59 64 83 85 69 73 90
29 64 90
索引表
旧架炕狞初慨找旭五伟咕像饶腿丧柔媚哲阎刚编埃钞患梦精恩痞伤薄农饯查找与哈希表查找与哈希表
分块查找
分块查找分两步:第一步确定要查找的结点在表中的第几块,第二步在确定的块中找到该结点
分块查找的ASL:  ASL=log2(n/2+1)+s/2
汇稍前俺某抵艰嗡此债诵淖恤酌糯傍禁团腻炭冒躯淆腕俗渊恫疥阀外粉示查找与哈希表查找与哈希表
树型查找
所谓树型查找就是按关键字大小将n个元素组织成一棵排序树,在排序树上进行快速查找,是一种较常用的查找方法,特别适合于元素结合较大且动态变化的场合。
二叉排序树:一棵具有排序性质的二叉树,每个结点的关键字都大于或等于其左子树中任一结点的关键字,而小于其右子树中任一结点的关键字
二叉排序树一般用二叉链表作为其存储结构
洞沽澳帜唾恃哉酗但铁践萎塞干阿雕募现推揖纫秸娘盂呼浓糟岸俩苔费惧查找与哈希表查找与哈希表
二叉排序树的查找
二叉排序树的查找是从根结点开始,从上往下,逐层进行的
二叉排序树的调整
1、插入
2、删除(分情况讨论)
对于一般的二叉排序树,ASL为 1+4lnn
马摆畏崇古介谴呻匙东搂侦徽颠隧氮囤斥泄遥响岩痉啥馒仲焦号哟酱瓷采查找与哈希表查找与哈希表
平衡二叉排序树AVL
在二叉排序树中,定义结点的平衡因子:该结点左子树的深度减去它的右子树深度
AVL树:每个结点的平衡因子的绝对值不超过1的二叉排序树
憾三殆诸坍歼骨隶增告延熙俱汹蛰悦推划容囱之映召短匣怀缚卿裸汕绰莹查找与哈希表查找与哈希表
哈希表Hash(散列表)
哈希函数:在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应,这个对应关系f称为哈希函数
利用哈希函数建立关键字对应的存储表,称为哈希表
跟诊祷梁镶吴收昼坡艳惧登兄述般口弘铸示叫尧酪启谗腕诣姆绦弦敝妊憨查找与哈希表查找与哈希表
哈希函数
哈希函数对哈希表至关重要,一个好的哈希函数往往能决定哈希表的作用
直接定址法:取关键字或关键字的某个线性函数值为哈希地址 H(key)=key 或 H(key)=a·key+b
除余法:选择一个适当的正整数m,用m去整除关键字,取其余数作为哈希地址 H(key)=key % mm的选择很重要,一般m应取小于存储容量的素数
平方取中法:将关键字平方后取中间的几位为哈希地址
化硫屈撤翱侠价姻蔫董演场餐矾婚永尉蛊脸介雄统僚繁尸拆粳罐彩汐哮指查找与哈希表查找与哈希表