単一リンクリストを使用してチェーンするハッシュテーブルを実装するC++プログラム

ハッシュテーブルは、キーと値のペアを格納するために使用されるデータ構造です。ハッシュ関数は、要素が挿入または検索される配列へのインデックスを計算するためにハッシュテーブルによって使用されます。

これは、単一リンクリストを使用してチェーンするハッシュテーブルを実装するためのC++プログラムです。

アルゴリズム

挿入の場合：

Begin
   Declare Function Insert(int k, int v)
      int hash_v = HashFunc(k)
      HashTableEntry* p = NULL
      HashTableEntry* en = ht[hash_v]
      while (en!= NULL)
         p = en
         en= en->n
      if (en == NULL)
         en = new HashTableEntry(k, v)
         if (p == NULL)
            ht[hash_v] = en
         else
            p->n= en
      else
         en->v = v
End.

削除の場合：

Begin
   Declare Function Remove(int k)
      int hash_v = HashFunc(k)
      HashTableEntry* en = ht[hash_v]
      HashTableEntry* p= NULL
      if (en == NULL or en->k != k)
         Print “No Element found at key”
         return
      while (en->n != NULL)
         p = en
         en = en->n
      if (p != NULL)
         p->n = en->n
      delete en
         Print “Element Deleted”
End.

キー値を検索する場合：

Begin
   Declare function SearchKey(int k)
      int hash_v = HashFunc(k)
      bool flag = false
      HashTableEntry* en = ht[hash_v]
      if (en != NULL)
         while (en != NULL)
            if (en->k == k)
               flag = true
            if (flag)
               Print “Element found at key”
               Print en->v
            en = en->n
      if (!flag)
         Print “No Element found at key”
End.

サンプルコード

#include <iostream>
const int T_S = 200;
using namespace std;
struct HashTableEntry {
   int v, k;
   HashTableEntry *n;
   HashTableEntry *p;
   HashTableEntry(int k, int v) {
      this->k = k;
      this->v = v;
      this->n = NULL;
   }
};
class HashMapTable {
   public:
      HashTableEntry **ht, **top;
      HashMapTable() {
         ht = new HashTableEntry*[T_S];
         for (int i = 0; i < T_S; i++)
            ht[i] = NULL;
      }
      int HashFunc(int key) {
         return key % T_S;
      }
      void Insert(int k, int v) {
         int hash_v = HashFunc(k);
         HashTableEntry* p = NULL;
         HashTableEntry* en = ht[hash_v];
         while (en!= NULL) {
            p = en;
            en = en->n;
         }
         if (en == NULL) {
            en = new HashTableEntry(k, v);
            if (p == NULL) {
               ht[hash_v] = en;
            } else {
               p->n = en;
            }
         } else {
            en->v = v;
         }
      }
      void Remove(int k) {
         int hash_v = HashFunc(k);
         HashTableEntry* en = ht[hash_v];
         HashTableEntry* p = NULL;
         if (en == NULL || en->k != k) {
            cout<<"No Element found at key "<<k<<endl;
            return;
         }
         while (en->n != NULL) {
            p = en;
            en = en->n;
         }
         if (p != NULL) {
            p->n = en->n;
         }
         delete en;
         cout<<"Element Deleted"<<endl;
      }
      void SearchKey(int k) {
         int hash_v = HashFunc(k);
         bool flag = false;
         HashTableEntry* en = ht[hash_v];
         if (en != NULL) {
            while (en != NULL) {
               if (en->k == k) {
                  flag = true;
               }
               if (flag) {
                  cout<<"Element found at key "<<k<<": ";
                  cout<<en->v<<endl;
               }
               en = en->n;
            }
         }
         if (!flag)
            cout<<"No Element found at key "<<k<<endl;
      }
      ~HashMapTable() {
         delete [] ht;
      }
};
int main() {
   HashMapTable hash;
   int k, v;
   int c;
   while (1) {
      cout<<"1.Insert element into the table"<<endl;
      cout<<"2.Search element from the key"<<endl;
      cout<<"3.Delete element at a key"<<endl;
      cout<<"4.Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter element to be inserted: ";
            cin>>v;
            cout<<"Enter key at which element to be inserted: ";
            cin>>k;
            hash.Insert(k, v);
         break;
         case 2:
            cout<<"Enter key of the element to be searched: ";
            cin>>k;
            hash.SearchKey(k);
         break;
         case 3:
            cout<<"Enter key of the element to be deleted: ";
            cin>>k;
            hash.Remove(k);
         break;
         case 4:
            exit(1);
         default:
            cout<<"\nEnter correct option\n";
      }
   }
   return 0;
}

出力

1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 2
Enter key at which element to be inserted: 1
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 3
Enter key at which element to be inserted: 4
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 7
Enter key at which element to be inserted: 6
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 8
Enter key at which element to be inserted: 9
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 6
Element found at key 6: 7
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
No Element found at key 7
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 9
Element Deleted
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4