删除:不改变标志位,关键字值改为NeverUsed
搜索:终止条件:遇到标志位为True或回到h(key)
插入:找到的第1个空关键字处,其值为NeverUsed
线性探查法的缺点:易使元素在表中连成一片,使得探查次数增加,影响搜索效率
改进方法:1、二次探查法
二次探测法使用下列探测序列进行探测,直到某个位置为空时,将关键字为key的元素插入该位置。
h(key),h1(key),h2(key),…,h2i-1(key),h2i(key),…。
探测序列由下列函数得到:
h2i-1(key)=(h(key)+i2)%M
h2i(key)=(h(key)-i2)%M
i=1,2,(M-1)/2
M是表长,应该是4k+3的素数,k是一整数。
i=1, h1(key)=(h(key)+12)%M
h2(key)=(h(key)-12)%M
i=2,h3(key)=(h(key)+22)%M
h4(key)=(h(key)-22)%M
2、双散列法
二次探测法能改善“线性聚集”,但是当二个关键字散列到同一位置时,则会有相同的探测序列,
产生“二次聚集”(如上例)。双散列法可以避免“二次聚集”。
使用下列探测序列进行探测,直到某个位置为空时,将关键字为key的元素插入该位置。
h1(key),(h1(key)+ h2(key))%M,(h1(key)+ 2h2(key))%M,…。
或 Hi=(h1(key)+ i*h2(key)) % M (i=0,1,M-1)
h2(key)应该是小于M且与M互质的整数,以保证探测序列能够最多经过M次探测即可遍历表中所有地址。
例如:若M为素数,则可取h2(key)=key%(M-2)+1
#include <stdio.h> #include <stdlib.h> #define NewArray(k) (HsNode*)malloc((k)*sizeof(HsNode)) #define FALSE 0 #define TRUE 1 #define NeverUsed 0 typedef int BOOL; typedef int KeyType ; typedef int DataType; typedef struct entry{ KeyType Key; DataType Data ; }T; typedef struct hsnode { T Element; BOOL Empty; }HsNode; typedef struct hashtable { int M; HsNode *t; }HashTable; void CreateHashTable(HashTable *htb,int divitor) { int i ; htb->M=divitor; htb->t=NewArray(htb->M); for(i=0;i<htb->M;i++) { htb->t[i].Empty=TRUE;//标志位空,用于散列表的搜索 htb->t[i].Element.Key=NeverUsed;//空值,用于插入 } } /* 线性探测散列表的搜索: 搜索思想:从基位置h(key)开始,按照线性循环探查序列查找该元素。 搜索成功:找到关键字值为key的元素; 搜索失败:1、遇到一个标志位为true (empty[i]==true) 2、回到h(key)(表满) */ int hSearch(HashTable htb,KeyType k) { int i,j ; i = k%htb.M; j=i; do { if(htb.t[j].Empty||htb.t[j].Element.Key==k)return j; j=(j+1)%htb.M; }while(j!=i);//回到h(key)表满 return j; } BOOL Search (HashTable htb,KeyType k,T *x) { int b=hSearch(htb,k); if(htb.t[b].Element.Key!=k) return FALSE; *x = htb.t[b].Element; return TRUE; } /* 函数探查的第一个空值位置,即关键字值为NeverUseed的位置, 以便插入新元素。 函数Insert需要判定是否存在重复元素或表是否已满。 若ht[b]=NeverUsed,则在该处插入元素e,插入成功;否则插入失败。 插入失败包括元素重复和表满。 备注:插入的条件:空关键字,即遇到关键字NeverUsed */ BOOL Insert(HashTable *htb,T x) { int i = x.Key%htb->M; int j = i ; do { if(htb->t[j].Element.Key==x.Key) { printf("Duplicate!"); return FALSE; }else { if(htb->t[j].Element.Key==NeverUsed) { htb->t[j].Empty=FALSE; htb->t[j].Element=x; return TRUE; } } j=(j+1)%htb->M; }while(j!=i); printf("OverFlow"); return FALSE; } /* 线性探查散列表的删除 删除时需考虑两点: 1、不能简单清除元素,否则会隔离探查序列后面的元素, 影响搜索; 2、删除后,该元素的位置能够重新使用。 方法:首先搜索该元素,若搜索成功,则置该位置为空值NeverUsed以便能再次插入, 但empty域不作更改,防止搜索时遇到empty=true,终止搜索而不继续探测后续元素! */ BOOL Delete(HashTable *htb,T *x) { int b=hSearch(*htb,k); if(htb->t[b].Element.Key!=k) { printf("No element"); return FALSE; } *x=htb->t[b].Element; htb->t[b].Element.Key=NeverUsed; return TRUE; } int main() { HashTable htb; int M; T x; int i; while(scanf("%d",&M)!=EOF) { CreateHashTable(&htb,M); for(i=5;i<=M+2;i++) { x.Data=i*10; x.Key=i; Insert(&htb,x); } for(i=5;i<=M+2;i++) { if(i%5==0)Delete(&htb,i,&x); if(Search(htb,&x)) { printf("find:%d %d\n",x.Key,x.Data); }else { printf("have no the element!\n"); } } } return 1; }