华清远见 数据结构

查找

华清远见 数据结构

“查找”(Searching)及“排序”(Sorting)是建立在数据结构上的两个重 要运算。查找(或检索)是在给定信息集上寻找特定信息元素的过程。据统计， 一些计算机、特别是商用计算机，其CPU处理时间约25%~75%花费在查找 或排序上。所以对查找和排序问题的处理，有时直接影响到计算机的工作 效率。 一、概 述 待查找的数据单位(或数据元素)称为记录。记录由若干数据项(或 属性)组成，如学生记录:学号 姓名 性别 年龄 ……

其中，“学号”、“姓名”、“性别”、“年龄”等都是记录的数 据项。若某个数据项的值能标识(或识别)一个或一组记录，称其为关键字 关键字 (key)。若一个key能唯一标识一个记录，称此key为主key。如“学号”的值 给定就唯一对应一个学生，不可能多个学生的学号相同，故“学号”在学 生记录里可作为主key。若一个key能标识一组记录，称此key为次key。如 “年龄”值为20时，可能有若干同学的年龄为20岁，故“年龄”可作次key。 下面主要讨论对主key的查找。

华清远见 数据结构

1.查找定义 查找定义 设记录表L=(R1 R2……Rn),其中Ri(l≤i≤n)为记录，对给定的某个值k, 在表L中确定key=k的记录的过程，称为查找。若表L中存在一个记录Ri 的key=k,记为Ri.key=k,则查找成功，返回该记录在表L中的序号i(或 Ri 的地址),否则(查找失败)返回0(或空地址Null)。 2.查找方法 . 查找方法很多，有顺序查找、折半查找、分块查找、树表查找及Hash 表查找等等。查找算法的优劣将影响到计算机的使用效率，应根据应用 场合选择相应的查找算法。 3.平均查找长度 . 评价一个算法优劣的量度，一是时间复杂度T(n),n为问题的体积， 此时为表长；二是空间复杂度D(n);三是算法的结构等其他特性。 对查找算法，主要分析其T(n)。查找过程是key的比较过程，时间主 要耗费在各记录的key与给定k值的比较上。比较次数越多，算法效率越 差(即T(n)量级越高),故用“比较次数”刻画算法的T(n)。另外，显 然不能以查找某个记录的时间来作为T(n),一般以“平均查找长度”来 衡量T(n)。 平均查找长度ASL(Average Search Length):对给定k,查找表L中 n 记录比较次数的期望值(或平均值),即： ASL = ∑ Pi C i

i =1 Pi为查找Ri的概率。等概率情况下Pi=1/n;Ci为查找Ri时key的比较次数(或查找次数)。

华清远见 数据结构

二、顺序表的查找 所谓顺序表(Sequential Table),是将表中记录(R1 R2……Rn)按其序号 存储于一维数组空间，如图所示。其特点是相邻记录的物理位置也是相 邻的。 R1 记录Ri的类型描述如下： R2 typedef struct … { keytype key; //记录key// … …… //记录其他项// Rn }Retype; 其中，类型keytype是泛指，即ke

ytype可以是int、float、char或其他的结 构类型等等。为讨论问题方便，一般取key为整型。 顺序表类型描述如下: #define maxn 1024; //表最大长度// typedef struct { Retype data[maxn]; //顺序表空间// int len; //当前表长，表空时len=0// }sqlist; 若说明：sqlist r,则(r.data[1],……,r.data[r.len])为记录表(R1……Rn), Ri.key为r.data[i].key, r.data[0]称为监视哨，为算法设计方便所设。

华清远见 数据结构

1 顺序查找算法及分析 顺序查找(Sequential Search)是最简单的一种查找方法。 算法思路 设给定值为k,在表(R1 R2……Rn)中，从Rn开始，查找key=k的记录。若 存在一个记录Ri (l≤i≤n)的key为k,则查找成功，返回记录序号i;否 则，查找失败，返回0。 算法描述 int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法// { int i; r.data[0].key=k; //k存入监视哨// i=r.len; //取表长// while(r.data[i].key!=k) i--; //顺序查找// return(i); } 算 法 用 了 一 点 技 巧 ： 先 将 k 存 入 监 视 哨 ， 若 对 某 个 i(≠0) 有 r.data[i].key=k,则查找成功，返回i;若i从n递减到1都无记录的key为k, i再减1为0时，必有r.data[0].key=k,说明查找失败，返回i=0。

华清远见 数据结构

顺序查找 算法分析 设Ci(1≤i≤n)为查找第i记录的key比较次数(或查找次数): 若r.data[n].key=k, Cn=1; 若r.data[n-1].key=k, Cn-1=2; …… 若r.data[i].key=k, Ci=n-i+1; …… 若r.data[1].key=k, n C1=n n n +1 1 所以，ASL= ∑ Pi C i = n ∑ (n i + 1) =i =1 i =1

2

故ASL=O(n)。而查找失败时，查找次数等于n+l,同样为O(n)。 对查找算法，若ASL=O(n),则效率是最低的，意味着查找某记录几 乎要扫描整个表，当表长n很大时，会令人无法忍受。下面关于查找的 一些讨论，大多都是围绕降低算法的ASL量级而展开的。 2 折半查找算法及分析 当记录的key按关系≤或≥有序时，即： 可采用折半或二分法查找 R1.key≤R2.key≤……≤Rn.key (升序) (Binary Search)。 或 R1.key≥R2.key≥……≥Rn.key (降序)

华清远见 数据结构

算法思路 对给定值k,逐步确定待查记录所在区间，每次将搜索空间减少一半(折 半),直到查找成功或失败为止。 设两个指针(或游标)low、high,分别指向当前待查找表的上界(表头)和 下界(表尾)。对于表(R1 R2……Rn),初始时low=l、high=n,令： mid= (low + high) / 2 指向当前待查找表中间的那个记录。下面举例说明折半查找的过程。 例1 设记录表的key序列如下: 序号： 1 2 3 4 5 6 7 8 9 10 11 12 (n=12) 03 12 18 20 32 55 60 68 80 86 90 100

low high mid low high mid 现查找k=20的记录。 mid 1mid= (1 + 12) / 2 =6。因k<r.data[6].key=55,若20存在，一定落在“55”的左 半区间(搜索空间折半)。令：high=mid-1。

2mid= (1 + 5) / 2 =3。因k>r.data[3].key=18,若20存在，一定落在“18”的右半区间。令

:low=mid+1。

3mid= (4 + 5) / 2 =4。因k=r.data[4].key=20,查找成功, 返回mid=4。

华清远见 数据结构

折半查找 再看查找失败的情况，设要查找k=85的记录。 序号： 1 2 3 4 5 6 7 8 03 low 12 18 20 32 55 60 68 9 80 10 86 11 12 (n=12)

90 100

mid low

mid low mid high high high mid

(1 + 12) / 2 =6。因k>r.data[6].key=55,若85存在，一定落在“55” 1mid=的右半区间。令：low=mid+1。 (10+12)/2 (10 + 10) / 2 =11。因k<r.data[11].key=90,若85存在，一定落在“90” 3mid= 的左半区间。令：high=mid-1。 (10 + 10) / 2 =10。因k<r.data[10].key=86,若85存在，一定落在“86” 4mid= 的左半区间。令：high=mid-1。此时，下界1ow=10,而上界high=9,表 明搜索空间不存在，故查找失败，返回0。

2mid=(7 + 12) / 2 =9。因k>r.data[9].key=80,若85存在，一定落在“80”

的右半区间。令： low=mid+1 。

华清远见 数据结构

折半查找 算法描述 int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法// { int low,high,mid; low=1;high=r.len; //上下界初值// while(low<=high) //表空间存在时// { mid=(low+high)/2; //求当前mid// if (k==r.data[mid].key) return(mid); //查找成功，返回mid// if (k<r.data[mid].key) high=mid-1; //调整上界，向左部查找// else low=mid+1; } //调整下界，向右部查找// return(0); } //low>high,查找失败// 算法分析 查找次数 对例1中记录表的查找过程 ……………. ……... 1×20 可得到如图所示的一棵判定树： 6

3 1 2 4 5 7 8

9 11 10

……………. 2×21 ………. 3×22

12

……. 4×5

华清远见 数据结构

折半查找 不失一般性，设表长n=2h-l,h=log2(n+1)。记录数n恰为一棵h层的满二 叉树的结点数。对照例1,得出表的判定树及各记录的查找次数如图所 查找次数 示。 ……………. ……... 1×20 ……………. 2×21 ………. 3×22 ……………………………………… …………………n

……… ….. h×2h-1

h 1 h i 1 i 1 0 1 2 h 2 h 1 ASL= ∑Pi Ci = ∑i 2 令S= ∑i 2 = 1 2 + 2 2 + 3 2 +……+ (h 1)2 + h 2 n i=1 i =1 i =1 1 2 3 2S= 1 2 + 2 2 + 3 2 + …… + (h 1)2 h 1 + h 2 h

S=2S-S= h 2h (20 + 21 + 22 +… + 2h 1 ) = h 2h (2h 1) = (n + 1) log 2 (n + 1) n … 故ASL= n1 n

(( n + 1) log 2 ( n + 1) n ) =

n +1 n

log 2 ( n + 1) 1

→∞

时, ASL=O(log2(n+1)),大大优于O(n)。 , 。

华清远见 数据结构

3 分块查找算法及分析 分块查找(Blocking Search),又称索引顺序查找(Indexed Sequential Search),是顺序查找方法的一种改进，目的也是为了提高查找效率。 1.分块 . 设记录表长为n,将表的n个记录分成b= n / s 个块，每块s个记录(最后 一块记录数可以少于s个),即：

且表分块有序，即第i(1≤i≤b-1)块所有记录的key小于第i+1块中记录的key, 但块内记录可以无序。 2.建立索引 . 每

块对应一索引项：

kmax

link

其中kmax为该块内记录的最大key;link为该块第一记录的序号(或指针)。

华清远见 数据结构

分块查找 例2 设表长n=19,取s=5,b= 19 / 5 = 4,分块索引结构 如图所示。 3.算法思路 分块索引查找分两步进行： . (1)由索引表确定待查找记录所在的块； (2)在块内顺序查找。Kmax 如查找k=19的记录，因19>18, 不会落在第1块；又19<50,若 19存在，必在第2块内。取第2 块起址(6),查找到key为19的记 录号为9。 查找失败情况，一是给定k值 超出索引表范围；二是若k落在 某块内，但该块中无key=k的记 录。 索引表是按照kmax有序的，可 对其折半查找。而块内按顺序 方法查找。 序号序号 R.key1 2 3 4 5 6 7 8 9 18 10 9 8 16 20 38 42 19 50 84 72 56 55 76 100 90 88 108

块1

18 50 84 108

1 6 11 16

块2

10 11 12 13 14 15 16 17 18 19

(索引表 索引表) 索引表

块3

块4

华清远见 数据结构

三、Hash表的查找 表的查找 1 Hash表的含义 表的含义 Hash表，又称散列表、杂凑表。在前面讨论的顺序、折半、分块查找 和树表的查找中，其ASL的量级在O(n)~O(log2n)之间。不论ASL在哪 ~ 个量级，都与记录长度n有关。随着n的扩大，算法的效率会越来越低。 ASL与n有关是因为记录在存储器中的存放是随机的，或者说记录的key 与记录的存放地址无关，因而查找只能建立在key的“比较”基础上。 理想的查找方法是：对给定的k,不经任何比较便能获取所需的记录， 其查找的时间复杂度为常数级O(C)。这就要求在建立记录表的时候，确 定记录的key与其存储地址之间的关系f,即使key与记录的存放地址H相 f 对应： key H: 记 录 ： 或者说，记录按key存放。之后，当要查找key=k的记录时，通过关系f 就可得到相应记录的地址而获取记录，从而免去了key的比较过程。这 个关系f就是所谓的Hash函数(或称散列函数、杂凑函数),记为 H(key)。它实际上是一个地址映象函数，其自变量为记录的key,函数 值为记录的存储地址(或称Hash地址)。 另外，不同的key可能得到同一个Hash地址，即当keyl≠key2时，可能 有H(key1)=H(key2),此时称key1和key2为同义词 同义词。这种现象称为“冲突 冲突” 同义词 冲突 或“碰撞”,因为一个数据单位只可存放一条记录。

华清远见 数据结构

Hash表 表 一般，选取Hash函数只能做到使冲突尽可能少，却不能完全避免。这 就要求在出现冲突之后，寻求适当的方法来解决冲突记录的存放问题。 例3 设记录的key集合为C语言的一些保留字，即k={case、char、float、for、 int、while、struct、typedef、union、goto、viod、return、switch、if、 break、continue、else},构造关于k的Hash表时，可按不同的方法选取 H(key)。 (1)令H1(key)=key[0]-‘a’,其中key[0]为key的第一

个字符。 显然这样选取的Hash函数冲突现象频繁。如：H1(float)=H1(for)=‘f’-‘a’=5。 Hash H (for)= f - a =5 解决冲突的方法之一是为“for”寻求另一个有效位置。 (2)令H2(key)=(key[0]+key[i-l]-2*‘a’)/2。其中key[i-l]为key的最后一个字符。 如：H2(float)=(‘f’+‘t’-2*‘a’)/2=12,H2(for)=(‘f’+‘r’-2*‘a’)/2=11,从而消除 了一些冲突的发生，但仍无法完全避免，如：H2(case)=H2(continue)。 综上所述，对Hash表的含义描述如下： 根据选取的Hash函数H(key)和处理冲突的方法，将一组记录(R1 R2……Rn)映象到记录的存储空间，所得到的记录表称为Hash表，如图： 、 (R1 R2……Rn) H(key)、解决冲突方法 R2 … R1 Rn

(Hash表) 表

华清远见 数据结构

2 Hash函数的构造方法 函数的构造方法 关于Hash表的讨论关键是两个问题，一是选取Hash函数的方法；二 是确定解决冲突的方法。 选取(或构造)Hash函数的方法很多，原则是尽可能将记录均匀分布， 以减少冲突现象的发生。以下介绍几种常用的构造方法。 1.直接地址法 . 此方法是取key的某个线性函数为Hash函数，即令： H(key)=a·key+b 其中a、b为常数，此时称H(key)为直接Hash函数或自身函数。 例4 设某地区1~100岁的人口统计表如表： 记录岁数 人数

R11 3000

R22 2500

…… …… ……

R2525 20000

…… …… ……

R100100 10

给定的存储空间为b+l~b+l00号单元(b为起始地址),每个单元可以 存放一条记录Ri(l≤i≤l00)。取“岁数”为key,令： H(key)=key+b 则按此函数构造的Hash表如下图所示：

华清远见 数据结构

Hash函数的构造 函数的构造 H(key) 岁数 b+1 b+2 … b+25 … b+100

人数

1 2 … 25 … 100

3000 2500 … 20000 … 10

当Hash表构造好后，如查找key=25岁 的人口，取H(25)=b+25,该地址单元便是 要查找的内容。直接地址不是压缩映象， 即用直接地址法产生Hash函数时，要求 key集与地址集的大小相等，所以不同的 key之间无冲突现象发生。用直接地址方 法选取Hash函数受到很大的限制，因为 key的取值范围一般远大于表的地址空间。

华清远见 数据结构

2.数字分析法 例5 设记录数等于80,记录的key为6位10进制数，即key=(k1 k2 k3 k4 k5 k6)10, ki(1≤i≤6)=0|1|2|……|9。另设表长为l00,地址空间为00~99,则可令： H(key)=kikj ki、kj为key中的某两位。具体取哪两位呢？要进行具体的“分析”,原则 是使这80个记录能较均匀地分布。例如这80个记录的key如表： 其中，k1 、k2 和k6 不可取， 否则冲突现象太严重；k5的 随机性也不理想；而k3、k4 的随机性较好，故取 H(key)= k3 k4 。于是，在构 造 Hash 表 时 ， key=231586 的记录被映象到“15”号单 元 ， key=242346 的 记 录 被 映象到“23”号单元，依此 类推。 k1 2 2 2 2 … 2 2 k2 3 4 3 3 … 4 3 k3 1 2 3 9 … 5

4 k4 5 3 7 8 … 7 2 k5 8 4 9 8 … 8 9 k6 6 6 6 6 … 6 6

此方法也受到限制。当记录动态产生时，事先无法得到记录表，因而 很难进行“分析”。也可能存在这种情况：如记录R1~R10中，k1k2的随 机性不好，k3较好，但从R11~R20时，情况反过来，使得确定H(key)变得

华清远见 数据结构

Hash函数的构造 函数的构造 3.平方取中法 . 当取key中某些位为Hash地址而不能使记录均匀分布时，根据数学原理， 取(key)2中的某些位可能会比较理想，所以平方取中法中，令： H(key)= ( key12~1+ r ) 即取(key)2中从左数第l位到第l+r位为选取的Hash函数，r具体多大，视给定 的存储空间而定。 例6 设Hash表地址空间为000~999。对一组随机性不好的key,按平方取中 法选取的H(key)如表所列： key (key)2 H(key) 0100 0110 1010 1001 0111 00 100 00 00 121 00 10 201 00 10 020 01 00 123 21 100 121 201 020 123

令：H(key)= (key)2 3—5 ,l=3、r=2。 (key)2的随机性比key要好得多，从 而使冲突现象减少。

华清远见 数据结构

Hash函数的构造 函数的构造 4.叠加法 . 将key分割成位数相同的几部分(最后一部分位数可以不同),然后取 各部分的叠加值作为H(key)。该方法又分为“移位叠加”和“间界叠 加”,前者是将分割后的每部分低位对齐相加；后者是沿分割线来回折 叠、对齐相加。 例7 设图书记录：(ISBN,书名，作者，种类，出版日期……),其中ISBN为 图书的国际标准编号，它是带分隔符的10进制数，取ISBN为key。 当图书种类少于10000时，地址空间取0000~9999,用叠加法构造值为4 10000 0000 9999 4 位的Hash函数。例如某图书的ISBN=7-04-005265-2,从低位起，每4位分 割。

7-0 | 4-005 | 265-2移位叠加： 2652 间界叠加： 2652 4005 5004 + 70 + 70 6727 7726 移位叠加时，H(7-04-005265-2)=6727,亦即该书对应的记录映象到表的 6727号单元；用间界叠加时，该书被映象到7726号单元。

华清远见 数据结构

Hash函数的构造 函数的构造 5.保留除数法 . 又称质数除余法，设Hash表空间长度为m,选取一个不大于m的最大质数p, 令：

H(key)=key%p

例如：m=8 16 32 64 128 256 512 1024 …… p=7 13 31 61 127 251 503 1019 …… 为何选取p为不大于m的最大质数呢？举例说明。 例8 设记录的key集合k={28,35,63,77,105……},若选取p=21=3*7(包括质 数因子7),有： key:28 35 63 77 105 …… H(key)=key%21: 7 14 0 14 0 …… 使得包含质数因子7的key都可能被映象到相同的单元，冲突现象严重。若取 p=l9(质数),同样对上面给定的key集合k,有： key:28 35 63 77 105 H(key)=key%19: 9 16 6 1 10 H(key)的随机度就好多了。

华清远见 数据结构

Hash函数的构造 函数的构造 6.随机函数法 随机函数法 编程语言中一般都提供一些随机函数，令：

H(key)=C×random(key) ×其中random(key)为相应于key的一个随机函数；

C为常数，选取相应的C 值使得H(key)符合Hash地址的要求。当key长度不一时，用此方法选取 Hash函数是合适的。 以上介绍了选取Hash函数的6种方法。从中看出，选取Hash函数要考 虑的因素为： (1)key的长度、类型以及分布的情况； (2)给定的Hash表表长m; (3)记录的查找效率等。 通常是几种方法结合使用，目的是使记录更好地均匀分布，减少冲突的发 生。