数据查找顺序二分索引哈希查找.docx

数据查找顺序二分索引哈希查找.docx

《数据查找顺序二分索引哈希查找.docx》由会员分享，可在线阅读，更多相关《数据查找顺序二分索引哈希查找.docx（28页珍藏版）》请在冰点文库上搜索。

数据查找顺序二分索引哈希查找

选题八数据查找

一、基本概念

查找表：

是由同一类型的数据元素（或记录）构成的集合。

查找：

也称检索，即根据给定的某个值，在查找表中确定一个其关键字等于给定值的第一条记录（元素）或全部记录。

若表中存在这样的记录，则查找成功，通常要求返回该记录存储位置；若不存在这样的记录，表明查找失败，返回特定值。

例：

在下表中查找学号为“98182”的学生信息

学号  

姓名

性别

籍贯

出生年月

1

98131

刘激扬

男

北京

1979.12 

2

98164

衣春生

男

青岛

1979.07

3

98165

卢声凯

男

天津

1981.02

4

98182

袁秋慧

女

 广州 

1980.10

5

98203

林德康

男

上海

1980.05

平均查找长度：

在查找成功情况下平均比较次数，可用作判定一个查找算法的时间复杂度：

其中：

n：

查找表长；

Pi：

查找第i个元素；

Ci：

查找第i个元素比较次数。

二、顺序查找

1．查找思路

顺序表：

指线性表的顺序存储结构。

本章讨论中，设顺序表采用一维数组A表示，其元素类型为ElemType，它含有关键字域key和其它一些数据域，并设定A的大小为整型常量MaxSize，数组的元素个数为n，n应小于等于MaxSize。

　typedefstruct{

　　KeyTypekey;

　　… 

　}ElemType;

顺序查找：

又称线性查找，它是一种最简单最基本查找方法。

查找思路：

从顺序表的一端开始，依次将每个元素关键字同给定值K进行比较，若某个元素关键字等于K，则查找成功，返回该元素所在下标，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败，反回特定值（常用-1表示）。

基本算法

intSeqsch（ElemTypeA[],intn,KeyTypeK）

{ 

//从顺序表A的n个元素中顺序查找关键字为K的元素，若成功返回其下标，否则返回-1

for（inti=0;i

if（A[i].key==K）

break;

if（i

   returni;

else

   return-1; 

}

如下图：

0

1

2

3

4

5

23

4

56

43

2

78

在顺序表中查找56，比较3次。

改进算法

对该算法作一改进：

在表的尾端A[n]设一岗哨，在查找前先将K赋给A[n],这样每循环一次不需比较下标是否越界，当比较到第n位置时，由于A[n].key==K成立，必退出循环。

intSeqsch（ElemTypeA[],intn,KeyTypeK）

{

//从顺序表A的n个元素中顺序查找关键字为K的元素，若成功返回其下标，否则返回-1

A[n].key=k;//设置岗哨 

for（inti=0;;i++）

if（A[i].key==K）

break;

if（i

returni;

else

return-1; 

}

在顺序表中查找56，设A[6]=56为岗哨：

0

1

2

3

4

5

6

23

4

56

43

2

78

56

性能描述

平均查找长度为：

顺序查找时间复杂度为O（n）。

缺点：

速度较慢，查找成功最多需比较n次，平均查找长度约为表长一半。

优点：

算法简单，适应面广，对表结构无任何要求。

三、二分查找

二分查找又称折半查找。

作为二分查找对象的表必须是顺序存储的有序表。

查找过程：

首先取整个有序表A[0]～A[n-1]的中点元素A[mid]（mid=└（n-1）/2┘的关键字与K比较。

如下图所示：

例如：

查找23：

查找96：

查找58：

1．二分查找的递归算法

intBinsch（ElemTypeA[],intlow,inthigh,KeyTypeK）

{//在A[low]～A[high]内查找K,low初值为0,high初值n-1

if（low<=high）

{

intmid=（low+high）/2;//求中间点下标

if（K==A[mid].key）

returnmid;//查找成功返回

elseif（K

returnBinsch（A,low,mid-1,K）;//左子表上查找

else

returnBinsch（A,mid+1,hign,K）;//右子表上查找

}

elsereturn-1;//查找失败反回-1

}

2．二分查找的非递归算法

在下面的递增有序序列中查找关键字6。

四、索引查找

1．概念

索引查找：

又称分级查找，计算机中为索引查找建立一张主表和各级索引表。

索引存储的基本思想是：

首先把一个线性表（主表）按一定的函数关系划分成若干逻辑上的子表，为每个子表分别建立一个索引项，由所有这些索引项构成主表的一个索引表，然后可采用顺序或链接方式存储索引表和子表。

职工号

姓名

单位

职称

工资

JS001

王大明

计算机

教授

680

JS002

吴进

计算机

讲师

440

JS003

邢怀学

计算机

讲师

460

DZ001

赵利

电子

助教

380

DZ002

刘平

电子

讲师

480

DZ003

张卫

电子

副教授

600

JJ001

安晓军

机械

讲师

450

JJ002

赵京华

机械

讲师

440

HG001

孙亮

化工

教授

720

HG002

陆新

化工

副教授

580

HG003

王方

化工

助教

400

索引表中每个索引项通常包含三个域：

一是索引值域（index）；二是子表开始位置域（start）；三是子表长度域（length）。

一个学校的教师登记表如下表，其中职工号作为关键字：

以每个记录的“职工号”作关键字，则线性表可简记：

LA=（JS001,JS002,JS003,JS004,DZ001,DZ002,DZ003,JJ001,JJ002,HG001,HG002,HG003）若按“单位”数据项值对LA划分，则得四个子表：

JS=（JS001,JS002,JS003）

DZ=（DZ001,DZ002,DZ003）

JJ=（JJ001,JJ002）

HG=（HG001,HG002,HG003）

可得索引表b1，如图所示：

index

start

length

0

JS

0

3

1

DZ

3

3

2

JJ

6

2

3

HG

8

3

2．索引表类型定义

索引项的类型和顺序存储的索引表类型如下定义：

structIndexItem

{

IndexKeyTypeindex;//IndexKeyType为事先定义

//的索引值类型

intstart;//子表中第一个元素所在下标位置

intlength;//子表的长度

};

typedefIndexItemindexlist[ILMSize];//ILMSize为事先定义整型常量，它大于等于索引项m。

若所有子表（合称为主表）被顺序存储在同一数组中，类型定义如下：

typedefElemTypemainlist[MaxSize];//MaxSize为事先定义的整型常量，它大于等于n。

index

start

length

0

JS

0

3

1

DZ

3

3

2

JJ

6

2

3

HG

8

3

3．索引查找算法

算法思路：

索引查找是有索引表和主表上进行的查找，其过程是：

先根据给定的索引值K1，在索引表上查找出索引值等于K1的索引项，以确定对应子表在主表中开始位置和长度，再根据给定关键字K2，在对应子表中查找出关键字等于K2的结点。

一个学校的教师登记表如下，职工号作为关键字：

职工号

姓名

单位

职称

工资

JS001

王大明

计算机

教授

680

JS002

 吴进

计算机

讲师

440

JS003

邢怀学

计算机 

讲师

460

DZ001

 赵利

电子

助教

380

DZ002

刘平

电子

讲师

480

DZ003

 张卫

电子

副教授

600

JJ001  

安晓军 

机械

讲师

450

JJ002 

赵京华

机械

讲师

440

HG001 

孙亮

化工

教授

720

HG002 

陆新

化工

副教授

580

HG003 

王方

化工

助教

400

按“单位”数据项值对线性表划分，则得四个子表：

JS=（JS001,JS002,JS003）

DZ=（DZ001,DZ002,DZ003）

JJ=（JJ001,JJ002）

HG=（HG001,HG002,HG003）

可得索引表b1，如图所示：

index

start

length

0

JS

0

3

1

DZ

3

3

2

JJ

6

2

3

HG

8

3

ntIndsch（mainlistA,indexlistB,intm,IndexKeyTypeK1,KeyTypeK2）

{

//利用主表A和大小为m的索引表B索引查找索引值为K1,关键字为K2的记录，返回该记录在主表中的下标位置，若查找失败返回-1

inti,j;

//在索引表中顺序查找索引值为K1的索引项

for（i=0;i

if（K1==B[i].index）break;

if（i==m）return-1；

//在已查找到的第i个子表中顺序查找关键字为K2的记录

j=B[i].start;

while（j

if（K2==A[j].key）break;

elsej++;

if（j

elsereturn-1;

}

设索引表长度为m,相应子表长度为s,索引查找的平均查找长度为：

（m+1）/2+（s+1）/2

4．分块查找

分块查找：

属于索引查找，它要求主表中每个子表之间递增（递减）有序，并且索引表中每个索引项的索引值域用来存储对应块中最大关键字。

分块查找算法：

intBlocksch（mainlistA,indexlistB,intm,KeyTypeK）

{

//利用主表A和大小为m的索引表B分块查找关键字为K的记录

inti,j;

//在索引表中顺序查找关键字为K所对应的索引项

for（i=0;i

if（K<=B[i].index）break;

if（i==m）return-1;

//在已经查找到的第i个子表中顺序查找关键字K

j=B[i].start;

while（j

if（K==A[j].key） break; 

else j++;

//若查找成功则返回元素的下标位置，否则返回-1

if（j

else  return-1;

}

五、散列查找

1．基本概念

散列函数：

在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量，通过函数h（K）计算出该元素的存储位置，我们将h函数称为散列函数或哈希函数。

h（K）的值称为散列地址或哈希地址。

例：

假定一个线性表为A=（18,75,60,43,54,90,46），选取散列函数为：

h（K）=K%m取m=13

则得每个元素散列地址：

h（18）=18%13=5h（75）=75%13=10 h（60）=60%13=8h（43）=43%13=4

h（54）=54%13=2h（90）=90%13=12 h（46）=46%13=7

根据散列地址，实现元素的存储映象H[m]：

0

1

2

3

4

5

6

7

8

9

10

11

12

H

54

43

18

46

60

75

90

冲突：

在实际应用中，通常可能出现一个待插入元素的散列地址单元已被占用情况，使得该元素无法直接存入此单元，这种情况称为冲突。

同义词：

具有不同关键字而具有相同散列地址的元素称为同义词，即key1≠key2，但h（key1）=h（key2）。

由同义词引起的冲突称作同义词冲突。

例：

如向下表中再插入元素70时，70%13=5，则出现了冲突

0

1

2

3

4

5

6

7

8

9

10

11

12

H

54

43

18

46

60

75

90

装填因子（α）：

指散列表中已存入的元素数n与散列表空间大小m的比值,即：

α=n/m。

当α越小时，冲突可能性就越小，但同时，存储空间利用率就越低。

散列表：

根据设定的哈希函数及处理冲突的方法将一组关键字映象到一个有限的连续的地址集上，即把记录存放在表中映象的位置上，这种表便称为散列表（哈希表）。

一个散列表的好坏与三个因素有关：

●装填因子

●所采用的散列函数

●解决冲突的方法

2．散列函数

构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上，同时使计算尽可能简单，以节省计算时间。

直接定址法

以关键字K本身或关键字加上某个数值常量C作为散列地址的方法，对应的散列函数：

h（K）=K+C（C为常数）

例：

有一个解放后出生的人口调查表，关键字是年份，h（K）=K+（-1948），如表所示：

地址   01  02 03      …            22… 

年份

194919501951    …            1970…

人数

 …  …  …                    15000... 

除留余数法

以关键字K除以散列长度m所得余数作为散列地址的方法，对应的散列函数：

h（K）=K%m

m为散列表长，取m=13,得散列表：

0

1

2

3

4

5

6

7

8

9

10

11

12

H

54

43

18

46

60

75

90

●取m为奇数比取m为偶数好

●确保m的值大于等于待散列的线性表的长度n

●当关键字K为字符串时，需转换为整数（先求K长，接着把每个字符的ASCII码累加到无符号整型量h上，并且每次累加前，h值左移3位，扩大8倍）

intHash（char*K,intm） 

{

//把字符串K转换为0～m-1之间的一个值作为对应记录的散列地址

intlen=strlen（K）;//求字符串K的长度

unsignedinth=0; 

for（inti=0;i

{

//采用一种方法计算K所对应的整数

h<<=3;//h的值左移3位

h+=K[i];

}

returnh%m;

}

数字分析法

取关键字中某些数值较分散的数字位作为散列地址的方法，适用于所有关键字已知，并对关键字中每一位的取值分布情况作了分析。

例：

有一组关键字如下：

92326875

92739628

92343634

92706816

92774638

92381262

92394220

通过分析：

每个关键字从左到右第1、2、3位和第6位取值较集中，不宜作散列地址，其余的第4、5、7、8位取值分散，可以选择，若取最后两位作散列地址，得：

（2,75,28,34,16,38,62,20）

平方取中法

取关键字平方的中间几位作为散列地址的方法，由平方取中法得到的散列地址同关键字的每一位都有关，使得散列地址有较好分散性。

它适用于关键字中每一位取值都不够分散或者较分散的位数小于散列地址所需要的位数的情况。

折叠法：

首先将关键字分割成位数相同的几段（最后一段位数可少一些），然后将它们的叠加和（舍去最高位进位）作为散列地址的方法。

例：

有一关键字：

K=68242324，散列地址3位，将此关键字从左到右每三位一段划分后相叠加得：

3．处理冲突的方法

1）开放定址法

思路：

从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元的一类处理冲突的方法。

在使用该方法处理冲突的散列表中，查找一个元素的过程是：

先根据给定关键字K，利用与插入时使用的同一散列函数h（K）计算出散列地址（设下标为d）,然后用K同d单元的关键字比较，若相等则查找成功，否则按插入时处理冲突的相同次序，依次用K同所查单元的关键字比较，直到查找成功或查找到一空单元（表明查找失败）为止。

三种方法：

✧线性探查法

是用开放定址法处理冲突的一种最简单的探查方法。

从发生冲突的d单元起,依次探查下一个单元,直到碰到一个空闲单元或探查完所有单元为止探查时,当达到下标为m-1的表尾单元时,下一个探查的单元是下标为0的表首单元。

探查序列为d,d+1,d+2……，表示为（d+i）%m （0≤i≤m-1）。

例如：

构取m=13,线性表为A=（18,75,60,43,54,90,46），构造的散列表如下：

0

1

2

3

4

5

6

7

8

9

10

11

12

H

54

43

18

46

60

75

90

现向表中再插入关键字为31和58的两个元素,用线性探查法解决冲突。

先插入31，h（31）=31%13=5,因H[5]被占用，探查下一个即下标为6的单元，空闲，插入31。

0

1

2

3

4

5

6

7

8

9

10

11

12

H

54

43

18

31

46

60

75

90

再插入58，h（58）=58%13=6,因H[6]被占用，探查下一个即下标为7的单元，因H[7]仍不空闲，再接着向下探查，当探查到下标为9的单元时，空闲，插入58。

0

1

2

3

4

5

6

7

8

9

10

11

12

H

54

43

18

31

46

60

58

75

90

利用线性探查法处理冲突易造成元素的“堆积”（聚集） 

0

1

2

3

4

5

6

7

8

9

10

11

12

H

54

43

18

46

60

75

90

向散列表中插入一个元素：

intInsert（hashlist1HT,intm,ElemTypeitem）

{

//向长度为m的散列表HT中插入一个元素

intd=H（item.key,m）; //可选一种合适的构造散列函数的方法，计算散列地址

inttemp=d;

while（HT[d].key!

=NullTag）

{

//当d单元不空时继续向后查找空位置

d=（d+1）%m;

if（d==temp）return0; 

}

HT[d]=item;//将新元素插入到下标为d的位置

return1;

}

从散列表中查找一个元素：

intSearch（hashlist1HT,intm,ElemTypeitem）

{

//从长度为m的散列表HT中查找

intd=H（item.key,m）;

inttemp=d;

while（HT[d].key!

=NullTag）

{

//当散列地址中的关键字域不为空则循环 

if（HT[d].key==item.key）   returnd; 

else  d=（d+1）%m;

if（d==temp）return-1; 

}

return-1;

}

✧平方探查法

探查序列为d,d+12,d+22……,表示为（d+i2）%m（0≤i≤m-1）。

递推公式为：

优点：

它是一种较好的处理冲突的方法，可以较好避免堆积现象

缺点：

不能探查到散列表上所有单元。

例：

当d0=5,m=17时，只能探查到下标依次为5、6、9、14、4、13、7、3、1的单元。

d0=5; 

d1=（5+2*1-1）%17=6; d2=（6+2*2-1）%17=9; 

d3=（9+2*3-1）%17=14;d4=（14+2*4-1）%17=4;

d5=（4+2*5-1）%17=13;d6=（13+2*6-1）%17=7;

d7=（7+2*7-1）%17=3; d8=（3+2*8-1）%17=1; d9=（1+2*9-1）%17=1;

✧双散列函数探查法

思路：

该方法使用两个散列函数h1和h2，其中h1和前面的h（K）一样，以关键字为自变量，产生一个0～m-1之间的数作散列地址;h2也以关键字为自变量，产生一个1～m-1之间的、并和m互素的数作散列地址。

它的探查序列为：

利用双散列法，按一定的距离，跳跃式地寻找“下一个”桶，减少了“堆积”的机会，最多经过m-1次探查，它会遍历表中所有位置，回到H0位置。

例：

给出一组表项关键码{22,41,53,46,30,13,01,67}。

散列表为HT[0..10]，m=11。

散列函数为：

Hash（x）＝（3x）%11

再散列函数为：

ReHash（x）=（7x）%10+1

Hi=（Hi-1+（7x）%10+1）%11,i=1,2,

H0（22）=0H0（41）=2H0（53）=5H0（46）=6 

H0（30）=2冲突H1=（2+1）=3,H0（13）=6冲突H1=（6+2）=8 

H0（01）=3冲突H1=（3+8）=0,H2=（0+8）=8H3=（8+8）=5

H4=（5+8）=2H5=（2+8）=10,H0（67）=3冲突,H1=（3+10）=2H2=（2+10）=1 

搜索成功的平均搜索长度：

2）链接法

思路：

就是把发生冲突的同义词元素（结点