【資料結構】散清單總結

總結：線性探查表基本操作中的關鍵

删除：不改變标志位，關鍵字值改為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; 
}