Chương trình C ++ để thực hiện chuỗi băm bảng với danh sách liên kết Singly

Bảng băm là một cấu trúc dữ liệu được sử dụng để lưu trữ các cặp khóa-giá trị. Hàm băm được sử dụng bởi bảng băm để tính toán một chỉ mục vào một mảng trong đó một phần tử sẽ được chèn hoặc tìm kiếm.

Đây là một chương trình C ++ để triển khai chuỗi Hash Tables với các danh sách được liên kết đơn lẻ.

Thuật toán

Để chèn:

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.

Để xóa:

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.

Đối với Tìm kiếm, một giá trị chính:

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.

Mã mẫu

#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;
}

Đầu ra

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