10 65
865
9761059 95 97.6
()
2.7
·
·
·
a.
b.
271
KKK
1,(
typedef struct{
int key;
float info;
}SSTable;
Key info
0 1 2 3 4 5 6 7
a
40 80 30 6010 20 25
(b) K=80 (return i=4)
80 40 80 30 6010 20 25
0 1 2 3 4 5 6 7
(c) K=90 (return i=0 )
0 1 2 3 4 5 6 7
90 40 80 30 6010 20 25
int Search_seq(SSTable ST[ ],int n,int key)
{ int i=n;
ST[0].key=key;
while(ST[i].key!=key) i- -; /**/
return i;
}
0
ASL=(1+2+3+4+……+n)/n=(n+1)/2
n+1
ASL==((n+1)/2+n+1)/2=(n+1)3/4
2.7.2
2379 mid=(low+high)/2
( 08,14,23,37,46,55,68,79,91 )
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low high=mid-1mid( 08,14,23,37,46,55,68,79,91 )
low=mid+1 high
mid
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low high
mid
c
int Search_Bin( SSTable ST[ ],int n,int key)
{int low,high,mid;
low=1; high=n;
while(low<=high)
{ mid=(low+high)/2;
if(ST[mid].key= = key) return (mid); /**/
else if( key< ST[mid].key) high=mid-1; /**/
else low=mid+1; /**/
}
return (0); /**/
}
2.7.3
20 53 89
1 6 11
18 12 8 5 20 51 36 22 29 53 89 60 72 66 76
1.
2.
22
18 12 8 5 20 51 36 22 29 53 89 60 72 66 76
1 ——
2.7.3 HSAE
3127262119161309
11
0501
02
H(K)=int(K/3)+1
121110987654321
2
1 —— HK=K HK=A*K+BAB
20
33
01 02 03 …… 20
1 2 3 ……,20
……,……,……,…… ……
2——
K=308K2=94864HK=486
3 —— mp HK=K MOD p p?m
3
1
Hk=k MOD m
m,m=11)
p,
P+1,P+2,P+3,…,m -1,0,1,…,P-1.
29
17
60
0
1
2
3
4
5
6
7
8
9
10
3
1
HK=K MOD m m
i
Hi=(H(K)+di)MOD m (di=1,2,…,m -1i=1,2,…,F(F<=m -1))
60
17
29
38
0
1
2
3
4
5
6
7
8
9
10
# difine M 100
int h(int k) {
return (k%97);}
int SearchHase(int t[ ],int k)
{ int i,j=0;
i=h(K); /* */
while(j<M &&( t[i+j}%M!=k)&&(t[i+j)%M!=0)
j++; /**/
i=(i+j)%M;
if(t(i)= =k) return (i); /* */
else return (-1)} /**/
(2)
21 14 1958 65 32 72
H(K)=K MOD 11
21 65 32
19
72
14 58
0
1
2
3
4
5
6
7
8
9
10