线性表的查找 -- 顺序查找、折半查找、分块查找

数据定义?

typedef int KeyType;
typedef int InfoType;
typedef struct {
?? ?KeyType key;
?? ?InfoType info;
}RecType;

顺序查找?

//顺序查找
int SeqSearch(RecType R[], int n, KeyType k)
{
?? ?int i = 0;
?? ?while (i < n && R[i].key != k)
?? ??? ?i++;
?? ?if (i >= n)
?? ??? ?return 0;
?? ?else
?? ??? ?return i + 1;
}
//顺序查找 哨兵
int SeqSearch1(RecType R[], int n, KeyType k)
{
?? ?int i = 0;
?? ?R[n].key = k;
?? ?while (R[i].key != k)
?? ??? ?i++;
?? ?if (i == n)
?? ??? ?return 0;
?? ?else
?? ??? ?return i + 1;
}

折半查找?

// 折半查找
int BinSearch(RecType R[], int n, KeyType k)
{
?? ?int low = 0, high = n - 1, mid;
?? ?while (low <= high)
?? ?{
?? ??? ?mid = (low + high) / 2;
?? ??? ?if (k == R[mid].key)
?? ??? ??? ?return mid + 1;
?? ??? ?else if (k < R[mid].key)
?? ??? ??? ?high = mid - 1;
?? ??? ?else
?? ??? ??? ?low = mid + 1;
?? ?}
?? ?return 0;
}

分块查找?

// 分块查找
// 索引表数据类型
#define MAXI 20
typedef struct {
?? ?KeyType key; ? //关键字类型
?? ?int link; //对应块起始下标
}IdxType;
int IdxSearch(IdxType I[], int b, RecType R[], int n, KeyType k)
{
?? ?int s = (n + b - 1) / b; ?//s 每块元素个数 n/b|~~|
?? ?int low = 0, high = b - 1;
?? ?int mid, i;
?? ?// 折半找 块位置
?? ?while (low <= high)
?? ?{
?? ??? ?mid = (low + high) / 2;
?? ??? ?if (I[mid].key >= k)
?? ??? ??? ?high = mid - 1;
?? ??? ?else
?? ??? ??? ?low = mid + 1;
?? ?}
?? ?//在索引表 high+1 块中顺序查找
?? ?i = I[high + 1].link;
?? ?while (i <= I[high + 1].link + s - 1 && R[i].key != k)
?? ??? ?i++;
?? ?if (i <= I[high + 1].link + s - 1)
?? ??? ?return i + 1;
?? ?else
?? ??? ?return 0;
}