数据基础结构 7

教案纸（首页）第1页第次课学时授课时间___________教学主题查找的概念；顺序查找和折半查找算法；索引存储结构和分块查找方法教学要求1、掌握查找的概念。2、掌握线性表的顺序查找和折半查找算法，索引存储结构和分块查找方法。教学重点顺查找算法及其性能分析；折半查找算法及其性能分析；索引存储结构和分块查找的特点教学难点顺查找算法及其性能分析；折半查找算法及其性能分析；索引存储结构和分块查找的特点教学方法讲授教学手段多媒体、板书讲授要点1、查找的定义和查找的相关概念。2、顺序查找算法及其性能分析。3、折半查找算法及其性能分析。4、索引存储结构和分块查找算法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第1页教学内容备注与后记9.1查找查找（searching）根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。若表中存在这样的一个元素，则称查找是成功的，此时查找的结果为给出整个数据元素的信息，或指示该数据元素在查找表中的位置；若表中不存在这样的元素，则称查找不成功，此时查找的结果可给出一个"null"元素（或空指针）如何评价查找算法的时间效率？由于查找算法中为确定其关键字等于给定值的数据元素的基本操作为"关键字和给定值相比"，因此通常以查找过程中关键字和给定值比较的平均次数作为比较查找算法的度量依据。

定义：查找过程中先后和给定值进行比较的关键字个数的期望值称作查找算法的平均查找长度(AverageSearchLength)。

对于含有n个记录的查找表，查找成功时的平均查找长度为

其中：pi为查找表中第i个记录的概率，且

为找到表中第i个记录（其关键字等于给定值）时，曾和给定值进行过比较的关键字的个数，显然，ci的值将随查找过程的不同而不同。在本章以后各节讨论中涉及的数据元素(记录)将统一定义为如下描述的类型：

typedefstruct

{

KeyTypekey;//关键字项

……//其它数据项

}ElemType;//数据元素类型

其中的关键字类型可以为整型、实型、字符型、串类型等。9.2线性表的查找1、顺序查找思路：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较：若当前扫描到的关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的记录，则查找失败。算法实现如下：intSeqSearch(RecTypeR[],intn,KeyTypek){inti=0;while(i<n&&R[i].key!=k) //从表头往后找 i++;if(i>=n) //未找到返回0 return0;else returni+1; //找到返回逻辑序号i+1}ASLASL成功=平均查找长度2、折半查找折半查找也称为二分查找，要求线性表中的记录必须己按关键字值有序（递增或递减）排列。思路：查找区间逐渐缩小（折半）算法描述如下：low、high和mid分别指向待查元素所在区间的上界、下届和中点，key为给定的要查找的值：初始时，令low=0,high=n-1，mid=(low+high)/2让key与mid指向的记录比较若key==R[mid].key，查找成功若key<R[mid].key，则high=mid-1若key>R[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败算法实现如下：intBinSearch(RecTypeR[],intn,KeyTypek){intlow=0,high=n-1,mid;while(low<=high) //当前区间存在元素时循环{ mid=(low+high)/2; if(R[mid].key==k) //查找成功返回其逻辑序号mid+1 returnmid+1; if(k<R[mid].key) //继续在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找}return0;}折半查找的平均查找长度：3、分块查找和顺序表类似，以顺序存储结构的线性表存储静态查找表中的记录，但和顺序表又有所不同，要求线性表中的记录按关键字"分段有序"(如右图所示，称它为"分块有序表")，并在建立这个"分段有序"的顺序表的同时，另建一个"索引"，索引为"索引项"的有序表，而每个索引项则由各分段的"最大关键字"和"起始序号"组成，由"分块有序表"和相应的"索引"构成一个"索引顺序表"，也是静态查找表的一种实现方法。

在索引顺序表中进行查找的过程为：首先在索引表中进行折半或顺序查找，以确定待查关键字在分块有序表中所在"块"，然后在"块"中进行顺序查找。这种查找方法被称为"索引顺序查找"或"分块查找"。

思路：均匀分块，块间有序，块内无序算法实现如下：intIdxSearch(IdxTypeI[],intb,RecTypeR[],intn,KeyTypek){ints=(n+b-1)/b; //s为每块的元素个数，即s=n/bintlow=0,high=b-1,mid,i;while(low<=high) //折半查找，找到的位置为high+1{mid=(low+high)/2;if(I[mid].key>=k)high=mid-1;elselow=mid+1;}//在主数据表的high+1块中进行顺序查找i=I[high+1].link;while(i<=I[high+1].link+s-1&&R[i].key!=k)i++;if(i<=I[high+1].link+s-1)returni+1; //查找成功，返回该元素的逻辑序号elsereturn0; //查找失败，返回0}分块查找的平均查找长度：教学总结：本章节介绍了查找的基本定义，顺序查找，折半查找和分块查找。

第次课学时授课时间________教学主题二叉排序树；平衡二叉树；B+树和B-树教学要求1、掌握二叉排序树的定义、查找和插入算法、删除过程。2、掌握平衡二叉树的特点及其调整方法。3、掌握B-树的定义和基本操作过程，B+的定义。教学重点二叉排序树的查找和插入算法设计，删除过程；平衡二叉树的调整过程和性能分析。教学难点二叉排序树的查找和插入算法设计，删除过程；平衡二叉树的调整过程和性能分析教学方法讲授+练习教学手段多媒体、上机实操讲授要点1、二叉排序树的定义、查找和插入算法、删除过程。2、平衡二叉排序树的定义、查找性能分析和调整过程。3、B-树的定义和基本操作过程B+的定义。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第1页教学内容备注与后记9.3树表的查找1、二叉排序树

定义：

二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；

（3）它的左、右子树也都分别是二叉查找树。

例如，右图所示是一棵二叉排序树。

通常情况下均以如下定义的二叉链表作为二叉排序树的存储结构。

typedefstructBiTNode{//结点结构

ElemTypedata;//数据元素

structBiTNode*lchild,*rchild;//左右孩子指针

}BiTNode,*BSTree;

二叉排序树的查找算法

在二叉排序树上进行查找的过程类似于次优查找树。

若二叉排序树为空，则查找不成功；否则

1）若给定值等于根结点的关键字，则查找成功；

2）若给定值小于根结点的关键字，则继续在左子树上进行查找；

3）若给定值大于根结点的关键字，则继续在右子树上进行查找。从这几个例子可见，在二叉查找树中进行查找的过程为：从根结点出发，沿着左分支或右分支递归进行查询直至关键字等于给定值的结点；或者从根结点出发，沿着左分支或右分支递归进行查询直至子树为空树止。前者为查找成功的情况，后者为查找不成功的情况。算法描述如下。

算法9.5

boolSearchBST(BSTreeT,KeyTypekval,BSTreef,BSTree&p)

{

//根指针T所指二叉查找树中递归查找关键字等于kval的数据元素,若查找成

//功,则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上访

//问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL

if(!T){p=f;returnFALSE;}//查找不成功

elseif(key==T->data.key)

{p=T;returnTRUE;}//查找成功

elseif(key<T->data.key)

returnSearchBST(T->lchild,key,T,p);

//返回在左子树中继续查找所得结果

elsereturnSearchBST(T->rchild,key,T,p);

//返回在右子树中继续查找所得结果

}//SearchBST需要注意的是，算法中的引用参数指针p在算法结束时的状态。若查找成功，即二叉查找树中存在等于给定值的关键字，则p指向该关键字所在结点，正如学员在上页的演示中所看到的；若查找不成功，则p应该指向查找路径上最后一个结点。二叉排序树的插入算法

对于动态查找表，在查找不成功时尚需进行插入，即当二叉查找树中不存在其关键字等于给定值的结点时，需插入一个关键字定于给定值的数据元素。

实际上，二叉查找树结构本身正是从空树开始逐个插入生成的。插入的原则为：若二叉查找树为空树，则插入的结点为新的根结点；否则，插入的结点必为一个新的叶子结点，其插入位置由查找过程确定。例如，若给定值序列为{50,30,40,80,20,36,90,40,38}，从空树起，逐个插入后构成的二叉查找树如右所示。

算法9.6

boolInsertBST(BiTree&T,ElemTypee)

{

//当二叉查找树T中不存在关键字等于e.key的数据元素时，

//插入e并返回TRUE，否则返回FALSE

if(!SearchBST(T,e.key,NULL,p){//查找不成功

s=newBiTNode;

if(!s)exit(1);//存储分配失败

s->data=e;s->lchild=s->rchild=NULL;

if(!p)T=s;//插入*s为新的根结点

elseif(e.key<p->data.key)

p->lchild=s;//插入*s为*p的左孩子

elsep->rchild=s;//插入*s为*p的右孩子

returnTRUE;

}//if

elsereturnFALSE;//树中已有关键字相同的结点，不再插入

)//InsertBST二叉排序树的删除算法

在二叉排序树上删除一个结点之后应该仍是一棵二叉树，并保持其二叉查找树的特性。

那么在二叉排序树上如何删除一个结点，即如何修改结点的指针？分三种情况讨论：

(1)被删结点为"叶子"，此时删除该结点不影响其它结点之间的关系，因此仅需修改其双亲结点的相应指针即可；

(2)被删结点只有左子树或右子树，则只需保持该结点的子树和其双亲之间原有的关系即可，即删除该结点之后，它的子树中的结点仍在其双亲的左子树或右子树上，因此只需要将其左子树或右子树直接链接到其双亲结点成为为其双亲的子树即可；

(3)被删结点的左右子树均不空。此时若将二叉查找树视作一个有序序列，为保持其左子树和其右子树间的有序关系，可将"前驱"替代被删数据元素，即将被删结点的数据元素赋值为它的"前驱"，然后从二叉查找树上删去这个"前驱"结点，使得删除一个结点之后的二叉查找树上其余结点之间的"有序"关系不变，而其前驱结点由于只有左子树容易删除。算法9.7

boolDeleteBST(BiTree&T,KeyTypekval){

//若二叉查找树T中存在关键字等于kval的数据元素时，则删除

//该数据元素结点*p，并返回TRUE；否则返回FALSE

if(!T)returnFALSE;//不存在关键字等于kval的数据元素

else{

if(kval==T->data.key)}

{DeleteNode(T);//找到关键字等于kval的数据元素

returnTRUE;}

elseif(kval<T->data.key)

returnDeleteBST(T->lchild,kval);

//返回在左子树上查找的结果

elsereturnDeleteBST(T->rchild,kval);

//返回在右子树上查找的结果

}//else

}//DeleteBST

其中删除操作过程如下所描述：

voidDeleteNode(BiTree&p){

//从二叉查找树中删除结点p，并重接它的左或右子树

if(!p->rchild){//右子树空则只需重接它的左子树

q=p;p=p->lchild;deleteq;

}

elseif(!p->lchild){//只需重接它的右子树

q=p;p=p->rchild;deleteq;

}

else{//左右子树均不空

q=p;s=p->lchild;

while(!s->rchild){q=s;s=s->rchild;}

p->data=s->data;//s指向被删结点的前驱

if(q!=p)q->rchild=s->lchild;

elseq->lchild=s->lchild;//重接*q的左子树

deletes;

}

}//Delete2、平衡二叉(查找)树

称二叉树为"平衡"指的是，它或是空树，或具有下列特性：其左子树和右子树都是平衡二叉树，且左右子树深度之差的绝对值不大于1。例如右侧上的两棵二叉树为平衡树，右侧下的两棵二叉树不是平衡树。树中结点内的数值称作结点的"平衡因子"，定义为左子树的深度减去右子树的深度。换句话说，平衡树上所有结点的平衡因子的绝对值均不大于1。可以证明，含有n个结点的平衡二叉树的深度为。因此，在平衡二叉树上进行查找时，和关键字进行比较的次数是和logn等数量级的。

"平衡"处理的原则是保证二叉查找树始终处于平衡状态。从空树起（空树是平衡树），每插入一个关键字都需要检查二叉查找树是否失去平衡，如因插入新的结点引起不平衡，则需对它进行"平衡旋转"处理。如何进行平衡旋转处理在教材和其它参考书中都有详细阐述，在此仅以一个例子作简单介绍。

假设关键字序列为{5,4,2,8,6,9}，从动画演示中可见，从空树起，依次插入5和4之后，二叉查找树仍为平衡树，但在插入2之后，它不再是平衡树。所谓"平衡旋转"处理是，在保持"查找树"的特性前提下改变结点之间的关系。例如在此时的左子树深度偏大的情况下，令左子树根为整棵树的根，而让原来的根结点成为它的右子树根。在继续插入关键字8和6之后，二叉查找树重新失去平衡，此时因为以5为根的子树为"最小不平衡子树"，故仅需对以5为根的子树进行旋转处理，但由于是因为在⑤的"右子树的左子树"上插入结点引起的不平衡，则不能简单地进行向左旋转，而是首先令⑧为⑥的左子树根（向右旋转），然后令⑤为⑥的右子树根（向左旋转）。最后由于插入关键字9使查找树失去平衡，此时以④为根的二叉树是最小不平衡子树，并且因为是在④的"右子树的右子树"上插入结点引起的不平衡，故仅需进行一次"向左旋转"处理即可。当生成二叉查找树的关键字序列非随机时，所生成的二叉查找树有可能偏向于单支，从而使其查找性能接近于顺序表。在这种情况下，需要在生成二叉查找树的过程中进行"平衡"处理，使得在任何时刻二叉查找树的形态都是"平衡"的。

3、B+树和B-树（了解内容）第次课学时授课时间______教学主题哈希表教学要求1、掌握哈希表的定义及其特点。2、掌握哈希函数构造方法和解决冲突的方法。教学重点哈希函数的定义；哈希函数构造方法和解决冲突的方法教学难点哈希函数构造方法和解决冲突的方法法教学方法讲授教学手段多媒体、板书讲授要点1、哈希表的定义及其特点。2、哈希函数构造方法和解决冲突的方法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）教学内容备注与后记哈希表的查找何谓哈希表

对于以上两节中讨论的各种结构，它们的平均查找长度不仅不可能为0，并且都随n（关键字集合的大小）的增长而增长。因为无论是在表示静态查找表的顺序表和有序表中，还是动态查找树表中，数据元素在结构中的位置都是随机的，和它的关键字无关。在这样的结构中进行查找的主要操作就是将给定值和表中关键字进行依次比较，其查找效率取决于比较次数。如果希望不经过比较直接取得其关键字等于给定值的记录，只能是在确定知晓该关键字在表中位置的情况下。例如，某城市人口调查表中的关键字为"年龄"，当以表长为120的有序表表示时，查询年龄为60岁的人口数时只需要直接取表中第60项的记录即可，显然，此时的平均查找长度为0。一般情况下，可设记录在表中的位置为关键字的某个函数，通常称这种函数为"哈希函数"。

例如，对于关键字序列{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}，可设关键字的哈希函数如下：

其中，CH1表示关键字中第1个字母，Ord为字符的次序函数。则以表长为14的顺序表表示的查找表如右所示。显然，此查找表的平均查找长度为0，若给定值为Qian，由上述关键字函数得到函数值为8，即可从"地址为8"的表中取得该记录。但这样的函数并不容易设计，如果同时存在关键字Zhou，则上述函数不可取，换句话说，为使平均查找长度等于0，必须找到一个能将查找表中所有关键字都"散列"在表中不同位置的哈希函数。若关键字不同而函数值相同，则称这两个关键字（对于该哈希函数而言）为"同义词"，并称这种现象为"冲突"。对于动态查找表很难找到不存在同义词的哈希函数，唯一弥补的办法是，在发生冲突时设法解决之，例如将关键字Zhou存入表中地址为0的空缺中等。

综合以上所述，可如下定义哈希表：

根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的"象"作为相应记录在表中的存储位置，这种表被称为哈希表，这一映象的过程亦被称为"散列"。构造哈希函数的方法

若对于关键字集合中的任意一个关键字，经哈希函数映象到地址集合中任何一个地址的概率相等，则称此类哈希函数为均匀的哈希函数。对数值型的关键字，常用的构造均匀的哈希函数的方法有如下几种：

一、直接定址法

取关键字本身或关键字的某个线性函数值作为哈希表的地址。

即Hash(key)=key或Hash(key)=akey+b（a和b均为常数）

直接定址所得地址集的大小和关键字集的大小相同，关键字和地址一一对应，决不会产生冲突。但实际应用中能采用直接定址的情况极少。二、数字分析法

如果可能出现的关键字的数位相同，且取值事先知道，则可对关键字进行分析，取其中"分布均匀"的若干位或它们的组合作为哈希表的地址。

例如已知80个记录的关键字为8位十进制数（右图列出其中部分），假设哈希表的表长为100，即地址为00～99。由于关键字中的第1、2、3和8位取值集中在某几个数上，则应取其余四位中的任意两位或其中两位与另两位之叠加和（舍去进位）作为哈希地址。三、平方取中法

如果关键字的所有各位分布都不均匀，则可取关键字的平方值的中间若干位作为哈希表的地址。由于一个数的平方值的中间几位数受该数所有位影响，将使随机分布的关键字得到的哈希函数值也随机。四、折叠法

若关键字的位数很多，且每一位上数字分布大致均匀，则可采用移位叠加或间界叠加，即将关键字分成若干部分，然后以它们的叠加和(舍去进位)作为哈希地址。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。

例如，key=110108780428895，则其移位叠加得到的哈希地址为321，间界叠加得到的哈希地址为410。(哈希表的表长为1000)

五、除留余数法

以关键字被某个数p除后所得余数作为哈希地址。即

Hash(key)=keyMODp

其中，MOD表示"取模"运算，p为不大于表长的素数或不包含小于20的质因素的合数。

六、随机数法

当关键字不等长时，可取关键字的某个伪随机函数值作为哈希地址。

Hash(key)=random(key)

对于非数值型关键字，则需先将它们转化为数字。实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。处理冲突的方法

有两类处理冲突的方法。

一、开放定址法

开放定址处理冲突的办法是，设法为发生冲突的关键字"找到"哈希表中另一个尚未被记录占用的位置。

令

上式的含义是，已知哈希表的表长为m（即哈希表中可用地址为：0～m-1），若对于某个关键字key，哈希表中地址为Hash(key)的位置已被占用，则为该关键字试探"下一个"地址H1=(Hash(key)+d1)MODm，若也已被占用，则试探再"下一个"地址H2=(Hash(key)+d2)MODm，…，依次类推直至找到一个地址H3=(Hash(key)+d3)MODm未被占用为止。即Hi是为解决冲突生成的一个地址序列，其值取决于设定"增量序列di"。对于di通常可有三种设定方法：

1）di=1,2,3,…,m-1，称这种处理冲突的方法为"线性探测再散列"。

例如右侧所示哈希表，当插入关键字23(Hash(23)=1)时，出现冲突现象，取增量di=1，求得处理冲突后的哈希地址为(1+1=)2；又如，在插入关键字36(Hash(36)=3)时，因哈希表中地址为3,4,5和6的位置均已存放记录，因此取增量dk=4，即处理冲突后的哈希地址为(3+4=)7。

2）di=12，-12，22，-22，…，±k2(k≤m/2)，称这种处理冲突的方法为"平方探测再散列"。

例如右侧所示按平方探测构建的哈希表中，对于关键字68（Hash(68)=2），因表中地址为2,3和1的位置均已填入记录，因此取增量d3=22，即处理