Rangkuman Algoritma & Struktur Data
Saya akan membahas sedikit materi tentang Algortima dan Struktur Data, meliputi :
~ Bahasan 1 “Struktur Data, Array, Pointer & Struktur”
~ Bahasan 2 “Linked List”
~ Bahasan 3 “Stack”
~ Bahasan 4 “Queue”
~ Bahasan 5 “Rekursif”
~ Bahasan 6 “Sorting”
BAHASAN 1
Struktur Data, Array, Pointer & StruktuR
Konsep Dasar Struktur Data
Struktuk Data adalah sebuah
bagian dari ilmu pemrograman dasar yang mempuyai karakteristik yang terkait
dengan sifat dan cara penyimpanan sekaligus pengguna atau pengakses
data. Struktuk data bertujuan agar cara mereprentsikan data dalam membuat
program dapat dilakuian secara efesien dalam pengolahan di memori dan
pengolahan penyimpanan dari program ke storage juga lebih mudah dilakukan.
Konsep dasar Struktur Array
Array adalah kumpulan elemen-elemen data. Kumpulan elemen tersebut mempunyai susunan yang teratur. Jmlah elemen terbatas, dan semua elemen mempunyai tipe data yang sama. Jenis-jenis array :
·
Array Satu Dimensi
Struktur array suatu
dimensi dapat di deklarasikan dengan bentuk umum berupa: tipe_var nama_var
[ukuran];
Dengan:
- Tipe_var:
untuk menyatakan jenis elemen array (misalnya int,char,unsigned)
- Nama_var:
untuk menyatakan nama variable yang dipakai
- Ukuran:
untuk menyatakan jumlah maksimal elemen array.
Contoh : float nilai_ujian [5];
Array Dua Dimensi
Tipe data array dua dimensi
bisa digunakan ntuk menyimpan, mengolah maupun menampilkan suatu data
dalam bentuk table atau matriks. Untuk mendeklarasikan array agar dapat
menyimpan data adalah :
Tipe_var_nama_var[ukuran1][ukuran2];
Dimana :
- Ukuran 1
menunjukkan jumlah /nomor baris.
- Ukuran 2
menunukan jumlah /nomor kolom.
Jumlah elemen yang di milki
array dua dimensi dapat ditentukan dari hasil perkalian :
Ukuran 1 X ukuran 2.
Seperti halnya pada array
satu dimensi, data array dua dimensi akan ditempatkan pada memori secara
berurutan.
Array multidimensi /
Dimensi Banyak
Array berdimensi banyak
atau multidimensi terdiri dari array yang tidak terbatas hanya dua dimensi
saja. Bentuk umum pendeklarasian array multi dimensi adalah : tipe_var nama_var
[ukuran1][ukuran2]…[ukuran];
Contoh : int data_angka [3][6][6];
Konsep Dasar Pointer
Pointer adalah sebuah variable yang berisi alamat variable yang lain. Satu pointer dimaksudkan untuk menunjuk kesuatu alamat memori sehingga alamat dari suatu variable dapat diketahui dengan mudah.
Oprator pointer :
- Oprator
(‘&’) : untuk mendapatkan alamat memori
operand/variable ponter.
- Oprator
(‘*’) : untuk mengakses nilai data
operand/variable pointer.
Konsep Dasar Struktur
Struktur adalah koleksi dari variable yang dinyatakan sebuah nama, dengan sifat setiap variable dapat memiliki tipe yang berlainan. Struktur bisa dipakai untuk mengelompokkan beberapa informasi yang berkaitan menjadi sebuah satu kesatuan. Contoh sebuah struktur adalah informasi data tanggal, yang berisi tanggal, bulan, dan tahun.
a) Cara Mendeklarasikan Struktur :
Contoh pendefinisian tipe data Struktur adalah :
struct
Data_tanggal
{int tanggal;
Masing-masing tipe dari elemen struktur dapat berlainan. Adapun
variable_struktur1 sampai dengan variable_struktur M menyatakan bahwa variable
struktur yang dideklarasikan bisa lebih dari satu. Jika ada lebih dari satu
variable, antara variable struktur dipisahkan dengan tanda koma.
b)
Cara Mengakses Elemen
Struktur:
Elemen dalam struktur dapat diakses dengan mengguanakan bentuk:
Variable_struktur.nama_field
Antara variable_struktur dab nama_field dipisahkan dengan oprator
titik (disebut oprator anggota struktur). Contoh berikut merupakan intruksi untuk mengisikan
data pada file tanggal:
Tgl_lahir.tanggal=30
int bulan;
Int tahun;
};
Yang mendefinisikan tipe bernama data_tanggal, yang terdiri dari
tiga buah elemen berupa tanggal, bulan, dan tahun. Bentuk umum dalam
mendefenisikan struktur adalah :
Struct nama_tipe_struktur
{
Tipefiled1; tipefiled2; tipefiled3;
}variable_struktur….variable_strukturM;
BAHASAN 2
Linked List
Linked List adalah sejumlah objek
atau elemen yang dihubungkan satu dengan lainya sehingga membentuk suatu list.
Sedangkan objek atau elemen itu sendiri adalah merupakan gabungan beberapa
data(variable) yang dijadikan satu kelompok atau structure atau record yang
dibentuk dengan perintah struct. Syarat linked
list adalah harus dapat diketahui alamat simpul pertama atau biasa
dipakai variable First/Start/Header. Untuk menggabungkan objek
satu dengan lainya, diperlukan paling tidak sebuah variable yang bertipe
pointer.
Istilah-istilah dalam linked
list :
a) Simpul
Simpul terdiri dari dua bagian yaitu :
- Bagian data
- Bagian pointer yang menunjuk ke simpul berikutnya
b) First/Header
Variabel First/Header berisi alamat (pointer)/acuan (refrence)
yang menunjuk lokasi simpul pertama linked list, digunakan
sebagai awal penelusuran linked list.
c) Nill/Null
Tidak bernilai, digunakan
untuk menyatakan tidak mengacu ke manapun.
d) Simpul Terakhir(Last)
Simpul terakhir linked list berarti tidak menunjuk simpul berikutnya. Tidak terdapat alamat disimpan di field pointer di simpul terakhir.
Jenis-jenis linked
list :
1. List kosong
List kosong hanya terdiri dari sebuah penunjuk elemen yang berisi
NULL (kosong), tidak meiliki satu buah elemen pun sehingga hanya berupa penunjuk
awal elemen berisi NULL.
2. List tunggal
List tunggal adalah list yang elemenya hanya menyimpan informasi elemen setelahnya (next), sehingga jalanya pengaksesan list hanya dapat dilakukan secara maju. List tunggal terbagi menjadi tiga jenis yaitu list tunggal dengan kepala (first), list tunggal dengan kepala (first) dan ekor (tail), serta list tunggal yang berputar.
3. List ganda
List ganda adalah sebuah list yang elemenya menyimpan informasi
elemen sebelumnya dan informasi elemen setelahnya, sehingga proses penelusuran
list dapat dilakukan secara maju dan mundur. List ganda terbagi menjadi tiga
jenis yaitu list ganda dengan kepala (first), list ganda dengan kepala (first)
dan ekor (tail), serta list ganda yang berputar.
Operasi Dasar pada Linked List :
IsEmpty : Fungsi ini
menentukan apakah linked list kosong atau tidak.
Size : Operasi untuk
mengirim jumlah elemen di linked list.
Create : Operasi untuk
penciptaan list baru yang kosong.
Insertfirst : Operasi untuk
penyisipan simpul sebagai simpul pertama.
Insertafter : Operasi untuk
penyisipan simpul setelah simpul tertentu.
Installaast : Operasi untuk
penyisipan simpul setelah simpul terakhir.
Insertbefore : Operasi untuk
penyisipan simpul sebelum simpul tertentu.
Deletefirst : Operasi penghapusan
simpul pertama.
Deleteafter : Operasi untuk
penghapusan setelah simpul tertentu.
Deletelast : Operasi penghapusan
simpul terakhir.
BAHASAN 3
Stuck
Stack adalah
kumpulan elemen-elemen yang tersimpan dalam suatu tumpukan. Beberapa contoh penggunaan stack adalah pemanggilan
prosedur, perhitungan ekspresi aritmatika, rekursifitas, backtracking,
penanganan interupsi, dan lain-lain. Karakteristik penting stack sebagai
berikut:
1. Elemen stack yaitu item-item data di elemen stack
2. TOP (elemen puncak dari stack)
3. Jumlah elemen pada stack
4. Status/kondisi stack
Aturan
penyisipan dan penghapusan elemennya tertentu:
- Penyisipan
selalu dilakukan ”di atas” TOP
- Penghapusan
selalu dilakukan pada TOP
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 tersusun secara LIFO (Last In First Out).
- Penuh
Bila elemen di tumpukan mencapai kapasitas maksimum tumpukan. Pada kondisi ini, tidak mungkin dilakukan penambahan ke tumpukan. Penambahan di elemen menyebabkan kondisi kesalahan Overflow.
- Kosong
Bila tidak ada elemen tumpukan. Pada kondisi
ini, tidak mungkin dilakukan pengambilan elemen tumpukan. Pengambilan elemen
menyebabkan kondisi kesalahan Underflow.
Stack memiliki operasi-operasi pokok sebagai
berikut:
Push :
Untuk menambahka item pada tumpukan paling atas.
Clear : Untuk
mengosongkan stack.
IsEmpty : Untuk memeriksa apakah stack kosong.
IsFull :
Untuk memeriksa apakah stack sudah penuh.
Representasi stack:
- Representasi statis
Stack dengan representasi statis biasanya
diimplementasikan dengan menggunakan array. Sebuah array memiliki tempat yang
dialokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array
terbatas pada tempat yang ada pada array. Karena menggunakan array maka stack
dengan representasi statis dalam mengalami kondisi elemen penuh.
- Representasi dinamis
Stack dengan representasi dinamis biasanya
diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen
yang dialokasikan pada memori.Karena semua operasi pada
sebuah stack diawali dengan elemen yang paling atas maka jika menggunakan
representasi dinamis saat elemen ditambahkan akan menggunakan
penambahan elemen pada awal stack (addfirst) dan saat pengambilan atau
penghapusan elemen menggunakan penghapusan di awal stack (deffirst).
BAHASAN 5
Queue (antrian)
Queue/antrian adalah ordered list dengan penyisipan di
satu ujung, sedang penghapusan di ujung lain. Ujung penyisipan biasa
disebut rear/tail, sedang ujung penghapusa disebut front/head. Fenomena
yang muncul adalah elemen yang lebih dulu disisipkan akan juga lebih dulu
diambil. Queue berdisiplin FIFO (First In, First
Out). Queue merupakan kasus khusus ordered list. Dengan
karakteristik terbatas itu maka kita dapat melakukan optimasi representasi ADT
Queue untuk memperoleh kerja paling optimal.
Misalnya Queue Q= (a1,a2,a3…,an), maka :
1. Elemen a1 adalah elemen paling depan
2. Elemen ai adalah diatas elemen ai-1, di mana 1<i<n.
3. Elemen an adalah elemen paling belakang
Karakteristik penting dalam Queue sebagai
berikut:
§ Elemen antrian yaitu item-item data yang terdapat
dielemen antrian
§ Heat/font (elemen terdepan dalam antrian).
§ Tail/rear (elemen terakhir antrian).
§ Jumlah antrian pada antrian
(count).
§ Status/kondisi antrian, ada dua yaitu:
Penuh
Bila elemen pada antrian mencapai kapasitas
maksimum antrian. Pada kondisi ini, tidak mungkin dilakuakan penambahan ke
antrian. Penambahan di elemen menyebabkan kondisi kesalahan overflow.
Kosong
Bila tidak ada elemen antrian. Pada kondisi
ini, tidak mungkin dilakuakan pengambilan elemen antrian. Pengambilan elemen
menyebabkan kondisi kesalahan underflow
Operasi-operasi pokok pada antrian
diantaranya adalah:
1. Create
→ Membuat antrian baru.
2. IsEmpety → Untuk memeriksa apakah Antrian
sudah penuh atau belum.
3. IsFull→mengecek apakah Antrian sudah penuh
atau belum.
4. Enqueue/Insert → menambahkan elemen ke dalam
Antrian, penambahan elemen selaluditambahkan di elemen paling belakang.
5. Dequeue/Remove → untuk menghapus elemen
terdepan/pertama dari Antrian Algoritma QDELETE.
Penggunaan Queue
1) Simulasi antrian di dunia nyata, antara lain :
- Lalu lintas pesawat udara tinggal landas (take-off) dan pendaratan
(landing).
- Antrian pembelian tiket di depan oket untuk bis, kereta api,
bioskop.
- Antrian mobil di depan gerbang jalan tol.
- Antrian kendaraan di jalanan umum.
2) Sistem Produksi
- Barisan bahan atau komponen yang akan diproses suatu mesin.
- Barisan bahan atau komponen yang akan diproses suatu manusia
3) Sistem Komputer
- Pemrosesan banyak job (tugas) pada system multiprogramming.
4) Sistem Jaringan Komputer
- Pemrosesan banyak paket yang dating dari banyak koneksi pada
suatu host, bridge, gateway dll.
Representasi Queue
1. Representasi sekuen
· Representasi sekuen linear
· Representasi sekuen melingkar merupakan implementasi statik yang
lebih baik disbanding sekuen linear.
2. Representasi Dinamis (linked list).
BAHASAN 5
Rekursif
Rekursif dapat diartikan bahwa suatu
proses yang bisa memanggil dirinya sendiri, artinya fungsi tersebut dipanggil di dalam
tubuh fungsi itu sendiri. Contoh menghitung nilai faktorial. Rekursif sangat
memudahkan untuk memecahkan permasalahan yang kompleks.
Sifat-sifat rekursif:
- Dapat
digunakan ketika inti dari masalah terjadi berulang kali.
- Sedikit
lebih efisien dari iterasi tapi lebih elegan.
- Method-methodnya
dimungkinkan untuk memanggil dirinya sendiri.
Contoh paling sederhana dari proses rekursi adalah menghitung
nilai factorial dari bilangan bulat. Secara rekursif dapat ditulis sebagai :
#include<iostream>
#include<conio.h>
using namespace std;
int faktorial (int n){
if(n==1)
return(1);
else
return(n*faktorial(n-1));}
main(){
int
x;
printf("Mencari
Nilai Faktorial\n");
printf("Masukan
Nilai X :");
scanf("%d",&x);
printf("Nilai
Faktorial dari %d=%d\n",x,faktorial(x));
system("pause");
getch();}
BAHASAN 6
Sorting (pengurutan)
Sorting atau pengurutan
adalah proses menyusun elemen – elemen dari masukan awal acak menjadi keluaran
akhir tertata dengan urutan tertentu. Ada
dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu:
- Urutan
naik (ascending) yaitu dari data yang mempunyai nilai paling kecil
sampai paling besar.
- Urutan
turun (descending) yaitu dari data yang mempunyai nilai paling besar
sampai paling kecil.
Keuntungan dari data yang sudah dalam keadaan
terurut yaitu :
a. Data mudah dicari, mudah untuk dibetulkan,
dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita mudah
melakukan pengecekan apakah ada data yang hilang.Misalnya kamus bahasa, buku
telepon.
b. Mempercepat proses pencarian data yang harus
dilakukan berulang kali.
Beberapa algoritma metode
pengurutan dan prosedurnya sebagai berikut:
o Bubble Sort adalah suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya. Diberi nama “bubble”karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat,seperti gelembung
Algoritma bubble sort:
1. i=0
2. selama (i<N-1)kerjakan
baris 3 sampai 7
3. j=N-1
4. selama (j>=i)kerjakan
baris 5 sampai 7
5. jika (data
[j-1]>data[j]maka tukar data[j-1]dengan data[j]
6. j=j-1
7. i=i+1
Prosedur yang menggunakan metode gelembung :
void
BubbleSort(){
int
i,j;
for(i=1;
i<Max-1; i++)
for(j=Max-1;
j>=i;j-)
if(Data[j-1]>Data[j])
Tukar(&Data[j-1],&Data[j]);
}
o Selection Sort Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan plvot.
Algoritma seleksi :
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
Prosedur yang menggunakan metode seleksi :
void SelectionSort(){
inti,j,k;
for(i=0;i){
k
= i;
for(j=i+1;
j<Max;j++)
if(Data[k]>data[j])
k=j;
Tukar(&Data[i],&Data[k]);}
}
o Merge Sort adalah algoritma pengurutan yang berdasarkan pada strategi divide and conquer. Terdiri dari dua bagian utama, pembagian list yang diberikan untuk di-sort ke dalam beberapa sublist yang lebih kecil,dan sort (mengurutkan) dan merge (menggabungkan) sublist-sublist yang lebih kecil ke dalam list hasil yang sudah diurutkan.
Algoritma untuk merge sort sebagai berikut:
A. untuk kasus n=1,maka table a sudah terurut sendiirinya (langkah solve)
B. untuk kasus n>1,maka
- DEVIDE: bagi table a menjadi dua bagian,bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.
- CONQUER: secara rekursif,terapkan algoritma D-dan-C pada masing-masing bagian.
- MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.
Semoga rangkuman
"Algoritma & Struktur Data" ini bermanfaat dan apabila ada
salah kata di dalam blog yang saya tulis, saya minta maaf.
Jika ingin mengenal lebih dalam tentang Universitas saya, silahkan akses link berikut: umsida.ac.id, fst.umsida.ac.id
Sekian dan Terima Kasih.
Saniya Izza Fitria (201080200216)
Instagram : saniaizza_
Tidak ada komentar:
Posting Komentar