清华大学：《实用数据结构》课程教学资源（PPT课件）第七章 查找技术

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第7章查找技术 7.1顺序查找 7.2有序表的对分查找 7.3分块查找 7.4二叉排序树查找 7.5多层索引树查找

第7章 查找技术 7.1 顺序查找 7.2 有序表的对分查找 7.3 分块查找 7.4 二叉排序树查找 7.5 多层索引树查找

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 7.1.1线性表在顺序存储下的顺序查找 7.1.2线性链表的顺序查找

7.1 顺序查找 7.1.1 线性表在顺序存储下的顺序查找 7.1.2 线性链表的顺序查找

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 7.1.1线性表在顺序存储下的顺序查找 (1)如果线性表为无序表(即表中元素 的排列是无序的),则不管是顺序存储 结构还是链式存储结构,都只能用顺序 查找。 (2)即使是有序线性表,如果采用链式 存储结构,也只能用顺序查找

7.1 顺序查找 7.1.1 线性表在顺序存储下的顺序查找 (1)如果线性表为无序表（即表中元素 的排列是无序的），则不管是顺序存储 结构还是链式存储结构，都只能用顺序 查找。 (2)即使是有序线性表，如果采用链式 存储结构，也只能用顺序查找

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 线性表在顺序存储结构下的顺序查找 输入:线性表长度n以及线性表的存储空间V; 被查找的元素x 输出:被查找元素x在线性表中的序号k。 如果在线性表中不存在元素x,则输出k=-1。 PROCEDURE SERCH (V, n, x, k) k=1 WHILE(k≤n)and(V(k)≠x)D0k=k+1 IF(k=n+1 then k= RETURN

7.1 顺序查找 线性表在顺序存储结构下的顺序查找 输入：线性表长度n以及线性表的存储空间V； 被查找的元素x。 输出：被查找元素x在线性表中的序号k。 如果在线性表中不存在元素x，则输出k＝－1。 PROCEDURE SERCH(V，n，x，k) k＝1 WHILE (k≤n)and(V(k)≠x) DO k＝k＋1 IF (k＝n＋1) THEN k＝－1 RETURN

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 /*函数返回被查找元素x在线性表中的序号, 如果在线性表中不存在元素值x,则返回一1*/ int serch(v, n, x) int n: ETv[],x;/米ET为线性表数据类型米/ i int k k=0 while((k<n)&&(v[k]))k=k+1 if (k==n)k=-1 return(k)

7.1 顺序查找 /*函数返回被查找元素x在线性表中的序号， 如果在线性表中不存在元素值x，则返回－1 */ int serch(v，n，x) int n； ET v[]，x； /*ET为线性表数据类型*/ { int k； k＝0； while ((k＜n)&&(v[k]≠x)) k＝k＋1； if (k＝＝n) k＝－1； return(k)； }

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 1.2线性链表的顺序查找

7.1 顺序查找 7.1.2 线性链表的顺序查找

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 线性表在链式存储结构下的顺序查找 输入:线性链表头指针HAD以及存储空间V、NEXT; 被查找的元素x。 输出:被查找元素x的结点在线性链表中的存储序号k 如果在线性链表中不存在元素值为x的结点, 则输出k=-1 PROCEDURE LSERCH(V, NEXT, HEAD,X,k K=HEAD WHIE(k≠0)and(V(k)≠x)DOk=NEXT(k) IF(K=0)Then k=-1 RETURN

7.1 顺序查找 线性表在链式存储结构下的顺序查找 输入：线性链表头指针HEAD以及存储空间V、NEXT； 被查找的元素x。 输出：被查找元素x的结点在线性链表中的存储序号k。 如果在线性链表中不存在元素值为x的结点， 则输出k＝－1。 PROCEDURE LSERCH(V，NEXT，HEAD，x，k) k＝HEAD WHILE (k≠0)and(V(k)≠x) DO k＝NEXT(k) IF (k＝0) THEN k＝－1 RETURN

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 struct node iet d; struct node *next: j /*函数返回被査找元素x所在结点的存储地址, 如果在线性链表中不存在元素值为x的结点,则返回NLL*/ struct node *serch(head, x) struct node *head ETx;/*ET为线性链表中值域的数据类型* i struct node k k=head while((k≠NUL&&(k->d≠x)k=k一>next; return(k)

7.1 顺序查找 struct node { ET d； struct node *next； }； /*函数返回被查找元素x所在结点的存储地址， 如果在线性链表中不存在元素值为x的结点，则返回NULL*/ struct node *lserch(head，x) struct node *head； ET x； /*ET为线性链表中值域的数据类型*/ { struct node k； k＝head； while ((k≠NULL)&&(k－>d≠x)) k＝k－>next； return(k)； }

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.2有序表的对分查找 设有序线性表的长度为n,被查元素为x。 将x与线性表的中间项进行比较: 若中间项的值等于x,则说明查到,查找结束; 若x小于中间项的值,则在线性表的前半部分(即中间项 以前的部分)以相同的方法进行查找; 若x大于中间项的值,则在线性表的后半部分(即中间项 以后的部分)以相同的方法进行查找。 这个过程一直进行到查找成功或子表长度为0(说明线性 表中没有这个元素)为止 在最坏情况下,对分查找只需要比较log2n次, 而顺序查找需要比较n次

7.2 有序表的对分查找 设有序线性表的长度为n，被查元素为x。 将x与线性表的中间项进行比较： 若中间项的值等于x，则说明查到，查找结束； 若x小于中间项的值，则在线性表的前半部分（即中间项 以前的部分）以相同的方法进行查找； 若x大于中间项的值，则在线性表的后半部分（即中间项 以后的部分）以相同的方法进行查找。 这个过程一直进行到查找成功或子表长度为0(说明线性 表中没有这个元素)为止。 在最坏情况下，对分查找只需要比较log2n次， 而顺序查找需要比较n次

清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.2有序表的对分查找 有序线性表在顺序存储结构下的对分查找 输入:有序线性表长度n以及线性表的存储空间V;被查找的元素x。 输出:被查找元素x在有序线性表中的序号k。如果在线性表中不存 在元素x,则输出k=-1 PROCEDURE BSERCH(V, n, x, k) n While (iX)then j=k-1; elsE i=k+1 IF (i>j)then k=-1 RETURN

7.2 有序表的对分查找 有序线性表在顺序存储结构下的对分查找 输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。 输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存 在元素x，则输出k＝－1。 PROCEDURE BSERCH(V，n，x，k) i＝1； j＝n WHILE (i＜＝j) DO { k＝(i＋j)/2 IF (V(k)＝x) THEN RETURN IF (V(k)＞x) THEN j＝k－1； ELSE i＝k＋1； } IF (i＞j) THEN k＝－1 RETURN