查找

查找分为静态查找和动态查找；

静态查找中顺序查找：

typedef float Keytype;
typedef int Keytype;
typedef char* Keytype;

typedef struct{
               Keytype key;
               ...........
     }Elemtype;

#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
#define LQ(a,b) ((a) <= (b))

#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b))<0)
#define LQ(a,b) (strcmp((a),(b))<=0)

静态查找表中顺序表查找法：
typedef struct{
Elemtype *elem;
int length;
}SStable;

int search_seq(SStable ST,Keytype key)
{
ST.elem[0].key =key;//“哨兵”
for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前查找；
return i;
}

顺序查找法性能分析：ASL=0.75*（n+1）

有序表查询可以使用折半查找：先确定待查记录所在的范围（区间），然后逐步缩小范围知道找到或找不到该记录为止。

int search_ban(SStable ST,Keytype key)
{
low=1;high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
if(key==ST.elem[mid].key) return mid;
else if(ST.elem[mid].key <key ) low=mid+1;
else
high=mid-1
}
return 0;
}

什么是好的哈希函数？

若对于关键字集合中任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等，则称此类哈希函数为均匀哈希函数。换句话说就是是关键字经过哈希函数得到一个“随机地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。