RANGKUMAN PRAKTIKUM ALGORITMA DAN STRUKTUR DATA
MODUL 1-6
Disusun Oleh:
Nama : Loranti Valentina
NIM :231080200049
Kelompok : 4
Assalamu’alaikum Wr.Wb.
Materi yang saya lampirkan ini merupakan hasil rangkuman dari materi praktikum Algoritma dan Struktur Data yang dilaksanakan selama satu semester ini untuk memenuhi tugas Praktikum Algoritma dan Struktur Data. Saya merupakan Mahasiswi Universitas Muhammadiyah Sidoarjo Program Studi Informatika Fakultas Sains dan Teknologi. Jika ingin mengetahui lebih detail tentang Universitas Muhammadiyah Sidoarjo bisa langsung mengakses link
umsida.ac.id atau fst.umsida.ac.id
POKOK BAHASAN 1
STRUKTUR DATA, ARRAY, POINTER, DAN STRUKTUR
PENDAHULUAN
Pada pokok bahasan ini berisi penjelasan disertai contoh mengenai konsep struktur data, array, pointer, dan struktur yang menjadi pemahaman dasar bagi mahasiswa sebelum mempelajari struktur data, dimana konsep array, pointer, dan struktur digunakan untuk mempresentasikan sebuah struktur data.
PENYAJIAN
(TUTORIAL)
A. Konsep
Dasar Struktur Data
Struktur data adalah sebuah bagian dari ilmu
pemrograman dasar yang mempunyai karakteristik yang terkait dengan sifat dan
cara penyimpanan sekaligus penggunaan atau pengaksesan data.
B. Konsep
Dasar Array
Array adalah kumpulan elemen-elemen data. Kumpulan elemen tersebut mempunyai susunan tertentu yang teratur. Jumlah elemen terbatas, dan semua elemen mempunyai tipe data yang sama. Jenis-jenis array :
a. Array Satu Dimensi
Struktur array satu dimensi dapat
dideklarasikan dengan bentuk umum berupa : tipe_var nama_nama [ukuran];
Dengan
:
- Tipe_var
: unutk menyatakan jenis elemen array (misalnya int, char, unsigned).
- Nama_var
: untuk menyatakan nama variab yang
dipakao.
- Ukuran
: untuk menyatakan jumlah maksimal elemen array.
Contoh : fload nilai_ujian [5];
b. Array Dua Dimensi
Tipe data array
dua dimensi bisa digunakan untuk menyimpan, mengolah maupun menampilkan suatu
data dalam bentuk tabel atau matriks. Untuk mendeklarasikan array agar dapat
menyimpan data adalah :
Tipe_var nama_var
[ukuran1][ukuran2];
Dimana :
- Ukuran1
menunjukkan jumlah/nomor baris.
- Ukuran2
menunjukkan jumlah/nomor kolom.
Jumlah elemen yang
dimiliki array dua dimensi dapat ditentukan dari hasil perkalian :
ukuran1 x ukuran2.
Seperti halnya
pada array satu dimensi, data array dua dimensi akan ditempatkan pada memori
secara berurutan.
c. Array Multidimensi /
Dimensi Banyak
Array berdimensi
banyak atau multidimensi terdiri dari array yang tidak terbatas hanya dua
dimensi saja. Bentuk umum pendeklarasian array multidimensi adalah : tipe_var
nama_var [ukuran1][ukuran2]…[ukurann];
Contoh : int
data_angka [3][6][6];
Mengakses Elemen Array :
Dalam Bahasa C++,
data array akan disimpan memori pada alokasi yang berurutan.
Elemen
pertama biasanya mempunyai indeks bernilai 0.
Contoh : Float
nilai_tes[5];
Inisialisasi
Array :
Array
dapat diinisialisasaikan secara langsung saat pertama kali dideklarasikan
(efisien
untuk array berdimensi sedikit).
Contoh : int x[2]={1,2};
Array dapat dideklarasikan terlebihan dahulu, baru
kemudian diisi elemennya.
Contoh :
Int x[2];
x[0]=1;
x[1]=2;
C. Konsep Dasar Pointer
Operator pointer :
Operator ‘&’ : untuk mendapatkan
alamat memori operand / varibel
pointer.
Operator ‘*’ : untuk mengakses nilai data
operand / variabel pointer.
D.
Konsep Dasar Struktur :
Struktur
adalah koleksi dari variabel yang dinyatakan dengan sebuah nama, dengan sifat
setiap variabel dapat memiliki tipe berlainan. Contoh sebuah struktur adalah informasi
data tanggal, yang berisi tanggal, bulan, dan tahun.
Mendeklarasikan Struktur :
Contoh
pendefinisian tipe data
struktur adalah : struct
data_tanggal
{int tanggal;
Masing-masing
tipe dari elemen struktur dapat berlainan. Jika ada lebih dari satu variabel,antara
variabel struktur dipisahkan dengan tanda koma.
Mengakses Elemen Struktur
:
Elemen
dari struktur dapat diakses dengan menggunakan bentuk :
variabel_struktur.nama_field
Antara
variabel_struktur dan nama_field dipisahkan dengan operator titik (disebut
operator anggota struktur). Contoh berikut merupakan intruksi untuk mengisikan
data pada field tanggal :
tgl_lahir.tanggal=30 int
bulan;
int tahun;
};
Yang
mendefinisikan tipe struktur bernama data_tanggal, yang terdiri dari tiga buah
elemen berupa tanggal, bulan, tahun. Bentuk umum dalam mendefinisikan dan
mendeklarasikan struktur adalah :
Struct
nama_tipe_struktur
{
Tipe
field1
; Tipe
field2
; Tipe
field3
;
}variabel_struktur1….variabel_strukturM;
POKOK BAHASAN 2
LINKED LIST (SENARAI)
PENDAHULUAN
Pada pokok bahasan ini akan dibahas mengenai struktur data senarai (list) yang pembahasannya meliputi definisi dan representasi list, jenis-jenis list serta operasi-operasi dasar pada list.
PENYAJIAN (TUTORIAL)
Linked List adalah sejumlah objek atau elemen yang dihubungkan satu dengan lainnya sehingga membentuk suatu list. Sedangkan objek atau elemen itu sendiri adalah merupakan gabungan beberapa data (variabel) yang dijadikan satu kelompok atau structure atau record yang dibentuk dengan perintah struct. Untuk menggabungkan objek satu dengan lainnya, diperlukan paling tidak sebuah variabel yang bertipe pointer. Syarat linked list adalah harus dapat diketahui alamat simpul pertama atau biasa dipakai variabel First/Start/Header. Struktur dasar sebuah list seperti gambar berikut :
Gambar
2.1 List Tunggal
Istilah-istilah
dalam linked list :
- Simpul
Simpul terdiri
dari dua bagian yaitu :
- First/Header
Variabel
First/header berisi alamat (pointer)/acuan (reference) yang
menunjuk lokasi simpul pertama linked list, digunakan sebagai awal
penelusuran linked list.
- Nil/Null
Tidak bernilai,
digunakan untuk menyatakan tidak mengacu ke manapun.
- Simpul
Terakhir
Simpul Terakhir
linked list berarti tidak menunjuk simpul berikutnya. Tidak terdapat alamat
disimpan di field pointer (bagian kedua dari simpul). Nilai null atau
nil disimpan di field pointer di simpul terakhir.
Jenis-jenis
linked list :
a. List Kosong
List Kosong hanya terdiri dari sebuah penunjuk elemen yang berisi NULL (kosong), tidak memiliki satu buah elemen pun sehingga hanya berupa penunjuk awal elemen berisi NULL.
b. List Tunggal
List tunggal
adalah list yang elemennya hanya menyimpan informasi elemen setelahnya (next), 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.
c. List Ganda
List ganda adalah sebuah
list yang elemennya menyimpan informasi elemen sebelumnya dan informasi elemen
setelahnya. 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 :
POKOK BAHASAN 3
STACK (TUMPUKAN)
PENDAHULUAN
Pada pokok bahasan ini akan dibahas mengenai data tumpukan atau stack, dimana stack merupakan suatu kumpulan data yang seolah-olah data yang diletakkan di atas data yang lain.
PENYAJIAN (TUTORIAL)
- Penyisipan
selalu dilakukan “di atas” TOP
- Penghapusan
selalu dilakukan pada TOP
Karena aturan
penyisipan dan penghapusan semacam itu, TOP adalah satu-satunya alamat terjadi
operasi, elemen yang ditambahkan paling akhir akan menjadi elemen yang akan
dihapus. Dikatakan bahwa elemen Stack secara LIFO (Last In First Out).
Beberapa contoh penggunaan stack adalah pemanggilan prosedur, perhitungan ekspresi aritmatika, rekursifitas, backtracking, penanganan interupsi, dan lain-lain.
Karakteristik penting stack sebagai berikut :
- 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 menambahkan item pada
tumpukan paling atas.
void
Push (ItemType x, Stack *S)
{
if (Full(S))
Printf("Stack
FULL");
else
{
S->Item[S->Count]=x;
++(S->count);
}
}
Pop : Untuk mengambil item teratas
int
Pop (Stack S, ItemType x)
{
if
(Empty (S))
Printf(“Stack
Kosong”);
else
{
--(S->Count);
x=s->Item(s->Count);
}
}
Clear : Untuk mengosongkan stack
void
Initialize Stack (Stack *S)
{
S->Count=0;
}
IsEmpty : Untuk memeriksa apakah stack kosong
int
Empty (Stack *S)
{
return
(S->Count==0);
}
IsFull : Untuk memeriksa apakah stack sudah
penuh
int
Full (Stack S)
{
return
(S-.>Count==MAXSTACK);
}
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.
Ilustrasi stack dengan representasi statis dapat dilihat pada gambar :
- Representasi
dinamis
Stack dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori.
Ilustrasi stack dengan represntasi dinamis dapat dilihat pada gambar :
POKOK BAHASAN 4
QUEUE (ANTRIAN)
PENDAHULUAN
8
Elemen Karakteristik penting-penting antrian sebagai berikut :
- Kosong, Bila tidak ada elemen antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.
Operasi-operasi pokok pada antrian
diantaranya adalah :
1. Create Membuat antrian baru.
NOEL(CREATE(Q)) = 0
FRONT(CREATE(Q)) = tidak
terdefinisi
REAR(CREATE(Q)) = tidak
terdefinisi
2. IsEmpty
Untuk memeriksa apakah Antrian sudah penuh atau belum.
ISEMPTY(Q) = True,jika Q adalah queue kosong.
3. IsFull mengecek apakah Antrian sudah penuh atau
belum.
ISFULL(Q) = True,jika Q adalah queue penuh.
4. Enqueue/Insert menambahkan elemen ke dalam Antrian,
penambahan elemen
selalu ditambahkan di elemen paling belakang.
REAR (INSERT(A,Q)) = A
ISEMPETY (INSERT(A,Q)) = FALSE
Algoritma QINSERT :
a. IF FRONT = 1 AND REAR
= N, OR IF FRONT = REAR +
1, THEN OVERFLOW, RETURN
b. IF FRONT := NULL,THEN
SET FRONT := 1 AND REAR := 1
ELSE IF REAR = N,
THEN SET REAR
:= 1
ELSE
SEF REAR := REAR+1
c. SET QUEUE[REAR] :=
ITEM
d. RETURN
5. Dequeue/Remove untuk menghapus elemen terdepan/petama
dari Antrian.
Algoritma QDELETE :
a. IF FRONT := NULL, THEN
UNDERFLOW, RETURN
b. SET ITEM :=
QUEUE[FRONT]
c. [FIND NEW VALUE OF
FRONT] IF FRONT =
REAR, THEN
SET FRONT := NULL AND REAR
;= NULL ELSE IF FRONT = N, THEN
SET FRONT := 1
ELSE
SET FRONT := FRONT+1
d. RETURN
Representasi queue :
Representasi
dinamis
POKOK BAHASAN 5
REKURSIF
PENDAHULUAN
a. Mengetahui dan memahami definisi rekursif.
b. Memahami sifat-sifat rekursif.
c. Mengaplikasikan rekursif.
PENYAJIAN (TUTORIAL)
· Dapat digunakan ketika inti dari masalah terjadi berulang kali.
POKOK BAHASAN 6
SORTING (PENGURUTAN)
PENDAHULUAN
Setelah
mempelajari bab ini diharapkan mahasiswa mampu :
a. Menunjukkan beberapa algoritma dalam
pengurutan.
b. Menunjukkan
bahwa pengurutan merupakan suatu persoalan yang bisa diselesaikan dengan
sejumlah algoritma yang berbeda satu sama lain.
c. Dapat memilih algoritma yang paling sesuai untuk menyelesaikan suatu permasalahan pemrograman.
PENYAJIAN (TUTORIAL)
· 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.
menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau lebih besar dari
yang lain didasarkan pada urutan relatif (collating sequence) seperti dinyatakan dalam table ASCII.
Keuntungan dari data yang sudah dalam keadaan terurut yaitu :
Data mudah dicari, mudah untuk dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadan
terurutkan, kita mudah melakukan pengecekan apakah ada yang hilang. Misalnya kamus
Bahasa, buku telepon.
Mempercepat proses
pencarian data yang harus dilakukan berulang kali.
Beberapa factor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain :
Banyak data yang
diurutkan.
Kapasitas
pengingat apakah mampu menyimpan semua data yang kita miliki.
Beberapa
algoritma metode pengurutan dan prosedurnya sebagai berikut:
1. Bubble
Sort
Bubble Sort adalah suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya. Apabila elemen sekarang > elemen berikutnya, maka posisinya ditukar. Kalau tidak, tidak perlu ditukar.
Data
paling akhir dibandingkan dengan data di depannya, jika ternyata lebih kecil
atau besar maka tukar sesuai dengan ketentuan(descending atau ascending). Dan
pengecekan yang sama dilakukan terhadap data yang selanjutnya sampai dengan
data paling awal.
2. Selection
Sort
Metode seleksi melakukan pengurutan dengan cara
mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai
acuan atau sering dinamakan pivot. Selama proses, pembandingan dan pengubahan
hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik
terjadi pada akhir proses. 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 elemen dalam keadaan terurutkan.
3. Merger
Sort
Algoritma Merge Sort ialah algoritma pengurutan yang
berdasarkan pada strategi divide and conquer. Algoritma ini
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. Pembagian bisa dikatakan cukup mudah karena
sublist-sublist tersebut dibagi ke dalam dua sublist yang ukurannya adalah
setengah dari ukuran semula. Hal ini terus diulang sampai sublist itu cukup
kecil untuk di-sort secara efisien (umumnya telah terdiri dari satu atau
dua elemen). Dalam Langkah merge dua sublist disatukan kembali dan
diurutkan pada saat yang sama. Algoritma untuk merge sort ialah sebagai
berikut :
A. Untuk kasus n=1, maka table a sudah terurut
sendirinya (langkah solver)
B. Untuk kasus n>1, maka :
a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.
b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian.
c.
MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang
terurut.
