第九章查找 静态查找表 动态查找表 哈希查找表 在各种系统软件和应用软件中,查 找表是一种最常见的数据结构,有着广 泛的应用
第九章 查找 • 静态查找表 • 动态查找表 • 哈希查找表 在各种系统软件和应用软件中，查 找表是一种最常见的数据结构，有着广 泛的应用
查找表基本概念 查找表( table):由同类型的DE(或记录)构成的集合 查找表上的基本运算 建立查找表 create(ST,n) 查找 search(ST,k) 遍历查找表 traverse(ST) 其抽象数据类型定义见书P216. 关键字(key):是表中数据元素中某个数据元素的某值, 用它可以标识(识别)这个数据元素。若此关键字可以唯一地标 识这个元素,则它称为主关键字( Primary Key);反之,若用 它能识别一批元素,则称它为次关键字( Secondary Key)
查找表基本概念 查找表(table):由同类型的DE(或记录)构成的集合. 查找表上的基本运算: • 建立查找表create(ST, n) • 查找search(ST, k) • 遍历查找表traverse(ST) 其抽象数据类型定义见书P216. 关键字（key）：是表中数据元素中某个数据元素的某值， 用它可以标识（识别）这个数据元素。若此关键字可以唯一地标 识这个元素，则它称为主关键字（Primary Key）；反之，若用 它能识别一批元素，则称它为次关键字（Secondary Key）
查找表基本概念 查找:在查找表中确定一个关键字与给定值相等的DE 的过程 查找结果: 查找成功 table中存在给定值的记录) 查找不成功(tabe中不存在给定值的记录) 查找表分为: 静态查找表(对查找表中的数据元素不进行插入和删 除操作) 动态查找表(对查找表中的数据元素可进行插入和删 除操作)
查找表基本概念 查找 : 在查找表中确定一个关键字与给定值相等的DE 的过程. 查找结果: • 查找成功 (table 中存在给定值的记录) • 查找不成功(table 中不存在给定值的记录) 查找表分为: • 静态查找表(对查找表中的数据元素不进行插入和删 除操作) • 动态查找表(对查找表中的数据元素可进行插入和删 除操作)
查找表基本概念 本章中涉及的关键字类型及数据元素类型如下 典型的关键字类型说明可以是: typedef float Key Type;∥关键字类型为实型 typedef int Key Type;∥关键字类型为整型 typedef char Key Type;∥关键字类型为字符串型 数据元素类型定义为: typedef struct( Key Type key;∥关键字域 ∥其它域 Elem Type
查找表基本概念 本章中涉及的关键字类型及数据元素类型如下： 典型的关键字类型说明可以是： typedef float KeyType; //关键字类型为实型 typedef int KeyType; //关键字类型为整型 typedef char KeyType; //关键字类型为字符串型 数据元素类型定义为： typedef struct{ KeyType key; //关键字域 ….. //其它域 }ElemType;
查找表基本概念 关键字比较的常用宏定义 用于数值关键字的有: #define eQ(a, b)((a==(b)) #define lt(a, b)((a<(b)) #define lQ(a, b)((a<=(b)) 用于字符串型关键字的有: #define eQ(a, b)(!strcmp ((a),(b)) #define lt(a, b)(strcmp((a),(b))<o #define LQ(a, b) (strcmp((a),(b))<=0
查找表基本概念 关键字比较的常用宏定义 用于数值关键字的有： #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) 用于字符串型关键字的有： #define EQ(a,b) (!strcmp((a),(b)) #define LT(a,b) (strcmp((a),(b))<0) #define LQ(a,b) (strcmp((a),(b))<=0)
9.1静态查找表 顺序表的查找 静态查找表的顺序存储结构为 typedef struct ElemType*elem;∥元素存储空间基址,0号单元留空 int length;∥/表长度 } SSTable;/顺序查找表类型 顺序查找( Sequential Search)的算法思想 从表中最后一个元素开始,把给定值与元素的关键字逐个作 相等比较,若有某元素的关键字与给定值相等,则査找成功 ,返回其位置序号;否则返回0
9.1 静态查找表 一. 顺序表的查找 静态查找表的顺序存储结构为 typedef struct{ ElemType *elem; //元素存储空间基址，0号单元留空 int length; // 表长度 }SSTable; //顺序查找表类型 顺序查找（Sequential Search）的算法思想： 从表中最后一个元素开始，把给定值与元素的关键字逐个作 相等比较，若有某元素的关键字与给定值相等，则查找成功 ，返回其位置序号；否则返回0
9.1静态查找表 int seqsrch(ssTable ST, KeyType key STele0=key;/没置“哨兵” for(I= STlength;:EQ( STele[i∴key,key);i-);/从后往前找 return i;/找不到时,i为0 M//search 1.查找过程:从n开始,依次与k进行比较,若相等则查找 成功;否则,继续进行,直到与r[0key比较为止 2.算法分析 (1)算法结构应由一个循环构成; (2)循环结束有两种可能: 查找成功 STelemi.key=key 查找不成功
9.1 静态查找表 1. 查找过程:从n开始,依次与k进行比较, 若相等则查找 成功; 否则, 继续进行,直到与r[0].key比较为止. 2. 算法分析: (1) 算法结构应由一个循环构成; (2) 循环结束有两种可能： • 查找成功 ST.elem[i].key = key • 查找不成功 i = 0 int seqsrch(SSTable ST， KeyType key) { ST.elem[0]=key;//设置“哨兵” for (I=ST.length;!EQ(ST.elem[i].key,key);i--);//从后往前找 return i；//找不到时，i为0 }//seqsrch
9.1静态查找表 (2)循环结束有两种可能 查找成功s! .elemi]. key=key条件控制 查找不成功i=0计数控制式 这两种可能形成两种不同类型的循环控制: 条件循环 while条件循环体 do循环体 while条件 ·计数循环or(I= STength;!EQST: elemi key, key);-); 常规解决办法: (1)条件循环为主 i=STlength; while(EQ(STelem(i]. key, key))i=i-1 (2)计数循环为主 for (i=sTlength; !EQ(STelemi. key, key); i--;
9.1 静态查找表 (2) 循环结束有两种可能： • 查找成功 ST.elem[i].key = key 条件控制式 • 查找不成功 i = 0 计数控制式 这两种可能形成两种不同类型的循环控制： • 条件循环 while 条件 循环体 do 循环体 while 条件 • 计数循环 for (I=ST.length;!EQ(ST.elem[i].key,key);i--); 常规解决办法: (1) 条件循环为主 i=ST.length; while (!EQ(ST.elem[i].key,key)) i=i-1; (2) 计数循环为主 for (i=ST.length;!EQ(ST.elem[i].key,key);i--);
9.1静态查找表 3.STem0起监视哨作用 4.查找方向可换 int seqsrchI(ssTable sT, KeyType key) STelem stlength+1}=key;/没置“哨兵” for(i=1;!EQ( STelemi. key,key);i+);/从前往后找 if(i!= STength+1) return0;/找不到时,i为 STength+1 return 1; int seqsrch(ssTable st, KeyType key) y//segsrchl &STelema]=key; for (ISTlength; EQ(ST.elemij key, key); i--) return i;)//seqsrch
9.1 静态查找表 int seqsrch1(SSTable ST， KeyType key) { ST.elem[ST.length+1]=key;//设置“哨兵” for (i=1;!EQ(ST.elem[i].key,key);i++);//从前往后找 if (i!= ST.length+1 ) return 0；//找不到时，i为ST.length+1 return i; }//seqsrch1 4. 查找方向可换 int seqsrch(SSTable ST， KeyType key) { ST.elem[0]=key; for (I=ST.length;!EQ(ST.elem[i].key,key);i--); return i；}//seqsrch 3. ST.elem[0]起监视哨作用
9.1静态查找表 平均查找长度(ASL 查找过程中,给定值需与关键字比较的次数的期望值 ASL=∑PCi 其中:P;为查找第个记录的概率 C为找到第个记录时,已比较的次数. 顺序查找的平均查找长度 ASLSS-=np1+(n-1)p2+…pn 当p=1/n时,ASLs=∑PAC:=(n+1)/2 i=1
9.1 静态查找表 平均查找长度(ASL): 查找过程中, 给定值需与关键字比较的次数的期望值. n ASL=∑PiCi i =1 其中: Pi 为查找第i 个记录的概率; Ci 为找到第i 个记录时, 已比较的次数. 顺序查找的平均查找长度ASLss=np1+(n-1)p2+……+pn n 当pi=1/n时, ASLss=∑PiCi =(n+1)/2 i =1