• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

一个C++实现的简单哈希表(hashtable)范例

OC/C/C++ 水墨上仙 1288次浏览

一个C++实现的简单哈希表(hashtable)范例

//A simple example of hashtable
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#define SIZE_KEY       16
#define SIZE_VALUE1    64
#define SIZE_VALUE2    16
#define DEFAULT_TABLESIZE    101
using namespace std;
 
struct NODE
{
   Node(const char* Key1 = "\0", const char* fName = "\0",
         const char *tele ="\0", const double sal = 0.0 )
   {
      strcpy(Key, Key1);
      strcpy(FullName, fName);
      strcpy(Tele_No, tele);
      Salary = sal;
      Tax = 0.005 * Salary;
      next = NULL;
   }
   char Key[SIZE_KEY];
   char FullName[SIZE_VALUE1];
   char Tele_No[SIZE_VALUE2];
   double Salary;
   double Tax;
   Node *next;
};
 
class Hashtable
{
   private:
      int table_size;
      NODE** table;
      int size;
      long hashString(char* Key);
      NODE* find(char* Key);
      NODE* current_entry;
      int current_index;
   public:
      Hashtable(int T = DEFAULT_TABLESIZE);//constructor
      virtual ~Hashtable();//destructor
      bool put(NODE *);
      bool get(NODE *);
      bool contains(char* Key);
      bool remove(char* Key);
      void removeAll();
      int getSize();
      void initIterator();
      bool hasNext();
      void getNextKey(char* Key);
      friend void disp(NODE *);
};
 
Hashtable::Hashtable(int T)
{
   size = 0;
   table_size = T;
   table = new NODE*[table_size];
   for(int i=0; i<table_size; i++)
   {
      table[i] = NULL;
   }
}
 
Hashtable::~Hashtable()
{
   removeAll();
   delete[] table;
}
 
void disp(NODE *N1)
{
 cout << "\nKey:      " << N1->Key << "\nFullName: "
      << N1->FullName <<"\nTele.:    " << N1->Tele_No << "\nSalary:   "
      << setprecision(12) << N1->Salary<< "\nTax:      " << N1->Tax << endl;
}
 
bool Hashtable::put(NODE *N)
{//start put
   if(find(N->Key) != NULL)
   {
      return false;
   }
   NODE* entry = new NODE(N->Key, N->FullName,N->Tele_No, N->Salary);
   int bucket = hashString(N->Key);
   entry->next = table[bucket];
   table[bucket] = entry;
   size++;
   return true;
}//end put
 
 
bool Hashtable::get(NODE* N)
{//start get
   NODE* temp = find(N->Key);
   if(temp == NULL)
   {
      N->FullName[0] = '\0';
      return false;
   }
   else
   {
      strcpy(N->FullName, temp->FullName);
      strcpy(N->Tele_No, temp->Tele_No);
      N->Salary = temp->Salary;
      N->Tax = temp->Tax;
      return true;
   }
}//end get
 
bool Hashtable::contains(char* Key)
{//start contains
   if(find(Key) == NULL)
   {
      return false;
   }
   else
   {
      return true;
   }
}//end contains
 
 
bool Hashtable::remove(char* Key)
{//start remove
   int bucket = hashString(Key);
   NODE* temp = table[bucket];
   if(temp == NULL)
   {
      return false;
   }
   else if(strcmp(Key, temp->Key) == 0)
   {
      table[bucket] = temp->next;
      delete temp;
      size--;
      return true;
   }
   else
   {
      NODE* temp_next = temp->next;
      while(temp_next != NULL)
      {
         if(strcmp(Key, temp_next->Key) == 0)
         {
            temp->next = temp_next->next;
            delete temp_next;
            size--;
            return true;
         }
         temp = temp->next;
         temp_next = temp_next->next;
      }
   }
   return false;
}//end remove
 
 
void Hashtable::removeAll()
{//start removeAll
   for(int i=0; i<table_size; i++)
   {
      NODE* temp = table[i];
      while(temp != NULL)
      {
         NODE* next = temp->next;
         disp(temp);
         delete temp;
         temp = next;
      }
   }
   size = 0;
}//end removeAll
 
int Hashtable::getSize()
{
   return size;
}
 
NODE* Hashtable::find(char* Key)
{ //start find
   int bucket = hashString(Key);
   NODE* temp = table[bucket];
   while(temp != NULL)
   {
      if(strcmp(Key, temp->Key) == 0)
      {
         return temp;
      }
      temp = temp->next;
   }
   return NULL;
}//end find
 
long Hashtable::hashString(char* Key)
{//start hashString
   int n = strlen(Key);
   long h = 0;
   for(int i=0; i<n; i++)
   {
      //To get almost fair distributions of nodes over the array
      h = (h << 3) ^ Key[i];
   }
    return abs(h % table_size );
}//end hashString
 
void Hashtable::initIterator()
{//start initIterator
   current_entry = NULL;
   current_index = table_size;
   for(int i=0; i<table_size; i++)
   {
      if(table[i] == NULL)
      {
          continue;
      }
      else
      {
         current_entry = table[i];
         current_index = i;
         break;
      }
   }
}//end initIterator
 
bool Hashtable::hasNext()
{
   if(current_entry == NULL)
   {
      return false;
   }
   else
   {
      return true;
   }
}
void Hashtable::getNextKey(char* Key)
{
   if(current_entry == NULL)
   {
      Key[0] = '\0';
      return;
   }
   strcpy(Key, current_entry->Key);
   if(current_entry->next != NULL)
   {
      current_entry = current_entry->next;
   }
   else
   {
     for(int i=current_index+1; i<table_size; i++)
     {
        if(table[i] == NULL)
        {
           continue;
        }
        current_entry = table[i];
        current_index = i;
        return;
     }
     current_entry = NULL;
     current_index = table_size;
   }
}
 
void dispAll(Hashtable* hashtable);
 
int main()
{
   char temp1[SIZE_KEY];
   Hashtable* hashtable = new Hashtable();
 
   NODE N1("389","Mariam","8216734",22123.267);
 
   if(!hashtable->contains(N1.Key))
   {
      cout << "\nAdding node:  ";
      disp(&N1);
      hashtable->put(&N1);
   }
 
   strcpy(N1.Key, "314");
   strcpy(N1.FullName, "Zeki");
   strcpy(N1.Tele_No, "8765623");
   N1.Salary = 98124.567;
   if(!hashtable->contains(N1.Key))
   {
      cout << "\nAdding node:  ";
      disp(&N1);
      hashtable->put(&N1);
   }
 
   strcpy(N1.Key, "320");
   strcpy(N1.FullName, "Murad");
   strcpy(N1.Tele_No, "7231144");
   N1.Salary = 19834.575;
   if(!hashtable->contains(N1.Key))
   {
      cout << "\nAdding node:  ";
      disp(&N1);
      hashtable->put(&N1);
   }
 
   strcpy(N1.Key, "768");
   strcpy(N1.FullName, "Hassan");
   strcpy(N1.Tele_No, "7689876");
   N1.Salary = 45124.755;
   if(!hashtable->contains(N1.Key))
   {
      cout << "\nAdding node:  ";
      disp(&N1);
      hashtable->put(&N1);
   }
 
   strcpy(N1.Key, "756");
   strcpy(N1.FullName, "Ali");
   strcpy(N1.Tele_No, "9874545");
   N1.Salary = 43554.125;
   if(!hashtable->contains(N1.Key))
   {
      cout << "\nAdding node:  ";
      disp(&N1);
      hashtable->put(&N1);
   }
 
   dispAll(hashtable);
 
    strcpy(temp1,"314");
   hashtable->remove(temp1);
   cout << "\n\nAfter removing 314:" << endl;
   dispAll(hashtable);
   cout << "\n\nDestroying hashtable:" << endl;
   delete hashtable;
   return 0;
}
 
void dispAll(Hashtable *hashtable)
{
        NODE N1;
   cout << "\n\nCurrent nodes in hashtable:" << endl;
   hashtable->initIterator();
   while(hashtable->hasNext())
   {
      hashtable->getNextKey(N1.Key);
      hashtable->get(&N1);
      disp(&N1);
   }
}
 
/*
Program's output
******************
Adding node:
Key:      389
FullName: Mariam
Tele.:    8216734
Salary:   22123.267
Tax:      110.616335
 
Adding node:
Key:      314
FullName: Zeki
Tele.:    8765623
Salary:   98124.567
Tax:      110.616335
 
Adding node:
Key:      320
FullName: Murad
Tele.:    7231144
Salary:   19834.575
Tax:      110.616335
 
Adding node:
Key:      768
FullName: Hassan
Tele.:    7689876
Salary:   45124.755
Tax:      110.616335
 
Adding node:
Key:      756
FullName: Ali
Tele.:    9874545
Salary:   43554.125
Tax:      110.616335
 
 
Current nodes in hashtable:
 
Key:      768
FullName: Hassan
Tele.:    7689876
Salary:   45124.755
Tax:      225.623775
 
Key:      314
FullName: Zeki
Tele.:    8765623
Salary:   98124.567
Tax:      490.622835
 
Key:      756
FullName: Ali
Tele.:    9874545
Salary:   43554.125
Tax:      217.770625
 
Key:      389
FullName: Mariam
Tele.:    8216734
Salary:   22123.267
Tax:      110.616335
 
Key:      320
FullName: Murad
Tele.:    7231144
Salary:   19834.575
Tax:      99.172875
 
 
After removing 314:
 
 
Current nodes in hashtable:
 
Key:      768
FullName: Hassan
Tele.:    7689876
Salary:   45124.755
Tax:      225.623775
 
Key:      756
FullName: Ali
Tele.:    9874545
Salary:   43554.125
Tax:      217.770625
 
Key:      389
FullName: Mariam
Tele.:    8216734
Salary:   22123.267
Tax:      110.616335
 
Key:      320
FullName: Murad
Tele.:    7231144
Salary:   19834.575
Tax:      99.172875
 
 
Destroying hashtable:
 
Key:      768
FullName: Hassan
Tele.:    7689876
Salary:   45124.755
Tax:      225.623775
 
Key:      756
FullName: Ali
Tele.:    9874545
Salary:   43554.125
Tax:      217.770625
 
Key:      389
FullName: Mariam
Tele.:    8216734
Salary:   22123.267
Tax:      110.616335
 
Key:      320
FullName: Murad
Tele.:    7231144
Salary:   19834.575
Tax:      99.172875
 
Process returned 0 (0x0)   execution time : 0.162 s
Press any key to continue.
*/


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明一个C++实现的简单哈希表(hashtable)范例
喜欢 (0)
加载中……