实施査找时有两种不同的环境 静态环境查找结构不需进行插入和 删除操作。 静态查找表 动态环境查找过程中可能要对查找 结构执行数据插入、删除或修改等操 作,并对查找结构进行调整,结构可 能发生变化。 动态查找表 动态查找表的表结构是在查找过程中动态生成 的。 第6页
实施查找时有两种不同的环境 ◼ 静态环境 查找结构不需进行插入和 删除操作。 ⎯ 静态查找表 第 6 页 ◼动态环境 查找过程中可能要对查找 结构执行数据插入、删除或修改等操 作，并对查找结构进行调整，结构可 能发生变化。 ⎯ 动态查找表 ◼动态查找表的表结构是在查找过程中动态生成 的
11顺序查找( Sequential Search >以线性结构表示静态查找表。 >基本原理:将待查找记录依 次逐个与表中记录进行比较。 第7页
第 7 页 ➢以线性结构表示静态查找表。 ➢基本原理：将待查找记录依 次逐个与表中记录进行比较。 1.1 顺序查找（Sequential Search)
顶序查找过程(从前向后查找 SLelem 213788199205645680753 01234567891011 假设给定查找值e=64, ST Length=11 要求 SL elema=e,问:k=? 第8页
第 8 页 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length=11 SL.elem 顺序查找过程（从前向后查找） 假设给定查找值 e=64, 要求 SL.elem[k] = e, 问: k = ? k k
顺序查找过程(从后向前查找) 0单元用于存放待查找关键字,作为“哨兵”( guard) SLelem 返回7i 642137881992056456807513 01234567891011 key=64 ST Length=ll 返回0 SL elem 602137881992056456807513 01234567891011 key=60 T Length=112页
第 9 页 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length=11 SL.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length=11 SL.elem i 60 i key=64 key=60 i 64 顺序查找过程（从后向前查找） 0单元用于存放待查找关键字，作为“哨兵”(guard) 返回0 返回7
顺序查找算法实现(从后向前查找) int Search Seq( tb sl, type key SLelem[o].key=key;“哨兵” for (i=SL length; SL elem[i]. key =key );∥/从后往前找 return i;/查找成功时为有效下标否则为0 第10页
第 10 页 int Search_Seq( TB SL, TYPE key ) { SL.elem[0].key = key; // “哨兵” for (i=SL.length; SL.elem[i].key!=key; --i); // 从后往前找 return i; // 查找成功时i为有效下标,否则i为0 } 顺序查找算法实现（从后向前查找）