第九章 线性表的查找

线性表的查找

第九章

查找

查找是数据处理中使用广泛的一种运算。 所谓查找就是在一种数据结构中查找满足某种条件的 结点。有两种常用的查找方式： (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) 只适应于顺序存储 适用于不经常改动记录，而经常查找的表，但若进行插入 或删除就不方便了，此时用二叉排序树和平衡二叉排就合 适，这在动态查找时讲。。