数据结构 第9章 查找1-静态查找表

第9章查找数据结构讲义-静态查找表9.1基本概念——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录(预先确定的记录的某种标志)——可以唯一标识一个记录的关键字例如“学号”例如“女”是一种数据结构——识别若干记录的关键字（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。（3)有哪些查找方法？查找方法取决于表中数据的排列方式;讨论：（1）查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。例如查字典针对静态查找表和动态查找表的查找方法也有所不同。“特定的”=关键字明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：averagesearchlength）。niiiCPASL1其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。统计意义上的数学期望值物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。（4）如何评估查找方法的优劣？针对静态查找表的查找算法主要有：9.2静态查找表静态查找表的抽象数据类型参见教材P216。一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、静态树表的查找四、分块查找（索引顺序查找）一、顺序查找（Linearsearch，又称线性查找）（1）顺序表的机内存储结构：typedefstruct{ElemType*elem;//表基址，0号单元留空。表容量为全部元素intlength;//表长，即表中数据元素个数}SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？见下页之例或教材P216；对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！（2）算法的实现：技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。例：若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0ST.elem[0].key=key;//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n1000时，查找时间将减少一半。for(i=ST.length;ST.elem[i].key!=key;--i);//不要用for(i=n;i0;--i)或for(i=1;i=n;i++)returni;//若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。}//Search_Seq算法演示——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回i=0。讨论②查找效率怎样计算？——用平均查找长度ASL衡量。讨论①查不到怎么办？讨论③如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n=(1+n)n/2未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1这是查找成功的情况若求某一个元素的平均查找次数，还应当除以n（等概率），即：ASL＝（1＋n）/2，时间效率为O(n)二、折半查找（又称二分查找或对分查找）优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL太长，时间效率太低。这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。对顺序表结构如何编程实现折半查找算法？——见下页之例，或见教材（P219）对单链表结构如何折半查找？——无法实现！因全部元素的定位只能从头指针head开始对非线性(树)结构如何折半查找？——可借助二叉排序树来查找（属动态查找表形式）。如何改进？讨论④顺序查找的特点：②运算步骤：(1)low=1,high=11,mid=6，待查范围是[1,11]；(2)若ST.elem[mid].keykey，说明key[mid+1,high]，则令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].keykey，说明key[low,mid-1]，则令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elem[mid].key=key（2）查找不成功：high≤low（意即区间长度小于0）解：①先设定3个辅助标志:low,high,mid，折半查找举例：Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置已知如下11个元素的有序表：（0513192137566475808892）,请查找关键字为21和85的数据元素。显然有：mid=(low+high)/2mjjj112讨论①若关键字不在表中，怎样得知和停止？——典型标志是：当查找范围的上界≤下界时停止查找。讨论②二分查找的效率（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次比较时查找成功的元素会有（2m-1）个；为方便起见，假设表中全部n个元素＝2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1＝推导过程平均每个数据的查找时间还要除以n，所以：（详细推导过程见教材P221的附录1）课堂练习（多项选择）：Ａ．采用链式存贮结构Ｂ．记录的长度≤128Ｃ．采用顺序存贮结构Ｄ．记录按关键字递增有序√√nnnnjnASLmjj2211log1)1(log121使用折半查找算法时，要求被查文件：思考：假设在有序线性表a[20]上进行折半查找，则平均查找长度为。查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。比较的关键字个数：为该结点在判定树上的层次数。•查找成功时比较的关键字个数最多不超过树的深度d:d=log2n+1•若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。•查找不成功的过程就是走了一条从根结点到外部结点的路径。折半查找效率分析法（参见教材P220）：三、分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。索引表最大关键字起始地址2212138920334244382448605874498653第1块第2块第3块224886例：2248861713特点：块间有序，块内无序查找步骤分两步进行：①对索引表使用折半查找法（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找效率：ASL=Lb+Lw对索引表查找的ASL对块内查找的ASL)21(log2)1(log22nASLnssnASLbsbsS为每块内部的记录个数，n/s即块的数目例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5作业假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。