数据结构-第8章-查找(作业)只是课件.ppt

《数据结构-第8章-查找(作业)只是课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构-第8章-查找(作业)查找：根据给定的关键字值，在查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。8.2静态查找表8.2.1顺序查找法顺序查找法的过程是：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，否则查找失败。存储结构通常为顺序结构，也可为链式结构。//静态查找表的顺序存储结构typedefstruct{ElemType*elem;//

2、数据元素存储空间基址，建//表时按实际长度分配，0号单元留空intlength;//表长度}SSTable;基于顺序结构的算法如下：intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。算法9.1inti;ST.elem[0].key=key;//哨兵for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前找returni;//找不到时，i为0}其中ST.elem[0]称为监视哨，可以起到防止越界的作

3、用。8.2.2有序表的查找折半查找法又称二分法查找法，这种方法适用于有序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。图8.1折半查找示意图折半查找的算法如下：intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中

4、的位置，否则为0。算法9.2low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)//找到待查元素returnmid;elseifLT(key,ST.elem[mid].key)high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}8.2.3索引顺序表的查找（分块查找法）分块查找法要求将列表组织成以下索引顺序结构：首先将列表分成若干个块(子表)。一般情况下

5、，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。图8.2分块查找法示意图下图的索引顺序表包括三个块，第一个块起始地址0，块内最大关键字25；第二个块起始地址为5，块内最大关键字58；第三个块起始地址为10，块内最大关键字为88。分块查找的基本过程如下：(1)首先将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。(2)用顺序查找法在相应块内查找关键字为

6、K的元素。例如，在上述索引顺序表中查找36。首先，将36与索引表中的关键字进行比较，因为25＜36≤58，所以36在第二个块中，进一步在第二个块中顺序查找，最后在8号单元中找到36。8.3动态查找表动态查找表的特点是表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。主要包括二叉排序树、平衡二叉树等。8.3.1二叉排序树二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树非空，则右子树上所有结点的

7、值均大于根结点的值；（3）它的左右子树也分别为二叉排序树。图8.3二叉排序树在下面讨论的二叉排序树的操作中，使用二叉链表作为存储结构，其结点结构说明如下：typedefstructnode{KeyTypekey;//关键字的值structnode*lchild,*rchild;//左右指针}BSTNode,*BSTree;1.二叉排序树的插入和生成已知一个关键字值为key的结点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入可以用下面的方法进行：①若二叉排序树是空树，则key成为二叉排序树的根；②若二叉