静态查找
顺序查找(Sequential Search)
基本过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直到第一个记录，其关键字和给定值比较都不等，则表明表中没有所查找记录，查找不成功。
二分查找
以有序表表示静态查找时
折半查找(Binary Search)基本过程：
先确定待查找记录所在的范围，然后逐步缩小范围直到找到活找不到记录为止。
–>斐波那契树查找
–>差值查找
分块查找(索引顺序表的查找)
顺序查找的一种改进方法。除表本身以外，尚需建立一个”索引表”。包括两项：关键字项和指针项
先确定待查找记录所在的块，然后在块中顺序查找。
一下是三种查找的实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
typedef int keyType;
typedef struct{
Elemtype elem[100];
int length;
}SSTable;
typedef struct{
Elemtype elem;
int low, high;
}IDXType;
int Search_Seq(SSTable ST, keyType key){
int i;
for ( i = ST.length-1; key != ST.elem[i] && i>=0 ; --i);
return i;
}
int Search_Bin(SSTable ST, keyType key){
int low = 0;
int high = ST.length;
int mid;
while (low <= high){
mid = (low + high) / 2;
if (key == ST.elem[mid])
return mid;
else if (key < ST.elem[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int Search_Blk(SSTable ST,IDXType idx[], int m, keyType key){ //m表示索引表的规模
int low = 0, high = m - 1,mid,i,j;
int find = false;
while (low <= high && !find){
mid = (low + high) / 2;
if (key < idx[mid].elem)
high = mid - 1;
else if (key > idx[mid].elem)
low = mid + 1;
else{
high = mid - 1;
find = true;
}
}
if (low < m){
i = idx[low].low;
j = idx[low].high;
}
printf("%d %d\n", i, j);
while (i < j&& ST.elem[i] != key)
i++;
if (i >= j)
return -1;
else
return i;
}
int main(){
int test[11] = { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };
SSTable ST;
int i;
ST.length = 11;
for (i = 0; i < 11; i++){
ST.elem[i] = test[i];
}
printf("%d\n", Search_Seq(ST, 6));
printf("%d\n", Search_Seq(ST, 80));
printf("%d\n", Search_Bin(ST, 6));
printf("%d\n", Search_Bin(ST, 80));
//分块查找 构造索引表
IDXType idx[3];
idx[0].elem = 21;
idx[0].low = 0;
idx[0].high = 3;
idx[1].elem = 64;
idx[1].low = 4;
idx[1].high = 6;
idx[2].elem = 94;
idx[2].low = 7;
idx[2].high = 10;
printf("%d\n",Search_Blk(ST, idx, 3, 6));
printf("%d\n", Search_Blk(ST, idx, 3, 80));
return 0;
}