9.2静态查找表 针对静态查找表的查找算法主要有： 一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、分块查找（索引顺序查找） 四、静态树表的查找 ADT StaticSearchTable 静态查找表的定义 数据对象D: (抽象数据类型) 参见教材P216 数据关系R: 基本操作P: ADT StaticSearchTable
6 针对静态查找表的查找算法主要有： 9.2 静态查找表 静态查找表的定义 （抽象数据类型） 参见教材P216 一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、分块查找（索引顺序查找） 四、静态树表的查找 ADT StaticSearchTable { 数据对象D: 数据关系R： 基本操作P： } ADT StaticSearchTable
顺序查找(Linear search,又称线性查找) 顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直 接的办法。 冬对顺序结构如何线性查找？ 见下页之例或教材P216 ÷对单链表结构如何线性查找？ 从头指针始“顺藤摸瓜” 冬对非线性树结构如何顺序查找？ 借助各种遍历操作！ (1)顺序表的机内存储结构： typedef struct ElemType *elem; /表基址，0号单元留空。表容量为全部元素 int length;/表长，即表中数据元素个数 SSTable;
7 一、顺序查找（ Linear search，又称线性查找 ） （1）顺序表的机内存储结构： typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数 }SSTable; 顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直 接的办法。 ❖ 对顺序结构如何线性查找？ ❖ 对单链表结构如何线性查找？ ❖ 对非线性树结构如何顺序查找? 见下页之例或教材P216 从头指针始 “顺藤摸瓜” 借助各种遍历操作！
(2)算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”)， 这样可以加快执行速度。 例：若将待查找的特定值key存入顺序表的首部（如0号单 元)，并从后向前逐个比较，就不必担心“查不到”。 int Search_Seq(SSTable ST,KeyType key ) ST.elem[0/在顺序表ST中，查找关键字与key相同的元素； 若成二a甘位置信息否训返回0 for(=ST/设立哨兵，可免去查找过程中每一步都要检 还查找完毕。当n>1000时，查找时间将 测 return减 /不要用for(i=l;i<=n;i++) /Sea /找不到 或for(i=n;i>0;-i 找得到=成功，返回值正好代表所我元素的位置！
8 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 （2）算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”）， 这样可以加快执行速度。 例：若将待查找的特定值key存入顺序表的首部（如0号单 元），并从后向前逐个比较,就不必担心“查不到” 。 //在顺序表ST中，查找关键字与key相同的元素； 若成功，返回其位置信息，否则返回0 //设立哨兵，可免去查找过程中每一步都要检 测是否查找完毕。当n>1000时，查找时间将 减少一半。 //找不到=不成功，返回值必为i=0； 找得到=成功，返回值i正好代表所找元素的位置。 //不要用for(i=1; i<=n; i+ +) 或 for(i=n; i>0; - -i)
讨论1：查找失败怎么办？ 返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”， 就是将关键字送入未地址sT.elem[0].key使之结束，并返回i=0。 讨论2：查找效率怎样计算？ 用平均查找长度ASL衡量。 讨论3：如何计算ASL? 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； 未考虑查找不成功的情况：查 找哨兵所需的比较次数为n+1 查找第n个元素所需的比较次数为n; 总计全部比较次数为：1+2+.+n=(1+n)n/2 若求某一个元素的平均查找次数，还应当除以（等概率）， 即：ASL=(1+n)2,时间效率为O() 这是查找成功的情况
9 ——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵” ， 就是将关键字送入末地址ST.elem[0].key使之结束，并返回 i=0。 讨论2：查找效率怎样计算？ ——用平均查找长度ASL衡量。 讨论1：查找失败怎么办？ 讨论3：如何计算ASL？ 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； . 查找第n个元素所需的比较次数为n； 总计全部比较次数为：1＋2＋.＋n = (1+n)n/2 未考虑查找不成功的情况：查 找哨兵所需的比较次数为n+1 这是查找成功的情况 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL＝（1＋n）/2 ，时间效率为O(n)
讨论4：顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。 缺点：ASL太大，时间效率太低。 如何改进？ 二、折半查找（又称二分查找或对分查找） 这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将ky 与正中元素相比，若key小，则缩小至右半部内查找；再取其中 值比较，每次缩小1/2的范围，直到查找成功或失败为止。 冬对顺序表结构如何编程实现折半查找算法？ 见下页之例，或见教材（P219) ?·对单链表结构如何折半查找？ 无法实现！因全部元素的定位只能从头指针head开 始 冬对非线性（树）结构如何折半查找？ 可借助叉排序树来查找（属动态查找表形式）
10 二、折半查找（又称二分查找或对分查找） 优点：算法简单，且对顺序结构或链表结构均适用。 缺点：ASL 太大，时间效率太低。 这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将key 与正中元素相比，若key小，则缩小至右半部内查找；再取其中 值比较，每次缩小1/2的范围，直到查找成功或失败为止。 ❖ 对顺序表结构如何编程实现折半查找算法？ ——见下页之例，或见教材（P219） ❖ 对单链表结构如何折半查找？ ——无法实现！因全部元素的定位只能从头指针head开 始 ❖ 对非线性(树)结构如何折半查找？ ——可借助二叉排序树来查找（属动态查找表形式）。 讨论4：顺序查找的特点： 如何改进？