数据结构第8章(查找)ppt课件.ppt

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

1、1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索（查找）、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构第八章查找本章要点8.1基本概念8.2顺序表8.3索引顺序表（简单，自己看）8.4二叉排序树8.5平衡二叉树（删除）8.6B-树（删除）8.7散列表查找（重点）本章小结8.1基本概念数据表：各种数据元素的有限集合。关键字（key）：唯一区分一条记录的字段。查找：就是在数据表中确定是否存在某记录的关键字等于给定值的过程。查找方

2、法：静态查找、动态查找（查找失败是将记录插入）衡量查找算法优劣指标：平均查找长度如对n个记录进行查找时，平均查找长度可表示为：Pi表示第i个数据元素被查找到的概率Ci表示查找此数据元素所需进行关键字的比较次数本章要点8.1基本概念8.2顺序表8.3索引顺序表（简单，自己看）8.4二叉排序树8.5平衡二叉树（删除）8.6B-树（删除）8.7散列表查找（重点）本章小结顺序表：采用顺序存储结构的表称为顺序表。基本思想：从表的一端开始顺序扫描，依次将表中的结点关键字和给定值进行比较，若两者相等，则查找成功；若扫描结束后

3、，还未找到与给定值相等的关键字，则查找失败。下面的算法描述了顺序查找过程。8.2顺序表待查找表的数据结构描述如下：typedefStruct{…………KeyDataKey,}DataType;typedefstruct{DataType*elem;//数据元素存储空间地址intlength;//表的长度}SeqTable;顺序查找算法intSeqSearch(SeqTables,KeyTypek)//在表s中顺序查找关键字k，若查找成功，则函数值为该元素在表中的位置，//若查找失败，返回-1。{inti;for

4、(i=0;i

5、}8.2.1顺序查找(3)从链表的第一个元素结点起，判断当前结点其值是否等于，若是，返回该结点的指针，否则继续下一个结点的查找，直到表结束为止。找不到，则返回空。算法如下：Item*Link::Locate(DataTypex){Item*p;p=head->next;while((p!=NULL)&&(p->data!=x))p=p->next;returnp;}复习单链表的查找方法：二分法思想：假设在210个记录中查询普通方法：最多比较1024次二分法：8.2.2有序表的查找(1)1248163264128

6、2565121024第一次划分第二次划分第三次划分……第十次折半查找基本思想：设表中的结点按关键字递增有序，首先将待查值k和表中间位置上的结点关键字进行比较，若两者相等(k＝A[mid].key),则查找成功；若k值小(kA[mid].key)，则在表的后半部继续利用折半查找法查找。这样，经过一次关键字比较就缩小一半的查找区间，如此进行下去，直到查找到该关键字或查找失败。【例1】已知有11个关键字的有序表序列如下所示：02，08，15，

7、23，31，37，42，49，67，83，91当给定的k值为23和83时，画出折半查找的过程，用“↑”指向中间位置。Low＝0；High＝n-1Low<=highMid与key相等Mid＝[low＋high]/2Returnmidkey>MidReturn-1Low＝mid＋1High＝mid-1开始结束TFTFFTintBinSearch(SeqTables,KeyTypek)//在表s中用折半查找法查找关键字k，若查找成功，则函数值为该元素在表中的位置，若查找失败，返回-1。{intlow,mid,high

8、;low=0;high=s.length-1;while(low<=high){mid=(low+high)/2;//取区间中点if(s.elem[mid].key==k)//查找成功return(mid);elseif(s.elem[mid].key>k)//在左区间中查找high=mid-1;elselow=mid+1;//在右区间中查找}return(-1);//查找失败}8.2