密I码中国科学技术大学

Ch.9查找§9.1基本概念

查找和排序是两个重要的运算对象：表、文件等。其中每个结点（记录）由多个数据项构成，假设每个结点有1个能唯一标识该结点的key。定义：给定1个值K，在含有n个结点的表中找出关键字等于K的结点，若找到（查找成功），则返回该结点信息或它在表中的位置；否则（查找失败），返回相关指示信息。分类：查找过程中是否修改表？动态查找、静态查找查找过程是否均在内存中进行？内部查找、外部查找1§9.1基本概念效率：与存储结构、文件状态（有序、无序）有关

平均查找长度(ASL)，即平均的比较次数，作为衡量查找效率的标准：

Pi：查找第i个结点的概率Ci：查找第i个结点的比较次数设Pi＝1/n,1≤i≤n约定：typedefintKeyType;2

§9.2线性表的查找对象：用线性表作为表的组织形式。分类：静态查找、内部查找方式：顺序查找、二分查找、分块查找＃definen100//

§9.2.1顺序查找基本思想

从表的一端开始，顺序扫描线性表，依次将扫描到的结点的Key与给定值K进行比较，若当前扫描到结点Key＝K，则查找成功返回；若扫描完整个表后，仍未找到，则查找失败。适用范围：顺序表、链表算法：3§9.2.1顺序查找

typedefstruct{KeyTypekey;InfoTypeotherinfo;//应用相关}NodeType,SeqList[n+1];//0号单元作为哨兵intSeqSearch(SeqListR,KeyTypeK){

//在R[1..n]中查找，成功时返回结点位置，失败时返回0intn;R[0].key=K;//设置哨兵for(i=n;R[i].key!=K;i--);//从后往前找returni;//若i为0，则失败}4

§9.2.1顺序查找哨兵的作用

for中省略了下标越界i>=1判定,节约了约一半时间时间分析

成功：ASLss=(n+1)/2，key的平均比较次数约为表长的一半

失败：n+1次比较优缺点优点：简单，对存储结构、Key之间的关系均无特殊要求

缺点：效率低，当n较大时不宜用5

§9.2.2二分（折半）查找适用范围：顺序表、有序基本思想（分治法）

（1）设R[low..high]是当前查找区间，首先确定该区间的中点位置：mid=

(low+high)/2//整除（2）将待查的K值与R[mid]比较，

①K＝R[mid].key：查找成功，返回位置mid②K＜R[mid].key：则左子表R[low..mid-1]是新的查找区间③K＞R[mid],key：则右子表R[mid+1..high]是新的查找区间初始的查找区间是R[1..n]，每次查找比较K和中间点元素，若查找成功则返回；否则当前查找区间缩小一半，直至当前查找区间为空时查找失败。6

§9.2.2二分（折半）查找算法：

intBinSearch(SeqListR,KeyTypeK){intmid,low=1,high=n;while(low<high){//当前查找区间R[low..high]非空mid=

(low+high)/2；//整除if(R[mid].key==K）returnmid;//成功返回位置midif(K＜R[mid].key)//两个子问题求解其中的一个high=mid-1;//在左区间中查找

elselow=mid+1；//在右区间中查找}//endwhilereturn0;//当前查找区间为空时失败}7查找过程

判定(比较)树：分析查找过程的二叉树，形态只与结点数相关，与输入实例的取值无关（为什么？）。例如n＝11的形态如下图所示。1234567891011（05,13,19,21,37,56,64,75,80,88,92），找21成功，找85失败。6R[1..11]19437102R[1..5]R[7..11]R[10..11]R[5..5]ΦR[11..11]-14-51-22-33-4R[1..2]R[2..2]Φ58R[4..5]ΦΦΦ5-66-77-8ΦΦΦ11R[7..8]ΦR[8..8]8-99-10ΦΦ11-10-11Φ＝＞＜内部结点外部结点8

§9.2.2二分（折半）查找时间分析

查找R[6]：比较1次;查找R[3]、R{9]：比较2次;查找R[1]、R[4]、R[7]、R[10]：比较3次;查找R[2]、R[5]、R[8]、R[11]：比较4次6R[1..11]19437102R[1..5]R[7..11]R[10..11]R[5..5]ΦR[11..11]-14-51-22-33-4R[1..2]R[2..2]Φ58R[4..5]ΦΦΦ5-66-77-8ΦΦΦ11R[7..8]ΦR[8..8]8-99-10ΦΦ11-10-11Φ＝＞＜9

§9.2.2二分（折半）查找时间分析

总结：查找过程走了一条从判定树的根到被查结点的路径。

成功：终止于一个内部结点，所需的Key比较次数恰为该结点在树中的层数;

失败：终止于一个外部结点，所需的Key比较次数为该路径上内部结点总数。（层数－1）平均查找长度（ASL）：

设n＝2h-1,则树高h＝lg(n+1)//不计外部结点的满二叉树第k层上结点数为2k－1，找该层上每个结点的比较次数为k，在等概率假设下：最坏时间：查找失败，不超过树高⌈lg(n+1)⌉

在链表上可做折半查找吗？10

§9.2.3分块查找（索引顺序查找）存储结构

将R[1..n]均分成b块，前b－1块中结点数为s＝⌈n/b⌉

，最后一块中的结点数可能小于s，引入索引表标记块。关键字状态分块有序：块间有序，块内不一定有序;例子：n＝18，b＝3，s＝62248861713最大关键字起始地址221213892033424438244860587449865311

§9.2.3分块查找（索引顺序查找）查找过程（两步查找）

索引表查找：确定块。n较大时用折半查找，n较小时用顺序查找。块内查找：只能顺序查找。性能分析以折半查找确定块：ASL＝ASLbs＋ASLss＝lg(b＋1)－1＋(s＋1)/2≈lg(n/s＋1)＋s/2以顺序查找确定块：ASL＝ASLss＋ASLss＝(b＋1)/2＋(s＋1)/2＝(s2＋2s＋n)/(2s)当s＝时，ASL取极小值＋1块不一定等分EX.9.312

§9.3树上的查找（动态查找）

折半查找效率最高，但它不适应插删操作。本节讨论适用于动态查找，即查找过程中动态维护表结构。§9.3.1二叉查找树（BST）定义：二叉查找树或是空树，或满足下述BST性质的二叉树：①若它的左子树非空，则左子树上所有结点的keys均小于根的key②若它的右子树非空，则右子树上所有结点的keys均大于根的key③左右子树又都是二叉查找树Note：性质1或2中，可以将“﹤”改为“≤”；或“﹥”改为“≥”BST性质

二叉查找树的中序序列是一个递增有序序列13§9.3.1二叉查找树（BST）举例存储结构：typedefstructnode{KeyTypekey;InfoTypeotherinfo;structnode*lchild,*rchild;}BSTNode,*BSTree;53729414§9.3.1二叉查找树（BST）1.查找基本思想

从根结点开始比较，若当前结点的key与待查的key相等，则查找成功，返回该结点的指针；否则在左子树或右子树中继续查找。若树中没有待查结点，则失败于某个空指针上。算法

BSTNode*SearchBST(BSTreeT,KeyTypekey){

//在T上查找key=K的节点，成功时返回该节点，否则返回NULLif(T==NULL||key==T->key)returnT;//若T为空，查找失败；否则成功if(key<T->key)returnSearchBST(T->lchild,key);//查找左子树elsereturnSearchBST(T->rchild,key);//查找右子树}53729415§9.况3.险1二叉尝查找蝴树（BS遇T）1.查找时间若成裹功，婚则走酱了一勉条从欣根到匪待查却节点咳的路榜径若失筐败，滤则走才了一旋条从鞭根到另叶子单的路源径？降（不仆一定控）上界胃：O(犹h)分析窑：与树烈高相吊关①最坏打情况：单支菌树，AS坚L=镜(n企+1描)/谊2,与顺集序查翻找相清同②最好是情况：AS揭L≈lg翅n，形遍态与情折半印查找带的判裳定树陵相似③平均情况：假通定n个ke敌ys所形房诚成的n!种排谣列是乒等概取率的猎，则松可证犁明由咏这n!个序侦列产萝生的n!棵BS槽T（其奴中有虾的形洪态相葬同）韵的平帽均高箭度为O(l刻gn)，故碎查找躁时间稳仍为O(l踩gn)537294162、BS型T的插上入和巡寿生成插入算法臂思想保证幅新结养点插勉入后沸满足BS昼T性质子，基患本思红想如坝下：若T为空局，则辰为待稍插入泰的Ke浙y申请碑一个运新结宾点，疑并令明其为猾根；否则断，从员根开桐始向常下查渣找插皮入位惜置，歪直到胶发现培树中喇已有Ke孕y，或共找到靠一个旦空指芦针为闻止；将新敢结点驻作为豪叶子撤插入宇空指断针的疮位置珍。查找妥过程氧是一麦个关玩键字冤的比迈较过鹿程，使易于框写出谎递归纹或非设递归丸算法愈，也钟可以下调用亩查找赔操作驻。算法胀实现172、BS梦T的插决入和陕生成vo榆idIn和se占rt贷BS怠T(BS卫Tr克ee*T茂,Ke肃yT宁yp僚eke急y株)族{//厘*T是根BS馅TN律od傲e*f武,痒*知p=站*T屡;//于p指向抬根结拘点wh后il站e(窄p自)裁{//当树恶非空伐时，络查找涉插入招位置if委(利p芹->董ke街y=投=ke叮y)膜re诱tu坟rn更;//树中蹄已有ke饼y，不帜允许译重复嫂插入f＝p；//丑f和p为父查子关亏系p＝(墓ke巴y烘<私p-熟>k删ey斑)桌?臭p轮->lc东hi宿ld;振p-弄>rc博hi酬ld;}//注意服：树轰为空袄时，张无须秀查找p术=陈(BS貌TN口od杜e*)ma拌ll舟oc腊(s伍iz艘eo思f(壁BS构TN如od送e))楼;p-玻>k杏ey睡=ke穗y;倚p鼻->lc鲜hi城ld=p赴->rc庆hi颗ld=N艰UL水L;//生成梯新结揭点if手(缩慧*执T唐==艺NU洪LL奇)推*秃T=绸p;//原树岂为空,新结骄点为格根el溉se//原树写非空,新结逆点作嫌为*f的左斥或右亮孩子鱼插入if兽(敏k赵ey将<筝f驼->绝ke计y庄)茄f拐->lc质hi声ld=p涛;el烤se另f-刷>rc吧hi袄ld=p侵;}//时间彩为O（h）182、BS盘T的插息入和园生成生成算法轨：从空码树开怨始，照每输阀入一拨个数狐据就脆调用色一次晚插入镰算法凯。BS振Tr号eeCr腔ea宪te科BS孝T(晌vo急id重)触{BS买Tr扣eeT＝NU师LL铸;//初始作时T为空Ke茄yT谣yp械eke碑y;sc昂an绩f(地“%阵d”柱,根&k秒ey俭)底;wh榜il边e(幸k皮ey朴)娱{//假设ke号y＝0表示街输入驾结束In接se灰rt肥BS阔T(外&T疾,氏ke该y蒙)卖;//将ke晓y插入型树T中sc辟an饥f(法“%汇d”鞋,日&k粗ey仍)；//读入前下一腿个关愤键字}re准tu姓rn泰T；//返回匆根指缴针}192、BS巨T的插惜入和档生成举例1010181018310183810183812101838122101838122710183812273输入敲实例{1格0，18，3，8，12，2，7，3}202、BS羽T的插殿入和搬生成一般为情况不同榨的输瓦入实钻例（守数据龙集不房诚同、功或排宁列不鹊同）核，生棚成的盐树的喉形态军一般仪不同碑。对n个结聪点的码同一温数据逃集，硬可生活成n！棵BS踩T。例外转情况但有变时不寺同的宵实例锯可能融生成怨相同遵的BS挡T，例舒如：椒（2，3，7，8，5，4）和丙（2，3，7，5，8，4）可司构造咐同一碎棵BS闭T。排序搭树名傅称的将由来因为BS着T的中相序序孕列有枣序，剩所以蓬对任纽奉意关稍键字慢序列削，构恰造BS井T的过逐程，充实际催上是宇对其紫排序州。生成n个结茫点的BS掌T的平个均时厨间是O(社nl励gn),但它奥约为盲堆排影序的2－3倍，次因此胃它并患不适致合排素序。213、BS道T的删驻除保证令删一著结点斗不能中将以梅该结仁点为乞根的阿子树册删去片，且秀仍须棵满足BS进T性质饮。即朗：删饺一结熄点相孤当于霞删有晨序序凤列中绣的一恐个结奇点。基本和思想查找旦待删锈结点尊*p，令pa涂re绢nt指向芽其双茅亲（坑初值NU抵LL）；员若找巾不到僚则返妙回，央否则堤进入晒下一孤步。在删挨除*p时处愿理其吹子树草的连榆接问赏题，患同时尊保持BS辅T性质肥不变仅。ca葵se承1:*p是叶安子，鲜无须务连接势子树确，只度需将营*pa回re船nt中指负向*p的指筋针置莫空ca气se响2:*p只有1个孩援子，佛只须忍连接凉唯一挤的1棵子令树，吉故可拾令此刘孩子稿取代敢*p与其双迎亲连盐接（4种状艇态）parentpchildchildparentpparentpchildparentpchild*p只有卧左孩累子膊*p只有盗右孩糕子223、BS共T的删动除基本碌思想ca伯se助3:*p有2个孩删子，胆有2种处雅理方生式：①找到走*p的中序腿后继(或前坊驱)*s，用陶*p的右(或左)子树委取代炭*p与其托双亲王*pa担re虏nt连接虑；而洽*p的左(或右)子树PL则作亿为*s的左(或右)子树与*s连接网。缺点旨：树卫高可卡能增谨大。PLsRsprparentPLsRpparentspr233、BS堵T的删屋除基本刻思想②令q=马p，找棕*q的中序后矛继*p，并令pa赞re渠nt指向杰*p的双妥亲，疤将*p的右阔子树胜取代区*p与其售双亲那*pa董re谷nt连接仙。将心*p的内具容co峰py到*q中，级相当镰于删我去了*q，将缴删*q的操灯作转柜换为谈删*p的操勺作。对非称地扩，也肥可找借*q的中先序前蹄驱因为*p最多督只有1棵非骡空的县子树涛，属伍于ca造se苍2。实越际上ca任se大1也是ca话se妖2的特疤例。因此辅，ca引se容3采用栋该方般式时叔，3种情树况可使以统乎一处虏理为ca适se春2。q=pparentpchildq=ppchild*q的中序后继就是其右孩子243、BS距T的删今除算法vo私idDe哭lB番ST欠No恰de(BS赤Tr炭ee*T贸,Ke闷yT捐yp剑eke共y)弹{//访*T是根BS示Tr私ee*q猾,尽*c匹hi戒ld越,苗*p款ar蚊en雄t=帆NU质LL汪,仰*p卫=*茫T;wh稳il柄e朋(厦p贷)拜{//找待将删结嘱点if奋(港p-兔>k免ey闹=扑=ke漏y)缴br宵ea崇k;//已找压到pa钓re逢nt用=p沟;//循环染不变专式是翠*pa蛛re科nt为*p的双压亲p＝(爆ke普y衰<省p-阅>k雹ey废)易?弦p既->lc弱hi直ld;桃p-惕>rc累hi险ld;}if伶(笔!凉p枯)剑re垒tu鹅rn把;//找不硬到被尺删结恢点，机返回q=烦p;//伤q记住千被删声结点鼻*pif笛(他q-怠>lc喘hi象ld&&惠q狂->rc凝hi污ld)//姑ca姓se欣3，找洽*q的中栗序后科继fo球r(因pa跃re垦nt=q,毕p=q测->rc梨hi务ld;冰p-臣>lc萌hi贫ld;蕉pa勉re嗽nt秀=p卡,口p=努p-病>lc霜hi站ld);253、BS纤T的删雾除//现在3种情视况已冤统一泰到情坐况2，被秀删结轿点*p最多愿只有1个非售空的凳孩子ch汇il庭d=受(