a数据结构课件第9章查找.pptxVIP

第9章 查找9.1 基本概念9.2 静态查找表9.3 动态查找表9.4 哈希表9.1 基本概念是一种数据结构查找表 查 找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别记录 (预先确定的记录的某种标志 ) ——可以唯一标识一个记录的关键字例如“学号”——识别若干记录的关键字例如“女”讨论：讨论1：查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行有哪些信誉好的足球投注网站，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。讨论2：对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。 “特定的”=关键字讨论3：有哪些查找方法？ 查找方法取决于表中数据的排列方式;例如查字典针对静态查找表和动态查找表的查找方法也有所不同。nASL=∑PiCii=1讨论4：如何评估查找方法的优劣？明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL。Average Search Length其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）;Ci是找到第i个记录时所经历的比较次数。物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。 9.2 静态查找表针对静态查找表的查找算法主要有：一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、分块查找（索引顺序查找）一、顺序查找（ Linear search，又称线性查找 ）顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直接的办法。 对顺序结构如何顺序查找？对单链表结构如何顺序查找？对非线性树结构如何顺序查找?（1）顺序表的机内存储结构：typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数}SSTable;（2）算法的实现：技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。例：若将待查找的特定值key存入顺序表的首部（如0号单元），并从后向前逐个比较,就不必担心“查不到”。int Search_Seq( SSTable ST , KeyType key ){ST.elem[0].key =key; for( i=ST.length; ST.elem[ i ].key!=key; - - i ); return i;} // Search_Seq//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n1000时，查找时间将减少一半。//不要用for(i=1; i=n; i+ +) 或for(i=n; i0; - -i)//找不到=不成功，返回值必为i=0； 找得到=成功，返回值i正好代表所找元素的位置。讨论1：查找失败怎么办？——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束，并返回 i=0。讨论2：查找效率怎样计算？——用平均查找长度ASL衡量。讨论3：如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n = (1+n)n/2若求某一个元素的平均查找次数，还应当除以n（等概率），即： ASL＝（1＋n）/2，时间效率为 O(n)这是查找成功的情况讨论4：顺序查找的特点：优点：算法简单，且对顺序结构或链表结构均适用。缺点： ASL 太大，时间效率太低。如何改进？二、折半查找（又称二分查找或对分查找）这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将key与中间元素相比，若key大，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。对顺序表结构如何编程实现折半查找算法？ ——见下页之例，或见教材（P219）对单链表结构如何折半查找？ ——无法实现！因全部元素的定位只能