厦门大学：《数据结构》课程教学课件（PPT讲稿）第九章 查找

Algorithms and DataStructures:Search 目录 第九章查找 1、静态查找表 2、动态查找表 3、哈希查找表 SEAR

1 物料管理 SEAR 1 Algorithms and DataStructures:Search 1、静态查找表 2、动态查找表 3、哈希查找表 目录 第九章 查找

Algorithms and DataStructures:Search 基本概念 查找表： 由同一类型的数据元素（或记录）构成的集合 静态查找表： 对查找表没有修改操作 ■动态查找表： 对查找表具有修改操作 ■关键字 可以标识一个数据元素的数据元素中的某个数据项的值 ■ 主关键字： 唯一标识数据元素 ■次关键字： 可以标识若干个数据元素 SEAR

2 物料管理 SEAR 2 Algorithms and DataStructures:Search 基本概念 ◼ 查找表: 由同一类型的数据元素（或记录）构成的集合 ◼ 静态查找表： 对查找表没有修改操作 ◼ 动态查找表： 对查找表具有修改操作 ◼ 关键字 可以标识一个数据元素的数据元素中的某个数据项的值 ◼ 主关键字： 唯一标识数据元素 ◼ 次关键字： 可以标识若干个数据元素

Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 ·应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序。 ·顺序表的表示和查找。 表示：typedef struct{ElemType*elem;int length;}SStable;∥length=n+1 实现： int Search_Seq(Sstable ST,KeyType key) ∥n:结点个数 {ST.elem[0.]key=key;∥哨兵 设置哨兵的好处： for(i=ST.length;EQ(ST.elem[i].key,key );-i) 在顺序表中总可以找到 待查结点。否则，必须将 return i;∥返▣O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 判断条件i>=0加进for 语句。 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 7 1 3 2 n-3n-2 n-1 n 3 SEAR

3 物料管理 SEAR 3 Algorithms and DataStructures:Search 1、静态查找表 1、顺序表的查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序。 • 顺序表的表示和查找。 表示：typedef struct { ElemType * elem; int length; } SStable; // length = n+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 . 0 1 2 n-3 n-2 n-1 n i 数组 ST.elem key e.g: 查找 key = 8 的结点所在的数组元素的下标。 8 100 10 0 7 1 3 设置哨兵的好处： 在顺序表中总可以找到 待查结点。否则，必须将 判断条件i >= 0 加进 for 语句。 // n： 结点个数

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;l返回O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 7 3 0 1 2 n-3n-2n-1n SEAR

4 物料管理 SEAR 4 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 7 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;∥返▣O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 7 1 3 0 2 n-3 n-2n-1 n SEAR

5 物料管理 SEAR 5 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 7 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;∥返回O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 7 3 0 1 2 n-3n-2n-1n 6 SEAR

6 物料管理 SEAR 6 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 7 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;∥返▣O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 71 3 0 2 n-3n-2 n-1 n SEAR

7 物料管理 SEAR 7 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 7 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;∥返回O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 7 3 0 1 2 n-3n-2n-1n SEAR

8 物料管理 SEAR 8 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 7 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;∥返▣O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 71 3 0 1 2 n-3n-2 n-1 n 查找失败，则i=0; 9 SEAR

9 物料管理 SEAR 9 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 的结点所在的数组元素的下标。 查找失败，则i = 0; 8 100 10 0 7 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;∥返回O,查找失败，否则，找到key所在的 ∥数组元素的下标地址 }∥Search_Seq e.g:查找key=8的结点所在的数组元素的下标。 key 数组ST.elem 8 100 10 0 8 3 0 1 2 n-3n-2 n-1 n 10 SEAR

10 物料管理 SEAR 10 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 i 数组 ST.elem key e.g: 查找 key = 8 的结点所在的数组元素的下标。 8 100 10 0 8 1 3