Monday, December 26, 2016

Bab 19. Soal & Penyelesaian C++


TABEL HASH





Soal & Penyelesaian
1.       Tulislah sebuah program C++ untuk mendemonstrasikan tabel hash dengan linear probing.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
//hashLinearProbing.cpp
//Mendemonstrasikan tabel hash dengan linear probing
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <conio.h>
using namespace std;

class ItemData
{
    public:
    int iData; //item data (kunci)

    ItemData(int ii) : iData(ii) //konstruktor
    { }
}; //akhir kelas ItemData

class TabelHash
{
    private:
        vector<ItemData*> arrayHash; //vector memuat tabel hash
        int ukuranArray;
        ItemData* pTakItem; //untuk item-item yang dihapus

    public:
        TabelHash(int ukuran) : ukuranArray(ukuran) //konstruktor
        {
            ukuranArray = ukuran;
            arrayHash.resize(ukuranArray); //ukuran vector
            for(int j=0; j<ukuranArray; j++) //menginisialisasi
                arrayHash[j] = NULL;

                     //kunci item yang dihapus adalah -1
                     pTakItem = new ItemData(-1);
        }

        void tampilTabel()
        {
            cout << "Tabel: ";
            for(int j=0; j<ukuranArray; j++)
            {
                if(arrayHash[j] != NULL)
                    cout << arrayHash[j]->iData << " ";
                else
                    cout << "** ";
            }
            cout << endl;
        }

        int fungsiHash(int kunci)
        {
            return kunci % ukuranArray; //fungsi hash
        }

        void sisip(ItemData* pItem) //menyisipkan sebuah ItemData
        //(asumsi tabel tidak penuh)
        {
            int kunci = pItem->iData; //mengekstrak kunci
            int nilaiHash = fungsiHash(kunci); //menghashkan kunci

            //sampai sel kosong atau -1,
            while(arrayHash[nilaiHash] != NULL &&
            arrayHash[nilaiHash]->iData != -1)
            {
                ++nilaiHash; //ke sel berikutnya
                nilaiHash %= ukuranArray;
            }
            arrayHash[nilaiHash] = pItem; //menyisipkan item
        } //akhir sisip()

        ItemData* hapus(int kunci) //menghapus sebuah ItemData
        {
            int nilaiHash = fungsiHash(kunci); //menghashkan kunci

            while(arrayHash[nilaiHash] != NULL) //sampai sel kosong,
            { //menemukan kunci?
                if(arrayHash[nilaiHash]->iData == kunci)
                {
                    //menyimpan item
                    ItemData* pTemp = arrayHash[nilaiHash];
                    arrayHash[nilaiHash] = pTakItem; //menghapus item
                    return pTemp; //menghasilkan item
                }
                ++nilaiHash; //ke sel berikutnya
                nilaiHash %= ukuranArray;
            }
            return NULL; //tidak menemukan
        } //akhir hapus()

        ItemData* cari(int kunci) //mencari item dengan kunci
        {
           int nilaiHash = fungsiHash(kunci); //menghashkan kunci

           while(arrayHash[nilaiHash] != NULL) //sampai sel kosong,
           { //menemukan kunci?
               if(arrayHash[nilaiHash]->iData == kunci)
                   return arrayHash[nilaiHash]; //ya, menghasilkan item
               ++nilaiHash; //ke sel berikutnya
               nilaiHash %= ukuranArray;
            }
            return NULL; //tidak menemukan item
        }
}; //akhir kelas TabelHash

int main()
{
    ItemData* pDataItem;
    int aKunci, ukuran, n, kunciPerSel;
    time_t waktuA;
    char pilihan = 'b';

    //membaca ukuran
    cout << "Masukkan ukuran tabel hash: ";
    cin >> ukuran;
       cout << "Masukkan jumlah awal item: ";
    cin >> n;
    kunciPerSel = 10;

    //menciptakan table
    TabelHash tabelHash(ukuran);
    srand( static_cast<unsigned>(time(&waktuA)) );

    for(int j=0; j<n; j++) //menyisipkan data
    {
        aKunci = rand() % (kunciPerSel*ukuran);
        pDataItem = new ItemData(aKunci);
        tabelHash.sisip(pDataItem);
    }

    while(pilihan != 'x') //berinteraksi dengan pengguna
    {
        cout << "Masukkan huruf pertama dari "
             << "tampil, sisip, hapus, atau cari: ";
        char pilihan;
        cin >> pilihan;

        switch(pilihan)
        {
            case 't':
                tabelHash.tampilTabel();
                break;

            case 's':
                cout << "Masukkan nilai kunci yang akan disisipkan: ";
                cin >> aKunci;
                pDataItem = new ItemData(aKunci);
                tabelHash.sisip(pDataItem);
                break;

            case 'h':
                cout << "Masukkan nilai kunci yang akan dihapus: ";
                cin >> aKunci;
                tabelHash.hapus(aKunci);
                break;

            case 'c':
                cout << "Masukkan nilai kunci yang akan dicari: ";
                cin >> aKunci;
                pDataItem = tabelHash.cari(aKunci);

                if(pDataItem != NULL)
                    cout << "Ditemukan " << aKunci << endl;
                else
                    cout << "Tidak ditemukan " << aKunci << endl;
                    break;

            default:
                cout << "Entri tak-valid\n";
        } //akhir switch
    } //akhir while

    getch();
    return 0;
} //akhir main()

Masukkan ukuran tabel hash: 12
Masukkan jumlah awal item: 8

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
Tabel: 96 37 72 14 87 ** ** ** 80 93 ** 71

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: c
Masukkan nilai kunci yang akan dicari: 80
Ditemukan 80

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: s
Masukkan nilai kunci yang akan disisipkan: 100

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
Tabel: 96 37 72 14 87 100 ** ** 80 93 ** 71

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: h
Masukkan nilai kunci yang akan dihapus: 100

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
Tabel: 96 37 72 14 87 -1 ** ** 80 93 ** 71

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari:

2.       Tulislah sebuah program C++ untuk mendemonstrasikan tabel hash dengan quadratic probing.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
//hashQuadraticProbing.cpp
//Mendemonstrasikan tabel hash dengan double hashing
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <conio.h>
using namespace std;

class ItemData
{
    public:
    int iData; //item data (kunci)

    ItemData(int ii) : iData(ii) //konstruktor
    { }
}; //akhir kelas ItemData

class TabelHash
{
    private:
        vector<ItemData*> arrayHash; //vector memuat tabel hash
        int ukuranArray;
        ItemData* pTakItem; //untuk item-item yg dihapus

    public:
        TabelHash(int ukuran) : ukuranArray(ukuran) //konstruktor
        {
            arrayHash.resize(ukuranArray); //ukuran vector
           
            for(int j=0; j<ukuranArray; j++) //menginisialisasi
                arrayHash[j] = NULL;

            pTakItem = new ItemData(-1);
        }

        void tampilTabel()
        {
            cout << "Tabel: ";
            for(int j=0; j<ukuranArray; j++)
            {
                if(arrayHash[j] != NULL)
                    cout << arrayHash[j]->iData << " ";
                else
                    cout << "** ";
            }
            cout << endl;
        }

        int fungsiHash1(int kunci)
        {
            return kunci % ukuranArray;
        }

        int fungsiHash2(int kunci)
        {
            return 5 - kunci % 5;
        }

        //menyisipkan sebuah ItemData
        void sisip(int kunci, ItemData* pItem)
        //(asumsi tabel tidak penuh)
        {
            int nilaiHash = fungsiHash1(kunci); //menghashkan kunci
            int ukuranLangkah = fungsiHash2(kunci); //membaca ukuran langkah

            //sampai sel kosong atau -1
            while(arrayHash[nilaiHash] != NULL &&
            arrayHash[nilaiHash]->iData != -1)
            {
                nilaiHash += ukuranLangkah; //menambah langkah
                nilaiHash %= ukuranArray;
            }
            arrayHash[nilaiHash] = pItem; //menyisipkan item
        } //akhir sisip()

        ItemData* hapus(int kunci) //menghapus sebuah ItemData
        {
            int nilaiHash = fungsiHash1(kunci); //menghashkan kunci
           
            //membaca ukuran langkah
            int ukuranLangkah = fungsiHash2(kunci);

            while(arrayHash[nilaiHash] != NULL) //sampai sel kosong,
            { //apakah nilaiHash tepat?
                if(arrayHash[nilaiHash]->iData == kunci)
                {
                    //menyimpan item
                    ItemData* pTemp = arrayHash[nilaiHash];
                    arrayHash[nilaiHash] = pTakItem; //menghapus item
                    return pTemp; //menghasilkan item
                }

                nilaiHash += ukuranLangkah; //menambah langkah
                nilaiHash %= ukuranArray;
             }
             return NULL; //tidak menemukan
        } //akhir hapus()

        ItemData* cari(int kunci) //mencari item dengan kunci
        //(asumsi tabel tidak penuh)
        {
            int nilaiHash = fungsiHash1(kunci); //menghashkan kunci
           
            //membaca ukuran langkah
            int ukuranLangkah = fungsiHash2(kunci);

            while(arrayHash[nilaiHash] != NULL) //sampai sel kosong,
            { //apakah nilaiHash tepat?
                if(arrayHash[nilaiHash]->iData == kunci)
                    return arrayHash[nilaiHash]; //ya

                nilaiHash += ukuranLangkah; //menambah langkah
                nilaiHash %= ukuranArray;
            }
            return NULL; //tidak menemukan
        };
}; //akhir kelas TabelHash

int main()
{
    int aKunci;
    ItemData* pItemData;
    int ukuran, n;
    char pilihan = 'b';
    time_t waktuA;

       //membaca ukuran
    cout << "Masukkan ukuran tabel hash: ";
    cin >> ukuran;
       cout << "Masukkan jumlah awal item: ";
    cin >> n;

    //menciptakan tabel
    TabelHash tabelHash(ukuran); //tunas angka acak
    srand( static_cast<unsigned>(time(&waktuA)) );

    for(int j=0; j<n; j++) //menyisipkan data
    {
        aKunci = rand() % (2 * ukuran);
        pItemData = new ItemData(aKunci);
        tabelHash.sisip(aKunci, pItemData);
    }

    while(true) //berinteraksi dengan pengguna
    {
        cout << "Masukkan huruf pertama dari "
             << "tampil, sisip, hapus, atau cari: ";
        char pilihan;
        cin >> pilihan;

        switch(pilihan)
        {
            case 't':
                tabelHash.tampilTabel();
                break;

            case 's':
                cout << "Masukkan nilai kunci yang akan disisipkan: ";
                cin >> aKunci;
                pItemData = new ItemData(aKunci);
                tabelHash.sisip(aKunci, pItemData);
                break;

            case 'h':
                cout << "Masukkan nilai kunci yang akan dihapus: ";
                cin >> aKunci;
                tabelHash.hapus(aKunci);
                break;

            case 'c':
                cout << "Masukkan nilai kunci yang akan dicari: ";
                cin >> aKunci;
                pItemData = tabelHash.cari(aKunci);

                if(pItemData != NULL)
                    cout << "Ditemukan " << aKunci << endl;
                else
                    cout << "Tidak ditemukan " << aKunci << endl;
                    break;

            default:
                cout << "Entri tak-valid\n";
        } //akhir switch
    } //akhir while

    getch();
    return 0;
} //akhir main()

Masukkan ukuran tabel hash: 12
Masukkan jumlah awal item: 8

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
Tabel: 0 22 14 ** ** 17 18 ** 20 9 6 **

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: c
Masukkan nilai kunci yang akan dicari: 17
Ditemukan 17

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: s
Masukkan nilai kunci yang akan disisipkan: 100

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
Tabel: 0 22 14 ** 100 17 18 ** 20 9 6 **

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: s
Masukkan nilai kunci yang akan disisipkan: 100

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
Tabel: 0 22 14 ** 100 17 18 100 20 9 6 **

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: h
Masukkan nilai kunci yang akan dihapus: 22

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
Tabel: 0 -1 14 ** 100 17 18 100 20 9 6 **

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari:

3.       Tulislah sebuah program C++ untuk mendemonstrasikan tabel hash dengan separate chaining.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
//hashSeparateChaining.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <conio.h>
using namespace std;

class Simpul
{ //(bisa memuat item lain)
    public:
        int iData; //data item
        Simpul* pBrktnya; //simpul berikutnya dalam senarai

        Simpul(int it) : iData(it) //konstruktor
        { }

        void tampilSimpul() //menampilkan simpul
        { cout << iData << " "; }
}; //akhir kelas Simpul

class SenaraiTerurut
{
    private:
        Simpul* pPertama; //referensi ke item pertama

    public:
        SenaraiTerurut() //konstruktor
        { pPertama = NULL; }

        void sisip(Simpul* pSimpul) //menyisipkan simpul scr berurutan
        {
            int kunci = pSimpul->iData;
            Simpul* pSblmnya = NULL; //mulai simpul pertam
            Simpul* pSkrg = pPertama;

            //sampai akhir senarai,
            while(pSkrg != NULL && kunci > pSkrg->iData)
            { //atau pSkrg > kunci,
               pSblmnya = pSkrg;
               pSkrg = pSkrg->pBrktnya; //ke item berikutnya
            }

            if(pSblmnya==NULL) //jika di awal senarai,
                pPertama = pSimpul; // pertama -> simpul baru
            else //tidak di awal,
                pSblmnya->pBrktnya = pSimpul; // sblmnya -> simpul baru
           
            pSimpul->pBrktnya = pSkrg; //simpul baru -> sekarang
        } //akhir sisip()

        void hapus(int kunci) //menghapus Simpul
        { //(asumsi senarai tak-kosong)
            Simpul* pSblmnya = NULL; //mulai di awal
            Simpul* pSkrg = pPertama;

            //sampai akhir senarai,
            while(pSkrg != NULL && kunci != pSkrg->iData)
            { //atau kunci == skrg,
                pSblmnya = pSkrg;
                pSkrg = pSkrg->pBrktnya; //ke simpul brktnya
            }

            //mendiskonek Simpul
            if(pSblmnya==NULL) // jika di awal senarai
                pPertama = pPertama->pBrktnya; // menghapus simpul pertama
            else // tidak di awal
                //menghapus simpul sekarang
                pSblmnya->pBrktnya = pSkrg->pBrktnya;
        } //akhir hapus()

        Simpul* cari(int kunci) //mencari Simpul
        {
            Simpul* pSkrg = pPertama; //mulai di awal

            //sampai akhir senarai,
            while(pSkrg != NULL && pSkrg->iData <= kunci)
            { //atau kunci terlalu kecil,
                if(pSkrg->iData == kunci) //apakah ini simpul tsb?
                    return pSkrg; //ditemukan

                pSkrg = pSkrg->pBrktnya; //ke item berikutnya
            }
            return NULL; //tidak ditemukan
        } //akhir cari()

        void tampilSenarai()
        {
            cout << "Senarai (pertama->akhir): ";
            Simpul* pSkrg = pPertama; //mulai di awal senarai

            while(pSkrg != NULL) //sampai akhir senarai,
            {
                pSkrg->tampilSimpul(); //menampilkan data
                pSkrg = pSkrg->pBrktnya; //ke simpul brktnya
            }
            cout << endl;
        }
}; //akhir kelas SenaraiTerurut

class TabelHash
{
    private:
        vector<SenaraiTerurut*> arrayHash; //vector senarai
        int ukuranArray;

    public:
        TabelHash(int ukuran) //konstruktor
        {
            ukuranArray = ukuran;
            arrayHash.resize(ukuranArray); //menetapkan ukuran vector

            for(int j=0; j<ukuranArray; j++) //mengisi vector
                arrayHash[j] = new SenaraiTerurut; //dengan senarai
        }

        void tampilTabel()
        {
            for(int j=0; j<ukuranArray; j++) //untuk tiap sel,
            {
                cout << j << ". "; //menampilkan nomor sel
                arrayHash[j]->tampilSenarai(); //menampilkan senarai
            }
        }

        int fungsiHash(int kunci) //fungsi hash
        {
            return kunci % ukuranArray;
        }

        void sisip(Simpul* pSimpul) //menyisipkan sebuah Simpul
        {
            int kunci = pSimpul->iData;
            int nilaiHash = fungsiHash(kunci); //menghashkan kunci

            //menyisipkan pada nilaiHash
            arrayHash[nilaiHash]->sisip(pSimpul);
        } //akhir sisip()

        void hapus(int kunci) //menghapus Simpul
        {
            int nilaiHash = fungsiHash(kunci); //menghashkan kunci
            arrayHash[nilaiHash]->hapus(kunci); //menghapus Simpul
        } //akhir hapus()

        Simpul* cari(int kunci) //mencari Simpul
        {
            int nilaiHash = fungsiHash(kunci); //menghashkan kunci
           
            //membaca Simpul
            Simpul* pSimpul = arrayHash[nilaiHash]->cari(kunci);
            return pSimpul; //menghasilkan Simpul
        }
}; //akhir kelas TabelHash

int main()
{
    int aKunci;
    Simpul* pItemData;
    int ukuran, n, kunciPerSel = 100;
    time_t waktuA;
    char pilihan = 'b';

    //membaca ukuran
    cout << "Masukkan ukuran tabel hash: ";
    cin >> ukuran;
       cout << "Masukkan jumlah awal item: ";
    cin >> n;

    TabelHash tabelHash(ukuran); //menciptakan tabel

    //menginisialisasi angka-angka acak
    srand( static_cast<unsigned>(time(&waktuA)) );
    for(int j=0; j<n; j++) //menyisipkan data
    {
        aKunci = rand() % (kunciPerSel * ukuran);
        pItemData = new Simpul(aKunci);
        tabelHash.sisip(pItemData);
    }

    while(pilihan != 'x') //berinteraksi dengan pengguna
    {
        cout << "Masukkan huruf pertama dari "
             << "tampil, sisip, hapus, atau cari: ";
        char pilihan;
        cin >> pilihan;

        switch(pilihan)
        {
            case 't':
                tabelHash.tampilTabel();
                break;

            case 's':
                cout << "Masukkan nilai kunci yang akan disisipkan: ";
                cin >> aKunci;
                pItemData = new Simpul(aKunci);
                tabelHash.sisip(pItemData);
                break;

            case 'h':
                cout << "Masukkan nilai kunci yang akan dihapus: ";
                cin >> aKunci;
                tabelHash.hapus(aKunci);
                break;

            case 'c':
                cout << "Masukkan nilai kunci yang akan dicari: ";
                cin >> aKunci;
                pItemData = tabelHash.cari(aKunci);

                if(pItemData != NULL)
                    cout << "Ditemukan " << aKunci << endl;
                else
                    cout << "Tidak ditemukan " << aKunci << endl;
                    break;

            default:
                cout << "Entri tak-valid\n";
        } //akhir switch
    } //akhir while

    getch();
    return 0;
} //akhir main()


Masukkan ukuran tabel hash: 20
Masukkan jumlah awal item: 20

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari: t
0. Senarai (pertama->akhir): 1580
1. Senarai (pertama->akhir):
2. Senarai (pertama->akhir): 1582
3. Senarai (pertama->akhir):
4. Senarai (pertama->akhir): 1724
5. Senarai (pertama->akhir): 1285 1885
6. Senarai (pertama->akhir): 1346 1706
7. Senarai (pertama->akhir):
8. Senarai (pertama->akhir): 1748
9. Senarai (pertama->akhir):
10. Senarai (pertama->akhir):
11. Senarai (pertama->akhir): 1611
12. Senarai (pertama->akhir):
13. Senarai (pertama->akhir): 373 913
14. Senarai (pertama->akhir): 214 1134
15. Senarai (pertama->akhir):
16. Senarai (pertama->akhir):
17. Senarai (pertama->akhir): 537 837
18. Senarai (pertama->akhir): 538 818
19. Senarai (pertama->akhir): 639 679 999

Masukkan huruf pertama dari tampil, sisip, hapus, atau cari:

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)