第七章查找 查找也叫检索,是一种在实际中大量应用的基本运算 查找表是由同一类型的数据元素(或记录)构成的集合 对查找表经常进行的操作有以下几种: (1)查询某个“特定的”数据元素是否在查找表中; (2)检索某个“特定的”数据元素的各种属性; (3)在查找表中插如一个数据元素; (4)从査找表中删去某个数据元素 只对查找表进行(1)、(2)二种操作时,称查找表为静态查找 表.若对查找表需同时进行上述四种操作时称查找表为动态查 找表在上述四种操作中,(1)、(2)二种是基本的操作统称为查找 下面给出“特定的”这个词的含义: 关键字(key):是数据元素(或记录)中某个数据项的值,用以 标识(识别)一个数据元素(或记录)
第 七 章 查 找 查找也叫检索, 是一种在实际中大量应用的基本运算. 查找表是由同一类型的数据元素(或记录)构成的集合. 对查找表经常进行的操作有以下几种: (1)查询某个“特定的”数据元素是否在查找表中; (2)检索某个“特定的”数据元素的各种属性; (3)在查找表中插如一个数据元素; (4)从查找表中删去某个数据元素. 只对查找表进行(1)﹑(2)二种操作时, 称查找表为静态查找 表. 若对查找表需同时进行上述四种操作时,称查找表为动态查 找表. 在上述四种操作中, (1)﹑(2)二种是基本的操作,统称为查找 下面给出“特定的”这个词的含义: 关键字(key): 是数据元素(或记录)中某个数据项的值, 用以 标识(识别)一个数据元素(或记录)
主关键字( primary key):能唯一地标识一个记录的 关键字,对不同的记录,其主关键词的值均不同. 次关键字 condary key):用以识别若干个记录的 关键字 查找:设查找表Fn个记录,K为记录R的关键字 现给定关键字K,将寻找相应的记录R的过程称为查找 以后为讨论问题方便起见常用记录的关键字值K表 示该记录 7线性表的查找 711顺序查找 顺序查找是最简单的一种查找方法,其查找过程为: 从表的一端开始,逐个进行记录的关键字值和给定关键字 值的比较,若找到一个记录的关键字值和给定关键字值相 等,则查找成功;若整个表中记录均已比较,仍未有记录 的关键字值等于给定值,则査找失败
主关键字(primary key): 能唯一地标识一个记录的 关键字, 对不同的记录, 其主关键词的值均不同. 次关键字(secondary key): 用以识别若干个记录的 关键字. 查找: 设查找表F有n个记录, Ki 为记录 Ri 的关键字 现给定关键字K, 将寻找相应的记录R的过程称为查找. 以后为讨论问题方便起见, 常用记录的关键字值K表 示该记录. 7.1线性表的查找 7.1.1 顺序查找 顺序查找是最简单的一种查找方法, 其查找过程为: 从表的一端开始, 逐个进行记录的关键字值和给定关键字 值的比较, 若找到一个记录的关键字值和给定关键字值相 等, 则查找成功; 若整个表中记录均已比较, 仍未有记录 的关键字值等于给定值, 则查找失败
由于顺序查找方法是顺序地逐个进行记录关键字的 比较,因此这种查找方法既适合于线性表的顺序存储, 也适合于线性表的链式存储.且对于查找表中的记录是 否按关键字值有序也无关 下面先给出对顺序存储的线性表进行顺序查找的C函 数 struct node d ink key; char ch; j typedef struct node node void search(rn, k) NODE r int n, k; f int i; rn1key=k;/标识边界,在此称为上监视哨,如r10key=k,称为下监视哨,/ /*下面程序有些语句需作相应改动 hile(ri.keyl =k)i++; ff=n) printi(“成功%d%”,r[key,ri]ch) else printf(“表中无此记录Ⅷn”);
由于顺序查找方法是顺序地逐个进行记录关键字的 比较, 因此这种查找方法既适合于线性表的顺序存储, 也适合于线性表的链式存储. 且对于查找表中的记录是 否按关键字值有序也无关. 下面先给出对顺序存储的线性表进行顺序查找的C函 数. struct node { ink key; char ch; } typedef struct node NODE; void seqsrch(r,n,k) NODE r[ ]; int n,k; { int i; r[n+1].key=k; /* 标识边界, 在此称为上监视哨, 如r[0].key=k, 称为下监视哨, */ /* 下面程序有些语句需作相应改动. */ i=1; while(r[i].key!=k) i++; if(i<=n) printf(“成功.%d%c”,r[i].key, r[i].ch); else printf(“表中无此记录\n”); }
下面给出的C函数其作用是对带头结点的单向循环链 表中的记录进行顺序查找 truct node f ink key; char ch; struct node *next j typedef struct node node; void segsrch(h, k) NODE *h: int k INODE*p; p=h->next; while(pl=h) fif(p->key==k) printf(“成功%d%c”,p>key,p>ch); return;} else p=p->next; printf(“表中无此记录n”)
下面给出的C函数其作用是对带头结点的单向循环链 表中的记录进行顺序查找. struct node { ink key; char ch; struct node *next } typedef struct node NODE; void seqsrch(h,k) NODE *h; int k; { NODE *p; p=h->next; while(p!=h) { if(p->key==k) { printf(“成功.%d%c”, p->key, p->ch); return; } else p=p->next; } printf(“表中无此记录\n”); }
查找操作的性能分析 在此主要分析查找操作的时间复杂度.查找算法中的 基本运算是“将记录的关键字和给定值进行比较”.因 此 通常以“其关键字和给定值进行过比较的记录个数的平均 值”作为量度查找算法的好坏依据 定义:为确定记录在查找表中的位置,需和给定值进 行比较的关键字个数的期望值称为查找算法在查找成功时 的平均查找长度,也即时间复杂度 对含有n个记录拘套找查找成功时的平均查找长度 上式中P为查找表中第个记录的概率,且有∑P=1 当查找表中任一个记录的概率相等即等概时,有P,=
查找操作的性能分析 在此主要分析查找操作的时间复杂度. 查找算法中的 基本运算是“ 将记录的关键字和给定值进行比较”. 因 此 通常以“ 其关键字和给定值进行过比较的记录个数的平均 值” 作为量度查找算法的好坏依据. 定义: 为确定记录在查找表中的位置, 需和给定值进 行比较的关键字个数的期望值称为查找算法在查找成功时 的平均查找长度, 也即时间复杂度. 对含有n个记录的查找表 , 查找成功时的平均查找长度 = = n i ACN pi ci 1 上式中: pi 为查找表中第i个记录的概率, 且有 1 1 = = n i pi 当查找表中任一个记录的概率相等即等概时,有 n pi 1 =
C为找到表中其关键字与给定值相等的第个记录时,和给 定值已进行过比较的关键字个数 对于顺序查找算法,等概时查找成功的平均查找长度 H: AcN=>pc=I>i=In(n+D=n+I 则顺序查找算法查找成功时的时间复杂度为on) 在实际应用的大多数情况下,查找成功的可能性比不 成功的可能性大的多,特别是当n很大时,查找不成功的概 率可忽略不计.但当查找不成功的概率不能忽略时,查找 算法的平均查找长度应当是查找成功时的平均查找长度和 查找不成功时的平均查找长度之和 对于顺序査找,不论给定关键字值为何值,查找不成功 时和给定值进行比较的关键字个数均为n+1.设查找成功和 不成功的概率相等,即均为二分之一,对每个记录的查找 概率也相等
为找到表中其关键字与给定值相等的第i个记录时, 和给 定值已进行过比较的关键字个数. 对于顺序查找算法, 等概时查找成功的平均查找长度 i c 为: 2 1 2 1 1 ( 1) 1 1 + = + = = = = = n n n n i n ACN p c n i n i i i 则顺序查找算法查找成功时的时间复杂度为O(n). 在实际应用的大多数情况下, 查找成功的可能性比不 成功的可能性大的多, 特别是当n很大时, 查找不成功的概 率可忽略不计. 但当查找不成功的概率不能忽略时, 查找 算法的平均查找长度应当是查找成功时的平均查找长度和 查找不成功时的平均查找长度之和. 对于顺序查找, 不论给定关键字值为何值,查找不成功 时和给定值进行比较的关键字个数均为n+1. 设查找成功和 不成功的概率相等, 即均为二分之一, 对每个记录的查找 概率也相等
则P1=1/2n,此时顺序查找的平均查找长度为: n+11 ACN=∑pC1+ n+1n+1,n+13(n+1) 22n7 2 4 4 顺序査找的优点:算法简单,适应面广,查找表中的记 录按关键字值的排列即可无序,也可有序,查找表的存储结 构即可为顺序,也可为链表 顺序查找的缺点:平均查找长度较大,尤其当n较大时 查找效率较低 712折半查找 折半查找也叫二分査找,其前提条件是:查找表必须以 顺序表的结构存储,且查找表中的记录必须按关键字值有序 排列 以后所举例子中假设查找表中的记录按关键字值递增有 序排列 下面用具体的例子说明折半查找的基本思想和手工操作 的过程
则 p n ,此时顺序查找的平均查找长度为: i =1/ 2 4 3( 1) 2 1 4 1 2 1 2 1 2 1 1 1 + = + + + = + = + + = + = = n n n n i n n ACN p c n i n i i i 顺序查找的优点: 算法简单, 适应面广, 查找表中的记 录按关键字值的排列即可无序, 也可有序, 查找表的存储结 构即可为顺序, 也可为链表. 顺序查找的缺点: 平均查找长度较大, 尤其当n较大时 查找效率较低. 7.1.2 折半查找 折半查找也叫二分查找, 其前提条件是: 查找表必须以 顺序表的结构存储, 且查找表中的记录必须按关键字值有序 排列. 以后所举例子中假设查找表中的记录按关键字值递增有 序排列. 下面用具体的例子说明折半查找的基本思想和手工操作 的过程
例:设在顺序存储的有序表中各记录的关键字为: 234567891011 03四9237566475808892 现要求查找关键字值为21的记录 查找过程如下:设三个变量分别为l,hg,mid,它们的初值 0=1hg=1lmd=(o+hig)/2」=6,则它们的初始指向如 1234567891011下左图.第一次比较: 03921375664758088927 mid].key=7ey=56k=21 hig=mid-1=6-1=5 hig mid =L(low +hig)/2]=3 low mid hig第二次比较: [mid].key=13key=19<k=21 p=md+1=3+1=4,md=(o+hg)/2」=4 mnhg第三次比较:1mlky=n1ky=21-=k=21 Ow 所以查找成功
例: 设在顺序存储的有序表中各记录的关键字为: 现要求查找关键字值为21的记录. 查找过程如下: 设三个变量分别为 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low,hig,mid , 它们的初值 low =1,hig =11,mid = (low + hig)/ 2 = 6 , 则它们的初始指向如 1 2 3 4 5 6 7 8 9 10 11 下左图. 05 13 19 21 37 56 64 75 80 88 92 low mid hig 第一次比较: ( )/ 2 3 1 6 1 5 [ ]. [6]. 56 21 = + = = − = − = = = = mid low hig hig mid r mid key r key k low mid hig 第二次比较: r[mid].key = r[3].key =19 k = 21 low = mid +1= 3 +1= 4,mid = (low + hig)/ 2 = 4 low mid hig 第三次比较: r[mid].key = r[4].key = 21= k = 21 所以查找成功
若现需查找关键字值为85的记录,则过程如下:第一次比较: 1234567891011 [mid.key=r[6key=56k=85 hig=mid-1=10-1=9 O hig g <l=10 查找不成功.其它例子可见教材P.173~P174.算法的C函数 可见教材P175 下面分析折半查找的平均查找长度
若现需查找关键字值为85的记录, 则过程如下: 第一次比较: 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low mid hig ( )/ 2 9 1 6 1 7 [ ]. [6]. 56 85 = + = = + = + = = = = mid low hig low mid r mid key r key k low mid hig 第二次比较: ( )/ 2 10.5 10 1 9 1 10 [ ]. [9]. 80 85 = + = = = + = + = = = = mid low hig low mid r mid key r key k 第三次比较: low mid hig 1 10 1 9 [ ]. [10]. 88 85 = − = − = = = = hig mid r mid key r key k low hig hig = 9 low =10 查找不成功. 其它例子可见教材P.173~P.174. 算法的C函数 可见教材P.175 下面分析折半查找的平均查找长度
折半查找中查到每一个记录的比较次数可通过二叉 判定树来描述.画二叉判定树的步骤为: 1)用当前查找区间的中间位置上的记录作为根 (2)左子表和右子表中的记录分别作为根的左子树和右 子树 (3)分别对左子表和右子表执行步骤(1) 下面用前面举的例子介绍画二叉判定树的过程 1234567891011 053121375664阿5808892 ∠mz 81 low2t mid, hig high
折半查找中查到每一个记录的比较次数可通过二叉 判定树来描述. 画二叉判定树的步骤为: (1) 用当前查找区间的中间位置上的记录作为根. (2) 左子表和右子表中的记录分别作为根的左子树和右 子树. (3) 分别对左子表和右子表执行步骤(1) . 下面用前面举的例子介绍画二叉判定树的过程. 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 1 low 1 mid1 hig 56 2 low 2 hig mid2 19 3 low 3 hig mid3 05
