第7章查找表 ·7.1查找表的基本概念 ·7.2静态查找表 ·7.3动态查找表 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第7章 查找表 • 7.1查找表的基本概念 • 7.2静态查找表 • 7.3动态查找表
7.1查找表的基本概念 查找表： 一由同一类元素或记录构成的集合。对数据元素间的关系未作限定。 对查找表的操作有 一查找某个“特定”的元素是否在表中。 一查找某个"特点” 的元素的各种属性。 在查找表中插入一个元素。 - 在查找表中删除一个元素 ·静态查找表、动态查找表 。 关键字 一数据元素中的某个数据项值。可以标识一个数据元素，如可以唯一 标识，则为主关键字（primary key)。 查找 一根据给定的某个值，在查找表中确定一个关键字等于给定值的数据 元素。若找到表示查找成功，返回该元素详细信息或在查找表中的 位置；否则返回NULL ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 • 查找表： – 由同一类元素或记录构成的集合。对数据元素间的关系未作限定。 • 对查找表的操作有 – 查找某个“特定”的元素是否在表中。 – 查找某个“特点”的元素的各种属性。 – 在查找表中插入一个元素。 – 在查找表中删除一个元素 • 静态查找表、动态查找表 • 关键字 – 数据元素中的某个数据项值。可以标识一个数据元素，如可以唯一 标识，则为主关键字（primary key）。 • 查找 – 根据给定的某个值，在查找表中确定一个关键字等于给定值的数据 元素。若找到表示查找成功，返回该元素详细信息或在查找表中的 位置；否则返回NULL 7.1查找表的基本概念
7.2静态查找表 typedef struct{ Datatype data; ∥元素数据 KeyType key; /元素关键字 }Elemtype;:/数据元素类型 typedef struct{ Elemtype *elem: /约定从下标1开始 int len; }StaticSrhTable;顺序静态查找表类型 ypb@ustc.edu.cn 3 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 7.2静态查找表 typedef struct{ Datatype data; //元素数据 KeyType key; //元素关键字 }Elemtype; //数据元素类型 typedef struct{ Elemtype *elem; //约定从下标1开始 int len; }StaticSrhTable; //顺序静态查找表类型
>顺序查找 算法7.1 int SeqSearch(StaticSrhTable SST,KeyType kval) /*在顺序表SST中顺序查找关键字为kval的记录。 若找到，则返回记录在表中的位序；否则，返回0*/ SST.elem[0].key =kval; ∥放置监视哨 for(i=SST.len,SST.elem[i.key=kval;i-);∥查找 return i; ∥查找结果 ypb@ustc.edu.cn 4 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 ➢ 顺序查找 算法7.1 int SeqSearch(StaticSrhTable SST, KeyType kval) { /* 在顺序表SST中顺序查找关键字为kval的记录。 若找到，则返回记录在表中的位序；否则，返回0 */ SST.elem[0].key = kval; // 放置监视哨 for (i = SST.len; SST.elem[i].key != kval; i--); // 查找 return i; // 查找结果 }
·例7.1在顺序查找表中查找成功和失败 平均查找长度 一查找过程中先后和给定值进行比较的关键字的个 数的期望值 ASL=∑PCi∑P=1i=1,2,。。 。。n C=n-i+1P:=1/m ASLss=1/n∑（n-i+1)=(n+1)/2 ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 • 例7.1在顺序查找表中查找成功和失败 • 平均查找长度 – 查找过程中先后和给定值进行比较的关键字的个 数的期望值 ASL＝∑PiCi ∑Pi＝1 i＝1，2，。。。。。n Ci＝n－i＋1 Pi＝1/n ASLss＝1/n∑（n－i＋1）=(n+1)/2