第七章查找 查找也叫检索,是一种在实际中大量应用的基本运算 查找表是由同一类型的数据元素(或记录)构成的集合 对查找表经常进行的操作有以下几种: (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 =