文本教程第六章查找

1、1 物料管理物料管理SEAR11、静态查找表、静态查找表2、动态查找表、动态查找表3、哈希查找表哈希查找表目录目录 查找查找2 物料管理物料管理SEAR21、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内结点之间可无序。表内结点之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; / 此处此处length = n 实现：int Search_Seq( Sstable ST, KeyTy

2、pe key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回返回 0，查找失败，否则，找到，查找失败，否则，找到 key 所在的所在的 / 数组元素的下标地址数组元素的下标地址 / 注意：本语句的循环体语句为空语句注意：本语句的循环体语句为空语句 ： 012n-3n-2n-1ni数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。8100100713设置哨兵的好处：设置哨

3、兵的好处： 在顺序表中总可以找到在顺序表中总可以找到给定关键字的给定关键字的结点结点（虽然（虽然意味着查找失败）意味着查找失败） 。若不若不设该单元，则设该单元，则必须将判断必须将判断条件条件 i 0 加进加进 for语句之语句之中，每次循环都要判断一中，每次循环都要判断一次。次。 / n： 结点结点总总数数3 物料管理物料管理SEAR31、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struc

4、t ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素

5、的下标。8100100713i4 物料管理物料管理SEAR41、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST

6、.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。8100100713i5 物料管理物料管理SEAR51、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和

7、查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye.g: 查找查找 key = 8 的结点

8、所在的数组元素的下标的结点所在的数组元素的下标。8100100713i6 物料管理物料管理SEAR61、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i =

9、 ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。8100100713i7 物料管理物料管理SEAR71、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无

10、序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye

11、.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。8100100713i8 物料管理物料管理SEAR81、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key =

12、 key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。查找失败，则查找失败，则 i = 0; 8100100713i9 物料管理物料管理SEAR91、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：

13、顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 /

14、Search_Seq012n-3n-2n-1ni数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。810010081310 物料管理物料管理SEAR101、静态查找表、静态查找表1、顺序表的查找、顺序表的查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq(

15、 Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。8100100813i11 物料管理物料管理SEAR111、静态查找表、静态查找表1、顺序表的查找、顺序表的

16、查找 应用范围：顺序表或线性链表表示的应用范围：顺序表或线性链表表示的静态查找表静态查找表。表内元素之间可无序。表内元素之间可无序。 顺序表的表示和查找。顺序表的表示和查找。 表示：typedef struct ElemType * elem; int length; SStable; 实现：int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找

17、到 key 所在的 / 数组元素的下标地址 / Search_Seq012n-3n-2n-1n数组数组 ST.elem keye.g: 查找查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。8100100813 查找成功，则查找成功，则 i 是是key 值为值为 8 的结点所在的数组元素的下标的结点所在的数组元素的下标。ii = n-212 物料管理物料管理SEAR121、静态查找表、静态查找表1、顺序表的查找、顺序表的查找int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for (

18、 i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq 性能分析：性能分析： 平均查找长度平均查找长度ASL（Average Search Length ） 成功查找情况下：设每个结点的查找概率相等成功查找情况下：设每个结点的查找概率相等 1 ASL ( n-i+1) i=n n （n+1）/ 2 一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种

19、情 况可能性相等，每个结况可能性相等，每个结 点的查找概率也相等。点的查找概率也相等。 012100013345610813 物料管理物料管理SEAR131、静态查找表、静态查找表1、顺序表的查找、顺序表的查找int Search_Seq( Sstable ST, KeyType key ) ST.elem0. key = key; / 哨兵 for ( i = ST.length ; ! EQ(ST.elemi. key, key ) ; - - i ); return i; / 返回 0，查找失败，否则，找到 key 所在的 / 数组元素的下标地址 / Search_Seq 性能分析：性能

20、分析： 平均查找长度平均查找长度ASL（Average Search Length ） 一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情况一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情况 可能性相等，每个结点的查找概率也相等。可能性相等，每个结点的查找概率也相等。 3(n+1)/4 0121001008133456310108100共有共有n+1=7种不成功的查找情况种不成功的查找情况) 1(21 1)n (21 1)i -n (11ni1ninn14 物料管理物料管理SEAR141、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法

21、）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=4 但但 key=9 10, 向左向左keye.g: 查找查找 key = 9 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下

22、标）= 7 （初始时为最大下标（初始时为最大下标 n ）; 比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 =4 4 8 9 10 11 13 1934567high=7low=115 物料管理物料管理SEAR151、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=4keye.g: 查找查找 key = 9 的结点所在的数组元素的下标地址的结点所在的

23、数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 3 ; 4 8 9 10 11 13 1934567high=3（mid-1）low=116 物料管理物料管理SEAR161、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接

24、用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=2keye.g: 查找查找 key = 9 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key 8, 向右向右keye.g: 查找查找 key = 9 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增

25、序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 3 ; 比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 =2 4 8 9 10 11 13 1934567high=3（mid-1）low=118 物料管理物料管理SEAR181、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表

26、内元素之间有序。不可直接用于线性链表。012keye.g: 查找查找 key = 9 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 3; high（高下标）高下标）= 3 ; 4 8 9 10 11 13 1934567high=3low=3（mid+1）mid=219 物料管理物料管理SEAR191、静态查找表、

27、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=3; keye.g: 查找查找 key = 9 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）

28、= 3; high（高下标）高下标）= 3 ; 比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 = 3 4 8 9 10 11 13 1934567high=3low=320 物料管理物料管理SEAR201、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=3; 但但 key=9 中点值也为中点值也为 9 ，找到，找到keye.g: 查找查找 key

29、= 9 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 3 ; 比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 = 3 4 8 9 10 11 13 1934567high=3low=321 物料管理物料管理SEAR211、

30、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=4 但但 key=5 10, 向左向左keye.g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找不成功的情况：数组查找不成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-

31、1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 7 （初始时为最大下标（初始时为最大下标 n ）; 比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 4 8 9 10 11 13 1934567high=7low=122 物料管理物料管理SEAR221、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=4keye.

32、g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找不成功的情况：数组查找不成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 3 ; 4 8 9 10 11 13 1934567high=3（mid-1）low=123 物料管理物料管理SEAR231、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查

33、找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=2keye.g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找不成功的情况：数组查找不成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 3 ; 比较对象：中

34、点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 =2 4 8 9 10 11 13 1934567high=3low=124 物料管理物料管理SEAR241、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=2; 但但 key=5 8, 向左向左keye.g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：

35、数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 3 ; 比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 =2 4 8 9 10 11 13 1934567high=3low=125 物料管理物料管理SEAR251、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（

36、或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=2keye.g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 1 ; 4 8 9 10 11 13 1

37、934567high=1（mid-1）low=126 物料管理物料管理SEAR261、静态查找表、静态查找表2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=1keye.g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key 4, 向右

38、向右keye.g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key 4, 向右向右key 4 8 9 10 11 13 1934567high=1low=2 （mid+1）失败条件：失败条件：low high; 处于间处于间隙中的键值导致这种情况！隙中的键值导致这种情况！ 折半查找（或二分查找法）折半查找（或二分查找法）1、顺序表，表内元素之间有序。不可直接用于线性链表。、顺序表，表内元素之间有序

39、。不可直接用于线性链表。e.g: 查找查找 key = 5 的结点所在的数组元素的下标地址的结点所在的数组元素的下标地址。查找成功的情况：数组查找成功的情况：数组 ST.elem 如下图所示有序如下图所示有序 数组数组 ST.elem ：递增序：递增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1 查找范围查找范围 ：low（低下标）低下标）= 1; high（高下标）高下标）= 1 ; 比较对象：中点元素，其下标地址为比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 = 129 物料管理物料管理SEAR291、静态查找表、静态

40、查找表 表示：typedef struct ElemType * elem; int length; SStable; / length = nint Search_bin ( SStable ST, KeyType key ) / 在有序表中查找关键字之值为 key 的结点，找到返回该结点 / 在表中的下标地址，否则返回 0 low = 1 ; high = ST.length ; while ( low = high ) mid = ( low + ligh ) / 2 ; if ( EQ(ST.elemmid. key, key ) return mid ; else if ( LT(

41、key , ST.elemmid. key ) ) high = mid -1 ; else low = mid + 1; return 0 ； / Search_Bin2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）2、程序实现程序实现30 物料管理物料管理SEAR301、静态查找表、静态查找表 2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）3、性能分析：、性能分析： 1、最坏情况分析：设、最坏情况分析：设 key 和中点的二次比较的时间代价和中点的二次比较的时间代价 1 如果如果 n = 1, 则则 low = high =

42、 mid , 则代价为则代价为 1，记为，记为 S（1） 1 如果如果 n 是奇数，那么中点元素的左、右段各有是奇数，那么中点元素的左、右段各有 (n-1)/2 个元素个元素 如果如果 n 是偶数，中点元素的左段有是偶数，中点元素的左段有 n/2-1 个元素；右段有个元素；右段有 n/2 个元素个元素 因此，算法工作的那一段，最多有因此，算法工作的那一段，最多有 n/2 项项 S（n）= 1 + S（ n/2 ）= 1 + 1 + S（ n/22 ）= 1 + 1 + 1 + S（ n/23 ） = 1 + 1 + 1 + + 1 + S（ n/2k ）注意：注意：(n-1)/2 = n/2

43、注意：注意：n/2 = n/2 总共总共 K 个个 1 当当 1 = n/2k 2 时；则时；则 n/2k = 1 此时：此时： 2k = n 2k+1 即即 k = log2n k+1注意：注意：k 不可为小数，它是正整数。不可为小数，它是正整数。 k = log2n 故：故： S（n）= 1 + log2n 31 物料管理物料管理SEAR311、静态查找表、静态查找表012mid= 4 4 8 9 10 11 13 1934567high=7low=1012mid= 4 4 8 9 10 11 13 1934567low=1 20high=8832 物料管理物料管理SEAR321、静态查找

44、表、静态查找表 2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）3、性能分析：、性能分析： 1、最坏情况分析：、最坏情况分析： 定理：在最坏情况下，二分查找法的查找有序表的最大的比较次数为定理：在最坏情况下，二分查找法的查找有序表的最大的比较次数为 1+ log2n ，大体上和大体上和 log2n 成正比。成正比。 也可用判定树的方法进行推导。也可用判定树的方法进行推导。 如：如：16735248key = k4?012345678489101113192912345678 当寻找当寻找 key = 8 及小于、大及小于、大 于于 8 的键值的相应结点时，的键值

45、的相应结点时， 查找次数最大。达到了判定查找次数最大。达到了判定 树的高度。树的高度。 注意：当判定树为注意：当判定树为 n = 2t -1 （ t=1,2,3 ）时，为丰满树。否时，为丰满树。否 则，除最下一层外，余为丰满树。则，除最下一层外，余为丰满树。33 物料管理物料管理SEAR331、静态查找表、静态查找表 2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）3、性能分析：、性能分析： 2、平均情况分析（在成功查找的情况下）：设每个、平均情况分析（在成功查找的情况下）：设每个 结点的查找概率相同都为结点的查找概率相同都为 1/n。为了简单起见，设结点个数为

46、为了简单起见，设结点个数为 n = 2t -1 （t = 1,2,3 ）。）。 经过经过 1 次比较确定的结点个数为次比较确定的结点个数为 1 = 20 个个 ，红色标识的结点。，红色标识的结点。 经过经过 2 次比较确定的结点个数为次比较确定的结点个数为 2 = 21 个个 ，绿色标识的结点。，绿色标识的结点。 经过经过 3 次比较确定的结点个数为次比较确定的结点个数为 4 = 22 个个 ，灰色标识的结点。，灰色标识的结点。. 经过经过 t 次比较确定的结点个数为次比较确定的结点个数为 2t-1 个个 ，黑色标识的结点。，黑色标识的结点。 注意：注意： 20 + 21 + 22 + + 2

47、t-1 = 2t -1 最多经过最多经过 t 次比较可以找到有序表中的任何一个结点次比较可以找到有序表中的任何一个结点 e.g: 当当 t = 4 时的例子：最多经过时的例子：最多经过 t=4 次比较找到任何一个结点次比较找到任何一个结点48910 111319291234567832476577819399910111213141534 物料管理物料管理SEAR341、静态查找表、静态查找表 2、有序表的查找、有序表的查找 折半查找（或二分查找法）折半查找（或二分查找法）3、性能分析：、性能分析： 2、平均情况分析（在成功查找的情况下）：、平均情况分析（在成功查找的情况下）： ASL = (

48、 201 + 212 + 223 + + 2t-1 t ) / n t = (i 2i-1 ) / n i=1= (n + 1) ( log2(n + 1) - 1 ) + 1 / n = (n + 1) ( log2(n + 1) / n - 1 = (n + 1) ( log2(n + 1) / n - 1 结论：结论：在成功查找的情况下，在成功查找的情况下，平均查找的代价约为平均查找的代价约为 ASL = log2(n + 1) - 1 或者简单地记为：或者简单地记为：ASL = log2n - 1 35 物料管理物料管理SEAR351、静态查找表、静态查找表 2、有序表的查找、有序表的

49、查找 折半查找（或二分查找法）折半查找（或二分查找法）3、性能分析：、性能分析： 3、平均情况分析（在成功、非成功查找两种的情况下）：、平均情况分析（在成功、非成功查找两种的情况下）： 为了简单起见，设结点个数为为了简单起见，设结点个数为 n = 2t -1 （t = 1,2,3 ）。）。 这样，成功查找的情况共有这样，成功查找的情况共有 n 种情况，非成功查找的情况共有种情况，非成功查找的情况共有 n + 1 情况。情况。 设每种情况出现的概率相同，即都为设每种情况出现的概率相同，即都为 1/(2n+1) 。1673524data. key ) ) return ( T ) ; else i

50、f ( LT( key , T -data. key ) ) return (SearchBST ( T - lchild, key ); else return (SearchBST ( T - rchild, key ); / SearchBSTGO4838 物料管理物料管理SEAR382、动态查找表、动态查找表2、插入算法：、插入算法： 首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结

51、点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为排序二叉树的结作为排序二叉树的结 点的关键字值，生成排序二叉树。点的关键字值，生成排序二叉树。39 物料管理物料管理SEAR392、动态查找表、动态查找表2、插入算法：、插入算法： 首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。 若二叉树为

52、空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为排序二叉树的结作为排序二叉树的结 点的关键字值，生成排序二叉树。点的关键字值，生成排序二叉树。12240 物料管理物料管理SEAR402、动态查找表、动态查找表2、插入算法：、插入算法： 首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作

53、为叶子结点插入。 若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为排序二叉树的结作为排序二叉树的结 点的关键字值，生成排序二叉树。点的关键字值，生成排序二叉树。1221229941 物料管理物料管理SEAR412、动态查找表、动态查找表2、插入算法：、插入算法： 首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。

54、将被 插结点作为叶子结点插入。插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为排序二叉树的结作为排序二叉树的结 点的关键字值，生成排序二叉树。点的关键字值，生成排序二叉树。122122991222509942 物料管理物料管理SEAR422、动态查找表、动态查找表2、插入算法：、插入算法： 首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的

55、左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为排序二叉树的结作为排序二叉树的结 点的关键字值，生成排序二叉树。点的关键字值，生成排序二叉树。12212299122250991222501109943 物料管理物料管理SEAR432、动态查找表、动态查找表2、插入算法：、插入算法： 首先执行查找算法，找出被插结点的父亲

56、结点。首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为排序二叉树的结作为排序二叉树的结 点的关键字值，生成排序二叉树。点的关键字值，生成排序二叉树。1221229912225099122250110991222503001109944 物料管理物料管

57、理SEAR442、动态查找表、动态查找表2、插入算法：、插入算法： 首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。12225030011028099e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为排序二叉树的结作为排序二叉树的结 点的关键字值，生成排序二

58、叉树。点的关键字值，生成排序二叉树。1221229912225099122250110991222503001109945 物料管理物料管理SEAR452、动态查找表、动态查找表2、插入、插入 算法：算法： Status SearchBST ( BiTree T，KeyType key， BiTree f，BiTree &p ) / 在排序二叉树查找关键字之值为 key 的结点。初始时 f 为 NULL。如树空，返回 / p 为 NULL及 FALSE。如树非空且查找成功，返回 p = T 及 TRUE。 / 如树非空且查不成功，返回 p = f 及 FALSE。f 为待插入结点的的父

59、亲结点的 / 地址。 if ( ( !T) p = f; return FALSE; else if ( EQ( key, T -data. key ) ) p = T; return TRUE; else if ( LT( key , T -data. key ) ) return (SearchBST ( T - lchild, key, T, p ); else return (SearchBST ( T - rchild, key , T, p ); / SearchBST 程序实现：程序实现： 12225030011099Tpf:nullf: T 的父亲结点的父亲结点p: 指向最后一

60、个结点，指向最后一个结点，TRUE 找到；找到；FALSE 叶叶子的父亲结点。如：插入子的父亲结点。如：插入 280 的过程。的过程。28046 物料管理物料管理SEAR462、动态查找表、动态查找表2、插入算法：、插入算法： 执行实例：插入值为执行实例：插入值为 280 的结点的结点 12225030011099Tf：null12225030011099fTKey=28012225030011099fTKey=280f12225030011099T:nullKey=280p1222503001109928047 物料管理物料管理SEAR472、动态查找表、动态查找表2、插入算法：、插入算法： Status