โปรแกรม C++ สำหรับ Hash Tables Chaining ด้วย List Heads

ตารางแฮช (Hash Table) เป็นโครงสร้างข้อมูลสำหรับจัดเก็บคู่คีย์-ค่า ฟังก์ชันแฮชคำนวณดัชนีในอาร์เรย์สำหรับแทรกหรือค้นหา

นี่คือโปรแกรม C++ สำหรับ Hash Tables Chaining ด้วย List Heads

อัลกอริทึม

การแทรก (Insert):

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

การค้นหาคีย์ (Search Key):

Begin
    Declare Function SearchKey(int k)
        int hash_v = HashFunc(k)
        if (ht[hash_v] == NULL) return -1
        else
            ListHead *en = ht[hash_v]
            while (en != NULL and en->k != k) en = en->n
            if (en == NULL) return -1
            else return en->v
End

การลบ (Delete):

Begin
    Declare Function Remove(int k)
        int hash_v = HashFunc(k)
        if (ht[hash_v] != NULL)
            ListHead *en = ht[hash_v], *p = NULL
            while (en->n != NULL and en->k != k) p = en, en = en->n
            if (en->k == k)
                if (p == NULL) ListHead *n = en->n, delete en, ht[hash_v] = n
                else ListHead *n = en->n, delete en, p->n = n
End.

โค้ดตัวอย่าง

#include <iostream>
using namespace std;
const int T_S = 20;

class ListHead {
public:
    int k, v;
    ListHead *n;
    ListHead(int k, int v) { this->k = k; this->v = v; this->n = NULL; }
};

class HashMapTable {
private:
    ListHead **ht;
public:
    HashMapTable() {
        ht = new ListHead*[T_S];
        for (int i = 0; i < T_S; i++) ht[i] = NULL;
    }
    int HashFunc(int k) { return k % T_S; }
    void Insert(int k, int v) {
        int hash_v = HashFunc(k);
        if (ht[hash_v] == NULL) ht[hash_v] = new ListHead(k, v);
        else {
            ListHead *en = ht[hash_v];
            while (en->n != NULL) en = en->n;
            if (en->k == k) en->v = v;
            else en->n = new ListHead(k, v);
        }
    }
    int SearchKey(int k) {
        int hash_v = HashFunc(k);
        if (ht[hash_v] == NULL) return -1;
        else {
            ListHead *en = ht[hash_v];
            while (en != NULL && en->k != k) en = en->n;
            if (en == NULL) return -1;
            else return en->v;
        }
    }
    void Remove(int k) {
        int hash_v = HashFunc(k);
        if (ht[hash_v] != NULL) {
            ListHead *en = ht[hash_v], *p = NULL;
            while (en->n != NULL && en->k != k) { p = en; en = en->n; }
            if (en->k == k) {
                if (p == NULL) { ListHead *n = en->n; delete en; ht[hash_v] = n; }
                else { ListHead *n = en->n; delete en; p->n = n; }
            }
        }
    }
    ~HashMapTable() { delete[] ht; }
};

int main() {
    HashMapTable hash;
    int k, v, 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;
                    if (hash.SearchKey(k) == -1) cout << "No element found at key " << k << endl;
                    else { cout << "Elements at key " << k << " : " << hash.SearchKey(k) << endl; }
                    break;
            case 3: cout << "Enter key of the element to be deleted: "; cin >> k;
                    if (hash.SearchKey(k) == -1) cout << "Key " << k << " is empty" << endl;
                    else { hash.Remove(k); cout << "Entry Removed" << endl; }
                    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: 1
Enter key at which element to be inserted: 2
...
Enter your choice: 2
Enter key of the element to be searched: 6
Elements at key 6 : 7
...
Enter your choice: 3
Enter key of the element to be deleted: 1
Entry Removed
Enter your choice: 4