線性探測法
哈希表結構體
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 100
struct HashTable{
int count; //元素個數
int p;
int data[MAX]={0}; //資料域
};
計算哈希演算法，這里采用最常用的求余數法
int hash(int value,int p){
return value%p;
}
插入元素，線性探測法
就是如果發生碰撞，就一直往前尋找空位子，所以P這個引數會影響碰撞的次數
int Insert(HashTable* table,int value) //線性探測
{
int address = hash(value,table->p);
if(table->data[address]==0){
table->data[address]=value;
}else{
if(table->count<MAX){
while(table->data[address]!=0){
address = (address+1)%MAX;
}
table->data[address] = value;
}else{
cout<<"滿了"<<endl;
}
}
}
尋找元素的索引位置
int find(HashTable* table,int value) //查找值的位置 不存在回傳-1
{
int index = (value%table->p);
int count=1;
while(table->data[index]!=value && count<=(MAX+1)){
count++;
index = (index+1)%MAX;
}
if(count>MAX){
cout<<"找不到"<<endl;
return -1;
}else{
return index;
}
}
void Delete(HashTable* table,int value){
int index = find(table,value);
if(index!=-1){
table->data[index] = 0;
}
}
洗掉元素
void Delete(HashTable* table,int value){
int index = find(table,value);
if(index!=-1){
table->data[index] = 0;
}
}
可執行的完整代碼
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 100
struct HashTable{
int count; //元素個數
int p;
int data[MAX]={0}; //資料域
};
int hash(int value,int p){
return value%p;
}
int Insert(HashTable* table,int value) //線性探測
{
int address = hash(value,table->p);
if(table->data[address]==0){
table->data[address]=value;
}else{
if(table->count<MAX){
while(table->data[address]!=0){
address = (address+1)%MAX;
}
table->data[address] = value;
}else{
cout<<"滿了"<<endl;
}
}
}
int find(HashTable* table,int value) //查找值的位置 不存在回傳-1
{
int index = (value%table->p);
int count=1;
while(table->data[index]!=value && count<=(MAX+1)){
count++;
index = (index+1)%MAX;
}
if(count>MAX){
cout<<"找不到"<<endl;
return -1;
}else{
return index;
}
}
void Delete(HashTable* table,int value){
int index = find(table,value);
if(index!=-1){
table->data[index] = 0;
}
}
int main(){
HashTable* table = new HashTable;
table->p = 91;
table->count=0;
memset(table->data,0,sizeof(int)*MAX);
Insert(table,986);
Insert(table,1986);
Insert(table,286);
Insert(table,96);
cout<<find(table,986)<<endl;
cout<<find(table,1986)<<endl;
cout<<find(table,96)<<endl;
Delete(table,1986);
cout<<find(table,1986)<<endl;
return 0;
}
拉鏈法
結構體
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 10
#define P 7
struct Node{
int value;
Node* next;
};
struct HashTable{
int count=0;
Node data[MAX];
};
插入元素，如果發生碰撞，就在當前節點的鏈表上插入
void Insert(HashTable* table,int value){
int index = (value%P);
if(table->data[index].value!=0){
Node** node = &(table->data[index].next);
while((*node)!=NULL)
*node = (*node)->next;
*node = new Node;
(*node)->value = https://www.cnblogs.com/biningooginind/p/value;
(*node)->next = NULL;
}else{
table->data[index].value = value;
}
}
尋找元素
Node* find(HashTable* table,int val){
int index = (val%P);
if(table->data[index].value=https://www.cnblogs.com/biningooginind/p/=val){
return &table->data[index];
}else{
Node* node = table->data[index].next;
while( node!=NULL&&node->value!=val){
node = node->next;
}
return node;
}
}
洗掉元素
如果元素在鏈表上，那和洗掉鏈表節點一樣，特殊情況需要考慮的就是頭結點
如果是在哈希表上，則如果有鏈表，則將鏈表提升，沒有的話直接清零
可執行代碼
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 10
#define P 7
struct Node{
int value;
Node* next;
};
struct HashTable{
int count=0;
Node data[MAX];
};
void Insert(HashTable* table,int value){
int index = (value%P);
if(table->data[index].value!=0){
Node** node = &(table->data[index].next);
while((*node)!=NULL)
*node = (*node)->next;
*node = new Node;
(*node)->value = https://www.cnblogs.com/biningooginind/p/value;
(*node)->next = NULL;
}else{
table->data[index].value = value;
}
}
Node* find(HashTable* table,int val){
int index = (val%P);
if(table->data[index].value==val){
return &table->data[index];
}else{
Node* node = table->data[index].next;
while( node!=NULL&&node->value!=val){
node = node->next;
}
return node;
}
}
int main(){
HashTable* table = new HashTable;
for(int i=0;idata[i].value=0;
table->data[i].next=NULL;
}
Insert(table,1);
Insert(table,8);
Insert(table,9);
Insert(table,6);
Insert(table,2);
//
cout<next->value;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71865.html
標籤：其他
上一篇：《Mathematical Analysis of Algorithms》中有關“就地排列”(In Situ Permutation)的演算法分析