HASHテーブル(チェーンテーブルによるhash衝突処理)

hash.h:
 

#ifndef __HASH
#define __HASH
//              
struct Node;
typedef Node * List;
typedef int ElementType;
#define MIN  13//     

//        
struct Node 
{
 ElementType ele;
 Node * next;
};
struct HashTable
{
 int table_size;//    
 List *table;//         
};
//      
HashTable * init_table(const int &max_size);
Node * find(const ElementType &ele,HashTable *H);
bool insert(const ElementType &ele,HashTable *H);
HashTable * destory_table(HashTable *H);
int hash(const ElementType &ele,HashTable * H);//         hash  
int next_prime(const int &max_size);//          ，      max_size           
bool is_prime(const int & n);

#endif

 
hash.cpp:
 

#include "hash.h"
#include <cmath>
#include <cstdlib>
using std::sqrt;
HashTable * init_table(const int &max_size)
{
 HashTable * H=new HashTable;
 H->table_size=max_size>MIN ? next_prime(max_size):MIN;
 H->table=new Node *[H->table_size];
 //          
 for(int i=0;i!=H->table_size;++i)
 {
  H->table[i]=new Node;
  H->table[i]->ele=-1;
  H->table[i]->next=NULL;
 }
 return H;
}

Node * find(const ElementType &ele,HashTable *H)
{
 Node *pos=H->table[hash(ele,H)];//     
 pos=pos->next;
 while(pos!=NULL&&pos->ele!=ele)
  pos=pos->next;
 return pos;
}

bool insert(const ElementType &ele,HashTable *H)
{
 bool flage=false;
 Node * pos;
 Node * new_ele;
 if(find(ele,H)==NULL)//    ，      
 {
  pos=H->table[hash(ele,H)];//         
  new_ele=new Node;
  new_ele->ele=ele;
  //        
  new_ele->next=pos->next;
  pos->next=new_ele;
  flage=true;
 }
 return flage;
}

HashTable * destory_table(HashTable *H)
{
 Node * cur;
 Node * temp;
 for(int i=0;i!=H->table_size;++i)
 {
  cur=H->table[i];//      
    
  while(cur->next)//         
   {
    temp=cur->next;
    cur->next=temp->next;
    delete temp;
   }
   delete H->table[i];//     
 }
 delete [] H->table;//      
 delete H;
 return NULL;
 
}
//hash  ，         int ，         
int hash(const ElementType &ele,HashTable * H)
{
 return (ele%H->table_size);
}

int next_prime(const int &max_size)
{
 if(is_prime(max_size))
  return max_size;
    int temp=max_size;
 while(!is_prime(temp))
     temp++;
 return temp;
}
//            
bool is_prime(const int & n)
{
    bool flage=false;
    if(n==2||n==3)
        return true;
    for(int k=2;k<=(int)sqrt((double)n);++k)
    {
        if(n%k==0)
            return false;
        else
            flage=true;
    }
    return flage;
}
 
 

 
//テストファイル
main.cpp:

#include <iostream>
#include "hash.h"
using std::cout;
using std::endl;
int main()
{
 HashTable * H=init_table(15);
 cout<<"The size of hash table="<<H->table_size<<endl;
 insert(23,H);
 insert(12,H);
 cout<<find(12,H)->ele<<endl;
 cout<<insert(12,H)<<endl;
 destory_table(H);
 return 0;
}