Salam Mahasiswa,
Perkenalkan
Nama : Dwi Prastio
Sekolah : STMIK STIKOM BALI
Kelas : CA141
Nim : 140010137
Kali ini saya akan memberikan beberapa ilmu mengenai materi untuk matakuliah Praktikum Struktur Data. Beberapa materi yang akan di bahas diantaranya :
- Variable
- Array 1 dimensi dan 2 dimensi
- Stack
- Queue
- Sorting (Selection Sort dan Insertion Sort)
- Searching (Sequential Sort dan Binary Search)
1. VARIABLE
Variabel adalah
sebuah identifier yang nilainya dapat diubah sesuai dengan kebutuhan program. Jika dibutuhkan sebuah variabel yang dapat dikenali
oleh semua lingkungan dalam program, maka harus digunakan variabel Global.
Pada C++ selalu
terdapat fungsi utama, variabel global biasanya dideklarasikan di luar fungsi
utama tersebut. Juga terdapat
variabel Lokal. Variabel lokal hanya dikenali oleh suatu fungsi saja, artinya
variabel lokal tidak dikenal oleh lingkungan luar di dalam program yang dibuat.Variabel
lokal harus berada dalam lingkup fungsi tertentu
Pada saat
mendeklarasikan sebuah variabel, secara otomatis harus mendeklarasikan tipe
data yang dapat ditampung oleh varibel tersebut.
Di dalam bahasa pemrograman terdapat beberapa tipe data dasar yang
telah didefenisikan dan digolongkan :
- tipe bilangan bulat (integer)
- bilangan real(floating point),
- tipe logika(boolean) dan
- tipe karakter/teks(character/string)
2. ARRAY
Array merupakan kumpulan elemen
yang bertipe sama dalam urutan tertentu yang menggunakan nama yang sama. Letak
atau posisi dari elemen array ditunjukan oleh index atau posisi.
Array dapat berupa 1 dimensi, 2
dimensi, dan bahkan n-dimensi. Suatu array dikatakan sebagai 1 dimensi, 2
dimensi, atau n-dimensi berdasarkan banyaknya penunjuk indeks/posisi.
Deklarasi Array dapat dilihat pada gambar berikut :
Inisialisasi Array
Nilai suatu variabel array dapat
juga diinisialisasikan secara langsung pada saat deklarasi
Misalnya:
int
nil [5] = {1, 3, 6, 12, 24};
Maka di penyimpanan ke dalam
array dapat digambarkan sebagai berikut :
Untuk mengakses nilai array,
dapat menggunakan sintak seperti berikut :
nama_array
[index];
Pada contoh diatas, variabel nil
memiliki 5 buah elemen yang masing -
masing berisi data.
Misal untuk memberi nilai 75 pada
elemen ke 3 maka pernyataannya adalah :
Nil [2] = 75;
Contoh penggunaan array 1 dimensi :
#include<iostream.h>
#include<conio.h>
void main()
int
ujian [5]={90, 95,78, 80, 85};
for(int i=0;i<5;i++)
{
cout<<"Nilai dari ujian index ke
"<<i <<" = "<<ujian [i]<<endl;
}
getch();
Hasil dari script tersebut seperti gambar berikut :
s Array 2 dimensi
Array dua dimensi
sering sekali digambarkan/dianalogikan sebagai sebuah matriks. Dimana
indeks
pertama menunjukkan baris dan indeks kedua menunjukan kolom.
Array dua
dimensi terdiri dari beberapa baris dan beberapa kolom elemen yang bertipe
sama.
Array dua
dimensi terdapat dua jumlah elemen yang terdapat didalam kurung siku dan
keduanya boleh tidak sama.
Contoh array 2 dimensi
#include<iostream.h>
#include<conio.h>
void main()
{
int
matrix[3][4]={{5,10,1,11},{4,7,67,-9},{9,0,45,3}};
for(int i=0;i<3;i++)
{
for(int j=0;j<4;j++)
{
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
getch();
hasil dari script tersebut dapat dilihat pada gambar di bawah
3. STACK
Stack berarti tumpukan.
Jika dikaitkan dengan struktur data, Stack berarti sekumpulan data yang
organisasi atau terstruktur dengan sifat operasi penambahan ( Push ) dan
pengambilan ( Pop) elemen melalui satu tempat ( Top Of Stack) .
Pengertian Stack atau Tumpukan adalah suatu struktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), Benda yang terakhir masuk ke dalam stack akan menjadi pertama yang di keluarkan dari stack. Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP) dan aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu dilakukan paling atas (TOP) dan penghapusan juga selalu dilakukan pada TOP
“Top “
merupakan pintu untuk keluar masuknya elemen – elemen stack. A, B, dan C
merupakan suatu koleksi. Dari ilustrasi dapat digambarkan bahwa C merupakan
elemen yang terakhir memasuki stack namun pertama keluar dari stack. Begitu
sebaliknya dengan A. A merupakan elemen pertama yang memasuki tumpukan namun
terakhir saat keluar dari tumpukan.
Di
dalam pengembangannya, stack dapat dikelompokkan menjadi dua bagian. Dua bagian
tersebut yaitu Single Stack dan Double Stack.
Stack karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen stack akan tersusun secara LIFO (Last In First Out).
OPERASI-OPERASI/FUNGSI STACK
Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
Clear : digunakan untuk mengosongkan stack
IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh
ilustrasi stack
a.
Single Stack
Single
Stack atau Stack Tunggal adalah stack yang hanya terdiri dari satu koleksi.
Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan
harus dilakukan bertahap dari indeks TOP-nya.
Di
dalam proses single stack terdapat tiga macam proses utama, yaitu :
-
Inisialisasi
- PUSH
(Insert, Masuk, Simpan, Tulis)
- POP
(Delete, Keluar, Ambil, Baca, Hapus)
Contoh
programnya ada di bawah.
#include <iostream.h>
#include <conio.h>
#define max 10
struct Tumpukan{
int atas;
int data[max];
}T;
void awal(){
T.atas=-1;
}
int kosong(){
if(T.atas==-1)
return 1;
else
return 0;
}
int penuh(){
if(T.atas==max-1)
return 1;
else
return 0;
}
void input(int data){
if(kosong()==1)
{T.atas++;
T.data[T.atas]=data;
cout<<"Data
"<<T.data[T.atas]<<" masuk ke stack";}
else if(penuh()==0)
{T.atas++;
T.data[T.atas]=data;
cout<<"Data
"<<T.data[T.atas]<<" masuk ke stack";}
else
cout<<"Tumpukan
penuh";
}
void hapus(){
if(kosong()==0){
cout<<"Data teratas sudah
terambil";
T.atas--;
}
else
cout<<"Data kosong";
}
void tampil(){
if(kosong()==0)
{for(int i=T.atas;i>=0;i--)
{cout<<"\nTumpukan ke
"<<i<<"="<<T.data[i];}
}
else
cout<<"Tumpukan kosong";
}
void bersih(){
T.atas=-1;
cout<<"Tumpukan kosong!";
}
void main(){
int pil,data;
awal();
do
{
clrscr();
cout<<"1. Input\n2. Hapus\n3. Tampil\n4.
Bersihkan\n5. Keluar\nMasukkan pilihan :";
cin>>pil;
switch(pil)
{case
1:cout<<"Masukkan data = ";cin>>data;
input(data);
break;
case 2:hapus();
break;
case 3:tampil();
break;
case 4:bersih();
break;
case 5: cout<<"Terimakasih, tekan enter
untuk keluar";
}
getch(); }
while(pil!=5);}
screenshoot program sebagai berikut :
4. QUEUE / ANTRIAN
Antrian dapat diartikan sebagai suatu kumpulan data yang seolah - olah terlihat seperti ada data yang diletakkan di sebelah data yang lain
Bersifat FIFO (First In First Out)
Elemen yang pertama masuk ke antrian akan keluar pertama kalinya
Contoh :
1. Penjualan karcis kereta, bioskop
2. Penjadualan Pencetakan
3. Penjadualan pemakaian CPU
4. Penyimpanan barang di Apotek
Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya. Sehingga membutuhkan 2 variabel : Head dan Tail
Operasi - operasi queue :
Create ()
Untuk menciptakan dan menginisialisasi Queue
Dengan cara membuat Head dan Tail = -1
IsEmpty()
Untuk memeriksa apakah antrian kosong atau tidak dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah
Pergerakan pada antrian terjadi dengan penambahan elemen antrian kebelakang yaitu menggunakan nilai Tail
Clear ()
Untuk menghapus elemen-elemen antrian dengan cara membuat Tail dan Head = -1
Penghapusan elemen-elemen antrian sebenarnya tidak menghapus arraynya namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen antrian tidak lagi terbaca
Tampil ()
Untuk menampilkan nilai-nilai elemen antrian
Menggunakan looping dari head s/d tail
5. SORTING
Pengurutan data
(sorting) didefinisikan
sebagai suatu proses untuk menyusun
kembali humpunan obyek menggunakan aturan tertentu. Menurut Microsoft Book-shelf,definisi Algoritma
Pengurutan adalah algoritma untuk meletakkan kumpulan elemen
data ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam
tiap-tiap elemen.
Ada dua macam urutan yang biasa digunakan
dalam proses pengurutan yaitu :
- urut naik (ascending)
yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
- urut turun (descending)
yaitu data yang mempunyai nilai paling besar sampai paling kecil.
Algoritma untuk
melakukan Sorting
1. Selection Sort
2. Insertion Sort
3. BubbleSort
4. Quick Sort
1. Metode Seleksi (Selection Sort)
Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil
kemudian menukarkannya dengan
data yang digunakan sebagai acuan atau sering
dinamakan pivot.
Proses pengurutan dengan metode
seleksi dapat dijelaskan sebagai berikut :
Ø Langkah pertama : dicari data terkecil dari data pertama
sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama.
Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding
data yang lain.
Ø Langkah kedua : data terkecil kita cari mulai dari
data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar
dengan data kedua dan demikian seterusnya sampai semua elemen dalam
keadaan terurutkan.
Algoritma seleksi dapat
dituliskan sebagai berikut :
1 i ← 0
2 selama (i < N-1) kerjakan baris 3 sampai dengan 9
3 k ← i
4 j ← i + 1
5 Selama (j < N) kerjakan baris 6 dan 7
6 Jika (Data[k] > Data[j]) maka k ← j
7 j ← j + 1
8 Tukar Data[i] dengan Data[k]
9 i ← i + 1
Untuk lebih memperjelas langkah-langkah algoritma seleksi dapat
dilihat pada
tabel di bawah. Proses pengurutan pada tabel 6.2 dapat
dijelaskan sebagai berikut:
·
Pada saat i=0, data
terkecil antara data ke-1 s/d ke-9 adalah data ke-4, yaitu 3, maka data ke-0
yaitu 12 ditukar dengan data ke-4 yaitu 3.
·
Pada saat i=1, data
terkecil antara data ke-2 s/d ke-9 adalah data ke-2, yaitu 9, maka data ke-1
yaitu 35 ditukar dengan data ke-2 yaitu 9.
·
Pada saat i=2, data
terkecil antara data ke-3 s/d ke-9 adalah data ke-3, yaitu 11, maka data ke-2
yaitu 35 ditukar dengan data ke-3 yaitu 11.
·
Pada saat i=3, data
terkecil antara data ke-4 s/d ke-9 adalah data ke-4, yaitu 12, maka data ke-3
yaitu 35 ditukar dengan data ke-4 yaitu 12.
Dan seterusnya
2.
Insertion
Sort
Mirip dengan cara
orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke
tempat yang seharusnya
Pengurutan dimulai
dari data ke 2 sampai dengan data terakhir , jika ditemukan data yang lebih
kecil, maka akan di tempatkan (diinsert) di posisiyang seharusnya.
Pada penyisipan elemen
maka elemen – elemen lain akan bergeser ke belakang
Algoritma sorting ini umumnya digunakan apabila
jumlah elemennya sedikit (n kecil). Masalah yang akan muncul dengan metoda ini
adalah bagaimana cara menyisipkan A[K] ke dalam letak yang seharusnya pada
subarray terurut A[1], A[2], ....., A[K-1]. Hal ini dapat dilakukan dengan
membandingkan A[K] dengan A[K-1], kemudian A[K] dengan A[K-2], A[K] dengan
A[K-3] dan seterusnya, sampai menemukan elemen A[J] dimana A[J] A[K].
Algoritma ini menggunakan
sentinel elemen (A[0]) yang digunakan sebagai perbandingan. Yang dimaksud
dengan sentinel elemen adalah elemen yang memiliki nilai yang sangat kecil.
Penggambaran proses Insertion Sort :
|
Proses
|
A[0]
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
A[6]
|
A[7]
|
A[8]
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 1:
|
-
|
77
|
33
|
44
|
11
|
88
|
22
|
66
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 2:
|
-
|
77
|
33
|
44
|
11
|
88
|
22
|
66
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 3:
|
-
|
33
|
77
|
44
|
11
|
88
|
22
|
66
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 4:
|
-
|
33
|
44
|
77
|
11
|
88
|
22
|
66
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 5:
|
-
|
11
|
33
|
44
|
77
|
88
|
22
|
66
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 6:
|
-
|
11
|
33
|
44
|
77
|
88
|
22
|
66
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 7:
|
-
|
11
|
22
|
33
|
44
|
77
|
88
|
66
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
K
= 8:
|
-
|
11
|
22
|
33
|
44
|
66
|
77
|
88
|
55
|
|
|
|
|
|
|
|
|
|
|
|
|
Urutan
:
|
-
|
11
|
22
|
33
|
44
|
55
|
66
|
77
|
88
|
6. SEARCHING
Searching adalah metode pencarian
informasi dalam suatu aplikasi, dengan suatu kunci (key). Pencarian diperlukan
untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari
informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan
dengan referensi pada adanya sekelompok data yang tersimpan secara
terorganisasi, kelompok data tersebut kita sebut table. Pada metode searching
(pencarian) ada 2 teknik yang digunakan yaitu : Pencarian sekuensial
(sequential search) dan Pencarian biner (Binary search).
1. Pencarian Sekuensial (sequential
search)
Pencarian sekuensial (sequential
search) atau sering disebut pencarian linier menggunakan prinsip sebagai
berikut : data yang ada di bandingkan satu persatu secara berurutan dengan yang
dicari.
Pada dasarnya, pencarian ini hanya
melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan,
di bandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah
ditemukan. Sebaliknya apabila sampai akhir pengulangan, tidak ada yang sama
berarti data tidak ada.
Kelebihan serta Kekurangan Pencarian
Sekuensial yaitu :
a. Kelebihannya :
Ø Relatif lebih cepat dan efisien
untuk data yang terbatas
Ø Algoritma sederhana.
b. Kekuranganya :
Ø Kurang cepat untuk data dalam jumlah
besar
Ø Beban komputasi cenderung lebih
besar
2. Pencarian Biner (Binary Search)
Salah satu syarat pencarian biner
(binary search) dapat dilakukan adalah data sudah dalam keadaan terurut. Dengan
kata lain, apabila data belum dalam keadaan terurut , pencarian biner tidak
dapat dilakukan . Dalam kehidupan sehari-hari, sebenarnya kita juga serig
menggunakan pencarian biner. Misalnya saat kita ingin mencari suatu kata dalam
kamus.
Langkah dalam pencarian biner adalah
:
1. Mula-mula diambil dari posisi awal=1
dan posisi akhir = n
2. Kemudian kita cari posisi data
tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) dibagi 2
3. Kemudian data yang di cari
dibandingkan dengan data tengah
a. Jika sama, data ditemukan, Proses
selesai
b. Jika lebih kecil, proses dilakukan
kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1,
c. Jika lebih besar, proses dilakukan
kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.
4. Ulangi langkah kedua hingga data
ditemukan, atau tidak ditemukan.
5. Pencarian biner ini akan berakhir
jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi
awal sudah lebih besar dari posisi akhir berarti data tidak diketemukan.
DAFTAR PUSTAKA :
http://elearning.stikom-bali.ac.id/mahasiswa/kelas-detail.aspx?mk=SK0207&kls=CA141
Catatan harian matakuliah Struktur Data
http://www.slideshare.net/wawanext01/materi-tipe-data-dan-variabel
http://www.academia.edu/7491124/Pengertian_Array_dan_Contoh_Program_Array_1_dan_2_Dimensi
