Bab. 10 Struktur Data
|
Tujuan
Instruksional
|
|
|
·
Struktur
referensi-diri.
·
Alokasi memori
dinamis.
·
Senarai berantai.
|
·
Tumpukan.
·
Antrian.
·
Pohon.
|
10.1 Struktur Referensi-Diri
Struktur referensi diri memuat sebuah
anggota pointer yang menunjuk ke suatu struktur bertipe sama. Sebagai contoh, definisi
struct simpul {
int data;
struct
simpul *berikutPtr;
};
mendefinisikan sebuah tipe, struct simpul. Sebuah struktur bertipe struct simpul mempunyai dua anggota, yaitu anggota
integer data dan anggota pointer berikutPtr. Anggota berikutPtr menunjuk ke suatu struktur bertipe struct simpul, sebuah struktur bertipe sama dengan yang sedang
dideklarasikan. Anggota berikutPtr dikenal dengan link atau rantai dan berikutPtr dapat digunakan untuk mengikat suatu
struktur bertipe struct simpul dengan struktur
lain bertipe sama. Struktur referensi-diri dapat dihubungkan untuk membentuk
beberapa struktur data seperti senarai, antrian, tumpukan, dan pohon. Gambar
10.1 mengilustrasikan dua objek struktur referensi-diri yang dirantai atau
dihubungkan bersama untuk membentuk sebuah senarai. Tand slash (\), yang
merepresentasikan sebuah pointer NULL, ditempatkan pada struktur referensi-diri
yang kedua untuk mengindikasikan bahwa rantai tidak menunjuk ke struktur
lainnya. Sebuah pointer NULL biasanya mengindikasikan akhir suatu struktur data
sama seperti karakter null yang mengindikasikan akhir suatu string.
Gambar 10.1 | Dua struktur referensi-diri yang
dirantai bersama
10.2 Alokasi Memori Dinamis
Penciptaan struktur data dinamis
memerlukan alokasi memori dinamis, dimana program mampu untuk mendapatkan
memori tambahan pada waktu eksekusi untuk menampung semua simpul baru dan untuk
membebaskan memori yang tidak lagi diperlukan. Batas untuk alokasi memori
dinamis adalah sebesar memori fisik yang tersedia di dalam komputer atau
sebesar memori virtual yang tersedia di dalam sistem memori virtual. Tetapi,
seringkali bahwa batas memori dinamis jauh lebih kecil karena memori harus
dibagi dengan banyak aplikasi lainnya.
Fungsi malloc dan free, dan operator sizeof
esensial bagi alokasi memori dinamis. Fungsi malloc mengambil jumlah byte yang akan dialokasikan sebagai argumen dan
menghasilkan nilai balik berupa sebuah pointer bertipe void * (pointer ke void) yang menunjuk ke memori teralokasi. Pointer void * dapat ditugasi variabel bertipe
pointer sembarang. Fungsi malloc normalnya
dipakai dengan operator sizeof. Sebagai
contoh, statemen
baruPtr = malloc( sizeof( struct simpul ) );
mengevaluasi sizeof(struct simpul) untuk menentukan ukuran dalam byte
dari sebuah struktur bertipe struct simpul, mengalokasikan
area baru di dalam memori sejumlah byte tersebut, dan menyimpan sebuah pointer
yang menunjuk ke memori teralokasi dalam variabel baruPtr. Memori teralokasi tidak diinisialisasi. Jika tidak ada memori yang
tersedia, malloc akan menghasilkan NULL.
Fungsi free membebaskan memori, yaitu memori dikembalikan kepada sistem sehingga
memori tersebut dapat dialokasikan-ulang pada masa datang. Untuk membebaskan
memori yang dialokasikan secara dinamis menggunakan malloc, digunakan statemen
free( baruPtr
);
C juga menyediakan fungsi calloc dan realloc untuk menciptakan dan memodifikasi array secara dinamis. Pada beberapa
bagian ke depan akan didiskusikan senarai berantai, tumpukan, antrian, dan
pohon, yang masing-masing diciptakan dengan alokasi memori dinamis dan struktur
referensi-diri.
10.3 Senarai Berantai
Senarai berantai adalah koleksi linier
atas beberapa struktur referensi-diri, yang dinamakan simpul, terhubung oleh
rantai-rantai pointer. Senarai berantai diakses dengan sebuah pointer yang
menunjuk ke simpul pertama di dalam senarai. Simpul-simpul diakses lewat
anggota pointer rantai yang disimpan di akhir senarai. Data disimpan secara
dinamis di dalam senarai berantai, dimana setiap simpul diciptakan jika
diperlukan. Sebuah simpul dapat memuat sembarang tipe termasuk objek-objek struct. Tumpukan dan antrian juga merupakan
struktur data linier, dan, seperti yang akan Anda lihat, merupakan versi
terkekang dari senarai berantai. Pohon adalah struktur data tak-linier.
Runtun data dapat disimpan di dalam
array, tetapi senarai berantai memberikan beberapa keuntungan. Senarai berantai
cocok dipakai bila jumlah elemen data yang akan direpresentasikan di dalam
struktur data tidak terprediksi. Senarai berantai bersifat dinamis, jadi
panjang suatu senarai dapat bertambah atau berkurang jika diperlukan.
Sebaliknya, ukuran suatu array tidak dapat diubah setelah memori dialokasikan.
Array dapat menjadi penuh. Senarai berantai menjadi penuh hanya jika sistem
tidak mempunyai memori yang cukup untuk memenuhi permintaan alokasi penyimpanan
dinamis.
Senarai berantai dapat dikembangkan
dengan tatanan terurut dengan menyisipkan setiap elemen baru pada titik sesuai
di dalam senarai.
Simpul-simpul senarai berantai
normalnya tidak disimpan secara bertetangga di dalam memori. Gamabr 10.12
mengilustrasikan sebuah senarai berantai dengan beberapa simpul.
Gambar 10.2 | Representasi grafikal atas senarai
berantai
Gambar 10.3 (keluaran program
ditampilkan pada Gambar 10.4) memanipulasi suatu runtun karakter. Program
memampukan Anda untuk menyisipkan suatu karakter di dalam senara dengan tatanan
alfabetikal (fungsi sisip) atau untuk
menghapus sebuah karakter dari senarai (fungsi hapus). Program ini termasuk kompleks dan besar. Diskusi detil atas program
akan disajikan setelah kode sumber.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
/* Gambar 10.3: gambar10_03.c
Mengoperasikan dan mengembangkan senarai berantai */
#include <stdio.h>
#include <stdlib.h>
/* struktur referensi-diri */
struct simpulSenarai {
char
data; /* setiap simpulSenarai memuat sebuah karakter */
struct
simpulSenarai *berikutPtr; /* pointer ke simpul berikutnya */
}; /* akhir struktur simpulSenarai */
typedef struct simpulSenarai SimpulSenarai; /* sinonim untuk struct simpulSenarai*/
typedef SimpulSenarai *SimpulSenaraiPtr; /* sinonim untuk SimpulSenarai* */
/* prototipe */
void sisip( SimpulSenaraiPtr *sPtr, char nilai
);
char hapus( SimpulSenaraiPtr *sPtr, char nilai
);
int apaKosong( SimpulSenaraiPtr sPtr );
void tampilSenarai( SimpulSenaraiPtr sekarangPtr );
void instruksi( void );
int main( void )
{
SimpulSenaraiPtr awalPtr = NULL; /* awalnya tidak ada simpul */
int
pilihan; /* pilihan pengguna */
char
item; /* char yang dimasukkan pengguna */
instruksi(); /* menampilkan menu */
printf( "? " );
scanf( "%d", &pilihan );
/*
loop while pengguna tidak memilih 3 */
while
( pilihan != 3 ) {
switch
( pilihan ) {
case
1:
printf( "Masukkan sebuah karakter: " );
scanf( "\n%c", &item );
sisip(
&awalPtr, item ); /* menyisipak item di dalam senarai */
tampilSenarai( awalPtr );
break;
case
2: /* menghapus sebuah elemen */
/* jika senarai tidak kosong */
if ( !apaKosong( awalPtr ) ) {
printf( "Masukkan karakter yang akan dihapus: " );
scanf( "\n%c", &item );
/* jika karakter ditemukan, hapus */
if ( hapus( &awalPtr, item )
) { /* menghapus item */
printf( "%c dihapus.\n", item );
tampilSenarai( awalPtr );
} /* akhir if */
else {
printf( "%c tidak ditemukan.\n\n", item );
} /* akhir else */
}
/* akhir if */
else {
printf( "Senarai kosong.\n\n" );
}
/* akhir else */
break;
default:
printf( "pilihan tidak benar.\n\n" );
instruksi();
break;
}
/* akhir switch */
printf( "? " );
scanf( "%d", &pilihan );
} /*
akhir while */
printf( "Akhir dari program.\n" );
return
0; /* indikasi terminasi sukses */
} /* akhir main */
/* menampilkan instruksi program pada
pengguna */
void instruksi( void )
{
printf( "Masukkan pilihan Anda:\n"
" 1 untuk menyisipkan sebuah elemen ke dalam senarai.\n"
" 2 untuk menghapus sebuah elemen dari senarai.\n"
" 3 untuk mengakhiri.\n" );
} /* akhir fungsi instruksi */
/* menyisipkan
sebuah nilai baru ke dalam senarai dengan tatanan terurut */
void sisip( SimpulSenaraiPtr *sPtr, char nilai
)
{
SimpulSenaraiPtr baruPtr; /* pointer ke simpul baru */
SimpulSenaraiPtr sebelumPtr; /* pointer ke simpul
sebelumnya di dalam senarai */
SimpulSenaraiPtr sekarangPtr; /* pointer ke simpul
sekarang di dalam senarai */
baruPtr = malloc( sizeof(
SimpulSenarai ) ); /* menciptakan simpul */
if
( baruPtr != NULL ) { /* apakah memori tersedia */
baruPtr->data
= nilai; /* menempatkan nilai di dalam simpul */
baruPtr->berikutPtr = NULL; /* simpul tidak terhubung ke
simpul lain */
sebelumPtr = NULL;
sekarangPtr = *sPtr;
/*
loop untuk mencari lokasi tepat di dalam list */
while
( sekarangPtr != NULL && nilai > sekarangPtr->data ) {
sebelumPtr = sekarangPtr; /* berjalan ke ... */
sekarangPtr = sekarangPtr->berikutPtr; /* ... simpul berikut */
}
/* akhir while */
/*
menyisipkan simpul baru di awal senarai */
if ( sebelumPtr == NULL ) {
baruPtr->berikutPtr = *sPtr;
*sPtr = baruPtr;
}
/* akhi if */
else
{ /* menyisipkan simpul baru di antara sebelumPtr dan sekarangPtr */
sebelumPtr->berikutPtr = baruPtr;
baruPtr->berikutPtr = sekarangPtr;
}
/* akhir else */
} /*
akhir if */
else
{
printf( "%c tidak disisipkan. Tidak ada memori tersedia\n",
nilai );
} /*
akhir else */
} /* akhir fungsi sisip */
/* menghapus sebuah elemen senarai */
char hapus( SimpulSenaraiPtr *sPtr, char nilai
)
{
SimpulSenaraiPtr sebelumPtr; /* pointer ke simpul
sebelumnya di dalam senarai */
SimpulSenaraiPtr sekarangPtr; /* pointer ke simpul
sekarang di dalam senarai */
SimpulSenaraiPtr tempPtr; /* pointer simpul sementara */
/*
hapus simpul pertama */
if
( nilai == ( *sPtr )->data ) {
tempPtr = *sPtr; /* menampung simpul yang sedang dihapus */
*sPtr = ( *sPtr )->berikutPtr; /* menhubungkan-ulang simpul */
free(
tempPtr ); /* menghapus simpul yang terputus */
return nilai;
} /*
akhir if */
else
{
sebelumPtr = *sPtr;
sekarangPtr = ( *sPtr )->berikutPtr;
/*
loop untuk mencari lokasi sekarang di dalam senarai */
while
( sekarangPtr != NULL && sekarangPtr->data != nilai ) {
sebelumPtr = sekarangPtr; /* berjalan ke ... */
sekarangPtr = sekarangPtr->berikutPtr; /* ... simpul berikutnya */
}
/* akhir while */
/*
hapus node at sekarangPtr */
if
( sekarangPtr != NULL ) {
tempPtr = sekarangPtr;
sebelumPtr->berikutPtr = sekarangPtr->berikutPtr;
free( tempPtr );
return
nilai;
}
/* akhir if */
} /*
akhir else */
return
'\0';
} /* akhir fungsi sisip */
/* menghasilkan 1 jika senarai kosong,
sebaliknya 0 */
int apaKosong( SimpulSenaraiPtr sPtr )
{
return
sPtr == NULL;
} /* akhir fungsi apaKosong */
/* menampilkan senarai */
void tampilSenarai( SimpulSenaraiPtr sekarangPtr )
{
/*
jika senarai kosong */
if
( sekarangPtr == NULL ) {
printf( "Senarai kosong.\n\n" );
} /*
akhir if */
else
{
printf( "Senarai adalah:\n" );
/*
ketika tidak di ujung senarai */
while
( sekarangPtr != NULL ) {
printf( "%c --> ", sekarangPtr->data );
sekarangPtr = sekarangPtr->berikutPtr;
}
/* akhir while */
printf( "NULL\n\n" );
} /*
akhir else */
} /* akhir fungsi tampilSenarai */
|
Gambar 10.3 | Program
pertama dalam C
Masukkan pilihan Anda:
1 untuk menyisipkan sebuah elemen ke dalam
senarai.
2 untuk menghapus sebuah elemen dari senarai.
3 untuk mengakhiri.
? 1
Masukkan sebuah karakter: B
Senarai adalah:
B --> NULL
? 1
Masukkan sebuah karakter: A
Senarai adalah:
A --> B --> NULL
? C
Masukkan sebuah karakter: Senarai
adalah:
A --> B --> C --> NULL
? 2
Masukkan karakter yang akan dihapus: D
D tidak ditemukan.
? 2
Masukkan karakter yang akan dihapus: B
B dihapus.
Senarai adalah:
A --> C --> NULL
? 2
Masukkan karakter yang akan dihapus: C
C dihapus.
Senarai adalah:
A --> NULL
? 2
Masukkan karakter yang akan dihapus: A
A dihapus.
Senarai kosong.
? 4
pilihan tidak benar.
Masukkan pilihan Anda:
1 untuk menyisipkan sebuah elemen ke dalam
senarai.
2 untuk menghapus sebuah elemen dari senarai.
3 untuk mengakhiri.
? 3
Akhir dari program.
Gambar 10.4 | Keluaran
program pada Gambar 10.3
Dua fungsi utama pada senarai berantai
adalah sisip (baris 86-120) dan hapus (baris 123-156). Fungsi apaKosong (baris 159-162) merupakan sebuah fungsi predikat, yang tidak mengubah
senarai tetapi hanya menentukan apakah senarai kosong atau tidak. Jika senarai
kosong, apaKosong menghasilkan nilai balik 1; sebaliknya
nilai balik 0. Fungsi tampilSenarai (baris 165-182) menampilkan senarai.
Fungsi sisip
Karakter disisipkan ke dalam senarai
dengan urutan alfabetikal. Fungsi sisip (baris 86-120)
menerima alamat senarai dan sebuah karakter yang akan disisipkan. Alamat
senarai diperlukan ketika sebuah nilai akan disisipkan di awal senarai. Dengan
menyediakan alamat senarai, Anda dapat memodifikasi senarai (pointer yang
menunjuk ke simpul pertama di dalam senarai) lewat pemanggilan referensi. Karena
senarai itu sendiri adalah suatu pointer (ke elemen pertamanya), pelewatan
alamat senarai menciptakan sebuah pointer yang menunjuk ke suatu pointer
(indireksi ganda). Hal ini memerlukan teknik pemrograman yang perlu hati-hati.
Beberapa langkah menyisipkan sebuah karakter di dalam senarai adalah sebagai
berikut (lihat Gambar 10.5):
1.
Ciptakan simpul dengan memanggil malloc,
menugaskan alamat memori teralokasi
kepada baruPtr (baris 92),
menugaskan karakter yang akan disisipkan kepada baruPtr->data (baris 95),
dan menugaskan NULL kepada baruPtr->berikutPtr (baris 96).
2.
Inisialisasi sebelumPtr dengan NULL (baris 198)
dan sekarangPtr dengan *sPtr (baris 99),
dimana sPtr adalah pointer
ke awal senarai. Pointer sebelumPtr dan sekarangPtr menyimpan
lokasi simpul sebelum titik penyisipan dan simpul setelah titik penyisipan.
3.
Ketika sekarangPtr tidak NULL dan nilai yang
akan disisipkan lebih besar dari sekarangPtr->data (baris 102), tugaskan
sekarangPtr kepada sebelumPtr (baris 103)
dan tempatkan sekarangPtr ke simpul berikutnya di dalam
senarai (baris 104). Lokasi ini merupakan titik penyisipan bagi nilai yang akan
disisipkan.
4. Jika sebelumPtr adalah NULL (baris 108),
sisipkan simpul baru sebagai simpul pertama di dalam senarai (baris 109-110).
Tugaskan *sPtr kepada baruPtr->berikutPtr (rantai simpul
baru menunjuk ke
bekas simpul pertama) dan menugaskan baruPtr kepada *sPtr (*sPtr menunjuk ke simpul baru). Tugaskan baruPtr kepada sebelumPtr->berikutPtr (simpul sebelumnya menunjuk ke simpul
baru) dan tugaskan sekarangPtr kepada baruPtr->berikutPtr (rantai simpul baru menunjuk ke simpul sekarang).
Gambar 10.5 | Penyisipan sebuah simpul secara
berurutan di dalam senarai berantai
Gambar 10.5 mengilustrasikan penyisipan
sebuah simpul yang memuat karakter ‘c’ ke dalam suatu senarai terurut. Bagian
a) pada gambar tersebut menampilkan senarai dan simpul baru sebelum penyisipan.
Bagian b) pada gambar menunjukkan hasil penyisipan simpul baru. Pointer yang
ditugaskan-ulang ditampilkan dengan garis panah putus-putus. Agar sederhana,
fungsi sisip diimplementasikan dengan tipe nilai
balik void. Adalah hal yang memungkinkan bahwa
fungsi malloc dapat gagal mengalokasikan memori yang
diminta. Pada kasus itu, akan lebih baik jika fungsi sisip menghasilkan nilai balik berupa status yang mengindikasikan
apakah operasi berhasil atau tidak.
Fungsi delete
Fungsi delete (baris 123-156) menerima suatu alamat pointer yang menunjuk ke awal
senarai dan sebuah karakter yang akan dihapus. Langkah-langkah penghapusan
sebuah karakter dari senarai adalah sebagai berikut:
1.
Jika karakter yang akan dihapus cocok dengan
karakter di dalam simpul pertama senarai (baris 130), tugaskan *sPtr kepada tempPtr (tempPtr akan dipakai
untuk membebaskan memori yang tidak dibutuhkan lagi), tugaskan (*sPtr)->berikutPtr
kepada
*sPtr (*sPtr sekarang
menunjuk ke simpul kedua di dalam senarai), bebaskan memori yang ditunjuk oleh tempPtr, dan jadikan
karakter yang terhapus menjadi nilai balik.
2.
Sebaliknya, inisialisasi sebelumPtr dengan *sPtr dan
inisialisasi sekarangPtr dengan (*sPtr)->berikutPtr (baris
137-138).
3.
Ketika sekarangPtr tidak NULL dan nilai yang
akan dihapus tidak sama dengan sekarangPtr->data (baris 141),
tugaskan sekarangPtr kepada sebelumPtr (baris 142),
dan tugaskan sekarangPtr->berikutPtr kepada sekarangPtr (baris 143).
Hal ini melokasikan karakter yang akan dihapus jika karakter tersebut berada di
dalam senarai.
4. Jika sekarangPtr tidak NULL (baris 147),
tugaskan sekarangPtr kepada tempPtr (baris 148),
tugaskan sekarangPtr->berikutPtr kepada sebelumPtr->berikutPtr (baris 149),
bebaskan simpul yang ditunjuk oleh tempPtr (baris 150), dan karakter yang
dihapus dari senarai dijadikan nilai balik (baris 151). Jika sekarangPtr bernilai NULL, karakter null
(‘\0’) dijadikan nilai balik untuk menandakan bahwa karakter yang akan dihapus
tidak ditemukan di dalam senarai (baris 155).
Gambar 10.6 mengilustrasikan
penghapusan suatu simpul dari senarai berantai. Bagian a) pada gambar
menunjukkan senarai berantai setelah operasi penyisipan dilakukan. Bagian b)
menunjukkan penugasan-ulang elemen rantai dari sebelumPtr dan menugaskan sekarangPtr kepada tempPtr. Pointer tempPtr digunakan untuk membebaskan memori yang dialokasikan untuk menyimpan ‘C’.
Gambar 10.6 | Penghapusan sebuah simpul dari
senarai berantai
Fungsi tampil
Fungsi tampilSenarai (baris 165-182) menerima sebuah pointer yang menunjuk ke
awal senarai sebagai argumen. Fungsi ini pertama-tama menentukan apakah senarai
kosong atau tidak (baris 168-170) dan, jika demikian, menampilkan “Senarai
kosong” dan berhenti. Sebaliknya, fungsi ini menampilkan data di dalam senarai
(baris 171-181). Ketika sekarangPtr tidak NULL, nilai sekarangPtr->data ditampilkan oleh fungsi tampilSenarai, dan sekarangPtr->berikutPtr ditugaskan kepada sekarangPtr. Jika rantai pada simpul terakhir
tidak NULL, maka proses untuk menampilkan akan mencoba untuk melampaui akhir
senarai dan error akan terjadi. Algoritma untuk menampilkan identik untuk
senarai berantai, tumpukan, dan antrian.
10.4 Tumpukan
Tumpukan adalah versi terkekang dari
senarai berantai. Simpul-simpul baru dapat ditambahkan di atas tumpukan dan
dihapus dari hanya dari atas tumpukan. Karena alasan ini, tumpukan dikenal
sebagai struktur data LIFO (last-in, first-out). Tumpukan direferensi lewat
pointer yang menunjuk ke elemen atas dari tumpukan. Anggota rantai (link) pada simpul terakhir tumpukan
ditetapkan NULL untuk mengindikasikan bagian terbawah tumpukan.
Gambar 10.7 mengilustrasikan sebuah
tumpukan dengan beberapa simpul. Tumpukan dan senarai berantai
direpresentasikan secara identik. Perbedaan antara tumpukan dan senarai
berantai adalah bahwa penyisipan dan penghapusan dapat terjadi di mana saja di
dalam suatu senarai berantai, tetapi hanya boleh terjadi di atas suatu
tumpukan.
Gambar 10.7 | Representasi grafikal tumpukan
Dua fungsi utama yang digunakan untuk memanipulasi tumpukan adalah taruh (push) dan ambil (pop). Fungsi taruh menciptakan sebuah simpul baru dan menempatkannya di atas tumpukan.
Fungsi ambil menghapus sebuah simpul dari atas
tumpukan, membebaskan memori yang dialokasikan untuk simpul yang ditaruh dan
menghasilkan nilai balik berupa nilai terambil (terhapus) dari simpul.
Gambar 10.8 (keluaran ditampilkan pada Gambar 10.9) mengimplementasikan sebuah
tumpukan integer sederhana. Program menyediakan tiga opsi: 1) menaruh sebuah
nilai ke atas tumpukan (fungsi taruh), 2) mengambil sebuah
nilai dari atas tumpukan (fungsi ambil), dan 3) menghentikan
program.
|
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
|
/* Gambar 10.8: gambar10_08.c
Program tumpukan dinamis */
#include <stdio.h>
#include <stdlib.h>
/* struktur referensi-diri */
struct simpulTumpukan {
int
data; /* mendefinisikan data sebagai sebuah int */
struct
simpulTumpukan *berikutPtr; /* pointer simpulTumpukan */
}; /* akhir struktur simpulTumpukan */
typedef struct simpulTumpukan SimpulTumpukan; /* sinonim untuk struct simpulTumpukan*/
typedef SimpulTumpukan *SimpulTumpukanPtr; /* sinonim untuk SimpulTumpukan* */
/* prototipe */
void taruh( SimpulTumpukanPtr *atasPtr, int
info );
int ambil( SimpulTumpukanPtr *atasPtr );
int apaKosong( SimpulTumpukanPtr atasPtr );
void tampilTumpukan( SimpulTumpukanPtr sekarangPtr );
void instruksi( void );
/* fungsi main memulai eksekusi program */
int main( void )
{
SimpulTumpukanPtr tumpukanPtr = NULL; /* menunjuk ke atas tumpukan */
int
pilihan; /* pilihan menu pengguna */
int
nilai; /* int input by user */
instruksi(); /* menampilkan menu */
printf( "? " );
scanf( "%d", &pilihan );
/*
ketika pengguna tidak memilih 3 */
while
( pilihan != 3 ) {
switch
( pilihan ) {
/* taruh nilai di atas tumpukan */
case 1:
printf( "Masukkan sebuah integer: " );
scanf( "%d", &nilai );
taruh( &tumpukanPtr, nilai );
tampilTumpukan( tumpukanPtr );
break;
/* ambil nilai dari atas tumpukan */
case
2:
/* jika tumpukan tidak kosong */
if ( !apaKosong( tumpukanPtr ) ) {
printf("Nilai yang diambil (dihapus) adalah %d.\n", ambil( &tumpukanPtr
));
} /* akhir if */
tampilTumpukan( tumpukanPtr );
break;
default:
printf( "Pilihan tidak valid.\n\n" );
instruksi();
break;
}
/* akhir switch */
printf( "? " );
scanf( "%d", &pilihan );
} /*
akhir while */
printf( "Akhir program.\n" );
return
0; /* indikasi terminasi sukses */
} /* akhir main */
/* display program instruksi to user */
void instruksi( void )
{
printf( "Masukkan pilihan:\n"
"1 untuk menaruh sebuah nilai di atas tumpukan\n"
"2 untuk mengambil sebuah nilai dari atas tumpukan\n"
"3 untuk mengakhiri program\n" );
} /* akhir fungsi instruksi */
/* Menyisipkan sebuah simpul di atas
tumpukan */
void taruh( SimpulTumpukanPtr *atasPtr, int
info )
{
SimpulTumpukanPtr baruPtr; /* menunjuk ke simpul baru */
baruPtr = malloc( sizeof(
SimpulTumpukan ) );
/*
menyisipkan sebuah simpul di atas tumpukan */
if
( baruPtr != NULL ) {
baruPtr->data = info;
baruPtr->berikutPtr = *atasPtr;
*atasPtr = baruPtr;
} /*
akhir if */
else
{ /* tidak ada memori tersedia */
printf( "%d tidak disisipkan. Tidak ada memori tersedia.\n",
info );
} /*
akhir else */
} /* akhir fungsi taruh */
/* Menghapus sebuah simpul dari atas
tumpukan */
int ambil( SimpulTumpukanPtr *atasPtr )
{
SimpulTumpukanPtr tempPtr; /* pointer simpul sementara */
int
nilaiDiambil; /* nilai simpul */
tempPtr = *atasPtr;
nilaiDiambil = ( *atasPtr )->data;
*atasPtr = ( *atasPtr )->berikutPtr;
free(
tempPtr );
return
nilaiDiambil;
} /* akhir fungsi ambil */
/* Menampilkan tumpukan */
void tampilTumpukan( SimpulTumpukanPtr sekarangPtr )
{
/*
jika tumpukan kosong */
if
( sekarangPtr == NULL ) {
printf( "Tumpukan kosong.\n\n" );
} /*
akhir if */
else
{
printf( "Tumpukan adalah:\n" );
/*
ketika tidak akhir tumpukan */
while
( sekarangPtr != NULL ) {
printf( "%d --> ", sekarangPtr->data );
sekarangPtr = sekarangPtr->berikutPtr;
}
/* akhir while */
printf( "NULL\n\n" );
} /*
akhir else */
} /* akhir fungsi tampilTumpukan */
/* Menghasilkan 1 jika tumpukan kosong,
sebaliknya 0 */
int apaKosong( SimpulTumpukanPtr atasPtr )
{
return
atasPtr == NULL;
} /* akhir fungsi apaKosong */
|
Gambar 10.8 | Program tumpukan sederhana
Masukkan pilihan:
1 untuk menaruh sebuah nilai di atas
tumpukan
2 untuk mengambil sebuah nilai dari
atas tumpukan
3 untuk mengakhiri program
? 1
Masukkan sebuah integer: 5
Tumpukan adalah:
5 --> NULL
? 1
Masukkan sebuah integer: 6
Tumpukan adalah:
6 --> 5 --> NULL
? 1
Masukkan sebuah integer: 4
Tumpukan adalah:
4 --> 6 --> 5 --> NULL
? 2
Nilai yang diambil (dihapus) adalah 4.
Tumpukan adalah:
6 --> 5 --> NULL
? 2
Nilai yang diambil (dihapus) adalah 6.
Tumpukan adalah:
5 --> NULL
? 2
Nilai yang diambil (dihapus) adalah 5.
Tumpukan kosong.
? 4
Pilihan tidak valid.
Masukkan pilihan:
1 untuk menaruh sebuah nilai di atas
tumpukan
2 untuk mengambil sebuah nilai dari
atas tumpukan
3 untuk mengakhiri program
? 3
Akhir program.
Gambar 10.9 | Keluaran
program pada Gambar 10.8
Fungsi taruh
Fungsi taruh (baris 77-92)
menempatkan sebuah simpul baru di atas tumpukan. Fungsi ini mengandung tiga
langkah:
1.
Ciptakan sebuah
simpul baru dengan memanggil malloc dan tugaskan lokasi dari memori teralokasi kepada
baruPtr (baris 81).
2.
Tugaskan nilai
yang akan ditempatkan di atas tumpukan kepada baruPtr->
data (baris 85) dan tugaskan *atasPtr (pointer atas
tumpukan) kepada baruPtr->berikutPtr (baris 86), dimana anggota rantai dari baruPtr sekarang
menunjuk ke bekas simpul atas.
3.
Tugaskan baruPtr kepada *atasPtr (baris 87),
dimana *atasPtr sekarang menunjuk ke atas tumpukan yang baru.
Manipulasi ini melibatkan pengubahan
nilai tumpukanPtr oleh
*atasPtr
di dalam main. Gambar 10.10
mengilustrasikan fungsi taruh. Bagian a) gambar
menunjukkan tumpukan dan simpul baru sebelum operasi taruh. Anak panah putus-putus pada bagian b) mengilustrasikan langkah 2 dan
langka 3 pada operasi taruh agar simpul yang memuat
12 menjadi atas tumpukan yang baru.
Gambar 10.10 | Operasi taruh (push)
Fungsi ambil
Fungsi ambil (baris 95-105) menghapus
sebuah simpul dari atas tumpukan. Fungsi main menentukan apakah tumpukan kosong sebelum pemanggilan ambil. Operasi ambil memuat lima langkah:
1.
Tugaskan *atasPtr kepada tempPtr (baris 100); tempPtr akan dipakai
untuk membebaskan memori yang tidak lagi dibutuhkan.
2.
Tugaskan (*atasPtr)->data kepada nilaiDiambil (baris 101)
untuk menyimpan nilai yang ada di atas tumpukan.
3.
Tugaskan (*atasPtr)->berikutPtr kepada *atasPtr (baris 102)
sehingga *atasPtr memuat alamat dari simpul atas yang baru.
4.
Membebaskan
memori yang ditunjuk oleh tempPtr (baris 103).
5.
Menjadikan
nilaiDiambil sebagai nilai balik kepada pemanggil (baris 104).
Gambar 10.11 mengilustrasikan fungsi ambil. Bagian a) menunjukkan tumpukan setelah operasi ambil dilakukan. Bagian b) menunjukkan tempPtr yang menunjuk ke simpul pertama tumpukan dan atasPtr menunjuk ke simpul kedua tumpukan. Fungsi free dipakai untuk membebaskan memori yang ditunjuk oleh tempPtr.
10.5 Antrian
Struktur data umum lain adalah antrian (queue). Antrian seperti antrian pembeli di suatu supermarket,
dimana pengantri pertama dilayani terlebih dahulu, dan pengantri lainnya
memasuki antrian di ujung akhir dan menunggu untuk dilayani. Simpul-simpul
antrian dihapus (diambil) hanya dari kepala antrian dan disisipkan hanya pada
ekor antrian. Karena alasan ini, antrian dikenal sebagai struktur data FIFO (first-in, first-out). Operasi penyisipan dan penghapusan dikenal sebagai enqueue dan dequeue.
Gambar 10.11 | Operasi ambil (pop)
Antrian mempunyai banyak terapan dalam sistem komputer. Banyak komputer
hanya memiliki satu prosesor, jadi hanya satu pengguna pada satu waktu yang
akan dilayani. Entri dari pengguna lainnya ditempatkan di dalam antrian. Setiap
entri secara bertahap menuju depan antrian. Entri pada depan antrian adalah
yang paling lebih dahulu dilayani.
Antrian juga dapat dipakai untuk mendukung pencetakan jaringan. Lingkungan
pengguna-jamak dapat hanya memiliki satu printer. Banyak pengguna antri untuk
mencetak. Jika printer sibuk, pesan untuk mencetak dari pengguna lain
ditempatkan di dalam antrian. Gambar
11.12 mengilustrasikan sebuah antrian dengan beberapa simpul. Perhatikan bahwa
pointer pointer yang menunjuk ke kepala antrian dan yang menunjuk ke ekor
antrian.
Gambar 11.13 (keluaran ditampilkan pada Gambar 11.14) melakukan beberapa
manipulasi antrian. Program menyediakan beberapa opsi: menyisipkan sebuah
simpul di dalam antrian (fungsi enqueue), menghapus sebuah simpul dari antrian (fungsi dequeue), dan menghentikan program.
Gambar 10.12 | Representasi grafikal atas antrian
|
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
|
/* Gambar 10.13: gambar10_13.c
Mengoperasikan sebuah antrian */
#include <stdio.h>
#include <stdlib.h>
/* struktur referensi-diri */
struct simpulAntrian {
char
data; /* mendefinisikan data sebagai char */
struct
simpulAntrian *berikutPtr; /* pointer simpulAntrian */
}; /* akhir struktur simpulAntrian */
typedef struct simpulAntrian SimpulAntrian;
typedef SimpulAntrian *SimpulAntrianPtr;
/* prototipe fungsi */
void tampilAntrian( SimpulAntrianPtr sekarangPtr );
int apaKosong( SimpulAntrianPtr kepalaPtr );
char dequeue( SimpulAntrianPtr *kepalaPtr,
SimpulAntrianPtr *ekorPtr );
void enqueue( SimpulAntrianPtr *kepalaPtr,
SimpulAntrianPtr *ekorPtr,
char
nilai );
void instruksi( void );
/*
program main memulai eksekusi program */
int main( void )
{
SimpulAntrianPtr kepalaPtr = NULL; /* menginisialisasi
kepalaPtr */
SimpulAntrianPtr ekorPtr = NULL; /* menginisialisasi ekorPtr */
int
pilihan; /* menu pilihan pengguna */
char
item; /* masukan char oleh pengguna */
instruksi(); /* menampilkan menu */
printf( "? " );
scanf( "%d", &pilihan );
/*
ketika pengguna tidak memasukkan 3 */
while
( pilihan != 3 ) {
switch(
pilihan ) {
/* menempatkan nilai pada antrian (enqueue) */
case
1:
printf( "Masukkan sebuah karakter: " );
scanf( "\n%c", &item );
enqueue(
&kepalaPtr, &ekorPtr, item );
tampilAntrian( kepalaPtr );
break;
/* dequeue */
case
2:
/* jika antrian tidak kosong */
if ( !apaKosong( kepalaPtr ) ) {
item = dequeue( &kepalaPtr, &ekorPtr );
printf( "%c telah di-dequeue.\n", item );
} /* akhir if */
tampilAntrian( kepalaPtr );
break;
default:
printf( "pilah tak-valid.\n\n" );
instruksi();
break;
}
/* akhir switch */
printf( "? " );
scanf( "%d", &pilihan );
} /*
akhir while */
printf( "Akhir program.\n" );
return
0; /* indikasi terminasi sukses */
} /* akhir main */
/* menampilan menu untuk pengguna */
void instruksi( void )
{
printf ( "Masukkan pilihan Anda:\n"
" 1 untuk menambah sebuah elemen ke dalam antrian\n"
" 2 untuk menghapus sebuah item dari antrian\n"
" 3 untuk mengakhiri program\n" );
} /* akhir fungsi instruksi */
/* menyisipkan sebuah simpul di ekor antrian
*/
void enqueue( SimpulAntrianPtr *kepalaPtr,
SimpulAntrianPtr *ekorPtr,
char
nilai )
{
SimpulAntrianPtr baruPtr; /* pointer ke simpul baru */
baruPtr = malloc( sizeof(
SimpulAntrian ) );
if
( baruPtr != NULL ) { /* apakah memori tersedia */
baruPtr->data = nilai;
baruPtr->berikutPtr = NULL;
/*
jika kosong, sisipkan simpul di kepala antrian */
if
( apaKosong( *kepalaPtr ) ) {
*kepalaPtr = baruPtr;
}
/* akhir if */
else
{
( *ekorPtr )->berikutPtr =
baruPtr;
}
/* akhir else */
*ekorPtr = baruPtr;
} /*
akhir if */
else
{
printf( "%c tidak disisipkan. Memori tidak tersedia.\n",
nilai );
} /*
akhir else */
} /* akhir fungsi enqueue */
/* menghapus simpul dari kepala antrian */
char dequeue( SimpulAntrianPtr *kepalaPtr,
SimpulAntrianPtr *ekorPtr )
{
char
nilai; /* nilai simpul */
SimpulAntrianPtr tempPtr; /* pointer simpul sementara */
nilai = ( *kepalaPtr )->data;
tempPtr = *kepalaPtr;
*kepalaPtr = ( *kepalaPtr )->berikutPtr;
/*
jika antrian kosong */
if
( *kepalaPtr == NULL ) {
*ekorPtr = NULL;
} /*
akhir if */
free(
tempPtr );
return
nilai;
} /* akhir fungsi dequeue */
/* Menghasilkan 1 jika antrian kosong,
sebaliknya 0 */
int apaKosong( SimpulAntrianPtr kepalaPtr )
{
return
kepalaPtr == NULL;
} /* akhir fungsi apaKosong */
/* menampilkan antrian */
void tampilAntrian( SimpulAntrianPtr sekarangPtr )
{
/*
jika antrian kosong */
if
( sekarangPtr == NULL ) {
printf( "Antrian kosong.\n\n" );
} /*
akhir if */
else
{
printf( "Antrian adalah:\n" );
/*
ketika tidak akhir antrian */
while
( sekarangPtr != NULL ) {
printf( "%c --> ", sekarangPtr->data );
sekarangPtr = sekarangPtr->berikutPtr;
}
/* akhir while */
printf( "NULL\n\n" );
} /*
akhir else */
} /* akhir fungsi tampilAntrian */
|
Gambar 10.13 | Memproses antrian
Masukkan pilihan Anda:
1 untuk menambah sebuah elemen ke dalam
antrian
2 untuk menghapus sebuah item dari antrian
3 untuk mengakhiri program
? 1
Masukkan sebuah karakter: A
Antrian adalah:
A --> NULL
? 1
Masukkan sebuah karakter: B
Antrian adalah:
A --> B --> NULL
? 1
Masukkan sebuah karakter: C
Antrian adalah:
A --> B --> C --> NULL
? 2
A telah di-dequeue.
Antrian adalah:
B --> C --> NULL
? 2
B telah di-dequeue.
Antrian adalah:
C --> NULL
? 2
C telah di-dequeue.
Antrian kosong.
? 4
pilah tak-valid.
Masukkan pilihan Anda:
1 untuk menambah sebuah elemen ke dalam
antrian
2 untuk menghapus sebuah item dari antrian
3 untuk mengakhiri program
? 3
Akhir program.
Gambar 10.14 | Keluaran
program pada Gambar 10.13
Fungsi enqueue
Fungsi enqueue (baris 80-104) menerima tiga argumen dari main: alamat pointer yang menunjuk ke kepala antrian, alamat pointer yang
menunjuk ke ekor antrian, dan nilai yang akan disisipkan ke dalam antrian.
Fungsi ini memuat tiga langkah:
1.
Ciptakan sebuah
simpul baru: Panggil malloc, tugaskan lokasi memori teralokasi kepada baruPtr (baris 85),
tugaskan nilai yang akan disisipkan ke dalam antrian kepada baruPtr->data (baris 88),
dan tugaskan NULL kepada baruPtr->berikutPtr (baris 89).
2.
Jika antrian
kosong (baris 92), tugaskan baruPtr kepada *kepalaPtr (baris 93); Sebaliknya, tugaskan baruPtr kepada (*ekorPtr)->berikutPtr (baris 96).
3.
Tugaskan baruPtr kepada *ekorPtr (baris 99).
Gambar 10.15 mengilustrasikan operasi enqueue. Bagian a) menampilkan antrian dan simpul baru sebelum operasi. Anak
panah putus-putus pada bagian b) mengilustrasikan langkah 2 dan langkah 3 dari
fungsi enqueue yang membuat simpul baru ditambahkan
ke ujung akhir antrian.
Gambar 10.15 | Operasi enqueue
Fungsi dequeue
Fungsi dequeue (baris 107-123) menerima alamat pointer yang menunjuk ke kepala antrian
dan alamat pointer yang menunjuk ke ekor antrian sebagai argumen dan menghapus
simpul pertama dari antrian. Operasi dequeue memuat enam langkah:
1.
Tugaskan (*kepalaPtr)->data kepada nilai
untuk menyimpan nilai (baris 112).
2.
Tugaskan *kepalaPtr kepada tempPtr (baris 113),
yang akan dipakai untuk membebaskan memori yang tak lagi diperlukan.
3.
Tugaskan (*kepalaPtr)->berikutPtr kepada *kepalaPtr (baris 114)
sehingga *kepalaPtr sekarang menunjuk ke simpul pertama baru di dalam
antrian.
4.
Jika *kepalaPtr adalah NULL (baris 117), maka tugaskan NULL kepada *ekorPtr (baris 118).
5.
Bebaskan memori yang ditunjuk oleh tempPtr (baris 121).
6.
Variabel nilai dijadikan nilai balik kepada pemanggil (baris 122).
Gambar 10.16 mengilustrasikan fungsi dequeue. Bagian a) menunjukkan antrian setelah operasi enqueue dilakukan. Bagian b) menunjukkan tempPtr yang menunjuk ke simpul yang dihapus, dan kepalaPtr menunjuk ke simpul pertama baru di dalam antrian. Fungsi free dipakai untuk membebaskan memori yang ditunjuk oleh tempPtr.
Gambar 10.16 | Operasi dequeue
10.6 Pohon
Senarai berantai, tumpukan, dan antrian adalah struktur data linier. Pohon
adalah struktur data tak-linier, dua-dimensil dengan beberapa watak spesial.
Simpul-simpul pohon memuat dua atau lebih rantai (link). Bagian ini akan mendiskusikan tentang pohon biner (Gambar
10.17), yaitu pohon dengan semua simpul memuat dua rantai (tidak satupun, satu
rantai, atau kedua rantai bisa NULL). Simpul akar adalag simpul pertama di
dalam pohon. Setiap rantai di dalam simpul akar disebut dengan anak. Anak kiri
adalah simpul pertama di dalam subpohon kiri, dan anak kanan adalah simpul
pertama di dalam subpohon kanan. Simpul tanpa anak disebut dengan simpul daun.
Gambar 10.17 | Representasi grafikal atas pohon
biner
Pada bagian ini, pohon biner spesial yang dinamakan pohon pencarian biner
diciptakan. Pohon pencarian biner (tanpa nilai simpul duplikat) memiliki karakteristik
bahwa nilai-nilai di sembarang subpohon kiri lebih kecil dari nilai di simpul
induk (simpul orang-tua), dan nilai-nilai di sembarang subpohon kanan lebih
besar dari nilai di simpul induk. Gambar 10.18 mengilustrasikan sebuah pohon
pencarian biner dengan 12 nilai.
Gambar 10.18 | Pohon pencarian biner
Gambar 10.19 (keluaran ditampilkan pada Gambar 10.20) menciptakan sebuah
pohon pencarian biner dan menjelajahinya (mengurutkannya) dengan tiga cara,
yaitu inorder, preorder, dan postorder. Program menghasilkan 10 angka acak dan
menyisipkannya di dalam pohon dan nilai duplikat yang ada dibuang.
|
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
|
/* Gambar 10.19: gambar10_19.c
Menciptakan pohon biner dan menjelajahinya dengan
cara preorder, inorder, dan postorder */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* struktur referensi-diri */
struct simpulPohon {
struct
simpulPohon *kiriPtr; /* pointer ke subpohon kiri */
int
data; /* nilai simpul */
struct
simpulPohon *kananPtr; /* pointer ke subpohon kanan */
}; /* akhie struktur simpulPohon */
typedef struct simpulPohon SimpulPohon; /* sinonim untuk struct simpulPohon */
typedef SimpulPohon *SimpulPohonPtr; /* sinonim untuk
SimpulPohon* */
/* prototipe */
void sisipkanSimpul( SimpulPohonPtr *pohonPtr, int
nilai );
void inOrder( SimpulPohonPtr pohonPtr );
void preOrder( SimpulPohonPtr pohonPtr );
void postOrder( SimpulPohonPtr pohonPtr );
/* fungsi main untuk memulai eksekusi */
int main( void )
{
int
i; /* kounter untuk loop dari 1-10 */
int
item; /* variabel untuk menampung nilai acak */
SimpulPohonPtr akarPtr = NULL; /* pohon awalnya kosong */
srand( time( NULL ) );
printf( "Angka-angka yang akan ditempatkan pada pohon adalah:\n"
);
/*
menyisipkan angka acak antara 0 sampai 14 ke dalam pohon */
for
( i = 1; i <= 10; i++ ) {
item = rand() % 15;
printf( "%3d", item );
sisipkanSimpul( &akarPtr,
item );
} /*
akhir for */
/*
menjelajahi pohon secara preOrder */
printf( "\n\nPenjelajahan preOrder adalah:\n" );
preOrder( akarPtr );
/*
menjelajahi pohon secara inOrder */
printf( "\n\nPenjelajahan inOrder adalah:\n" );
inOrder( akarPtr );
/*
menjelajahi pohon dengan postOrder */
printf( "\n\nPenjelajahan postOrder adalah:\n" );
postOrder( akarPtr );
return
0; /* indikasi terminasi sukses */
} /* akhir main */
/* menyisipkan simpul ke dalam pohon */
void sisipkanSimpul( SimpulPohonPtr *pohonPtr, int
nilai )
{
/*
jika pohon kosong */
if
( *pohonPtr == NULL ) {
*pohonPtr = malloc( sizeof( SimpulPohon ) );
/*
jika memori telah dialokasikan dan data ditugaskan */
if
( *pohonPtr != NULL ) {
( *pohonPtr )->data = nilai;
( *pohonPtr )->kiriPtr = NULL;
( *pohonPtr )->kananPtr = NULL;
}
/* akhir if */
else
{
printf( "%d tidak disisipkan. Memori tidak tersedia.\n",
nilai );
}
/* akhir else */
} /*
akhir if */
else
{ /* pohon tidak kosong */
/*
data yang akan disisipkan kurang dari data di dalam simpul sekarang */
if
( nilai < ( *pohonPtr )->data ) {
sisipkanSimpul( &( ( *pohonPtr )->kiriPtr ), nilai );
}
/* akhir if */
/*
data yang akan disisipkan lebih besar dari data di
dalam simpul sekarang */
else
if ( nilai > ( *pohonPtr )->data ) {
sisipkanSimpul( &( ( *pohonPtr )->kananPtr ), nilai );
}
/* akhir else if */
else
{ /* nilai duplikat dibuang */
printf( "duplikat dibuang" );
}
/* akhir else */
} /*
akhir else */
} /* akhir fungsi sisipkanSimpul */
/* memulai penjelajahan inorder atas pohon
*/
void inOrder( SimpulPohonPtr pohonPtr )
{
/*
jika pohon tak kosong kemudian jelajahi */
if
( pohonPtr != NULL ) {
inOrder( pohonPtr->kiriPtr );
printf( "%3d", pohonPtr->data );
inOrder( pohonPtr->kananPtr );
} /*
akhir if */
} /* akhir fungsi inOrder */
/* memulai penjelajahan preorder atas pohon
*/
void preOrder( SimpulPohonPtr pohonPtr )
{
/*
jika pohon tak kosong kemudian jelajahi */
if
( pohonPtr != NULL ) {
printf( "%3d", pohonPtr->data );
preOrder( pohonPtr->kiriPtr );
preOrder( pohonPtr->kananPtr );
} /*
akhir if */
} /* akhir fungsi preOrder */
/* memulai penjelajahan postorder atas pohon
*/
void postOrder( SimpulPohonPtr pohonPtr )
{
/*
jika pohon tak kosong kemudian jelajahi */
if
( pohonPtr != NULL ) {
postOrder( pohonPtr->kiriPtr );
postOrder( pohonPtr->kananPtr );
printf( "%3d", pohonPtr->data );
} /*
akhir if */
} /* akhir fungsi postOrder */
|
Gambar 10.19 | Menciptakan dan menjelajah sebuah pohon biner
Angka-angka yang akan ditempatkan pada
pohon adalah:
2 3 12 3duplikat dibuang 2duplikat dibuang 9
8 5 1 4
Penjelajahan preOrder adalah:
2 1 3 12
9 8 5 4
Penjelajahan inOrder adalah:
1 2 3
4 5 8 9 12
Penjelajahan postOrder adalah:
1 4 5
8 9 12 3 2
Gambar 10.20 | Keluaran
program pada Gambar 10.19
Fungsi-fungsi yang digunakan pada Gambar 10.19 untuk menciptakan suatu
pohon pencarian biner dan menjelajahi pohon adalah fungsi rekursif. Fungsi sisipkanSimpul (baris 56-86) menerima alamat pohon dan sebuah integer yang akan disimpan
sebagai argumen. Simpul hanya dapat disisipkan sebagai simpul daun di dalam
suatu pohon pencarian biner. Langkah-langkah penyisipan sebuah simpul di dalam
pohon pencarian biner adalah sebagai berikut:
1.
Jika *pohonPtr adalah NULL (baris 59), maka ciptakan sebuah
simpul baru (baris 60). Panggil malloc, tugaskan memori teralokasi kepada *pohonPtr, tugaskan
integer yang akan disimpan kepada (*pohonPtr)->data (baris 64), tugaskan nilai NULL kepada (*pohonPtr)->kiriPtr dan (*pohonPtr)->kananPtr (baris 65-66), dan kembalikan kendali kepada
pemanggil.
2.
Jika nilai dari
*pohonPtr tidak NULL dan nilai yang akan disisipkan
kurang dari (*pohonPtr)->data, maka fungsi sisipkanSimpul dipanggil dengan alamat dari (*pohonPtr)->kiriPtr (baris 75). Jika
nilai dari *pohonPtr tidak NULL dan nilai yang akan disisipkan lebih dari (*pohonPtr)->data, maka fungsi sisipkanSimpul dipanggil
dengan alamat dari (*pohonPtr)->kananPtr (baris 80). Sebaliknya, langkah rekursif akan
terus berlanjut sampai sebuah pointer NULL ditemukan, kemudian langkah 1
dieksekusi untuk menyisipkan simpul baru.
Gambar 10.21 | Pohon pencarian biner dengan tujuh
simpul
Fungsi inOrder (baris 89-97), preOrder (baris 100-108), dan postOrder (baris 111-119) masing-masing menerima sebuah pohon (yaitu, pointer yang
menunjuk ke simpul akar pohon) dan menjelajahi pohon. Langkah-langkah untuk
penjelajahan inOrder adalah:
1.
Jelajahi
subpohon kiri secara inOrder.
2.
Proses nilai di
dalam simpul.
3.
Jelajahi
subpohon kanan secara inOrder.
Nilai di dalam sebuah simpul tidak akan diproses sampai nilai-nilai di
subpohon kirinya selesai diproses. Penjelajahan inOrder atas pohon yang ditampilkan pada Gambar 10.21 adalah:
6 13 17 27 33
42 48
Penjelajahan inOrder atas suatu pohon pencarian biner menampilkan nilai-nilai simpul dengan
urutan menaik. Proses penciptaan pohon pencarian biner menyebabkan data terurut
dan hal ini dikenal dengan pengurutan pohon biner.
Langkah-langkah untuk penjelajahan preOrder adalah:
1.
Proses nilai di
dalam simpul.
2.
Jelajahi
subpohon kiri secara preOrder.
3.
Jelajahi
subpohon kanan secara preOrder.
Nilai di dalam setiap simpul diproses ketika simpul tersebut dikunjungi.
Setelah nilai di dalam simpul yang diberikan diproses, nilai-nilai di dalam
subpohon kiri diproses, kemudian nilai-nilai di dalam subpohon kanan diproses.
Penjelajahan preOrder atas pohon yang ditampilkan pada Gambar 10.21 adalah:
27 13 6 17 42
33 48
Langkah-langkah untuk penjelajahan postOrder adalah:
1.
Jelajahi
subpohon kiri secara postOrder.
2.
Jelajahi
subpohon kanan secara postOrder.
3.
Proses nilai di
dalam simpul.
Nilai di dalam setiap simpul tidak ditampilkan sampai nilai-nilai dari
semua anak dari simpul tersebut ditampilkan. Penjelajahan postOrder atas pohon yang ditampilkan pada Gambar 10.21 adalah
6 17 13 33 48
42 27
Kesimpulan
§ Struktur referensi diri memuat sebuah
anggota pointer yang menunjuk ke suatu struktur bertipe sama.
§ Struktur referensi-diri dapat
dihubungkan untuk membentuk beberapa struktur data seperti senarai, antrian,
tumpukan, dan pohon.
§ Penciptaan struktur data dinamis
memerlukan alokasi memori dinamis, dimana program mampu untuk mendapatkan
memori tambahan pada waktu eksekusi untuk menampung semua simpul baru dan untuk
membebaskan memori yang tidak lagi diperlukan. Batas untuk alokasi memori
dinamis adalah sebesar memori fisik yang tersedia di dalam komputer atau
sebesar memori virtual yang tersedia di dalam sistem memori virtual. Tetapi,
seringkali bahwa batas memori dinamis jauh lebih kecil karena memori harus
dibagi dengan banyak aplikasi lainnya.
§ Fungsi malloc dan free, dan operator sizeof
esensial bagi alokasi memori dinamis. Fungsi malloc mengambil jumlah byte yang akan dialokasikan sebagai
argumen dan menghasilkan nilai balik berupa sebuah pointer bertipe void * (pointer ke void) yang menunjuk ke memori teralokasi.
Pointer void * dapat ditugasi variabel bertipe pointer sembarang. Fungsi malloc normalnya dipakai dengan operator sizeof.
§ Fungsi free membebaskan memori, yaitu memori dikembalikan kepada sistem
sehingga memori tersebut dapat dialokasikan-ulang pada masa datang.
§ Senarai berantai adalah koleksi linier
atas beberapa struktur referensi-diri, yang dinamakan simpul, terhubung oleh
rantai-rantai pointer. Senarai berantai diakses dengan sebuah pointer yang
menunjuk ke simpul pertama di dalam senarai. Simpul-simpul diakses lewat
anggota pointer rantai yang disimpan di akhir senarai. Data disimpan secara
dinamis di dalam senarai berantai, dimana setiap simpul diciptakan jika
diperlukan. Sebuah simpul dapat memuat sembarang tipe termasuk objek-objek struct.
§ Tumpukan adalah versi terkekang dari
senarai berantai. Simpul-simpul baru dapat ditambahkan di atas tumpukan dan
dihapus dari hanya dari atas tumpukan. Karena alasan ini, tumpukan dikenal
sebagai struktur data LIFO (last-in, first-out). Tumpukan direferensi lewat
pointer yang menunjuk ke elemen atas dari tumpukan. Anggota rantai (link) pada simpul terakhir tumpukan
ditetapkan NULL untuk mengindikasikan bagian terbawah tumpukan.
§ Dua fungsi utama yang digunakan untuk memanipulasi tumpukan adalah taruh (push)
dan ambil (pop). Fungsi taruh menciptakan sebuah simpul baru dan
menempatkannya di atas tumpukan. Fungsi ambil menghapus sebuah simpul dari atas tumpukan, membebaskan memori yang
dialokasikan untuk simpul yang ditaruh dan menghasilkan nilai balik berupa
nilai terambil (terhapus) dari simpul.
§ Struktur data umum lain adalah antrian (queue). Antrian seperti antrian pembeli di suatu supermarket,
dimana pengantri pertama dilayani terlebih dahulu, dan pengantri lainnya
memasuki antrian di ujung akhir dan menunggu untuk dilayani. Simpul-simpul
antrian dihapus (diambil) hanya dari kepala antrian dan disisipkan hanya pada
ekor antrian. Karena alasan ini, antrian dikenal sebagai struktur data FIFO (first-in, first-out). Operasi penyisipan dan penghapusan dikenal sebagai enqueue dan dequeue.
§ Fungsi enqueue (baris 80-104) menerima tiga argumen dari main: alamat pointer yang menunjuk ke kepala antrian, alamat pointer yang
menunjuk ke ekor antrian, dan nilai yang akan disisipkan ke dalam antrian.
§ Senarai berantai, tumpukan, dan antrian adalah struktur data linier. Pohon
adalah struktur data tak-linier, dua-dimensil dengan beberapa watak spesial.
Simpul-simpul pohon memuat dua atau lebih rantai (link). Bagian ini akan mendiskusikan tentang pohon biner (Gambar
10.17), yaitu pohon dengan semua simpul memuat dua rantai (tidak satupun, satu
rantai, atau kedua rantai bisa NULL). Simpul akar adalag simpul pertama di
dalam pohon. Setiap rantai di dalam simpul akar disebut dengan anak. Anak kiri
adalah simpul pertama di dalam subpohon kiri, dan anak kanan adalah simpul
pertama di dalam subpohon kanan.
§ Pohon pencarian biner (tanpa nilai simpul duplikat) memiliki karakteristik
bahwa nilai-nilai di sembarang subpohon kiri lebih kecil dari nilai di simpul
induk (simpul orang-tua), dan nilai-nilai di sembarang subpohon kanan lebih
besar dari nilai di simpul induk.
No comments:
Post a Comment