《数据结构查找》PPT课件.ppt
《《数据结构查找》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《数据结构查找》PPT课件.ppt(54页珍藏版)》请在三一办公上搜索。
1、数据结构课程的内容,9.1 基本概念9.2 静态查找表9.3 动态查找表9.4 哈希表,第9章 查找,教材第8、11和12章省略,因操作系统课程会涉及。,9.1 基本概念,若表中存在特定元素,称查找成功,应输出该记录;否则,称查找不成功(也应输出失败标志或失败位置),查找表查 找查找成功查找不成功静态查找动态查找关键字主关键字次关键字,由同一类型的数据元素(或记录)构成的集合。,查询(Searching)特定元素是否在表中。,只查找,不改变集合内的数据元素。既查找,又改变(增减)集合内的数据元素。记录中某个数据项的值,可用来识别一个记录(预先确定的记录的某种标志)可以唯一标识一个记录的关键字,
2、例如“学号”,例如“女”,是一种数据结构,识别若干记录的关键字,(2)对查找表常用的操作有哪些?查询某个“特定的”数据元素是否在表中;查询某个“特定的”数据元素的各种属性;在查找表中插入一元素;从查找表中删除一元素。,(3)有哪些查找方法?查找方法取决于表中数据的排列方式;,讨论:,(1)查找的过程是怎样的?给定一个值K,在含有n个记录的文件中进行搜索,寻找一个关键字值等于K的记录,如找到则输出该记录,否则输出查找不成功的信息。,例如查字典,针对静态查找表和动态查找表的查找方法也有所不同。,“特定的”=关键字,(4)如何评估查找方法的优劣?,明确:查找的过程就是将给定的K值与文件中各记录的关键
3、字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度(ASL:average search length)。,其中:n是文件记录个数;Pi是查找第i个记录的查找概率(通常取等概率,即Pi=1/n);Ci是找到第i个记录时所经历的比较次数。,统计意义上的数学期望值,物理意义:假设每一元素被查找的概率相同,则查找每一元素所需的比较次数之总和再取平均,即为ASL。,显然,ASL值越小,时间效率越高。,针对静态查找表的查找算法主要有:,9.2 静态查找表,静态查找表的抽象数据类型参见教材P216。,一、顺序查找(线性查找)二、折半查找(二分或对分查找)三、静态树表的查找四、分块
4、查找(索引顺序查找),一、顺序查找(Linear search,又称线性查找),(1)顺序表的机内存储结构:,typedef struct ElemType*elem;/表基址,0号单元留空。表容量为全部元素 int length;/表长,即表中数据元素个数SSTable;,顺序查找:即用逐一比较的办法顺序查找关键字,这显然是最直接的办法。对顺序结构如何线性查找?见下页之例或教材P216;对单链表结构如何线性查找?函数虽未给出,但也很容易编写;只要知道头指针head就可以“顺藤摸瓜”;对非线性树结构如何顺序查找?可借助各种遍历操作!,(2)算法的实现:,技巧:把待查关键字key存入表头或表尾(
5、俗称“哨兵”),这样可以加快执行速度。,例:,若将待查找的特定值key存入顺序表的首部(如0号单元),则顺序查找的实现方案为:从后向前逐个比较!,int Search_Seq(SSTable ST,KeyType key)/在顺序表ST中,查找关键字与key相同的元素;若成功,返回其位置信息,否则返回0 ST.elem0.key=key;/设立哨兵,可免去查找过程中每一步都要检测是否查找完毕。当n1000时,查找时间将减少一半。for(i=ST.length;ST.elem i.key!=key;-i);/不要用for(i=n;i0;-i)或 for(i=1;i=n;i+)return i;/
6、若到达0号单元才结束循环,说明不成功,返回0值(i=0)。成功时则返回找到的那个元素的位置i。/Search_Seq,返回特殊标志,例如返回空记录或空指针。前例中设立了“哨兵”,就是将关键字送入末地址ST.elem0.key使之结束并返回 i=0。讨论 查找效率怎样计算?用平均查找长度ASL衡量。,讨论 查不到怎么办?,讨论 如何计算ASL?,分析:查找第1个元素所需的比较次数为1;查找第2个元素所需的比较次数为2;查找第n个元素所需的比较次数为n;,总计全部比较次数为:12n=(1+n)n/2,未考虑查找不成功的情况:查找哨兵所需的比较次数为n+1,这是查找成功的情况,若求某一个元素的平均查
7、找次数,还应当除以n(等概率),即:ASL(1n)/2,时间效率为 O(n),二、折半查找(又称二分查找或对分查找),优点:算法简单,且对顺序结构或链表结构均适用。缺点:ASL 太长,时间效率太低。,这是一种容易想到的查找方法。先给数据排序(例如按升序排好),形成有序表,然后再将key与正中元素相比,若key小,则缩小至右半部内查找;再取其中值比较,每次缩小1/2的范围,直到查找成功或失败为止。,对顺序表结构如何编程实现折半查找算法?见下页之例,或见教材(P219)对单链表结构如何折半查找?无法实现!因全部元素的定位只能从头指针head开始对非线性(树)结构如何折半查找?可借助二叉排序树来查找
8、(属动态查找表形式)。,如何改进?,讨论 顺序查找的特点:,运算步骤:(1)low=1,high=11,mid=6,待查范围是 1,11;(2)若 ST.elemmid.key key,说明keylow,mid-1,则令:high=mid1;重算 mid;(4)若 ST.elem mid.key=key,说明查找成功,元素序号=mid;结束条件:(1)查找成功:ST.elemmid.key=key(2)查找不成功:highlow(意即区间长度小于0),解:先设定3个辅助标志:low,high,mid,,折半查找举例:,Low指向待查元素所在区间的下界,high指向待查元素所在区间的上界,mid
9、指向待查元素所在区间的中间位置,已知如下11个元素的有序表:(05 13 19 21 37 56 64 75 80 88 92),请查找关键字为21 和85的数据元素。,显然有:mid=(low+high)/2,讨论 若关键字不在表中,怎样得知和停止?,典型标志是:当查找范围的上界下界时停止查找。,讨论 二分查找的效率(ASL),1次比较就查找成功的元素有1个(20),即中间值;2次比较就查找成功的元素有2个(21),即1/4处(或3/4)处;3次比较就查找成功的元素有4个(22),即1/8处(或3/8)处 4次比较就查找成功的元素有8个(23),即1/16处(或3/16)处 则第m次比较时查
10、找成功的元素会有(2m-1)个;为方便起见,假设表中全部n个元素 2m-1个,此时就不讨论第m次比较后还有剩余元素的情况了。,全部比较总次数为120221322423m2m1,推导过程,三、分块查找(索引顺序查找),这是一种顺序查找的另一种改进方法。先让数据分块有序,即分成若干子表,要求每个子表中的数值(用关键字更准确)都比后一块中数值小(但子表内部未必有序)。然后将各子表中的最大关键字构成一个索引表,表中还要包含每个子表的起始地址(即头指针)。,索引表,最大关键字,起始地址,第1块,第2块,第3块,22,48,86,例:,特点:块间有序,块内无序,查找步骤分两步进行:,对索引表使用折半查找法
11、(因为索引表是有序表);确定了待查关键字所在的子表后,在子表内采用顺序查找法(因为各子表内部是无序表);查找效率:ASL=Lb+Lw,对索引表查找的ASL,对块内查找的ASL,S为每块内部的记录个数,n/s即块的数目,例如当n=9,s=3时,ASLbs=3.5,而折半法为3.1,顺序法为5,特点:,一、二叉排序树的定义二、二叉排序树的插入与删除三、二叉排序树的查找分析四、平衡二叉树,9.3 动态查找表,表结构在查找过程中动态生成。,要求:,对于给定值key,若表中存在其关键字等于key的记录,则查找成功返回;否则插入关键字等于key 的记录。,典型的动态表二叉排序树,一、二叉排序树的定义,练:
12、下列2种图形中,哪个不是二叉排序树?,-或是一棵空树;或者是具有如下性质的非空二叉树:(1)左子树的所有结点均小于根的值;(2)右子树的所有结点均大于根的值;(3)它的左右子树也分别为二叉排序树。,讨论:对(a)中序遍历后的结果是什么?,二、二叉排序树的查找、插入与删除,将数据元素构造成二叉排序树的优点:查找过程与顺序结构有序表中的折半查找相似,查找效率高;中序遍历此二叉树,将会得到一个关键字的有序序列(即实现了排序运算);一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。如果查找不成功,能够方便地将被查元素插入到二叉树的叶子结点上,而且插入或
13、删除时只需修改指针而不需移动元素。,注:若数据元素的输入顺序不同,则得到的二叉排序树形态也不同!,这种既查找又插入的过程称为动态查找。二叉排序树既有类似于折半查找的特性,又采用了链表存储,它是动态查找表的一种适宜表示。,45,如果待查找的关键字序列输入顺序为:(24,53,45,45,12,24,90),,24,讨论1:二叉排序树的插入和查找操作,则生成二叉排序树的过程为:,例:输入待查找的关键字序列=(45,24,53,45,12,24,90),则生成的二叉排序树形态不同:,二叉排序树的查找&插入算法如何实现?,查找算法参见教材P228算法9.5(a);插入算法参见教材P228算法9.5(b
14、)_9.6;,一种“二合一”的算法如下:,BiTree SearchBST(BiTree T,KeyType key)/若查找成功,则返回指向该数据元素结点的指针,否则返回空指针 if(!T)|EQ(key,Tdata.key)return(T);/查找结束 else if LT(key,Tdata.key)/在左子树中继续查找 return(SearchBST(Tlchild,key);else return(SearchBST(Trchild,key);/在右子树中继续查找/SearchBST,Status SearchBST(BiTree T,KeyType key,BiTree f,B
15、iTree/在右子树中继续查找/SearchBST,Status InsertBST(BiTree&T,ElemType e)if(!SearchBST(T,e.key,NULL,p)/查找不成功 s=(BiTree)malloc(sizeof(BiTNode);sdata=e;slchild=srchild=NULL;/建立新结点 if(!p)T=s;/T为空树 else if LT(e.key,pdata.key)plchild=s;/被插结点*s为左孩子 else prchild=s;/被插结点*s为右孩子 return TRUE;else return FALSE;/树中已有关键字相同
16、的结点,不再插入/Insert BST,对于二叉排序树,删除树上一个结点相当于删除有序序列中的一个记录,删除后仍需保持二叉排序树的特性。(对链表进行删除操作是很方便的),讨论2:二叉排序树的删除操作,如何删除一个结点?假设:*p表示被删结点的指针;PL和PR 分别表示*P的左、右孩子指针;*f表示*p的双亲结点指针;并假定*p是*f的左孩子;则可能有三种情况:PR 为*S 的右子树;SL 为 Q(*S的双亲结点)右孩子,*p为叶子:删除此结点时,直接修改*f指针域即可;*p只有一棵子树(或左或右):令PL或PR为*f的左孩子即可;*p有两棵子树:情况最复杂,*p有两棵子树时,如何进行删除操作?
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构查找 数据结构 查找 PPT 课件
链接地址:https://www.31ppt.com/p-5519675.html