Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 ·应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序。 ·顺序表的表示和查找。 表示：typedef struct{ElemType*elem;int length;}SStable; 实现： int Search_Seq(Sstable ST,KeyType key) {ST.elem[0.]key=key;∥哨兵 for(i=ST.length;EQ(ST.elem[i].key,key );-i) return i;∥返▣O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组sT.elem 8 100 10 0 8 3 0 1 2 n-3n-2n-1n 11 SEAR
11 物料管理 SEAR 11 Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序。 • 顺序表的表示和查找。 表示：typedef struct { ElemType * elem; int length; } SStable; 实现： int Search_Seq( Sstable ST, KeyType key ) { ST.elem[0]. key = key; // 哨兵 for ( i = ST.length ; ! EQ(ST.elem[i]. key, key ) ; - - i ) return i; // 返回 0，查找失败，否则，找到key 所在的 // 数组元素的下标地址 } // Search_Seq . 0 1 2 n-3 n-2 n-1 n 数组 ST.elem key e.g: 查找 key = 8 的结点所在的数组元素的下标。 8 100 10 0 8 1 3 i
Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 ·应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序。 ·顺序表的表示和查找。 表示：typedef struct{ElemType*elem;int length;}SStable; 实现： int Search_Seq(Sstable ST,KeyType key) {ST.elem[0].key=key;∥哨兵 for(i=ST.length;EQ(ST.elem[i].key,key );-i) return i;W返回O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 查找成功，则i是key值为8的结点所在的数组元素的下标。i=n-2 key 数组ST.elem 8 100 10 0 8 1 3 0 1 2 n-3n-2 n-1 n 12 SEAR
12 物料管理 SEAR 12 Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序。 • 顺序表的表示和查找。 表示：typedef struct { ElemType * elem; int length; } SStable; 实现： int Search_Seq( Sstable ST, KeyType key ) { ST.elem[0]. key = key; // 哨兵 for ( i = ST.length ; ! EQ(ST.elem[i]. key, key ) ; - - i ) return i; // 返回 0，查找失败，否则，找到key 所在的 // 数组元素的下标地址 } // Search_Seq . 0 1 2 n-3 n-2 n-1 n 数组 ST.elem key e.g: 查找 key = 8 的结点所在的数组元素的下标。 8 100 10 0 8 1 3 查找成功，则 i 是key 值为8 的结点所在的数组元素的下标。 i i = n-2
Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 int Search_Seq(Sstable ST,KeyType key) {ST.elem[0].key=key;W哨兵 for (i=ST.length;EQ(ST.elem[i].key,key );-i) return;is∥返回O,查找失败，否则，找到key所在的 ∥ 数组元素的下标地址 }∥Search Seq ·性能分析： 平均查找长度ASL(Average Search Length) 成功查找情况下：设每个结点的查找概率相等 ASL=(n-i+1)/n i=1 (n+1)/2 一般查找情况下（包括成功、不成功两种情况）： 设成功与不成功两种情况可能性相等，每个结 点的查找概率也相等。 13 SEAR
13 物料管理 SEAR 13 Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 int Search_Seq( Sstable ST, KeyType key ) { ST.elem[0]. key = key; // 哨兵 for ( i = ST.length ; ! EQ(ST.elem[i]. key, key ) ; - - i ) return i; // 返回 0，查找失败，否则，找到key 所在的 // 数组元素的下标地址 } // Search_Seq • 性能分析： 平均查找长度ASL（Average Search Length ） 成功查找情况下：设每个结点的查找概率相等 n ASL＝∑( n-i+1) i=1 ＝ （n+1）/ 2 n 一般查找情况下（包括成功、不成功两种情况）： 设成功与不成功两种情况可能性相等，每个结 点的查找概率也相等
Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 int Search_Seq(Sstable ST,KeyType key) {sT.elem[0.]key=key;∥哨兵 for(i=ST.length;EQ(ST.elem[i].key,key);-i) return;is∥返回O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq ·性能分析： 平均查找长度ASL(Average Search Length) 一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情况 可能性相等，每个结点的查找概率也相等。 ASL= (n1)+n* 2n存1 3(n+1)/4 100 10 0 8 1131811601 0 1 2 3 4 5 6 共有n+M=7种不成功的查找情况sEAR
14 物料管理 SEAR 14 Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 int Search_Seq( Sstable ST, KeyType key ) { ST.elem[0]. key = key; // 哨兵 for ( i = ST.length ; ! EQ(ST.elem[i]. key, key ) ; - - i ) return i; // 返回 0，查找失败，否则，找到key 所在的 // 数组元素的下标地址 } // Search_Seq • 性能分析： 平均查找长度ASL（Average Search Length ） 一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情况 可能性相等，每个结点的查找概率也相等。 1 n 1 n+1 ASL＝ ∑( n-i+1) + ∑( n+1) 2n i=1 2(n+1) i=1 ＝ 3(n+1)/4 0 1 2 100 10 0 8 1 3 3 4 5 6 0 1 3 10 8 100 共有n+1=7种不成功的查找情况
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=9的结点所在的数组元素的下标地址。 查找成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem).Key<=ST.elem+1].Key;ie1,2,.n-1 ·查找范围：low(低下标)=1；high(高下标)=7（初始时为最大下标n); ·比较对象：中点元素，其下标地址为mid=(Iow+high)I2=4 mid=4但key=9<10,向左 key 4 8 9 10 11 13 19 0 2 3 4 5 6 low=1 high=7 15 SEAR
15 物料管理 SEAR 15 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=4 但 key=9 < 10, 向左 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,.n-1 • 查找范围：low（低下标）= 1; high（高下标）= 7 （初始时为最大下标n ）; • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 =4 4 8 9 10 11 13 19 3 4 5 6 7 high=7 low=1