Sunday, December 25, 2016

Bab 15. Visual Basic .NET Belajar Dari Contoh



15. Struktur Data







Pengantar

Struktur data yang telah dipelajari sejauh ini, seperti array subskript-tunggal dan array subskript-ganda, adalah struktur data berukuran tetap. Bab ini akan mengintroduksi struktur data dinamais, yang dapat bertumbuh dan menyusut pada saat eksekusi. Senarai berantai adalah koleksi item data, dimana pengguna dapat menyisipkan dan menghapus sembarang item di mana saja di dalam senarai tersebut. Tumpukan penting pada kompiler dan sistem operasi; penyisipan dan penghapusan hanya berlaku untuk item pada posisi paling atas tumpukan. Antrian merepresentasikan baris antrian; penyisipan hanya dilakukan di belakang (disebut juga dengan ekor) antrian, dan penghapusan hanya dilakukan di depan (disebut pula dengan kepala) antrian. Pohon biner memfasilitasi pencarian dan pengurutan kecepatan-tinggi, dimana di dalamnya dilakukan eliminasi efisien atas item-item data duplikat. Antrian merepresentasikan hirarki sistem-file dan kompilasi ekspresi menjadi bahasa mesin.

Pada bab ini, akan didiskusikan setiap tipe struktur data dan diimplementasikan beberapa program yang menciptakan dan memanipulasi setiap struktur data tersebut. Kelas, pewarisan, dan komposisi diciptakan sehingga dapat meningkatkan kapabilitas struktur data.


Kelas Referensi-Diri
Sebuah kelas referensi-diri memuat sebuah anggota referensi yang menunjuk ke suatu objek kelas yang memili tipe kelas yang sama. Sebagai contoh, definisi kelas pada kode 15.1 mendefinisikan tipe CSimpul. Tipe ini memiliki dua variabel instans Private (baris 5-6), Integer mData dan referensi CSimpul mSimpulBerikutnya. Anggota mSimpulBerikutnya mereferensi sebuah objek bertipe CSimpul, tipe yang sama dengan kelasnya. Jadi, istilah referensi-diri sangat tepat untuk kasus ini. Anggota mSimpulBerikutnya dikenal dengan sebuah link atau rantai (ini berarti bahwa mSimpulBerikutnya dapat dipakai untuk “merantai atau mengikat” sebuah objek bertipe CSimpul dengan objek lain bertipe sama). Kelas CSimpul juga memiliki dua properti: satu untuk variabel mData, dinamai Data (baris 13-23), dan yang lain untuk variabel mSimpulBerikutnya, dinamai SimpulBerikutnya (baris 26-36).

Objek referensi-diri dapat dirantai atau dihubungkan bersama untuk membentuk struktur data, seperti senarai, antrian, tumpukan, dan pohon. Gambar 15.1 mengilustrasikan pengikatan dua objek referensi-diri untuk membentuk sebuah senarai. Garis-miring (backslash) \, yang merepresentasikan referensi Nothing), ditempatkan pada anggota dari objek referensi-diri kedua bertujuan untuk mengindikasikan bahwa link atau rantai tidak menunjuk ke objek lain. Referensi Nothing biasanya mendefinisikan akhir sebuah struktur data.
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
' Kode 15.1: Simpul.vb
' Kelas Simpul referensi-diri.

Class CSimpul
    Private mData As Integer
    Private mSimpulBerikutnya As CSimpul

    Public Sub New(ByVal nilaiData As Integer)
        ' tubuh konstruktor
    End Sub ' New

    ' Properti Data
    Public Property Data() As Integer

        Get
            ' tubuh Get
        End Get

        Set(ByVal nilaiData As Integer)
            ' tubuh Set
        End Set

    End Property ' Data

    ' Properti SimpulBerikutnya
    Public Property SimpulBerikutnya() As CSimpul

        Get
            ' mendapatkan simpul berikutnya
        End Get

        Set(ByVal nilaiSimpul As CSimpul)
            ' menetapkan simpul berikutnya
        End Set

    End Property ' SimpulBerikutnya

End Class 'CSimpul


Gambar 15.1 Dua objek kelas referensi-diri dirantai atau dihubungkan bersama


Penciptaan struktur data dinamis memerlukan alokasi memori dinamis, yaitu kemampuan program untuk mendapatkan memori tambahan (untuk menampung variabel-variabel baru) dan untuk melepaskan memori yang sudah tidak lagi dibutuhkan pada saat eksekusi. Ingat bahwa program Visual Basic secara otomatis melakukan koleksi sampah memori.

Katakunci New penting dalam alokasi memori dinamis. Katakunci New mengambil nama kelas suatu objek sebagai operand. Ia kemudian secara dinamis mengalokasikan memori untuk objek yang baru, memanggil konstruktor kelas, dan menghasilkan sebuah referensi yang menunjuk ke objek yang baru saja diciptakan. Sebagai contoh, statemen:

Dim simpulYgAkanDitambahkan As CSimpul = New CSimpul(10)

mengalokasikan sejumlah memori tertentu untuk menyimpan sebuah CSimpul, memanggil konstruktor CSimpul dengan argumen 10 (untuk anggota mData pada CSimpul), dan menyimpan sebuah referensi yang menunjuk ke objek ini di dalam simpulYgAkanDitambahkan.

Beberapa topik ke depan akan mendiskusikan senarai, tumpukan, antrian, dan pohon. Semua struktur data tersebut diciptakan dan dikembangkan dengan alokasi memori dinamis dan kelas referensi-diri.


Senarai Berantai
Senarai berantai adalah sebuah koleksi linier (runtun) atas objek-objek kelas referensi-diri, yang dinamakan dengan simpul, yang dikoneksi oleh rantai-rantai referensi. Program dapat mengakses sebuah senarai berantai melalui referensi yang menunjuk ke simpul pertama pada senarai. Setiap simpul diakses via anggota referensi pada simpul sekarang. Secara konvensi, referensi pada simpul terakhir ditetapkan menjadi Nothing untuk menandai akhir senarai. Data disimpan pada sebuah senarai berantai secara dinamis, dimana setiap simpul diciptakan jika diperlukan. Simpul dapat memuat sembarang tipe data.

Meskipun array juga dapat menyimpan koleksi data, senarai berantai memberikan beberapa keuntungan dan keunggulan lebih. Sangat tepat untuk menggunakan senarai berantai apabila jumlah elemen data yang akan disajikan pada struktur data tidak dapat diprediksi. Tidak seperti senarai berantai, ukuran dari array Visual Basic konvensional tidak dapat diubah, karena ukuran array tetap ketika array diciptakan. Array konvensional bisa menjadi penuh, tetapi senarai berantai hanya bisa penuh ketika sistem tidak lagi mempunyai memori untuk memenuhi permintaan pengalokasian dinamis.

Programer dapat mengembangkan senarai berantai secara berurutan hanya dengan menyisipkan setiap elemen baru pada titik yang tepat di dalam senarai. Jadi, penyisipan elemen baru tidak menyebabkan pemindahan elemen-elemen yang sudah ada.

Normalnya, memori tidak menyimpan simpul-simpul senarai berantai secara bertetangga di dalam memori. Gambar 15.2 mengilustrasikan sebuah senarai berantai yang memuat beberapa simpul.


Gambar 15.2 Representasi grafikal atas senarai berantai


Program pada kode 15.2-15.4 menggunakan sebuah objek kelas CSenarai untuk memanipulasi sekumpulan objek bertipe Object. Metode Main pada module modUjiSenarai (Kode 15.5) menciptakan beberapa objek, menyisipkan objek di awal senarai (menggunakan metode CSenarai SisipDiDepan), menyisipkan objek di akhir senarai (menggunakan metode CSenarai SisipDiBelakang), menghapus objek dari depan senarai (menggunakan metode CSenarai HapusDariDepan), dan menghapus objek dari belakang senarai (menggunakan metode CSenarai HapusDariBelakang). Setiap operasi penyisipan atau penghapusan akan memanggil metode CSenarai Tampil untuk menampilkan isi senarai sekarang. Diskusi detil atas program akan diberikan. Sebuah EksepsiSenaraiKosong terjadi jika percobaan untuk menghapus sebuah item dari senarai kosong dilakukan.

Program memuat empat kelas, CSimpulSenarai (kode 15.2), CSenarai (kode 15.3), EksepsiSenaraiKosong (kode 15.4), dan module modUjiSenarai (kode 15.5). Kelas-kelas pada kode 15.2-15.4 menciptakan sebuah pustaka senarai-berantai. Ketiga kelas tersebut berada di dalam namespace LinkedListLibrary.

Terenkapsulasi di dalam tiap objek CSenarai adalah sebuah senarai berantai yang memuat objek-objek CSimpulSenarai. Kelas CSimpulSenarai (kode 15.2) memuat dua variabel anggota, mData dan mSimpulBerikutnya. Anggota mData dapat menunjuk ke sembarang Object. Anggota mSimpulBerikutnya menyimpan sebuah referensi yang menunjuk ke objek CSimpulSenarai berikutnya pada senarai berantai. Sebuah CSenarai mengakses variabel-variabel anggota CSimpulSenarai melalui properti Data (baris 22-28) dan SimpulBerikutnya (baris 31-41).

Kelas CSenarai (kode 15.3) memuat anggota-anggota Private simpulPertama (sebuah referensi yang menunjuk ke CSimpulSenarai pertama pada sebuah CSimpul) dan simpulAkhir (sebuah referensi yang menunjuk ke CSimpulSenarai terakhir pada sebuah CSimpul). Konstruktor (baris 10-14 dan 17-19) menginisialisasi kedua referensi menjadi Nothing. Metode SisipDiDepan (baris 22-36), SisipDiBelakang (baris 39-54), HapusDariDepan (baris 57-81), dan HapusDari-Belakang (baris 84-117) adalah metode-metode utama pada kelas CSenarai. Setiap metode menggunakan blok SyncLock untuk memastikan bahwa objek-objek CSenarai menjadi multithread safe.

Metode ApaKosong (baris 120-132) adalah metode predikat yang menentukan apakah senarai kosong (apakah referensi ke simpul pertama senarai adalah Nothing). Metode predikat secara umum menguji sebuah kondisi dan tidak memodifikasi objek. Jika senarai kosong, metode ApaKosong menghasilkan True; sebaliknya, ia menghasilkan False. Metode Tampil (baris 135-159) menampilkan isi senarai. Kedua metode ApaKosong dan metode Tampil menggunakan blok SyncLock untuk memastikan bahwa keadaan senarai tidak berubah ketika metode-metode tersebut melakukan tugasnya.

Kelas EksepsiSenaraiKosong (kode 15.4) mendefinisikan sebuah kelas eksepsi untuk menangani operasi-operasi ilegal pada CSenarai yang kosong. Sebagai contoh, sebuah EksepsiSenarai-Kosong terjadi jika program mencoba menghapus sebuah simpul dari CSenarai yang kosong.

Module modUjiSenarai (kode 15.5) menggunakan pustaka senarai-berantai untuk menciptakan dan memanipulasi sebuah senarai berantai. Baris 10 menciptakan sebuah instans bertipe CSenarai, dinamai senarai. Kemudian, baris 13-16 menciptakan data yang akan ditambahkan ke dalam senarai. Baris 19-29 menggunakan metode-metode penyisipan CSenarai untuk menyisipkan objek-objek dan menggunakan metode CSenarai Tampil untuk menampilkan isi senarai setelah tiap penyisipan dilakukan. Kode di dalam blok Try (baris 35-70) menghapus objek-objek (menggunakan metode-metode penghapusan CSenarai), menampilkan objek yang dihapus, dan menampilkan isi senarai setelah setiap penghapusan dilakukan. Jika terdapat percobaan untuk menghapus sebuah objek dari senarai kosong, maka blok Catch (baris 68-69) akan menangkap EksepsiSenaraiKosong. Perhatikan bahwa module modUjiSenarai menggunakan namespace LinkedListLibrary. Jadi, projek yang memuat module modUjiSenarai harus memuat sebuah referensi yang menunjuk ke pustaka kelas LinkedListLibrary.

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
' Kode 15.2: SimpulSenarai.vb
' Kelas untuk merepresentasikan satu simpul di dalam sebuah CSenarai.

Public Class CSimpulSenarai
    Private mData As Object
    Private mSimpulBerikutnya As CSimpulSenarai

    ' menciptakan CSimpulSenarai dengan nilaiData dalam senarai
    Public Sub New(ByVal nilaiData As Object)
        MyClass.New(nilaiData, Nothing)
    End Sub ' New

    ' menciptakan CSimpulSenarai, nilaiData dan nilaiSimpulBerikutnya dalam senarai
    Public Sub New(ByVal nilaiData As Object, _
        ByVal nilaiSimpulBerikutnya As Object)

        mData = nilaiData
        mSimpulBerikutnya = nilaiSimpulBerikutnya
    End Sub ' New

    ' properti Data
    Public ReadOnly Property Data() As Object

        Get
            Return mData
        End Get

    End Property ' Data

    ' properti mSimpulBerikutnya
    Public Property SimpulBerikutnya() As CSimpulSenarai

        Get
            Return mSimpulBerikutnya
        End Get

        Set(ByVal nilai As CSimpulSenarai)
            mSimpulBerikutnya = nilai
        End Set

    End Property ' SimpulBerikutnya

End Class ' CSimpulSenarai

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
' Kode 15.3: Senarai.vb
' Definisi kelas CSenarai.

Public Class CSenarai
    Private simpulPertama As CSimpulSenarai
    Private simpulAkhir As CSimpulSenarai
    Private nama As String

    ' menciptakan Senarai kosong dengan nama tertentu
    Public Sub New(ByVal namaSenarai As String)
        nama = namaSenarai
        simpulPertama = Nothing
        simpulAkhir = Nothing
    End Sub ' New

    ' menciptakan Senarai kosong dengan "senarai" sebagai namanya
    Public Sub New()
        MyClass.New("senarai")
    End Sub ' New

    ' menyisipkan objek di depan Senarai
    Public Sub SisipDiDepan(ByVal itemSisip As Object)

        SyncLock (Me) ' memastikan thread safe

            ' jika senarai kosong, ciptakan simpul
            If ApaKosong() Then
                simpulAkhir = New CSimpulSenarai(itemSisip)
                simpulPertama = simpulAkhir
            Else ' menciptakan simpul dan menyisipkannya sebelum simpul pertama
                simpulPertama = New CSimpulSenarai(itemSisip, simpulPertama)
            End If

        End SyncLock

    End Sub ' SisipDiDepan

    ' menyisipkan objek di belakang Senarai
    Public Sub SisipDiBelakang(ByVal itemSisip As Object)

        SyncLock (Me) ' memastikan thread safety

            ' jika senarai kosong, ciptakan simpul dan tetapkan simpulPertama
            If ApaKosong() Then
                simpulAkhir = New CSimpulSenarai(itemSisip)
                simpulPertama = simpulAkhir
            Else ' menciptakan simpul dan menyisipkannya setelah simpul akhir
                simpulAkhir.SimpulBerikutnya = New CSimpulSenarai(itemSisip)
                simpulAkhir = simpulAkhir.SimpulBerikutnya
            End If

        End SyncLock

    End Sub ' SisipDiBelakang

    ' menghapus simpul pertama dari Senarai
    Public Function HapusDariDepan() As Object

        SyncLock (Me) ' memastikan thread safety
            Dim itemHapus As Object = Nothing

            ' melempar eksepsi jika mencoba menghapus senarai kosong
            If ApaKosong() Then
                Throw New EksepsiSenaraiKosong(nama)
            End If

            itemHapus = simpulPertama.Data ' mengambil data

            ' mereset referensi simpulPertama dan simpulAkhir
            If simpulPertama Is simpulAkhir Then
                simpulPertama = Nothing
                simpulAkhir = Nothing
            Else
                simpulPertama = simpulPertama.SimpulBerikutnya
            End If

            Return itemHapus ' menghasilkan item yang dihapus

        End SyncLock

    End Function ' HapusDariDepan

    ' menghapus simpul akhir dari Senarai
    Public Function HapusDariBelakang() As Object

        SyncLock (Me) ' memastikan thread safe
            Dim itemHapus As Object = Nothing

            ' melempar eksepsi jika mencoba menghapus senarai kosong
            If ApaKosong() Then
                Throw New EksepsiSenaraiKosong(nama)
            End If

            itemHapus = simpulAkhir.Data ' mengambil data

            ' mereset referensi simpulPertama dan simpulAkhir
            If simpulPertama Is simpulAkhir Then
                simpulAkhir = Nothing
                simpulPertama = simpulAkhir
            Else
                Dim sekarang As CSimpulSenarai = simpulPertama

                ' loop while simpul sekarang bukan simpulAkhir
                While (Not (sekarang.SimpulBerikutnya Is simpulAkhir))
                    sekarang = sekarang.SimpulBerikutnya ' ke simpul berikutnya
                End While

                ' sekarang adalh simpulAkhir yang baru
                simpulAkhir = sekarang
                sekarang.SimpulBerikutnya = Nothing
            End If

            Return itemHapus ' menghasilkan item yang dihapus

        End SyncLock

    End Function ' HapusDariBelakang

    ' menghasilkan true jika senarai kosong
    Public Function ApaKosong() As Boolean

        SyncLock (Me)

            If simpulPertama Is Nothing Then
                Return True
            Else
                Return False
            End If

        End SyncLock

    End Function ' ApaKosong

    ' menampilkan isi Senarai
    Public Overridable Sub Tampil()

        SyncLock (Me)

            If ApaKosong() Then
                Console.WriteLine("Kosong " & nama)

                Return
            End If

            Console.Write("# " & nama & " adalah: ")

            Dim sekarang As CSimpulSenarai = simpulPertama

            ' menampilkan data simpul sekarang ketika tidak di akhir senarai
            While Not sekarang Is Nothing
                Console.Write(sekarang.Data & " ")
                sekarang = sekarang.SimpulBerikutnya
            End While

            Console.WriteLine(vbCrLf)

        End SyncLock

    End Sub ' Tampil

End Class ' CSenarai

1
2
3
4
5
6
7
8
9
10
11
' Kode 15.4: EksepsiSenaraiKosong.vb
' Definisi kelas EksepsiSenaraiKosong.

Public Class EksepsiSenaraiKosong
    Inherits ApplicationException

    Public Sub New(ByVal nama As String)
        MyBase.New("# " & nama & " adalah kosong")
    End Sub ' New

End Class ' EksepsiSenaraiKosong

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
' Gambar 15.5: UjiSenarai.vb
' Menguji kelas CSenarai.

' Program ini dapat dikembangkan oleh para mahasiswa
' untuk berbagai aplikasi di dunia nyata.

Module modUjiSenarai

    Sub Main()
        Dim senarai As CSenarai = New CSenarai() ' menciptakan kontainer CSenarai

        ' menciptakan data untuk menyimpan di dalam CSenarai
        Dim aBoolean As Boolean = True
        Dim aKarakter As Char = "$"c
        Dim anInteger As Integer = 34567
        Dim aString As String = "hallo"

        ' menggunakan metode-metode penyisipan CSenarai
        senarai.SisipDiDepan(aBoolean) ' menyisipkan Boolean di depan
        senarai.Tampil()

        senarai.SisipDiDepan(aKarakter) ' menyisipkan Char di depan
        senarai.Tampil()

        senarai.SisipDiBelakang(anInteger) ' menyisipkan Integer di belakang
        senarai.Tampil()

        senarai.SisipDiBelakang(aString) ' menyisipkan String di belakang
        senarai.Tampil()

        ' menggunakan metode-metode penghapusan CSenarai
        Dim objekHapus As Object

        ' menghapus data dari senarai dan menampilkan setiap penghapusan
        Try

            ' menghapus objek dari depan senarai
            objekHapus = senarai.HapusDariDepan()
            Console.WriteLine(Convert.ToString(objekHapus) & _
            " dihapus")

            senarai.Tampil()

            ' menghapus objek dari depan senarai
            objekHapus = senarai.HapusDariDepan()
            Console.WriteLine(Convert.ToString(objekHapus) & _
            " dihapus")

            senarai.Tampil()

            ' menghapus objek dari belakang senarai
            objekHapus = senarai.HapusDariBelakang()
            Console.WriteLine(Convert.ToString(objekHapus) & _
             " dihapus")

            senarai.Tampil()

            ' menghapus objek dari belakang senarai
            objekHapus = senarai.HapusDariBelakang()
            Console.WriteLine(Convert.ToString(objekHapus) & _
            " dihapus")

            senarai.Tampil()

            ' menangkap eksepsi jika senarai kosong
        Catch eksepsiSenaraiKosong As EksepsiSenaraiKosong
            Console.Error.WriteLine(vbCrLf & _
            Convert.ToString(eksepsiSenaraiKosong))

        End Try

    End Sub ' Main

End Module ' modUjiSenarai

# senarai adalah: True

# senarai adalah: $ True

# senarai adalah: $ True 34567

# senarai adalah: $ True 34567 hallo

$ dihapus
# senarai adalah: True 34567 hallo

True dihapus
# senarai adalah: 34567 hallo

hallo dihapus
# senarai adalah: 34567

34567 dihapus
senarai kosong

Pada beberapa halaman ke depan, akan didisikusikan setiap metode dari kelas CSenarai secara detil. Metode SisipDiDepan (kode 15.3, baris 22-36) menempatkan sebuah simpul baru di depan senarai. Metode ini terdiri-dari tiga langkah, yang dapat dijelaskan berikut:
1.       Memanggil ApaKosong untuk menentukan apakah senarai kosong (kode 15.3, baris 27).

2.       Jika senarai kosong, kedua simpulPertama dan simpulAkhir ditetapkan untuk menunjuk ke CSimpulSenarai yang baru yang diinisialisasi dengan objek itemSisip (baris 28-29). Konstruktor CSimpulSenarai pada baris 9-11 (kode 15.2) memanggil konstruktor CSimpulSenarai  pada baris 14-19 (kode 15.2) untuk menetapkan variabel instans mData untuk menunjuk ke Object yang dilewatkan sebagai argumen pertama dan kemudian menetapkan mSimpulBerikutnya untuk menunjuk ke Nothing.

3.       Jika senarai tidak kosong, maka simpul baru dirantaikan ke dalam senarai dengan menetapkan simpulPertama agar menunjuk ke objek CSimpulSenarai yang baru, yang diinisialisasi dengan objek itemSisip dan simpulPertama (baris 30). Ketika konstruktor CSimpulSenarai (baris 14-19 pada kode 15.2) dieksekusi, ia akan menetapkan variabel instans mData agar menunjuk ke Object yang dilewatkan sebagai argumen pertama dan melakukan penyisipan dengan menetapkan referensi mSimpulBerikutnya agar menunjuk ke CSimpulSenarai yang dilewatkan sebagai argumen kedua.

Gambar 15.3 mengilustrasikan metode SisipDiDepan. Bagian a) menggambarkan senarai dan simpul baru selama operasi SisipDiDepan dan sebelum perantaian SimpulSenarai yang baru (memuat nilai 12) ke dalam senarai. Anak panah putus-putus pada bagian b) mengilustrasikan langkah 3 pada operasi SisipDiDepan, yang membuat SimpulSenarai menjadi bagian depan senarai yang baru.



Gambar 15.3 Representasi grafikal atas SisipDiDepan


Metode SisipDiBelakang (Kode 15.3, baris 39-54) menempatkan sebuah simpul baru di belakang senarai. Metode ini memuat tiga langkah:
1.       Memanggil ApaKosong untuk menentukan apakah senarai kosong (kode 15.3, baris 44).

2.       Jika senarai kosong, kedua simpulPertama dan simpulAkhir ditetapkan untuk menunjuk ke CSimpulSenarai yang baru yang diinisialisasi dengan objek itemSisip (baris 45-46). Konstruktor CSimpulSenarai pada baris 9-11 (kode 15.2) memanggil konstruktor CSimpulSenarai  pada baris 14-19 (kode 15.2) untuk menetapkan variabel instans mData untuk menunjuk ke Object yang dilewatkan sebagai argumen pertama dan kemudian menetapkan mSimpulBerikutnya untuk menunjuk ke Nothing.

3.       Jika senarai tidak kosong, maka simpul baru dirantaikan ke dalam senarai dengan menetapkan simpulAkhir dan simpulAkhir.SimpulBerikutnya agar menunjuk ke objek CSimpulSenarai yang baru, yang diinisialisasi dengan objek itemSisip (baris 48-49). Ketika konstruktor CSimpulSenarai (baris 9-11 pada kode 15.2) dieksekusi, ia akan menetapkan variabel instans mData agar menunjuk ke Object yang dilewatkan sebagai argumen dan melakukan penyisipan dengan menetapkan referensi mSimpulBerikutnya agar menunjuk ke Nothing.

Gambar 15.4 mengilustrasikan metode SisipDiBelakang. Bagian a) menggambarkan senarai dan SimpulSenarai yang baru (yang memuat nilai 5) selama operasi SisipDiBelakang dan sebelum perantaian simpul yang baru tersebut ke dalam senarai. Anak panah putus-putus pada bagian b) mengilustrasikan langkah-langkah pada operasi SisipDiBelakang, yang membuat SimpulSenarai menjadi bagian belakang senarai yang baru.

Metode HapusDariDepan (kode 15.3, baris 57-81) menghapus simpul depan dari senarai dan menghasilkan (menjadikan nilai balik) sebuah referensi yang menunjuk ke data terhapus. Metode ini melemparkan EksepsiSenaraiKosong (baris 63) jika program mencoba menghapus sebuah simpul dari senarai kosong. Metode ini memuat empat langkah:



Gambar 15.4 Representasi grafikal atas SisipDiBelakang


1.       Menugaskan simpulPertama.Data (data yang akan dihapus dari senarai) kepada referensi itemHapus (baris 67).

2.       Jika objek-objek yang ditunjuk oleh simpulPertama dan simpulAkhir adalah objek yang sama, maka ini mengindikasikan bahwa senarai hanya memuat satu elemen saja sebelum operasi penghapusan dilakukan. Pada kasus ini, metode HapusDariDepan menetapkan simpulPertama dan simpulAkhir menjadi Nothing (baris 71-72) untuk menghapus simpul dari senarai (sehingga senarai menjadi kosong).

3.       Jika senarai memuat lebih dari satu simpul sebelum penghapusan, maka metode ini membiarkan simpulAkhir seperti adanya dan hanya menugaskan simpulPertama.Sim-pulBerikunya untuk menunjuk ke simpulPertama (baris 77). Jadi, simpulPertama mereferensi simpul kedua sebelum pemanggilan metode HapusDariDepan.

4.       Menghasilkan referensi itemHapus (baris 77).

Gambar 15.5 mengilustrasikan metode HapusDariDepan. Bagian a) mengilustrasikan senarai sebelum operasi penghapusan. Bagian b) memotret manipulasi referensi yang terjadi.

Metode HapusDariBelakang (kode 15.3, baris 84-117) menghapus simpul akhir pada sebuah senarai dan menghasilkan sebuah referensi yang menunjuk ke data terhapus. Metode ini melemparkan EksepsiSenaraiKosong (baris 91) jika program mencoba menghapus sebuah simpul dari senarai kosong. Metode ini terdiri-dari tujuh langkah:
1.       Menugaskan simpulAkhir.Data (data yang akan dihapus dari senarai) kepada referensi itemHapus (baris 94).

2.       Jika objek-objek yang ditunjuk oleh simpulPertama dan simpulAkhir adalah objek yang sama (baris 97), maka ini mengindikasikan bahwa senarai hanya memuat satu elemen saja sebelum operasi penghapusan dilakukan. Pada kasus ini, metode HapusDariBelakang menetapkan simpulPertama dan simpulAkhir menjadi Nothing (baris 98-99) untuk menghapus simpul dari senarai (sehingga senarai menjadi kosong).



Gambar 15.5 Representasi grafikal atas HapusDariDepan



Gambar 15.6 Representasi grafikal atas HapusDariBelakang


3.       Jika senarai memuat lebih dari satu simpul sebelum penghapusan, maka diciptakan referensi CSimpulSenarai, sekarang, dan menugasinya simpulPertama (baris 101).

4.       Menggunakan sekarang untuk menjelajahi senarai sampai sekarang mereferensi simpul yang secara langsung berada tepat sebelum simpul akhir. Loop While (baris 104-106) menugaskan sekarang.SimpulBerikutnya untuk mereferensi sekarang asalkan sekarang.SimpulBerikutnya tidak sama dengan simpulAkhir.

5.       Setelah mengetahui lokasi simpul kedua terakhir, dilakukan penugasan sekarang kepada simpulAkhir (baris 109) untuk menghapus simpul akhir dari senarai.

6.        Menetapkan sekarang.SimpulBerikutnya menjadi Nothing (baris 110) pada simpul akhir yang baru.

7.       Menghasilkan referensi itemHapus (baris 113).


Tumpukan
Tumpukan adalah versi terkekang dari sebuah senarai berantai, dimana simpul baru dapat ditambahkan pada dan dihapus dari tumpukan hanya dari atasnya. Karena alasan ini, tumpukan disebuah dengan struktur data LIFO (least-in, first-out). Anggota link pada simpul bawah tumpukan ditetapkan menjadi Nothing untuk mengindikasikan bagian bawah tumpukan.

Beberapa operasi utama yang digunakan untuk memanipulasi tumpukan adalah push dan pop. Operasi push menambahkan sebuah simpul baru di atas tumpukan. Operasi pop menghapus sebuah simpul dari atas tumpukan dan menjadikan data dari simpul yang terhapus sebagai nilai balik.

Tumpukan memiliki banyak aplikasi. Sebagai contoh, ketika program memanggil sebuah metode, metode terpanggil harus mengetahui bagaiman kembali kepada pemanggilnya, sehingga alamat kembali ditempatkan di atas tumpukan eksekusi program. Jika serangkaian pemanggilan metode terjadi, alamat-alamat kembali ditempatkan ke atas tumpukan deengan gaya LIFO sehingga setiap metode dapat kembali kepada pemanggilnya.

Relasi yang dekat antara senarai dan tumpukan akan dipakai untuk mengimplementasikan kelas tumpukan dengan mendaur-ulang kelas senarai. Dua bentuk pendaur-ulangan kode akan didemons-trasikan. Pertama, akan diimplementasikan kelas tumpukan dengan mewarisi kelas CSenarai pada kode 15.3. Kemudian, akan diimplementasikan kelas tumpukan yang identik melalui komposisi dengan menyertakan objek CSenarai sebagai anggota Private dari kelas tumpukan.

Program pada kode 15.6 dan kode 15.7 menciptakan sebuah kelas tumpukan dengan mewarisi kelas CSenarai pada kode 15.3. Diinginkan bahwa tumpukan menyediakan metode Push, Pop, ApaKosong, dan Tampil. Secara esensial, semuanya adalah metode SisipDiDepan, HapusDariDepan, ApaKosong, dan Tampil dari kelas Senarai. Kelas Senarai memiliki beberapa metode lain, seperti SisipDiBelakang dan HapusDariBelakang, yang tidak bisa diakses melalui antarmuka Public pada tumpukan. Ingat bahwa semua metode pada antarmuka Public pada kelas CSenarai adalah metode Public pada kelas terderivasi CPewarisanTumpukan (kode 15.6).

Ketika metode-metode tumpukan diimplementasikan, setiap metode CPewarisanTumpukan memanggil metode CSenarai yang sesuai, yaitu metode Push memanggil SisipDiDepan dan metode Pop memanggil HapusDariDepan. Kelas CPewarisanTumpukan  tidak mendefinisikan metode ApaKosong dan Tampil, karena CPewarisanTumpukan mewarisi kedua metode ini dari kelas CSenarai. Semua metode pada kelas CPewarisanTumpukan tidak menggunakan statemen SyncLock. Setiap metode pada kelas ini memanggil metode dari kelas CSenarai yang menggunakan SyncLock.

Module metode Main pada modUjiPewarisanTumpukan (kode 15.7) menggunakan kelas CPewarisanTumpukan untuk menginstansiasi sebuah tumpukan Object, dinamai tumpukan. Baris 15-18 mendefinisikan empat objek yang akan ditempatkan ke atas tumpukan dan dihapus dari tumpukan. Program menempatkan sebuah Boolean dengan nilai True, sebuah Char dengan nilai $, sebuah Integer dengan nilai 34567, dan sebuah String dengan nilai “hallo” ke atas tumpukan (baris 21, 24, 27, dan 30). Loop While tak-hingga (baris 40-44) menghapus elemen-elemen tersebut dari tumpukan. Ketika tidak ada lagi objek yang akan dihapus, metode Pop melempar Eksepsi-SenaraiKosong, dan program menampilkan jejak tumpukan eksepsi, yang menggambarkan tumpukan eksekusi program ketika eksepsi terjadi. Program menggunakan metode Tampil (diwarisi dari kelas CSenarai) untuk menampilkan isi tumpukan setelah tiap operasi dilakukan.

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
' Kode 15.6: PewarisanTumpukan.vb
' Mengimplementasikan sebuah tumpukan dengan mewarisi kelas CSenarai.

‘ Metode Push memanggil metode SisipDiDepan
‘ Metode Pop memanggil metode HapusDariDepan

' kelas CPewarisanTumpukan mewarisi kelas CSenarai
Public Class CPewarisanTumpukan
    Inherits CSenarai

    ' melewatkan nama "tumpukan" kepada konstruktor CSenarai
    Public Sub New()
        MyBase.New("tumpukan")
    End Sub ' New

    ' menempatkan nilaiData di atas tumpukan dengan menyisipkan nilaiData
    ' di depan senarai berantai
    Public Sub Push(ByVal nilaiData As Object)
        MyBase.SisipDiDepan(nilaiData)
    End Sub ' Push

    ' menghapus item dari atas tumpukan dengan menghapus item yang ada di depan
    ' senarai berantai
    Public Function Pop() As Object
        Return MyBase.HapusDariDepan()
    End Function ' Pop

End Class ' CPewarisanTumpukan

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
' Kode 15.7: UjiPewarisanTumpukan.vb
' Menguji implementasi tumpukan.

‘ menempatkan beberapa item pada tumpukan dan
‘ menghapus item-item tersebut dari tumpukan


' demonstrasi fungsionalitas implementasi tumpukan
Module modUjiPewarisanTumpukan

    Sub Main()
        Dim tumpukan As CPewarisanTumpukan = New CPewarisanTumpukan()

        ' menciptakan objek-objek untuk disimpan pada tumpukan
        Dim aBoolean As Boolean = True
        Dim aKarakter As Char = Convert.ToChar("$")
        Dim anInteger As Integer = 34567
        Dim aString As String = "hallo"

        ' menggunakan metode Push untuk menambahkan item-item pada tumpukan
        tumpukan.Push(aBoolean) ' menambahkan Boolean
        tumpukan.Tampil()

        tumpukan.Push(aKarakter) ' menambahkan Char
        tumpukan.Tampil()

        tumpukan.Push(anInteger) ' menambahkan Integer
        tumpukan.Tampil()

        tumpukan.Push(aString) ' menambahkan String
        tumpukan.Tampil()

        ' menggunakan metode Pop untuk menghapus item-item dari tumpukan
        Dim objekDihapus As Object = Nothing

        ' menghapus item-item dari tumpukan
        Try

            ' menghapus item dan menampilkan item terhapus
            While True
                objekDihapus = tumpukan.Pop()
                Console.WriteLine(objekDihapus & " dihapus")
                tumpukan.Tampil()
            End While

            ' menangkap eksepsi jika Pop dipanggil ketika tumpukan kosong
        Catch eksepsiSenaraiKosong As EksepsiSenaraiKosong
            Console.Error.WriteLine(eksepsiSenaraiKosong.StackTrace)
        End Try

    End Sub ' Main

End Module ' modUjiPewarisanTumpukan

# tumpukan adalah: True

# tumpukan adalah: $ True

# tumpukan adalah: 34567 $ True

# tumpukan adalah: hallo 34567 $ True

hallo dihapus
# tumpukan adalah: 34567 $ True

34567 dihapus
# tumpukan adalah: $ True

$ dihapus
# tumpukan adalah: True

True dihapus

Kosong tumpukan
   at ConsoleApplication53.CSenarai.HapusDariDepan() in E:\CSenarai.vb:line 65
   at CPewarisanTumpukan.Pop() in E:\CPewarisanTumpukan.vb:line 22
   at modUjiPewarisanTumpukan.Main() in E:\modUjiPewarisanTumpukan.vb:line 38

Cara lain dalam mengimplementasikan sebuah kelas tumpukan adalah dengan mendaur-ulang kelas senarai melalui komposisi. Kelas pada 15.8 menggunakan sebuah objek Private dari kelas CSenarai (baris 9) di dalam definisi kelas CKomposisiTumpukan. Komposisi memampukan Anda untuk menyembunyikan metode-metode kelas CSenarai yang tidak perlu muncul di dalam antarmuka Public tumpukan. Hal ini dilakukan dengan menyediakan antarmuka Public bagi metode-metode yang diperlukan oleh metode-metode CSenarai. Kelas CKomposisiTumpukan mengimplemen-tasikan setiap metode tumpukan dengan mendelgasikan pekerjaanya kepada metode CSenarai yang sesuai. Kelas CKomposisiTumpukan memanggil metode-metode CSenarai, seperti SisipDi-Depan, HapusDariDepan, ApaKosong, dan Tampil.

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
' Kode 15.8: KomposisiTumpukan.vb
' Definisi KomposisiTumpukan dengan objek CSenarai terkomposisi.

‘ menempatkan beberapa item pada tumpukan dan
‘ menghapus item-item tersebut dari tumpukan

' kelas CKomposisiTumpukan mengenkapsulasi kapabilitas CSenarai
Public Class CKomposisiTumpukan
    Private tumpukan As CSenarai

    ' menciptakan tumpukan kosong
    Public Sub New()
        tumpukan = New CSenarai("tumpukan")
    End Sub ' New

    ' menambahkan objek ke tumpukan
    Public Sub Push(ByVal nilaiData As Object)
        tumpukan.SisipDiDepan(nilaiData)
    End Sub ' Push

    ' menghapus objek dari tumpukan
    Public Function Pop() As Object
        Return tumpukan.HapusDariDepan()
    End Function ' Pop

    ' menentukan apakah tumpukan kosong
    Public Function ApaKosong() As Boolean
        Return tumpukan.ApaKosong()
    End Function ' ApaKosong

    ' menampilkan isi tumpukan
    Public Sub Tampil()
        tumpukan.Tampil()
    End Sub ' Tampil

End Class ' CKomposisiTumpukan

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
' Kode 15.9: UjiKomposisiTumpukan.vb
' Menguji implementasi tumpukan dengan komposisi.

‘ menempatkan beberapa item pada tumpukan dan
‘ menghapus item-item tersebut dari tumpukan


' demonstrasi fungsionalitas implementasi tumpukan
Module modUjiKomposisiTumpukan

    Sub Main()
        Dim tumpukan As CKomposisiTumpukan = New CKomposisiTumpukan()

        ' menciptakan objek-objek untuk disimpan pada tumpukan
        Dim aBoolean As Boolean = True
        Dim aKarakter As Char = Convert.ToChar("$")
        Dim anInteger As Integer = 34567
        Dim aString As String = "hallo"

        ' menggunakan metode Push untuk menambahkan item-item pada tumpukan
        tumpukan.Push(aBoolean) ' menambahkan Boolean
        tumpukan.Tampil()

        tumpukan.Push(aKarakter) ' menambahkan Char
        tumpukan.Tampil()

        tumpukan.Push(anInteger) ' menambahkan Integer
        tumpukan.Tampil()

        tumpukan.Push(aString) ' menambahkan String
        tumpukan.Tampil()

        ' menggunakan metode Pop untuk menghapus item-item dari tumpukan
        Dim objekDihapus As Object = Nothing

        ' menghapus item-item dari tumpukan
        Try

            ' menghapus item dan menampilkan item terhapus
            While True
                objekDihapus = tumpukan.Pop()
                Console.WriteLine(objekDihapus & " dihapus")
                tumpukan.Tampil()
            End While

            ' menangkap eksepsi jika Pop dipanggil ketika tumpukan kosong
        Catch eksepsiSenaraiKosong As EksepsiSenaraiKosong
            Console.Error.WriteLine(eksepsiSenaraiKosong.StackTrace)
        End Try

    End Sub ' Main

End Module ' modUjiKomposisiTumpukan

# tumpukan adalah: 34567 $ True

# tumpukan adalah: hallo 34567 $ True

hallo dihapus
# tumpukan adalah: 34567 $ True

34567 dihapus
# tumpukan adalah: $ True

$ dihapus
# tumpukan adalah: True

True dihapus
Kosong tumpukan
   at CSenarai.HapusDariDepan() in E:\CSenarai.vb:line 65
   at CKomposisiTumpukan.Pop() in E:\CKomposisiTumpukan.vb:line 20
   at modUjiKomposisiTumpukan.Main() in E:\modUjiKomposisiTumpukan.vb:line 38


Antrian
Struktur data lain yang umum dijumpai adalah antrian. Antrian sama seperti antrian di pusat perbelanjaan, dimana orang pertama dalam antrian akan dilayani lebih dahulu, dan para pelanggan lainnya harus menunggu untuk dilayani. Simpul antrian dihapus hanya dari kepala antrian dan disisipkan hanya di ekor antrian. Karena alasan ini, antrian disebut dengan struktur data FIFO (first-in first-out). Operasi penyisipan dan operasi penghapusan dikenal sebagai enqueue dan dequeue.

Program pada kode 15.10 dan kode 15.11 menciptakan sebuah kelas antrian melalui pewarisan dari kelas senarai. Diinginkan bahwa kelas CPewarisanAntrian (kode 15.10) untuk menyertakan metode-metoe Enqueue, Dequeue, ApaKosong, dan Tampil. Perhatikan bahwa secara esensial semua metode tersebut adalah SisipDiBelakang, HapusDariDepan, ApaKosong, dan Tampil dari kelas CSenarai.

Ketika Anda mengimplementasikan metode-metode antrian, setiap pemanggilan metode CPewarisanAntrian akan memanggil metode CSenarai yang sesuai, dimana metode Enqueue memanggil SisipDiBelakang, dan metode Dequeue memangil HapusDariDepan, sedangkan ApaKosong dan Tampil memanggil versi kelas-basisnya.

Module metode Main pada modUjiPewarisanAntrian (kode 15.11) menggunakan kelas CPewarisanAntrian untuk menginstansiasi sebuah antrian Object, dinamai antrian. Baris 15-18 mendefinisikan empat objek yang akan ditempatkan ke dalam antrian dan dihapus dari antrian. Program menempatkan sebuah Boolean dengan nilai True, sebuah Char dengan nilai $, sebuah Integer dengan nilai 34567, dan sebuah String dengan nilai “hallo” ke dalam antrian (baris 21, 24, 27, dan 30).

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
' Kode 15.10: PewarisanAntrian.vb
' Mengimplementasikan sebuah antrian dengan mewarisi kelas Senarai.

' menempatkan beberapa item ke dalam antrian dan
' menghapus item-item tersebut dari antrian

' kelas CPewarisanAntrian mewarisi kelas CSenarai
Public Class CPewarisanAntrian
    Inherits CSenarai

    ' melewatkan nama "antrian" kepada konstruktor CSenarai
    Public Sub New()
        MyBase.New("antrian")
    End Sub

    ' menempatkan nilaiData di akhir antrian dengan menyisipkan
    ' nilaiData di akhir senarai berantai
    Public Sub Enqueue(ByVal nilaiData As Object)
        MyBase.SisipDiBelakang(nilaiData)
    End Sub ' Enqueue

    ' menghapus item dari depan antrian dengan menghapus
    ' item di depan senarai berantai
    Public Function Dequeue() As Object
        Return MyBase.HapusDariDepan()
    End Function ' Dequeue

End Class ' CPewarisanAntrian

Loop While tak-hingga (baris 40-44) menghapus elemen-elemen tersebut dari antrian. Ketika tidak ada lagi objek yang akan dihapus, metode Dequeu akan melempar Eksepsi-SenaraiKosong, dan program menampilkan jejak tumpukan eksepsi, yang menggambarkan tumpukan eksekusi program ketika eksepsi terjadi. Program menggunakan metode Tampil (diwarisi dari kelas CSenarai) untuk menampilkan isi tumpukan setelah tiap operasi dilakukan.

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
' Kode 15.11: UjiAntrian.vb
' Menguji implementasi antrian dengan pewarisan.

' menempatkan beberapa item ke dalam antrian dan
' menghapus item-item tersebut dari antrian


' demonstrasi fungsionalitas implementasi tumpukan
Module modUjiAntrian

    Sub Main()
        Dim antrian As CPewarisanAntrian = New CPewarisanAntrian()

        ' menciptakan objek-objek untuk disimpan dalam antrian
        Dim aBoolean As Boolean = True
        Dim aKarakter As Char = Convert.ToChar("$")
        Dim anInteger As Integer = 34567
        Dim aString As String = "hallo"

        ' menggunakan metode Enqueue untuk menambahkan item-item dalam antrian
        antrian.Enqueue(aBoolean) ' menambahkan Boolean
        antrian.Tampil()

        antrian.Enqueue(aKarakter) ' menambahkan Char
        antrian.Tampil()

        antrian.Enqueue(anInteger) ' menambahkan Integer
        antrian.Tampil()

        antrian.Enqueue(aString) ' menambahkan String
        antrian.Tampil()

        ' menggunakan metode Dequeue untuk menghapus item-item dari antrian
        Dim objekDihapus As Object = Nothing

        ' menghapus item-item dari antrian
        Try

            ' menghapus item dan menampilkan item terhapus
            While True
                objekDihapus = antrian.Dequeue()
                Console.WriteLine(objekDihapus & " dihapus")
                antrian.Tampil()
            End While

            ' menangkap eksepsi jika Pop dipanggil ketika tumpukan kosong
        Catch eksepsiSenaraiKosong As EksepsiSenaraiKosong
            Console.Error.WriteLine(eksepsiSenaraiKosong.StackTrace)
        End Try

    End Sub ' Main

End Module ' modUjiAntrian

# tumpukan adalah: True

# tumpukan adalah: $ True

# tumpukan adalah: 34567 $ True

# tumpukan adalah: hallo 34567 $ True

hallo dihapus
# tumpukan adalah: 34567 $ True

34567 dihapus
# tumpukan adalah: $ True

$ dihapus
# tumpukan adalah: True

True dihapus
Kosong tumpukan
   at CSenarai.HapusDariDepan() in E:\CSenarai.vb:line 65
   at CKomposisiTumpukan.Pop() in E:\CKomposisiTumpukan.vb:line 20
   at modUjiKomposisiTumpukan.Main() in E:\modUjiKomposisiTumpukan.vb:line 38


Pohon
Senarai berantai, tumpukan, dan antrian adalah struktur data linier. Sebaliknya, pohon adalah struktur data tak-linier, dua dimensi, dengan beberapa sifat spesial. Setiap simpul pada pohon mempunyai dua atau lebih link atau rantai. Bagian ini akan mendiskusikan pohon biner (Gambar 15.7), atau pohon dengan setiap simpul memiliki dua link (tidak ada, satu atau keduanya bisa Nothing). Simpul akar adalah simpul pertama pada pohon. Setiap link pada simpul akar disebut dengan anak. Anak kiri adalah simpul pertama pada subpohon kiri, dan anak kanan adalah simpul pertama pada subpohon kanan. Semua anak dari simpul tertentu disebut dengan sibling atau saudara. Sebuah simpul yang tidak memiliki anak disebut dengan simpul daun.

Contoh pohon-biner yang disajikan akan menciptakan sebuah pohon biner spesial, yang dikenal dengan pohon pencarian biner (binary search tree). Sebuah pohon pencarian biner (tanpa nilai simpul duplikat) memiliki karakteristik bahwa nilai-nilai pada sembarang subpohon kiri lebih rendah dari nilai simpul induk subpohon, dan bahwa nilai-nilai pada sembarang subpohon kanan lebih tinggi dari simpul induk subpohon. Gambar 15.8 mengilustrasikan sebuah pohon pencarian biner yang memuat 12 integer. Perhatikan bahwa bentuk sebuah pohon pencarian biner yang terkait dengan suatu himpunan data sangat bergantung pada urutan penyisipan nilai-nilai ke dalam pohon.



Gambar 15.7 Representasi grafikal atas pohon biner



Gambar 15.8 Pohon pencarian biner yang memuat 12 integer


Pohon Pencarian Biner dengan Nilai-Nilai Integer
Aplikasi pada kode 15.12, kode 15.13, dan kode 15.14 menciptakan sebuah pohon pencarian biner dengan nilai-nilai integer dan kemudian menjelajahi pohon tersebut (berjalan melalui semua simpulnya) dalam tiga cara, yaitu menggunakan penjelajahan inorder, preorder, dan postorder rekursif. Program membangkitkan 10 angka acak dan menyisipkan setiap angka acak itu ke dalam pohon. Kode 15.13 mendefinisikan kelas CPohon. Kode 15.14 mendefinisikan modUjiPohon, yang mendemonstrasikan fungsionalitas kelas CPohon. Metode Main pada modUjiPohon meng-instansiasi sebuah objek CPohon kosong, yang secara acak membangkitkan 10 integer dan menyisipkan setiap nilai ke dalam pohon menggunakan metode SisipSimpul. Program kemudian melakukan penjelajahan pohon secara preorder, inorder, dan postorder.

Kelas CSimpulPohon (kode 15.12) merupakan sebuah kelas referensi-diri yang memuat tiga anggota data Private, yaitu mSimpulKiri dan mSimpulKanan yang keduanya bertipe CSimpulPohon dan mData yang bertipe Integer (baris 5-7). Awalnya, setiap CSimpulPohon adalah simpul daun, jadi konstruktor (baris 10-14) menginisialisasi referensi mSimpulKiri dan mSimpulKanan dengan Nothing. Properti SimpulKiri (baris 17-27), Data (baris 30-40), dan SimpulKanan (baris 45-53) menyediakan akses terhadap anggota-anggota Private kelas CSimpulPohon.

Kelas CPohon (kode 15.13) memanipulasi objek-objek kelas CSimpulPohon. Kelas CPohon memuat sebuah simpul Private akar (baris 5), yaitu sebuah referensi yang menunjuk ke simpul akar pohon. Kelas ini juga memuat anggota Public SisipSimpul (baris 13-26), yang menyisipkan sebuah simpul ke dalam pohon, dan metode-metode Public PenjelajahanPreorder (baris 29-35), PenjelajahanInorder (baris 29-35), dan PenjelajahanPostorder (baris 83-89), yang memulai penjelajahan pohon. Setiap metode penjelajah memanggil metode utilitas rekursif secara terpisah untuk melakukan operasi penjelajahan pada pohon. Konstruktor CPohon (baris 8-10) menginisialisasi akar dengan Nothing untuk mengindikasikan bahwa pohon awalnya kosong.

Metode SisipSimpul pada kelas CPohon pertama-tama mengunci objek CPohon dan kemudian menentukan apakah pohon kosong atau tidak. Jika kosong, baris 19 akan menginstansiasi sebuah objek CSimpulPohon, menginisialisasi simpul dengan integer yang akan disisipkan, dan menugaskan simpul baru kepada akar. Jika pohon tidak kosong, maka metode SisipSimpul akan memanggil metode Sisip (baris 56-84) dari kelas CSimpulPohon, yang secar rekursif menentukan lokasi untuk simpul baru di dalam pohon dan menyisipkan simpul pada lokasi itu.

Metode Sisip pada kelas CSimpulPohon melakukan perbandingan atas nilai yang akan disisipkan dengan nilai mData pada simpul akar. Jika nilai yang akan disisipkan kurang dari data simpul-akar, maka program menentukan apakah subpohon kiri kosong atau tidak (baris 62). Jika kosong, maka baris 63 akan menginstansiasi sebuah objek CSimpulPohon, menginisialisasinya dengan integer yang akan disisipkan, dan menugaskan simpul baru pada referensi mSimpulKiri. Sebaliknya, jika subpohon kiri tidak kosong, maka baris 67 akan secara rekursif memanggil metode Sisip pada subpohon kiri untuk menyisipkan nilai ke dalam subpohon kiri. Jika nilai yang akan disisipkan lebih besar dari data simpul akar, maka program akan menentukan apakah subpohon kanan kosong atau tidak (baris 74). Jika kosong, baris 75 akan menginstansiasi sebuah objek CSimpulPohon, menginisialisasinya dengan integer yang akan disisipkan, dan menugaskan simpul baru kepada referensi mSimpulKanan. Sebaliknya, jika subpohon kanan tidak kosong, maka baris 79 akan secara rekursif memanggil metode Sisip pada subpohon kanan untuk menyisipkan nilai ke dalam subpohon kanan.

Metode-metode PenjelajahanInorder, PenjelajahanPreorder, dan PenjelajahanPostorder memanggil metode-metode pembantu PembantuInorder (baris 65-80), PembantuPreorder (baris 38-53), dan PembantuPostorder (baris 92-107) untuk menjelajah pohon dan menampilkan nilai setiap simpul. Setiap metode pembantu pada kelas CPohon membuat programer dapat mengawali penjelajahan tanpa perlu terlebih dahulu mendapatkan sebuah referensi yang menunjuk ke simpul pertama akar dan kemudian memanggil metode rekursif dengan referensi itu. Metode-metode PenjelajahanInorder, PenjelajahanPreorder, dan PenjelajahanPostorder cukup mengambil referensi Private akar dan melewatkannya kepada metode pembantu yang sesuai untuk mengawali penjelajahan pohon.

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
' Kode 15.12: SimpulPohon.vb
' Kelas CSimpulPohon merepresentasikan sebuah simpul pada sebuah CPohon.

Public Class CSimpulPohon
    Private mSimpulKiri As CSimpulPohon
    Private mData As Integer
    Private mSimpulKanan As CSimpulPohon

    ' menginisialisasi data dan membuat sebuah simpul daun
    Public Sub New(ByVal dataSimpul As Integer)
        mData = dataSimpul
        mSimpulKanan = Nothing ' simpul tanpa anak
        mSimpulKiri = Nothing ' simpul tanpa anak
    End Sub ' New

    ' properti SimpulKiri
    Public Property SimpulKiri() As CSimpulPohon

        Get
            Return mSimpulKiri
        End Get

        Set(ByVal nilai As CSimpulPohon)
            mSimpulKiri = nilai
        End Set

    End Property ' SimpulKiri

    ' properti Data
    Public Property Data() As Integer

        Get
            Return mData
        End Get

        Set(ByVal nilai As Integer)
            mData = nilai
        End Set

    End Property ' Data

    ' propert SimpulKanan
    Public Property SimpulKanan() As CSimpulPohon

        Get
            Return mSimpulKanan
        End Get

        Set(ByVal nilai As CSimpulPohon)
            mSimpulKanan = nilai
        End Set

    End Property ' SimpulKanan

    ' menyisipkan simpul ke dalam pohon
    Public Sub Sisip(ByVal nilaiSisip As Integer)

        ' menyisipkan ke subpohon kiri
        If nilaiSisip < mData Then

            ' menyisipkan CSimpulPohon baru
            If mSimpulKiri Is Nothing Then
                SimpulKiri = New CSimpulPohon(nilaiSisip)

                ' melanjutkan penjelajahan subpohon kiri
            Else
                SimpulKiri.Sisip(nilaiSisip)
            End If

            ' menyisipkan ke subpohon kanan
        ElseIf nilaiSisip > mData Then

            ' menyisipkan CSimpulPohon baru
            If SimpulKanan Is Nothing Then
                SimpulKanan = New CSimpulPohon(nilaiSisip)

                ' melanjutkan penjelajahan subpohon kanan
            Else
                SimpulKanan.Sisip(nilaiSisip)
            End If

        End If

    End Sub ' Sisip

End Class ' CSimpulPohon

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
' Kode 15.13: Pohon.vb
' Kelas CPohon adalah sebuah pohon yang memuat beberapa CSimpulPohon.

Public Class CPohon
    Private akar As CSimpulPohon

    ' menciptakan sebuah CPohon kosong yang memuat integer-integer
    Public Sub New()
        akar = Nothing
    End Sub ' New

    ' menyisipkan simpul baru ke dalam pohon pencarian biner
    Public Sub SisipSimpul(ByVal nilaiSisip As Integer)

        SyncLock (Me)

            ' jika simpul tidak ada, maka ciptakan simpul
            If akar Is Nothing Then
                akar = New CSimpulPohon(nilaiSisip)
            Else ' sebaliknya sisipkan simpul ke dalam pohon
                akar.Sisip(nilaiSisip)
            End If

        End SyncLock

    End Sub ' SisipSimpul

    ' memulai penjelajahan preorder
    Public Sub PenjelajahanPreorder()

        SyncLock (Me)
            PembantuPreorder(akar)
        End SyncLock

    End Sub ' PreOrderTraversal

    ' metode rekursif untuk melakukan penjelajahan preorder
    Private Sub PembantuPreorder(ByVal simpul As CSimpulPohon)

        If simpul Is Nothing Then
            Return
        End If

        ' menampilkan data simpul
        Console.Write(simpul.Data & " ")

        ' menjelajah subpohon kiri
        PembantuPreorder(simpul.SimpulKiri)

        ' traverse right subtree
        PembantuPreorder(simpul.SimpulKanan)

    End Sub ' PembantuPreorder

    ' memulai penjelajahan inorder
    Public Sub PenjelajahanInorder()

        SyncLock (Me)
            PembantuInorder(akar)
        End SyncLock

    End Sub ' PenjelajahanInorder

    ' metode rekursif untuk melakukan penjelajahan inorder
    Private Sub PembantuInorder(ByVal simpul As CSimpulPohon)

        If simpul Is Nothing Then
            Return
        End If

        ' menjelajah subpohon kiri
        PembantuInorder(simpul.SimpulKiri)

        ' menampilkan data simpul
        Console.Write(simpul.Data & " ")

        ' menjelajah subpohon kanan
        PembantuInorder(simpul.SimpulKanan)

    End Sub ' PembantuInorder

    ' memulai penjelajahan postorder
    Public Sub PenjelajahanPostorder()

        SyncLock (Me)
            PembantuPostorder(akar)
        End SyncLock

    End Sub ' PostorderTraversal

    ' metode rekursif untuk melakukan penjelajahan postorder
    Private Sub PembantuPostorder(ByVal simpul As CSimpulPohon)

        If simpul Is Nothing Then
            Return
        End If

        ' menjelajah subpohon kiri
        PembantuPostorder(simpul.SimpulKiri)

        ' menjelajah subpohon kanan
        PembantuPostorder(simpul.SimpulKanan)

        ' menampilkan data simpul
        Console.Write(simpul.Data & " ")

    End Sub ' PembantuPostorder

End Class ' CPohon

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
' Kode 15.14: UjiPohon.vb
' Program ini menguji kelas CPohon.

' Menciptakan objek CPohon
' dan memanfaatkan metode-metode kelas CSimpulPohon

Module modUjiPohon

    ' menguji kelas CPohon
    Sub Main()
        Dim pohon As CPohon = New CPohon()
        Dim nilaiSisip As Integer
        Dim i As Integer

        Console.WriteLine("Sisipkan nilai-nilai: ")
        Dim angkaAcak As Random = New Random()

        ' menyisipkan 10 integer acak dari 0-99 ke dalam pohon
        For i = 1 To 10
            nilaiSisip = angkaAcak.Next(100)
            Console.Write(nilaiSisip & " ")
            pohon.SisipSimpul(nilaiSisip)
        Next

        ' melakukan penjelajahan preorder atas pohon
        Console.WriteLine(vbCrLf & vbCrLf & "Penjelajahan Preorder")
        pohon.PenjelajahanPreorder()

        ' melakukan penjelajahan inorder atas pohon
        Console.WriteLine(vbCrLf & vbCrLf & "Penjelajahan Inorder")
        pohon.PenjelajahanInorder()

        ' melakukan penjelajahan postorder atas pohon
        Console.WriteLine(vbCrLf & vbCrLf & "Penjelajahan Postorder")
        pohon.PenjelajahanPostorder()

        Console.WriteLine()
    End Sub ' Main

End Module ' modUjiPohon

Sisipkan nilai-nilai:
85 65 50 91 23 9 96 54 1 87

Penjelajahan Preorder
85 65 50 23 9 1 54 91 87 96

Penjelajahan Inorder
1 9 23 50 54 65 85 87 91 96

Penjelajahan Postorder
1 9 23 54 50 65 87 96 91 85


Pohon Pencarian Biner dengan Objek-Objek IComparable
Contoh pohon-biner sebelumnya dapat bekerja dengan baik ketika semua data bertipa Integer. Namun, dimisalkan bahwa seorang programer ingin memanipulasi sebuah pohon pencarian biner yang memuat nilai-nilai double, maka ia harus menuliskan-ulang kelas CSimpulPohon dan CPohon sehingga dapat dipakai untuk memanipulasi nilai-nilai double.

Pada contoh selanjutnya, akan digunakan kapabilitas polimorfik pada Visual Basic. Akan diimplementasikan kelas CSimpulPohon dan CPohon, yang memanipulasi objek-objek yang mengimplementasikan antarmuka IComparable (dari namespace System). Kelas yang mengim-plementasikan antarmuka IComparable mendefinisikan metode CompareTo, yang membanding-kan objek yang memanggil metode dengan objek yang diterima metode tersebut sebagai argumen. Metode menghasilkan sebuah nilai Integer yang kurang dari nol jika objek pemanggil kurang dari objek argumen, nol jika kedua objek sama, atau sebuah Integer lebih besar dari nol jika objek pemanggil lebih besar dari objek argumen. Di samping itu, kedua objek pemanggil dan objek argumen harus bertipe data sama; jika tidak, metode akan melemparkan ArgumentException.

Program pada kode 15.15 dan kode 15.16 memperbaiki program sebelumnya untuk memanipulasi objek IComparable. Satu pembatasan pada versi baru dari kelas CSimpulPohon dan CPohon adalah bahwa setiap objek CPohon dapat memuat objek dengan satu tipe data (misalnya, semuanya String atau semuanya Double). Jika program mencoba untuk menyisipkan beberapa data berbeda pada objek CPohon yang sama, maka ArgumentException akan terjadi. Yang dimodifikasi hanyalah tujuh baris kode pada kelas CSimpulPohon (baris 6, 10, 30, 36, 56, 59, dan 71) dan satu baris kode pada kelas CPohon (baris 13) untuk memampukan pemrosesan objek IComparable. Dengan pengecualian pada baris 59 dan 71, semua modifikasi hanya mengganti tipe Integer dengan tipe IComparable. Baris 59 dan 71 sebelumnya menggunakan operator < dan > dalam membandingkan nilai yang disisipkan dengan nilai di dalam simpul tertentu. Kedua baris tersebut sekarang membandingkan objek-objek IComparable menggunakan metode CompareTo; Metode ini dipakai untuk menentukan nilai balik kurang dari nol (objek pemanggil kurang dari objek argumen), nol (objek pemanggil sama dengan objek argumen), atau lebih besar dari nol (objek pemanggil lebih besar dari objek argumen).

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
' Kode 15.15: SimpulPohon2.vb
' Kelas CSimpulPohon menggunakan objek-objek IComparable.

Public Class CSimpulPohon
    Private mSimpulKiri As CSimpulPohon
    Private mData As IComparable
    Private mSimpulKanan As CSimpulPohon

    ' menginisialisasi data dan membuat sebuah simpul daun
    Public Sub New(ByVal dataSimpul As IComparable)
        mData = dataSimpul
        mSimpulKanan = Nothing ' simpul tanpa anak
        mSimpulKiri = Nothing ' simpul tanpa anak
    End Sub ' New

    ' properti SimpulKiri
    Public Property SimpulKiri() As CSimpulPohon

        Get
            Return mSimpulKiri
        End Get

        Set(ByVal nilai As CSimpulPohon)
            mSimpulKiri = nilai
        End Set

    End Property ' SimpulKiri

    ' properti Data
    Public Property Data() As IComparable

        Get
            Return mData
        End Get

        Set(ByVal nilai As IComparable)
            mData = nilai
        End Set

    End Property ' Data

    ' propert SimpulKanan
    Public Property SimpulKanan() As CSimpulPohon

        Get
            Return mSimpulKanan
        End Get

        Set(ByVal nilai As CSimpulPohon)
            mSimpulKanan = nilai
        End Set

    End Property ' SimpulKanan

    ' menyisipkan simpul ke dalam pohon
    Public Sub Sisip(ByVal nilaiSisip As IComparable)

        ' menyisipkan ke subpohon kiri
        If nilaiSisip.CompareTo(mData) Then

            ' menyisipkan CSimpulPohon baru
            If mSimpulKiri Is Nothing Then
                SimpulKiri = New CSimpulPohon(nilaiSisip)

                ' melanjutkan penjelajahan subpohon kiri
            Else
                SimpulKiri.Sisip(nilaiSisip)
            End If

            ' menyisipkan ke subpohon kanan
        ElseIf nilaiSisip.CompareTo(mData) Then

            ' menyisipkan CSimpulPohon baru
            If SimpulKanan Is Nothing Then
                SimpulKanan = New CSimpulPohon(nilaiSisip)

                ' melanjutkan penjelajahan subpohon kanan
            Else
                SimpulKanan.Sisip(nilaiSisip)
            End If

        End If

    End Sub ' Sisip

End Class ' CSimpulPohon

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
' Kode 15.16: Pohon.vb
' Kelas CPohon adalah sebuah pohon yang data IComparable.

Public Class CPohon
    Private akar As CSimpulPohon

    ' menciptakan sebuah CPohon kosong yang memuat integer-integer
    Public Sub New()
        akar = Nothing
    End Sub ' New

    ' menyisipkan simpul baru ke dalam pohon pencarian biner
    Public Sub SisipSimpul(ByVal nilaiSisip As IComparable)

        SyncLock (Me)

            ' jika simpul tidak ada, maka ciptakan simpul
            If akar Is Nothing Then
                akar = New CSimpulPohon(nilaiSisip)
            Else ' sebaliknya sisipkan simpul ke dalam pohon
                akar.Sisip(nilaiSisip)
            End If

        End SyncLock

    End Sub ' SisipSimpul

    ' memulai penjelajahan preorder
    Public Sub PenjelajahanPreorder()

        SyncLock (Me)
            PembantuPreorder(akar)
        End SyncLock

    End Sub ' PreOrderTraversal

    ' metode rekursif untuk melakukan penjelajahan preorder
    Private Sub PembantuPreorder(ByVal simpul As CSimpulPohon)

        If simpul Is Nothing Then
            Return
        End If

        ' menampilkan data simpul
        Console.Write(Convert.ToString(simpul.Data) & " ")

        ' menjelajah subpohon kiri
        PembantuPreorder(simpul.SimpulKiri)

        ' traverse right subtree
        PembantuPreorder(simpul.SimpulKanan)

    End Sub ' PembantuPreorder

    ' memulai penjelajahan inorder
    Public Sub PenjelajahanInorder()

        SyncLock (Me)
            PembantuInorder(akar)
        End SyncLock

    End Sub ' PenjelajahanInorder

    ' metode rekursif untuk melakukan penjelajahan inorder
    Private Sub PembantuInorder(ByVal simpul As CSimpulPohon)

        If simpul Is Nothing Then
            Return
        End If

        ' menjelajah subpohon kiri
        PembantuInorder(simpul.SimpulKiri)

        ' menampilkan data simpul
        Console.Write(Convert.ToString(simpul.Data) & " ")

        ' menjelajah subpohon kanan
        PembantuInorder(simpul.SimpulKanan)

    End Sub ' PembantuInorder

    ' memulai penjelajahan postorder
    Public Sub PenjelajahanPostorder()

        SyncLock (Me)
            PembantuPostorder(akar)
        End SyncLock

    End Sub ' PostorderTraversal

    ' metode rekursif untuk melakukan penjelajahan postorder
    Private Sub PembantuPostorder(ByVal simpul As CSimpulPohon)

        If simpul Is Nothing Then
            Return
        End If

        ' menjelajah subpohon kiri
        PembantuPostorder(simpul.SimpulKiri)

        ' menjelajah subpohon kanan
        PembantuPostorder(simpul.SimpulKanan)

        ' menampilkan data simpul
        Console.Write(Convert.ToString(simpul.Data) & " ")

    End Sub ' PembantuPostorder

End Class ' CPohon


Module modUjiPohon2 (kode 15.17) menciptakan tiga objek CPohon untuk menyimpan nilai-nilai Integer, Double, dan String, yang semuanya didefinisikan Visual Basic .NET sebagai tipe IComparable. Program mengisi pohon dari nilai-nilai pada array arrayInteger (baris 11), arrayDouble (baris 12-13), dan arrayString (baris 15-16), dan kemudian memanggil metode PenjelajahanPohon untuk menampilkan penjelajahan preorder, inorder, dan postorder atas pohon CPohon. Metode IsiPohon (baris 36-47) menerima sebagai argumen sebuah Array yang memuat nilai-nilai penginisialisasi untuk CPohon, sebuah CPohon yang akan diisi oleh elemen-elemen array, dan sebuah String yang merepresentasikan nama CPohon. Metode IsiTipe kemudian menyisipkan setiap elemen Array ke dalam CPohon.

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
' Kode 15.17: UjiPohon2.vb
' Program ini menguji kelas CPohon.

' menciptakan tiga objek CPohon untuk menyimpan
' nilai-nilai Integer, Double, dan String

Module CUjiPohon2

    ' menguji kelas CPohon.
    Sub Main()
        Dim arrayInteger As Integer() = {8, 2, 4, 3, 1, 7, 5, 6}
        Dim arrayDouble As Double() = _
         {8.8, 2.2, 4.4, 3.3, 1.1, 7.7, 5.5, 6.6}

        Dim arrayString As String() = {"delapan", "dua", "empat", _
        "tiga", "satu", "tujuh", "lima", "enam"}

        ' menciptakan pohon Integer
        Dim pohonInteger As CPohon = New CPohon()
        IsiPohon(arrayInteger, pohonInteger, "pohonInteger")
        PenjelajahanPohon(pohonInteger, "pohonInteger")

        ' menciptakan pohon Double
        Dim pohonDouble As CPohon = New CPohon()
        IsiPohon(arrayDouble, pohonDouble, "pohonDouble")
        PenjelajahanPohon(pohonDouble, "pohonDouble")

        ' menciptakan pohon String
        Dim pohonString As CPohon = New CPohon()
        IsiPohon(arrayString, pohonString, "pohonString")
        PenjelajahanPohon(pohonString, "pohonString")

    End Sub ' Main

    ' mengisi pohon dengan elemen-elemen array
    Public Sub IsiPohon(ByVal array As Array, _
    ByVal pohon As CPohon, ByVal nama As String)

        Dim data As IComparable
        Console.WriteLine(vbCrLf & "Disisipkan ke dalam " & nama & ":")

        For Each data In array
            Console.Write(Convert.ToString(data) & " ")
            pohon.SisipSimpul(data)
        Next

    End Sub ' IsiPohon

    ' melakukan penjelajahan
    Public Sub PenjelajahanPohon(ByVal pohon As CPohon, _
    ByVal tipePohon As String)

        ' melakukan penjelajahan preorder atas pohon
        Console.WriteLine(vbCrLf & vbCrLf & _
        "Penjelajahan Preorder atas " & tipePohon)

        pohon.PenjelajahanPreorder()

        ' melakukan penjelajahan inorder atas pohon
        Console.WriteLine(vbCrLf & vbCrLf & _
        "Penjelajahan Inorder atas " & tipePohon)

        pohon.PenjelajahanInorder()

        ' melakukan penjelajahan postorder atas pohon
        Console.WriteLine(vbCrLf & vbCrLf & _
        "Penjelajahan Postorder atas " & tipePohon)

        pohon.PenjelajahanPostorder()

        Console.WriteLine(vbCrLf)
    End Sub ' PenjelajahanPohon

End Module ' CUjiPohon2

Disisipkan ke dalam pohonInteger:
8 2 4 3 1 7 5 6

Penjelajahan Preorder atas pohonInteger
8 2 4 3 1 7 5 6

Penjelajahan Inorder atas pohonInteger
6 5 7 1 3 4 2 8

Penjelajahan Postorder atas pohonInteger
6 5 7 1 3 4 2 8

Disisipkan ke dalam pohonDouble:
8.8 2.2 4.4 3.3 1.1 7.7 5.5 6.6

Penjelajahan Preorder atas pohonDouble
8.8 2.2 4.4 3.3 1.1 7.7 5.5 6.6

Penjelajahan Inorder atas pohonDouble
6.6 5.5 7.7 1.1 3.3 4.4 2.2 8.8

Penjelajahan Postorder atas pohonDouble
6.6 5.5 7.7 1.1 3.3 4.4 2.2 8.8

Disisipkan ke dalam pohonString:
delapan dua empat tiga satu tujuh lima enam

Penjelajahan Preorder atas pohonString
delapan dua empat tiga satu tujuh lima enam

Penjelajahan Inorder atas pohonString
enam lima tujuh satu tiga empat dua delapan

Penjelajahan Postorder atas pohonString
enam lima tujuh satu tiga empat dua delapan

Kelas-Kelas Koleksi
Dengan kelas-kelas koleksi, daripada harus menciptakan struktur data sendiri, programer dapat menggunakan struktur data yang ada tanpa perlu khawatir tentang bagaimana struktur data diimplementasikan. Metodologi ini merepresentasikan beberapa contoh pendaur-ulangan kode. Programer dapat mengkode lebih cepat dan dengan kinerja yang lebih baik dalam hal kecepatan eksekusi dan konsumsi memori.

Visual Basic .NET menyediakan beberapa koleksi. Akan didemonstrasikan empat kelas koleksi, yaitu Array, ArrayList, Stack, dan Hashtable. Namespace System.Collections juga menyediakan beberapa struktur data yang lain, termasuk BitArray, Queue, dan SortedList.


Kelas Array
Telah disebutkan bahwa semua array mewarisi kelas Array (namespace System), yang mende-finisikan properti Length yang menspesifikasi jumlah elemen di dalam array. Di samping itu, kelas Array juga menyediakan beberapa metode Shared yang mendefinisikan beberapa algoritma untuk memproses array. Semua metode kelas Array tersebut dioverload untuk memberikan opsi untuk merealisasikan algoritma. Sebagai contoh, metode Reverse dari kelas Array dapat membalikkan urutan elemen-elemen di dalam array secara keseluruhan atau dapat membalikkan elemen-elemen di dalam rentang tertentu pada array. Kode 15.18 mendemonstrasikan beberapa metode Shared dari kelas Array.

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
' Kode 15.18: MenggunakanArray.vb
' Menggunakan kelas Array untuk melakukan beberapa manipulasi array.

Imports System.Windows.Forms
Imports System.Collections

' demonstrasi beberapa algoritma kelas Array
Public Class CMenggunakanArray
    Private nilaiInteger As Integer() = {1, 2, 3, 4, 5, 6}
    Private nilaiDouble As Double() = _
        {8.4, 9.3, 0.2, 7.9, 3.4}

    Private salinNilaiInteger(6) As Integer
    Private keluaran As String

    ' membangun dan menampilkan keluaran program
    Public Sub Awal()
        Dim hasil As Integer

        keluaran = "Nilai-nilai awal array:" & vbCrLf
        TampilArray() ' menampilkan isi awal array

        ' mengurutkan nilaiDouble
        Array.Sort(nilaiDouble)

        ' menyalin nilaiInteger ke salinNilaiInteger
        Array.Copy(nilaiInteger, salinNilaiInteger, _
            nilaiInteger.Length)

        keluaran &= vbCrLf & vbCrLf & _
        "Nilai-nilai Array setelah Sort dan Copy:" & vbCrLf

        TampilArray() ' menampilkan isi array
        keluaran &= vbCrLf & vbCrLf

        ' mencari nilai 5 di dalam nilaiInteger
        hasil = Array.BinarySearch(nilaiInteger, 5)

        If hasil >= 0 Then
            keluaran &= "5 ditemukan pada elemen " & hasil & _
            " di dalam nilaiInteger"
        Else
            keluaran &= "5 tidak ditemukan" & " di dalam nilaiInteger"
        End If

        keluaran &= vbCrLf

        ' mencari nilai 8763 di dalam nilaiInteger
        hasil = Array.BinarySearch(nilaiInteger, 8763)

        If hasil >= 0 Then
            keluaran &= "8763 ditemukan pada elemen " & _
             hasil & " di dalam nilaiInteger"
        Else
            keluaran &= "8763 tidak ditemukan" & " di dalam nilaiInteger"
        End If

        MessageBox.Show(keluaran, "Menggunakan Kelas Array", _
            MessageBoxButtons.OK, MessageBoxIcon.Information)

    End Sub ' Awal

    ' menampilkan keluaran
    Private Sub TampilArray()
        Dim elemenDouble As Double
        Dim elemenInteger As Integer

        keluaran &= "nilaiDouble: "

        ' menampilkan setiap elemen di dalam array nilaiDouble
        For Each elemenDouble In nilaiDouble
            keluaran &= elemenDouble & " "
        Next

        keluaran &= vbCrLf & " nilaiInteger: "

        ' menampilkan setiap elemen di dalam array nilaiInteger
        For Each elemenInteger In nilaiInteger
            keluaran &= elemenInteger & " "
        Next

        keluaran &= vbCrLf & " salinNilaiInteger: "

        ' menampilkan setiap elemen array salinNilaiInteger
        For Each elemenInteger In salinNilaiInteger
            keluaran &= elemenInteger & " "
        Next

    End Sub ' TampilArray

    ' entri utama untuk aplikasi
    Shared Sub Main()
        Dim aplikasi As CMenggunakanArray = New CMenggunakanArray()
        aplikasi.Awal()
    End Sub ' Main

End Class ' CMenggunakanArray



Gambar 15.9 Keluaran program pada kode 15.18


Baris 24 menggunakan metode Shared Array, Sort, untuk mengurutkan sebuah array yang memuat nilai-nilai Double. Ketika metode ini selesai dieksekusi, array yang memuat elemen-elemen terurut secara menaik dijadikan nilai balik.

Baris 27-28 menggunakan metode Shared Array, Copy, untuk menyalin setiap elemen array arrayInteger ke dalam array salinArrayInteger. Argumen pertama adalah array yang akan disalin (nilaiInteger), argumen kedua adalah array tujuan penyalinan (salinNilaiInteger), dan argumen ketiga adalah sebuah integer yang merepresentasikan jumlah elemen yang akan disalin (pada kasus ini, properti nilaiInteger.Length menspesifikasi semua elemen akan disalin).

Baris 37 dan 49 memanggil metode Shared Array, BinarySearch, untuk melakukan pencarian biner terhadap array nilaiInteger. Metode BinarySearch menerima array terurut sebagai lokasi pencarian dan kunci untuk dicari. Metode ini menghasilkan indeks di dalam array, dimana di lokasi tersebut ia menemukan kunci yang dicari, atau jika kunci tidak ditemukan, maka metode menghasilkan nilai negatif.


Kelas ArrayList
Koleksi ArrayList pada Visual Basic (namespace System.Collections) menyerupai fungsionalitas array konvensional dan menyediakan kapabilitas pengubahan-ukuran dinamis. Sebuah ArrayList memuat sejumlah elemen, yang kurang dari atau sama dengan kapasitasnya. Jumlah elemen Program dapat memanipulasi kapasitas dengan properti Capacity pada ArrayList. Jika kapasitas  ArrayList perlu diperbesar, maka secara default ia akan menggandakan kapasitasnya.

ArrayList mereferensi Object. Semua kelas diderivasi dari kelas Object, jadi ArrayList dapat memuat objek-objek sembarang tipe. Gambar 15.10 mencantumkan beberapa metode penting dari kelas ArrayList. Kode 15.19 mendemonstrasikan kelas ArrayList dan beberapa metodenya. Pengguna dapat mengentrikan sebuah String ke dalam TextBox dan kemudian menekan sebuah tombol yang merepresentasikan suatu metode ArrayList untuk melihat fungsionalitas metode. TextBox menampilkan pesan yang mengindikasikan hasil tiap operasi.

Metode
Deskripsi
Add



Clear

Contains


IndexOf


Insert

Remove

RemoveAt

RemoveRange


Sort

TrimToSize
Menambahkan sebuah Object ke dalam ArrayList. Menghasilkan sebuah Integer yang menspesifikasi indeks dimana Object tersebut ditambahkan.

Menghapus semua elemen dari ArrayList.

Menghasilkan True jika Object yang dispesifikasi berada di dalam ArrayList; sebaliknya, menghasilkan False.

Menghasilkan indeks dari kemunculan pertama Object yang dispesifikasi di dalam ArrayList.

Menyisipkan sebuah Object pada indeks yang dispesifikasi.

Menghapus kemuculan pertama dari Object yang dispesifikasi.

Menghapus sebuah Object pada indeks yang dispesifikasi.

Menghapus sejumlah elemen tertentu berawal dari indeks yang dispesifikasi di dalam ArrayList.

Mengurutkan ArrayList.

Menetapkan Capacity dari ArrayList menjadi jumlah elemen yang sekarang dimuat di dalam ArrayList.

Gambar 15.10 Beberapa metode ArrayList


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
' Kode 15.19: UjiArrayList.vb
' Demonstrasi fungsionalitas kelas ArrayList.

Imports System.Collections
Imports System.Text
Imports System.Windows.Forms

Public Class FrmArrayList
    Inherits Form

    ' Tombol untuk memanggil fungsionalitas ArrayList
    Friend WithEvents cmdTambahkan As Button
    Friend WithEvents cmdHapus As Button
    Friend WithEvents cmdPertama As Button
    Friend WithEvents cmdAkhir As Button
    Friend WithEvents cmdApaKosong As Button
    Friend WithEvents cmdMemuat As Button
    Friend WithEvents cmdLokasi As Button
    Friend WithEvents cmdPotong As Button
    Friend WithEvents cmdStatistik As Button
    Friend WithEvents cmdTampilkan As Button

    ' TextBox untuk masukan pengguna
    Friend WithEvents txtMasukan As TextBox
    Friend WithEvents lblMasukan As Label

    Friend WithEvents txtKonsol As TextBox ' TextBox untuk keluaran

    ' Visual Studio .NET generated code

    ' ArrayList untuk memanipulasi String
    Private arrayList As ArrayList = New ArrayList(1)

    ' menambahkan item ke akhir arrayList
    Private Sub cmdTambahkan_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdTambahkan.Click

        arrayList.Add(txtMasukan.Text)
        txtKonsol.Text = "Ditambahkan ke akhir: " & txtMasukan.Text
        txtMasukan.Clear()
    End Sub  ' cmdTambahkan_Click

    'menghapus item yang dispesifikasi dari arrayList
    Private Sub cmdHapus_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdHapus.Click

        arrayList.Remove(txtMasukan.Text)
        txtKonsol.Text = "Dihapus: " & txtMasukan.Text
        txtMasukan.Clear()
    End Sub  ' cmdHapus_Click

    ' menampilkan elemen pertama
    Private Sub cmdPertama_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdPertama.Click

        ' mendapatkan elemen pertama
        Try
            txtKonsol.Text = "Elemen pertama: " & arrayList(0)

            ' menampilkan eksepsi jika tidak ada elemen di dalam arrayList
        Catch diluarRentang As ArgumentOutOfRangeException
            txtKonsol.Text = diluarRentang.ToString()
        End Try

    End Sub  ' cmdPertama_Click

    ' menampilkan elemen terakhir
    Private Sub cmdAkhir_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdAkhir.Click

        ' mendapatkan elemen terakhir
        Try
            txtKonsol.Text = "Elemen terakhir: " & _
            arrayList(arrayList.Count - 1)

            ' menampilkan eksepsi jika tidak ada elemen di dalam arrayList
        Catch diluarRentang As ArgumentOutOfRangeException
            txtKonsol.Text = diluarRentang.ToString()
        End Try

    End Sub  ' cmdAkhir_Click

    ' menentukan apakah arrayList kosong atau tidak
    Private Sub cmdApaKosong_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdApaKosong.Click

        If arrayList.Count = 0 Then
            txtKonsol.Text = "arrayList kosong"
        Else
            txtKonsol.Text = "arrayList tidak kosong"
        End If

    End Sub  ' cmdApaKosong_Click

    ' menentukan apakah arrayList memuat objek yang dispesifikasi
    Private Sub cmdMemuat_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdMemuat.Click

        If arrayList.Contains(txtMasukan.Text) Then
            txtKonsol.Text = "arrayList memuat " & _
            txtMasukan.Text()
        Else
            txtKonsol.Text = txtMasukan.Text & " tidak ditemukan"
        End If

    End Sub  ' cmdMemuat_Click

    ' menentukan lokasi dari objek yang dispesifikasi
    Private Sub cmdLokasi_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdLokasi.Click

        txtKonsol.Text = "Elemen berada pada lokasi " & _
            arrayList.IndexOf(txtMasukan.Text)
    End Sub  ' cmdLokasi_Click

    ' memotong arrayList menjadi ukuran sekarang
    Private Sub cmdPotong_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdPotong.Click

        arrayList.TrimToSize()
        txtKonsol.Text = "Vektor dipotong menjadi ukuran"
    End Sub  ' cmdPotong_Click

    ' menampilkan ukuran dan kapasitas sekarang dari arrayList
    Private Sub cmdStatistik_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdStatistik.Click

        txtKonsol.Text = "Ukuran = " & arrayList.Count & _
            "; kapasitas = " & arrayList.Capacity
    End Sub  ' cmdStatistik_Click

    ' menampilkan isi arrayList
    Private Sub cmdTampilkan_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdTampilkan.Click

        Dim enumerator As IEnumerator = arrayList.GetEnumerator()
        Dim buffer As StringBuilder = New StringBuilder()

        While enumerator.MoveNext()
            buffer.Append(enumerator.Current & " ")
        End While

        txtKonsol.Text = buffer.ToString()
    End Sub  ' cmdTampilkan_Click

End Class  ' FrmArrayList

ArrayList pada contoh ini menyimpan beberapa String yang dimasukkan pengguna di dalam TextBox. Baris 32 menciptakan sebuah ArrayList dengan kapasitas awal satu elemen. ArrayList ini akan menggandakan ukurannya setiap kali pengguna mengisi array dan mencoba untuk menambahkan satu elemen lain.

Metode Add pada kelas ArrayList menyambungkan sebuah elemen ke akhir sebuah ArrayList. Ketika pengguna mengklik Tambahkan, event handler cmdTambahkan_Click (baris 35-41) memanggil metode Add (baris 38) untuk menyambung String di dalam TextBox ke dalam ArrayList.



Gambar 15.11  Keluaran program pada kode 15.19


Kelas Stack
Kelas Stack (namespace System.Collections) mengimplementasikan struktur data tumpukan. Aplikasi pada kode 15.10 menyediakan sebuah GUI yang memampukan pengguna untuk menguji beberapa metode kelas Stack. Baris 31 pada konstruktor FrmUjiStack menciptakan sebuah Stack dengan kapasitas awal default (10 elemen).

Kelas Stack menyediakan metode Push dan Pop untuk melakukan beberapa operasi tumpukan dasar. Metode Push mengambil sebuah Object sebagai argumen dan menambahkannya ke atas Stack. Event handler cmdPush_Click (baris 37-42) menggunakan metode Push untuk menambahkan sebuah string yang dimasukkan pengguna ke atas tumpukan.

Metode Pop tidak memerlukan argumen. Metode ini menghapus dan menghasilkan objek yang sekarang berada di atas Stack. Event handler cmdPop_Click (baris 45-57) memanggil metode Pop (baris 50) untuk menghapus sebuah objek dari Stack. Eksepsi InvalidOperatioException akan terjadi jika Stack kosong ketika program memanggil Pop.

Metode Peek menghasilkan nilai dari elemen di atas tumpukan, tetapi tidak menghapus elemen dari Stack. Akan didemonstrasikan Peek pada baris 65 pada event handler cmdPeek_Click (baris 60-72) untuk menengok objek di atas Stack. Sama seperti Pop, Eksepsi InvalidOperatioException akan terjadi jika Stack kosong ketika program memanggil Peek.

Event handler cmdApaKosong_Click (baris 75-84) menentukan apakah Stack kosong dengan membandingkan properti Count pada Stack dengan nol. Jika nol, Stack kosong; sebaliknya, Stack tidak kosong. Event handler cmdCari_Click (baris 87-96) menggunakan metode Contains (baris 90) untuk menentukan apakah Stack memuat objek yang dispesifikasi sebagai argumennya atau tidak. Contains menghasilkan True jika Stack memuat objek yang dispesifikasi dan False jika sebaliknya.

Event handler cmdTampil_Click (baris 99-110) menggunakan sebuah IEnumerator untuk menjelajah Stack dan menampilkan isinya.

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
' Kode 15.10: UjiStack.vb
' Demonstrasi fungsionalitas kelas Stack.

Imports System.Collections
Imports System.Text
Imports System.Windows.Forms

Public Class FrmUjiStack
    Inherits Form

    ' Tombol untuk memanggil fungsionalitas Stack
    Friend WithEvents cmdPush As Button
    Friend WithEvents cmdPop As Button
    Friend WithEvents cmdPeek As Button
    Friend WithEvents cmdApaKosong As Button
    Friend WithEvents cmdCari As Button
    Friend WithEvents cmdTampil As Button

    ' TextBox menerima masukan dari pengguna
    Friend WithEvents txtMasukan As TextBox
    Friend WithEvents lblStatus As Label
    Friend WithEvents lblMasukan As Label

    Private tumpukan As Stack

    Public Sub New()
        MyBase.New()

        InitializeComponent()

        tumpukan = New Stack() ' menciptakan stack
    End Sub ' New

    ' kode yang dibangkitkan oleh Visual Studio .NET

    ' menempatkan elemen ke atas tumpukan
    Private Sub cmdPush_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdPush.Click

        tumpukan.Push(txtMasukan.Text)
        lblStatus.Text = "Ditempatkan ke atas tumpukan: " & txtMasukan.Text
    End Sub  ' cmdPush_Click

    ' menghapus elemen dari tumpukan
    Private Sub cmdPop_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdPop.Click

        ' menghapus elemen
        Try
            lblStatus.Text = "Dihapus dari tumpukan: " & tumpukan.Pop()

            ' menampilkan pesan jika tumpukan kosong
        Catch invalidOperation As InvalidOperationException
            lblStatus.Text = invalidOperation.ToString()
        End Try

    End Sub  ' cmdPop_Click

    ' mengintip ke elemen teratas tumpukan
    Private Sub cmdPeek_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdPeek.Click

        ' menengok elemen atas
        Try
            lblStatus.Text = "Elemen teratas tumpukan: " & tumpukan.Peek()

            ' menampilkan pesan jika tumpukan kosong
        Catch invalidOperation As InvalidOperationException
            lblStatus.Text = invalidOperation.ToString()
        End Try

    End Sub  ' cmdPeek_Click

    ' menentukan apakah tumpukan kosong atau tidak
    Private Sub cmdApaKosong_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdApaKosong.Click

        If tumpukan.Count = 0 Then
            lblStatus.Text = "Tumpukan kosong"
        Else
            lblStatus.Text = "Tumpukan tidak kosong"
        End If

    End Sub  ' cmdApaKosong_Click

    ' menentukan apakah elemen yang dispesifikasi berada pada tumpukan atau tidak
    Private Sub cmdCari_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdCari.Click

        If tumpukan.Contains(txtMasukan.Text) Then
            lblStatus.Text = txtMasukan.Text & " ditemukan"
        Else
            lblStatus.Text = txtMasukan.Text & " tidak ditemukan"
        End If

    End Sub  ' cmdCari_Click

    ' menampilkan isi tumpukan
    Private Sub cmdTampil_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdTampil.Click

        Dim enumerator As IEnumerator = tumpukan.GetEnumerator()
        Dim buffer As StringBuilder = New StringBuilder()

        While enumerator.MoveNext()
            buffer.Append(enumerator.Current & " ")
        End While

        lblStatus.Text = buffer.ToString()
    End Sub  ' cmdTampil_Click

End Class  ' FrmUjiStack



Gambar 15.12  Keluaran program pada kode 15.20


Kelas Hashtable
Sebuah fungsi hash melakukan perhitungan yang dapat dipakai untuk menentukan dimana menempatkan data di dalam hashtable. Fungsi hash diterapkan terhadap sepasang objek kunci/nilai. Kelas Hashtable dapat menerima sembarang objek sebagai kunci. Karena alasan ini, kelas Object mendefinisikan metode GetHashCode, yang diwarisi oleh semua objek Visual Basic. Kode 15.21 mendemonstrasikan beberapa metode dari kelas Hashtable.

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
' Kode 15.21: FrmUjiHashtable.vb
' Demonstrasi fungsionalitas kelas Hashtable.

Imports System.Collections
Imports System.Text
Imports System.Windows.Forms

Public Class FrmUjiHashtable
    Inherits Form

    ' Tombol untuk memanggil fungsionalitas Hashtable
    Friend WithEvents cmdTambah As Button
    Friend WithEvents cmdDapatkan As Button
    Friend WithEvents cmdHapus As Button
    Friend WithEvents cmdKosong As Button
    Friend WithEvents cmdMemuat As Button
    Friend WithEvents cmdBersihkan As Button
    Friend WithEvents cmdDaftarObjek As Button
    Friend WithEvents cmdDaftarKunci As Button

    ' TextBox untuk memasukan data hashtable
    Friend WithEvents txtPertama As TextBox
    Friend WithEvents txtAkhir As TextBox
    Friend WithEvents txtKonsol As TextBox

    Friend WithEvents lblPertama As Label
    Friend WithEvents lblAkhir As Label
    Friend WithEvents lblStatus As Label

    Private tabel As Hashtable

    Public Sub New()
        MyBase.New()

        'pemanggilan ini diperlukan oleh Windows Form Designer.
        InitializeComponent()

        tabel = New Hashtable() ' menciptakan objek Hashtable
    End Sub ' New

    ' kode yang dibangkitkan oleh Visual Studio .NET

    ' menambahkan nama akhir dan objek CKaryawan ke dalam tabel
    Private Sub cmdTambah_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdTambah.Click

        Dim karyawan As New CKaryawan(txtPertama.Text, txtAkhir.Text)

        ' menambahkan pasangan kunci/nilai yang baru
        Try
            tabel.Add(txtAkhir.Text, karyawan)
            lblStatus.Text = "Menempatkan: " & karyawan.ToString()

            ' jika kunci tidak ada, lempar eksepsi
        Catch argumentException As ArgumentException
            lblStatus.Text = argumentException.ToString()
        End Try

    End Sub  ' cmdTambah_Click

    ' mendapatkan objek untuk kunci yang dispesifikasi
    Private Sub cmdDapatkan_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdDapatkan.Click

        Dim hasil As Object = tabel(txtAkhir.Text)

        If Not hasil Is Nothing Then
            lblStatus.Text = "Didapatkan: " & hasil.ToString()
        Else
            lblStatus.Text = "Didapatkan: " & txtAkhir.Text & " tidak ada di dalam tabel"
        End If

    End Sub  ' cmdDapatkan_Click

    ' menghapus pasangan kunci/nilai dari tabel
    Private Sub cmdHapus_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdHapus.Click

        tabel.Remove(txtAkhir.Text)
        lblStatus.Text = "Objek dihapus"
    End Sub  ' cmdHapus_Click

    ' menentukan apakah tabel kosong
    Private Sub cmdKosong_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdKosong.Click

        lblStatus.Text = "Tabel "

        If tabel.Count = 0 Then
            lblStatus.Text &= "kosong"
        Else
            lblStatus.Text &= "tidak kosong"
        End If

    End Sub  ' cmdKosong_Click

    ' menentukan apakah tabel memuat kunci yang dispesifikasi
    Private Sub cmdMemuat_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdMemuat.Click

        lblStatus.Text = "Memuat kunci: " & _
            tabel.ContainsKey(txtAkhir.Text)
    End Sub  ' cmdMemuat_Click

    ' membuang semua isi tabel
    Private Sub cmdBersihkan_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdBersihkan.Click

        tabel.Clear()
        lblStatus.Text = "Dibersihkan: Tabel sekarang kosong"
    End Sub  ' cmdBersihkan_Click

    ' menampilkan semua objek di dalam tabel
    Private Sub cmdDaftarObjek_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) _
        Handles cmdDaftarObjek.Click

        Dim enumerator As IDictionaryEnumerator = _
            tabel.GetEnumerator()

        Dim buffer As StringBuilder = New StringBuilder()

        While enumerator.MoveNext()
            buffer.Append(Convert.ToString(enumerator.Value) & _
            vbCrLf)
        End While

        txtKonsol.Text = buffer.ToString()
    End Sub  ' cmdDaftarObjek_Click

    ' menampilkan semua kunci di dalam tabel
    Private Sub cmdDaftarKunci_Click(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles cmdDaftarKunci.Click

        Dim enumerator As IDictionaryEnumerator = _
            tabel.GetEnumerator()

        Dim buffer As StringBuilder = New StringBuilder()

        While enumerator.MoveNext()
            buffer.Append(enumerator.Key & vbCrLf)
        End While

        txtKonsol.Text = buffer.ToString()
    End Sub  ' cmdDaftarKunci_Click

End Class  ' FrmUjiHashtable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
' Kode 15.22: Karyawan.vb
' Kelas CKarywan untuk digunakan pada HashTable.

Public Class CKaryawan
    Private namaPertama, namaAkhir As String

    Public Sub New(ByVal pertama As String, ByVal akhir As String)
        namaPertama = pertama
        namaAkhir = akhir
    End Sub ' New

    ' menghasilkan nama pertama dan nama akhir Karyawan sebagai String
    Public Overrides Function ToString() As String
        Return namaPertama & " " & namaAkhir
    End Function ' ToString

End Class ' CKaryawan

  


Gambar 15.13  Keluaran program pada kode 15.21


Latihan
1.       Tulislah sebuah program yang menggabungkan dua daftar objek integer terurut menjadi satu daftar objek integer terurut. Metode Merge dari kelas ListMerge harus menerima referensi dari tiap daftar objek untuk digabungkan dan harus menghasilkan sebuah referensi yang menunjuk ke daftar objek hasil penggabungan.


2.       Tulislah sebuah program yang membaca sebaris teks dan kemudian menggunakan sebuah objek tumpukan untuk menampilkan baris teks tersebut secara terbalik.


Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)