◆关键字:数据元素中某个数据项的值,用它可以标示 查找表中的一个数据元素。主关键字可以唯一地标识 个记录,次关键字用以识别若干记录。 ◆査找:就是根据给定的关键字值,在特定的查找表中 确定一个其关键字与给定值相同的数据元素,并返回 该数据元素在查找表中的位置。如果找到数据元素 则称查找成功,否则查找失败。 ◆平均查找长度:为了确定数据元素在查找表中的位置 需要和给定值进行比较的关键字个数期望值,称为査 找算法在查找成功时的平均查找长度
◆关键字：数据元素中某个数据项的值，用它可以标示 查找表中的一个数据元素。主关键字可以唯一地标识 一个记录，次关键字用以识别若干记录。 ◆查找：就是根据给定的关键字值，在特定的查找表中 确定一个其关键字与给定值相同的数据元素，并返回 该数据元素在查找表中的位置。如果找到数据元素， 则称查找成功，否则查找失败。 ◆平均查找长度：为了确定数据元素在查找表中的位置 需要和给定值进行比较的关键字个数期望值，称为查 找算法在查找成功时的平均查找长度
对于长度为n的查找表,查找成功的平均查找长度为: ASL=PC1+P2C2+……+PnCn=PC 其中P为查找表中第i个数据元素的概率,C1为找到 查找表中第i个元素时,已经进行的比较次数。由于 査找算法的基本元素是关键字之间的比较操作,所以 可以平均査找长度来衡量查找算法的性能
•对于长度为n的查找表，查找成功的平均查找长度为： •其中Pi为查找表中第i个数据元素的概率，Ci为找到 查找表中第i个元素时，已经进行的比较次数。由于 查找算法的基本元素是关键字之间的比较操作，所以 可以平均查找长度来衡量查找算法的性能
92顺序表 顺序表中相邻的两个记录R和Ri+1在存储器中 的物理位置也是相邻的,因此存储结构采用的 是顺序结构。 顺序结构有关C+语言描述的数据类型定义: (为了简单起见,我们假设记录的排序码为整 型,在本章以后讨论的顺序表中均采用这样的 向量存储结构)
9.2顺序表 顺序表中相邻的两个记录Ri和Ri+1在存储器中 的物理位置也是相邻的，因此存储结构采用的 是顺序结构。 顺序结构有关C++语言描述的数据类型定义 ： （为了简单起见，我们假设记录的排序码为整 型，在本章以后讨论的顺序表中均采用这样的 向量存储结构）
# define maxn30∥文件中最大记录数 tyi pedef struct int key;∥假设记录排序码为整数 char *other;∥记录中其它信息城,暂不用 record; typedef record recordfilelmaxn 顺序表的查找方法分为顺序查找法、二分法 (折半)查找法以及分块(索引)查找法
•顺序表的查找方法分为顺序查找法、二分法 （折半）查找法以及分块（索引）查找法。 #define maxn 30 // 文件中最大记录数 typedef struct { int key; // 假设记录排序码为整数 char *other; // 记录中其它信息域，暂不用 } record; typedef record recordfile[maxn];
921顺序查找 顺序查找( sequential search)用待查的关键字值与线 性表里各结点的关键字值逐个比较, 查找 0 2345678 765687697623113244查找次数=5 监视哨 查找第n个元素:比较次数1查找第n-1个元素:比较次数2 查找第1个元素:比较次数n 查找第个元素:比较次数n+1-i查找失败:比较次数n+1
9.2.1顺序查找 顺序查找（sequential search)用待查的关键字值与线 性表里各结点的关键字值逐个比较， •查找第n个元素：比较次数1 查找第n-1个元素：比较次数2 ………. 查找第1个元素：比较次数 n 查找第i个元素：比较次数n+1-i 查找失败：比较次数n+1 76 56 87 69 76 23 11 32 44 0 1 2 3 4 5 6 7 8 监视哨 查 找 76 ↑i ↑i ↑i ↑i ↑i 查找次数＝5