【数据结构】散列表总结

总结：线性探查表基本操作中的关键

删除：不改变标志位，关键字值改为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,KeyType k,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,i,&x)) {
				printf("find:%d %d\n",x.Key,x.Data);
			}else {
				printf("have no the element!\n");
			}
		}
		
	}
	return 1; 
}