部编版第九章查找 学习指导材料.doc

《部编版第九章查找 学习指导材料.doc》由会员分享，可在线阅读，更多相关《部编版第九章查找 学习指导材料.doc（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第九章查寻第一局部常识点及例题精选9.1根本观点与术语以黉舍招生录用注销表为例，来探讨盘算机中表的观点。学号姓名性不诞诞辰期起源总分录用专业年月日200109832001098420010985赵剑平蒋伟峰郭娜男男女198219821983110901051225石家庄一中保定三中易县中学593601598盘算机盘算机盘算机图9.黉舍招生录用注销表1.数据项(也称项或字段)项是存在独破含意的标识单位，是数据弗成联系的最小单位。如表中“学号、“姓名、“年等。2.组合项由假定干项、组合项形成，表中“诞诞辰期确实是组合项，它由“年、“月、“日三项构成。3.数据元素记载数据元素是由假定干项、组合项形成

2、的数据单位，是在某一咨询题中作为全部进展思索跟处置的根本单位。数据元素有型跟值之分，表中项名的聚集，也即表头局部确实是数据元素的范例；而一个先生对应的一行数据确实是一个数据元素的值，表中全部先生即为数据元素的聚集。4.要害码要害码是数据元素记载中某个项或组合项的值，用它能够标识一个数据元素记载。能独一断定一个数据元素记载的要害码，称为主要害码；而不克不及独一断定一个数据元素记载的要害码，称为次要害码。表中“学号即可当作主要害码，“姓名那么应视为次要害码，因能够有同名同姓的先生。5.查寻表是由存在统一范例属性的数据元素记载构成的聚集。分为静态查寻表跟静态查寻表两类。静态查寻表：仅对查寻表进展查寻

3、操纵，而不克不及改动的表；静态查寻表：对查寻表除进展查寻操纵外，能够还要进展向表中拔出数据元素，或删除表中数据元素的表。6.查寻按给定的某个值kx，在查寻表中查寻要害码为给定值kx的数据元素记载。要害码是主要害码时：因为主要害码独一，因而查寻后果也是独一的，一旦寻到，查寻胜利，完毕查寻进程，并给出寻到的数据元素记载的信息，或唆使该数据元素记载的地位。如果全部表检测完，还不寻到，那么查寻掉败，如今，查寻后果应给出一个“空记载或“空指针。要害码是次要害码时：需求查遍表中一切数据元素记载，或在能够确信查寻掉败时，才干完毕查寻进程。7.数据元素范例阐明在手工绘制表格时，老是依照有多多数据项，每个数据项

4、应留多年夜宽度来断定表的结构，即表头的界说。而后，再依照需求的行数，画出表来。在盘算机中存储的表与手工绘制的相似，需求界说表的结构，并依照表的巨细为表调配存储单位。以图9.为例，用C言语的结构范例描绘之。/*诞诞辰期范例界说*/typedefstructcharyear5；/*年：用字符型表现，宽度为4个字符*/charmonth3；/*月：字符型，宽度为2*/chardate3；/*日：字符型，宽度为2*/BirthDate；/*数据元素范例界说*/typedefstructcharnumber7；/*学号：字符型，宽度为6*/charname9；/*姓名：字符型，宽度为8*/charsex

5、3；/*性不：字符型，宽度为2*/BirthDatebirthdate；/*诞诞辰期：结构范例，由该范例的宽度断定*/charcomefrom21；/*起源：字符型，宽度为20*/intresults；/*成果：整型，宽度由“次序计划C言语东西软件决议*/ElemType；以上界说的数据元素范例，相称于手工绘制的表头。要存储先生的信息，还需求调配必定的存储单位，即给出表长度。能够用数组调配，即次序存储结构；也能够用链式存储结构实现静态调配。/*次序调配1000个存储单位用来寄存最多1000个先生的信息*/ElemTypeelem1000；本章以后探讨中，触及的要害码范例跟数据元素范例一致阐明如

6、下：typedefstructKeyTypekey；/*要害码字段，能够是整型、字符串型、结构范例等*/*别的字段*/ElemType；9.2静态查寻表静态查寻表结构静态查寻表是数据元素的线性表，能够是基于数组的次序存储或以线性链表存储。/*次序存储结构*/typedefstructElemType*elem；/*数组基址*/intlength；/*表长度*/S_TBL；/*链式存储结构结点范例*/typedefstructNODEElemTypeelem；/*结点的值域*/structNODE*next；/*下一个结点指针域*/NodeType；9.2.2次序查寻次序查寻又称线性查寻，是最根

7、本的查寻办法之一。其查寻办法为：从表的一端开场，向另一端逐一按给定值kx与要害码进展比拟，假定寻到，查寻胜利，并给出数据元素在表中的地位；假定全部表检测完，仍未寻到与kx一样的要害码，那么查寻掉败，给出掉败信息。【算法9.1】以次序存储为例，数据元素从下标为1的数组单位开场寄存，0号单位留空。ints_search(S_TBLtbl，KeyTypekx)/*在表tbl中查寻要害码为kx的数据元素，假定寻到前往该元素在数组中的下标，否那么前往0*/tbl.elem0.key=kx；/*寄存监测，如此在从后向前查寻掉败时，不用判表能否检测完，*/*从而抵达算法一致*/for(i=tbl.lengt

8、h;tbl.elemi.keykx；i-)；/*从标尾端向前寻*/returni；【功能剖析】剖析查寻算法的效力，平日用平均查寻长度ASL来权衡。界说：在查寻胜利时，平均查寻长度ASL是指为断定命据元素在表中的地位所进展的要害码比拟次数的希冀值。ASL=PiCini=1对一个含n个数据元素的表，查寻胜利时ni=1Pi=1此中：Pi为表中第i个数据元素的查寻概率，Ci为表中第i个数据元素的要害码与给定值kx相称时，按算法定位时要害码的比拟次数。显然，差别的查寻办法，Ci能够差别。ASL=Pin-i+1ni=1就上述算法而言，关于n个数据元素的表，给定值kx与表中第i个元素要害码相称，即定位第i个

9、记载时，需进展n-i+1次要害码比拟，即Ci=n-i+1。那么查寻胜利时，次序查寻的平均查寻长度为：ni=1ASL=n-i+1=设每个数据元素的查寻概率相称，即Pi=，那么等概率状况下有查寻不胜利时，要害码的比拟次数老是n+1次。算法中的根本任务确实是要害码的比拟，因而，查寻长度的量级确实是查寻算法的时刻庞杂度，其为O(n)。很多状况下，查寻表中数据元素的查寻概率是不相称的。为了进步查寻效力，查寻表需依照查寻概率越高，比拟次数越少；查寻概率越低，比拟次数就较多的原那么来存储数据元素。次序查寻缺陷是当n非常年夜时，平均查寻长度较年夜，效力低；长处是对表中数据元素的存储不请求。别的，关于线性链表，

10、只能进展次序查寻。9.2.3有序表的折半查寻有序表等于表中数据元素按要害码升序或落序陈列。折半查寻的思维为：在有序表中，取两头元素作为比拟东西，假定给定值与两头元素的要害码相称，那么查寻胜利；假定给定值小于两头元素的要害码，那么在两头元素的左半区接着查寻；假定给定值年夜于两头元素的要害码，那么在两头元素的右半区接着查寻。不时反复上述查寻进程，直到查寻胜利，或所查寻的地区有数据元素，查寻掉败。【步调】low=1；high=length；/设置初始区间当lowhigh时，前往查寻掉败信息/表空，查寻掉败lowhigh，mid=(low+high)/2;/取中点a.假定kxtbl.elemmid.k

11、ey，low=mid+1；转/查寻在右半区进展c.假定kx=tbl.elemmid.key，前往数据元素在表中地位/查寻胜利【例9.】有序表按要害码陈列如下：7，14，18，21，23，29，31，35，38，42，46，49，52在表中查寻要害码为14跟22的数据元素。查寻要害码为14的进程0123456789101112137141821232931353842464952low=1设置初始区间high=13表空测试，非空；mid=7掉掉中点，比拟测试为a情况low=1high=6high=mid-1，调剂到左半区表空测试，非空；mid=3掉掉中点，比拟测试为a情况low=1high=2h

12、igh=mid-1，调剂到左半区表空测试，非空；mid=1掉掉中点，比拟测试为b情况low=2high=2low=mid+1，调剂到右半区表空测试，非空；mid=2掉掉中点，比拟测试为c情况查寻胜利，前往寻到的数据元素地位为2查寻要害码为22的进程0123456789101112137141821232931353842464952low=1设置初始区间high=13表空测试，非空；mid=7掉掉中点，比拟测试为a情况low=1high=6high=mid-1，调剂到左半区表空测试，非空；mid=3掉掉中点，比拟测试为b情况low=4high=6low=mid+1，调剂到右半区表空测试，非空；

13、mid=5掉掉中点，比拟测试为a情况low=4high=4high=mid-1，调剂到左半区表空测试，非空；mid=4掉掉中点，比拟测试为b情况high=4low=5low=mid+1，调剂到右半区表空测试，为空；查寻掉败，前往查寻掉败信息为0【算法9.2】intBinary_Search(S_TBLtbl，KEYkx)/*在表tbl中查寻要害码为kx的数据元素，假定寻到前往该元素在表中的地位，否那么，前往0*/intmid，flag=0；low=1；high=length；/*设置初始区间*/while(low=high)/*表空测试*/*非空，进展比拟测试*/mid=(low+high)/

14、2；/*掉掉中点*/if(kxtbl.elemmid.key)low=mid+1；/*调剂到右半区*/elseflag=mid；break；/*查寻胜利，元素地位设置到flag中*/returnflag;【功能剖析】从折半查寻进程看，以表的中点为比拟东西，并以中点将表联系为两个子表，对定位到的子表接着这种操纵。因而，对表中每个数据元素的查寻进程，可用二叉树来描绘，称那个描绘查寻进程的二叉树为断定树。4938291874252312346351421图9.2为例9.描绘折半查寻进程的断定树log2(n+1)log2(n+1)能够看到，查寻表中任一元素的进程，等于断定树中从根到该元素结点途径上各结

15、点要害码的比拟次数，也即该元素结点在树中的档次数。关于n个结点的断定树，树高为k，那么有2k-1-1n2k-1，即k-1(*q)-elem.key)/*kx年夜于以后结点*q的元素要害码*/*p=*q;*q=(*q)-rc;/*将以后结点*q的右后代置为新根*/elseif(kxelem.key)/*kx小于以后结点*q的元素要害码*/*p=*q;*q=(*q)-lc;/*将以后结点*q的左后代置为新根*/elseflag=1;break;/*查寻胜利，前往*/*while*/returnflag;三.二叉排序树拔出操纵跟结构一棵二叉排序树先探讨向二叉排序树中拔出一个结点的进程：设待拔出结点的

16、要害码为kx，为将其拔出，先要在二叉排序树中进展查寻，假定查寻胜利，按二叉排序树界说，待拔出结点已存在，不用拔出；查寻不胜利时，那么拔出之。因而，新拔出结点必定是作为叶子结点增加上去的。结构一棵二叉排序树那么是逐一拔出结点的进程。【例9.3】记载的要害码序列为：63，90，70，55，67，42，98，83，10，45，58，那么结构一棵二叉排序树的进程如下：70906355674298709063556742709063556770906370906355639063584298709063455583671042987090634555836710709063556783981042709

17、0635567839842图9.5从空树开场树破二叉排序树的进程【算法9.5】intInsertNode(NodeType*t,KeyTypekx)/*在二叉排序树*t上拔出要害码为kx的结点*/NodeType*p=*t,*q,*s;intflag=0;if(!SearchElem(*t,&p,&q,kx);/*在*t为根的子树上查寻*/s=(NodeType*)malloc(sizeof(NodeType);/*请求结点，并赋值*/s-elem.key=kx;s-lc=NULL;s-rc=NULL;flag=1;/*设置拔出胜利标记*/if(!p)t=s;/*向空树中拔出时*/elseif

18、(kxp-elem.key)p-rc=s;/*拔出结点为p的右后代*/elsep-lc=s;/*拔出结点为p的左后代*/returnflag;四.二叉排序树删除操纵从二叉排序树中删除一个结点之后，使其仍能坚持二叉排序树的特点即可。设待删结点为*pp为指向待删结点的指针，其双亲结点为*f，以下分三种状况进展探讨。*P*fFPF*p结点为叶结点，因为删去叶结点后不妨碍整棵树的特点，因而，只需将被删结点的双亲结点响应指针域改为空指针。图9.6如图9.6。*f*PFPPl*f*PFP*fFPl*fFPr图9.7*p结点只要右子树pr或只要左子树pl，如今，只需将pr或pl交换*f结点的*p子树即可。如

19、图9.7。Pr*p结点既有左子树Pl又有右子树Pr，可按中序遍历坚持有序进展调剂。设删除*p结点前，中序遍历序列为：P为F的左后代时有：，Pl子树，P，Pj，S子树，Pk，Sk子树，P2，S2子树，P1，S1子树，F，P为F的右后代时有：，F，Pl子树，P，Pj，S子树，Pk，Sk子树，P2，S2子树，P1，S1子树，那么删除*p结点后，中序遍历序列应为：P为F的左后代时有：，Pl子树，Pj，S子树，Pk，Sk子树，P2，S2子树，P1，S1子树，F，SJPj*f*PFPPlS1P1S2P2SPr*f*PFPrPlP1P1P2P2SjPjSP为F的右后代时有：，F，Pl子树，Pj，S子树，Pk

20、，Sk子树，P2，S2子树，P1，S1子树，有两种调剂办法： 直截了当令pl为*f响应的子树，以pr为pl中序遍历的最初一个结点pk的右子树； 令*p结点的直截了以后驱Pr或直截了当后继对Pl子树中序遍历的最初一个结点Pk交换*p结点，再按的办法删去Pr或Pk。图9.8所示的确实是以*p结点的直截了以后驱Pr交换*p。*f*PFPPlSPrFPr*f*PPlS图9.8按办法进展调剂的图示【算法9.6】intDeleteNode(NodeType*t,KeyTypekx)NodeType*p=*t,*q,*s,*f;intflag=0;if(SearchElem(*t,&p,&q,kx);fla

21、g=1;/*查寻胜利，置删除胜利标记*/if(p=q)f=&(*t);/*待删结点为根结点时*/else/*待删结点非根结点时*/f=&(p-lc);if(kxp-elem.key)f=&(p-rc);/*f指向待删结点的父结点的响应指针域*/if(!q-rc)*f=q-lc;/*假定待删结点无右子树，以左子树交换待删结点*/elseif(!q-lc)*f=q-rc;/*假定待删结点无左子树，以右子树交换待删结点*/else/*既有左子树又有右子树*/p=q-rc;s=p;while(p-lc)s=p;p=p-lc;/*在右子树上搜寻待删结点的先驱p*/*f=p;p-lc=q-lc;/*交换待

22、删结点q，重接左子树*/if(s!=p)s-lc=p-rc;/*待删结点的右后代有左子树时，还要重接右子树*/p-rc=q-rc;free(q);returnflag;对给定序列树破二叉排序树，假定阁下子树平均散布，那么其查寻进程相似于有序表的折半查寻。但假定给定序列本来有序，那么树破的二叉排序树就堕落为单链表，其查寻效力同次序查寻一样。因而，对平均的二叉排序树进展拔出或删除结点后，应答其调剂，使其依然坚持平均。9.3.2均衡二叉树(AVL树)均衡二叉树或许是一棵空树，或许是存在以下性子的二叉排序树：它的左子树跟右子树基本上均衡二叉树，且左子树跟右子树高度之差的相对值不超越1。91000065

23、504741853060727842-330-202141853060727842-1110010a.非均衡二叉树b.均衡二叉树图9.9图9.9给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的树中，左子树与右子树高度之差，那个数字称为结点的均衡因子。由均衡二叉树界说，一切结点的均衡因子只能取-1，0，1三个值之一。假定二叉排序树中存在如此的结点，其均衡因子的相对值年夜于1，这棵树就不是均衡二叉树。如图9.9a所示的二叉排序树。在均衡二叉树上拔出或删除结点后，能够使树掉掉均衡，因而，需求对掉掉均衡的树进展均衡化调剂。设a结点为掉掉均衡的最小子树根结点，对该子树进展均衡化调剂归结起来有以

24、下四种状况：xBhaEcDhh+1-2-1BhahEcDh0-1一.左单扭转xEh+1cDaBh+100a.拔出前b.拔出后，调剂前c.调剂后图9.10如图9.10的图(a)为拔出前的子树。此中，B为结点a的左子树，D、E分不为结点c的阁下子树，B、D、E三棵子树的高均为h。图(a)所示的子树是均衡二叉树。在图(a)所示的树上拔出结点x，如图(b)所示。结点x拔出在结点c的右子树E上，招致结点a的均衡因子相对值年夜于1，以结点a为根的子树掉掉均衡。【调剂战略】调剂后的子树除了各结点的均衡因子相对值不超越1，还必需是二叉排序树。因为结点c的左子树D可作为结点a的右子树，将结点a为根的子树调剂为左

25、子树是B，右子树是D，再将结点a为根的子树调剂为结点c的左子树，结点c为新的根结点，如图(c)。【均衡化调剂操纵断定】沿拔出途径反省三个点a、c、E，假定它们处于“直线上的统一个偏向，那么要作左单扭转，即以结点c为轴逆时针扭转。h+1h+1EcBaDx00hBaDcEhh01hxhBaDcEh+121二.右单扭转a.拔出前b.拔出后，调剂前c.调剂后图9.11hDbh-1GcFh-1hEa001右单扭转与左单扭转相似，沿拔出途径反省三个点a、c、E，假定它们处于“/直线上的统一个偏向，那么要作右单扭转，即以结点c为轴顺时针扭转，如图9.11所示。三.先左后右双向扭转如图9.12为拔出前的子树，

26、根结点a的左子树比右子树高度高1，待拔出结点x将拔出到结点b的右子树上，并使结点b的右子树高度增1，从而使结点a的均衡因子的相对值年夜于1，招致结点a为根的子树均衡被毁坏，如图9.12拔出前图9.13(a)、9.14(d)所示。h-1GhEacDhbFxh00-1hDbh-1GcFh-1hEax12-12h-1GchEaDhbFxh02a.拔出后，调剂前b.先左扭转c.再右扭转图9.13hDbh-1GcFh-1hEax2-1-1h-1cGhEaDhbFxh001h-1GchEaDhbFxh11-2d.拔出后，调剂前e.先左扭转f.再右扭转图9.14沿拔出途径反省三个点a、b、c，假定它们呈“l

27、c;/*lp指向*p左子树根结点*/(*p)-lc=lp-rc;/*lp的右子树挂接*p的左子树*/lp-rc=*p;*p=lp;/*p指向新的根结点*/voidL_Rotate(NodeType*p)/*对以*p指向的结点为根的子树，作左单扭转处置，处置之后，*p指向的结点为子树的新根*/lp=(*p)-rc;/*lp指向*p右子树根结点*/(*p)-rc=lp-lc;/*lp的左子树挂接*p的右子树*/lp-lc=*p;*p=lp;/*p指向新的根结点*/#defineLH1/*左高*/#defineEH0/*等高*/#defineRH1/*右高*/voidLeftBalance(Node

28、Type*p)/*对以*p指向的结点为根的子树，作左均衡扭转处置，处置之后，*p指向的结点为子树的新根*/lp=(*p)-lc;/*lp指向*p左子树根结点*/switch(*p)-bf)/*反省*p均衡度，并作响应处置*/caseLH:/*新结点插在*p左后代的左子树上，需作单右扭转处置*/(*p)-bf=lp-bf=EH;R_Rotate(p);break;caseEH:/*本来左、右子树等高，因左子树增高使树增高*/(*p)-bf=LH;*paller=TRUE;break;caseRH:/*新结点插在*p左后代的右子树上，需作先左后右双旋处置*/rd=lp-rc;/*rd指向*p左后代

29、的右子树根结点*/switch(rd-bf)/*修改*p及其左后代的均衡因子*/caseLH:(*p)-bf=RH;lp-bf=EH;break;caseEH:(*p)-bf=lp-bf=EH;break;caseRH:(*p)-bf=EH;lp-bf=LH;break;/*switch(rd-bf)*/rd-bf=EH;L_Rotate(&(*p)-lc);/*对*p的左子树作左扭转处置*/R_Rotate(p);/*对*t作右扭转处置*/*switch(*p)-bf)*/*LeftBalance*/intInsertAVL(NodeType*t,ElemTypee,Boolean*tall

30、er)/*假定在均衡的二叉排序树t中不存在跟e有一样要害码的结点，那么拔出一个数据元素为e的*/*新结点，并反回1，否那么反回0。假定因拔出而使二叉排序树掉掉均衡，那么作均衡扭转处置，*/*布尔型变量taller反应t长高与否*/if(!(*t)/*拔出新结点，树“长高，置taller为TURE*/*t=(NodeType*)malloc(sizeof(NodeType);(*T)-elem=e;(*t)-lc=(*t)-rc=NULL;(*t)-bf=EH;*taller=TRUE;/*if*/elseif(e.key=(*t)-elem.key)/*树中存在跟e有一样要害码的结点，不拔出*

31、/taller=FALSE;return0;if(e.keyelem.key)/*应接着在*t的左子树长进展*/if(!InsertAVL(&(*t)-lc),e,&taller)return0;/*未拔出*/if(*taller)/*已拔出到(*t)的左子树中，且左子树增高*/switch(*t)-bf)/*反省*t均衡度*/caseLH:/*本来左子树高，需作左均衡处置*/LeftBalance(t);*taller=FALSE;break;caseEH:/*本来左、右子树等高，因左子树增高使树增高*/(*t)-bf=LH;*taller=TRUE;break;caseRH:/*本来右子树高，使左、右子树