第九章 线性表的查找

线性表的查找

第九章

查找

查找是数据处理中使用广泛的一种运算。 所谓查找就是在一种数据结构中查找满足某种条件的 结点。有两种常用的查找方式： (1)查找指定值(例如关键字值)的结点。结果是成功或失 败。 (2)查找某个属性(字段)等于指定范围的所有结点。结果 是成功地找到一个或多个值，一个都不存在为失败。 查找往往是以找到其地址为目的。 查找算法与存储结构： 书写查找算法，要注意存储结构，根据存储结构特点 来确定其查找方法。不同存储结构，查找的算法往往是不 同的。

线性表的查找

查找的效率： 查找算法的效率用比较次数来衡量。通常用平均查找 长度ASL(n)表示： n ASL(n)=∑PiCi i=1 Pi---第i个元素的查找概率；Ci---第i个元素的比较次数。 约定： 在以后我们讨论查找时，为了讨论的方便，假定结点 是等长的，关键字都是正整数。

线性表的查找

&9.1 静态查找表 基本操作： Create(&ST,n):构造一个含n个数据元素的静态查找 表ST。 Search(ST,key):若ST中存在其关键字等于key的数 据元素，则函数为该元素的值或在表中的位置，否则为 “空”。 Traverse(ST,Visit()):按某种次日对ST的每个元素调 用函数Visit()一次且仅一次。一旦Visit()失败，则操作失 败。 一、顺序查找 顺序查找是一种最简单的查找方法。一般用于记录数 不多或记录没有次序的线性表中。

线性表的查找

查找方法： 从第一个记录开始，逐个检查其关键字，直到找到关 键字值等于指定值，找到为查找成功。如果直到整个表结 束，还没有找到，为查找失败。 顺序查找时的存储方式可以是顺序表，也可以是链接表。

线性表的查找

下面以顺序表结构为例说明顺序查找的算法。 【算法26】顺序查找算法查找的数据元素存储在顺序表S 中，S类型说明如下： elemtype S[MAXNUM]; 其中elemtype为数据元素的数据类型；MAXNUM为可能 有的数据元素的最大个数。 方法1:设置监视哨 int seq_search(elemtype S[],keytype k,int n) { int i; S[n].key = k; /* 监视哨：把要查找的关 键字放到S [n]单元中*/ i = 0;

线性表的查找

while (S[i].key != k) i++; if(i<n) { printf("searching success"); return( i ); } else { printf("searching failed"); return(-1); } }

线性表的查找

方法2:不设置监视哨 int seq_search(elemtype S[],keytype k,int n) { int i; i = 0; while (i<=n && S[i].key != k) i++; if(i<n) { printf("searching success"); return(i); } else { printf("searching failed"); return(-1); } }

线性表的查找

书上算法9.1: typedef struct{ ElemType *elem; Int length; }SSTable;

int Search_seq(SSTable ST,KeyType key){ ST.elem[0].key=key; for(i=ST.length; !EQ(ST.ELEM[I].KEY,KEY); --i); return i; }

线性表的查找

性能分析： 平均检索长度： 成功： Pi=1/n(概率相同),Ci=i(表中第i个数据元素所需 进行的比较次数),则顺序查找算法查找成功的平均查找 长度为ASLSq

=

PiCii 1

n

=

( n i)i 1

n

1

=

1 2

(n+1)

[1/n*(n(n+1)/2)=(n+1)/2] 约为表的一半。

线性表的查找

失败：为n+1(需进行n+1次比较后才确定查找失败)。 顺序检索效率不高，{但方法简单、可靠} 有一些方法可以提高顺序检索的效率： (1) 在算法上：减少循环的比较次数。方法是把n的 单元存放K值：使得可减少一个判断条件(i≤n),算法方法 1就是这样。 (2) 在存储方式上： A. 把经常需要查找的记录放在前面。提高成功查找 效率。 B. 把记录进行排序后存放，提高失败查找效率。

线性表的查找

二、有序表的查找(二分法查找或折半查找) 此方法是一种效率高的查找方法，查找要求表是按 关键字大小顺序排序的。 有序表的比较方法： 设：待查元素所K在区域的下界为low,上界为high,则 中间位置mid =└ (low + high)/2┘,在查找待查元素K时， 总是比较└ (low + high)/2┘(取(low + high)/2的下限值)位 置的值，如果： >└ (low + high)/2┘位置值： 在后一半进行有序表比较 K <└ (low + high)/2┘位置值： 在前一半进行有序表比较 =└ (low + high)/2┘位置值：则查找成功 或直到结束，没找到为不成功。

线性表的查找

例：[6,13,28,39,41,72,85] 在表中查找20 [6,13,28,39,41,72,85] l m h 移h [6,13,28] l m h 移l [28] lh 此题查找不成功，只进行三次比较。

线性表的查找

【算法27】 二分查找的算法 int bin_search(elemtype s[],keytype k,int n) low = 0; high = n-1; while(low <= high) { mid = (low+high)/2; if(s[mid].key == k) { printf(“searching success”); return(mid); } else if (s[mid].key < k) low = mid + 1; else high = mid – 1; } /* while循环结束 */ printf(“searching failed”);

线性表的查找

书上算法9.2: int Search_Bin(SSTable ST,KeyType key){ low=1; high=ST.length; while(low<=high){ mid=(low+high)/2; if EQ(key, ST.elem[mid].key) return mid; else if LT(key,ST.elem[mid].key) high=mid-1; else low=mid+1; } rreturn 0 }

线性表的查找

利用二叉树对有序表进行性能分析： 例：有序表 [05 13 19 21 37 56 84 75 80 88 92] 表中每个元素相对位置： 1 2 3 4 5 6 7 8 9 10 11 查找其中每个元素的比较次数为： ① mid=└(1+11)/2┘=6 ② mid=└(1+5)/2┘=3 小于往左， ③ mid=└(7+11)/2┘=9 大于往右 ┆ 6 A 如图：3 9

1

4

7

10

2

5

8

11

线性表的查找

查找比较次数最多不超过树的深度，因为每次比较可 否定一半的数据，平均查找长度ASL≈log2n,总的记录为 n,时间复杂度为O(n log2n) 证明： 2x=n 有n个记录，查找次数为x 例 n=8 x=3 n=16 x=4 则有x=log2n 优点：查找速度快； 缺点：(1) 需要排序 (2) 只适应于顺序存储 适用于不经常改动记录，而经常查找的表，但若进行插入 或删除就不方便了，此时用二叉排序树和平衡二叉排就合 适，这在动态查找时讲。。

线性表的查找

三、静态树表的查找 讨论在不等概率情况下的

查找 例：设有序表中含5个记录，它们的查找概率不等，分别 为p1=0.1, p2=0.2, p3=0.1, p4=0.4, p5=0.2, 按二分法查找查找成功的平均查找长度为 n ∑PiCi=0.1*2+0.2*3+0.1*1+.04*2+0.2*3=2.3 i=1 按从第四个记录的关键字进行比较，不成功再继续在 左子序列或右子序列中进行二分法查找，则查找成功的平 均查找长度为 n ∑PiCi=0.1*3+0.2*2+0.1*3+.04*1+0.2*2=1.8 i=1

线性表的查找

上例说明在不等概率情况下的二分法查找不一定最 优，而最优的是带权内路径长度取最小值的二叉树，即 n n PH=∑wihi=∑ (cpi)hi i=1↓ i=1↓↓ 权 常概 值 量率 当PH最小时称为静态最优查找树，但这种方法费时， 一般采用静态次优查找树。 构造静态次优查找树的方法：选取以序列中的各结点 依次为中心使其右边权值之和减去左边权值之和所得值为 最小的结点作为根结点，然后分别对所选根结点的左、右 子序列又构成两棵静态次优查找树，并分别设所选根结点 的左、右子树，以次类推。

线性表的查找

例9-1 已知含9个关键字的有序表及其相应权值为： 关键字 A B C D E F G H I 权值 1 1 2 5 3 4 4 3 5 构造静态次优查找树如图关键字 权值 累计权值 j keyj Wj S Wj Δ Pj (根) Δ Pj (根) Δ Pj (根) Δ Pj (根) 0 0 0 1 A 1 1 27 11 3 0 ↑i 2 B 1 2 25 9 1 ↑i 0 ↑i 3 C 2 4 22 6 2 4 D 5 9 15 1 ↑i 0 ↑i 0 ↑i 5 E 3 12 7 9 6 F 4 16 0 ↑i 8 1 ↑i 0 ↑i 7 7 G 4 20 8 8 H 3 23 15 9 I 5 28 23

F A D H

B

E

G

I

A

C 次优查找树

线性表的查找

例9-2 已知含5个关键字的有序表及其相应权值为： 关键字 A B C D E 权值 1 30 2 29 3

书上算法9.3 不等概率有序(即次优二叉树)的 查找算法C A B D A C A E 调整后的次优查找树 PH=105 B D E

调整前的次优查找树 PH=132

线性表的查找

Status SecondOptimal(BiTree &T,ElemType R[],float sw[],int low, int high){ i=low;min=abs(sw[high]-sw[low](;dw=sw[high]+sw[low1]; for(j=low+1;j<=high;++j) if(abs(dw-sw[j]-sw[j-1]<min){ i=j;min=abs(dw-sw[j]-sw[j-1]);} if(!)T=(BiTree)malloc(sizeof(BiTNode)))) return ERROR; T->data=R[i]; if(i==low) T->lchild=NULL; else SecondOptimal(T->lchild, R, sw, low, i-1); if(i==high) T->rchild=NULL; else SecondOptimal(T->rchild, R, sw, i+1, high);

本文来源：https://www.bwwdw.com/article/npt4.html