Pengenalan Algoritma dan Struktur Program

Materi I

Pengenalan Algoritma dan Struktur Program Sasaran Perkuliahan : 1) Mahasiswa dapat memahami definisi algoritma 2) Mahasiswa dapat memahami ciri, syarat dan kriteria algoritma 3) Mahasiswa dapat mengetahui cara penulisan algoritma 4) Mahasiswa dapat mengetahui struktur alur algoritma 5) Mahasiswa dapat mengetahui struktur program yang akan digunakan untuk mengimplementasikan algorima 1. Definisi Algoritma Definisi algoritma diuraikan secara beragam dari berbagai literatur. Walaupun definisi satu dengan yang lain bisa saja berbeda, tapi semuanya mendekatkan diri pada tata cara penulisan suatu bahasa pemrograman yang bentuknya umum. Sehingga dalam mempelajari algoritma akan dikaitkan dengan program yang dibentuk atau ditulis dalam suatu bahasa yang disebut dengan bahasa pemrograman walaupun sebenarnya algoritma itu sendiri tidak terikat dengan salah satu bahasa pemrograman manapun. Contoh dari bahasa pemrograman yaitu bahasa COBOL, bahasa BASIC, bahasa Pascal, bahasa C, bahasa java dan lain sebagainya. Dalam diktat ini, algoritma yang akan dipelajari lebih mendekatkan dengan bahasa C++, bahasa pemrograman yang mempunyai struktur yang baik sehingga mudah untuk dipahami dengan kompiler dan tools menggunakan Microsoft Visual C++ dan Borland C++ 5.02. Pada dasarnya algoritma adalah alur pikiran dalam menyelesaikan suatu pekerjaan yang dituangkan dalam bentuk tertulis yang dapat dimengerti oleh orang lain. Alur pikiran seseorang dapat berbeda dengan alur pikiran orang lain dalam menyelesaikan pekerjaan yang sama dengan hasil yang sama walaupun ditempuh dengan cara yang berbeda. Algoritma juga diartikan sebagai urutan langkah-langkah yang dinyatakan dengan jelas dan tidak rancu untuk memecahkan suatu masalah dalam rentang waktu tertentu. Artinya, setiap langkah harus dapat dikerjakan dan mempunyai efek tertentu, sehingga langkahlangkah yang tidak dapat dikerjakan dan tidak menghasilkan efek tertentu tidak dapat disebut algoritma. Bila dikaitkan dengan bahasa pemrograman, secara bebas definisi algoritma yang akan dipelajari adalah sekumpulan instruksi, yang apabila dijalankan, akan menyelesaikan suatu tugas tertentu. Sedangkan kata algoritma sendiri diambil dari nama ilmuwan muslim yaitu Abu Ja’far Muhammad bin Musa Al-Khwarizmi. 2. Syarat, Ciri & Kriteria Algoritma Secara umum syarat atau ciri dari algoritma sebagai berikut : a. Algoritma harus tidak ambigu (unambiguous) Deskripsi langkah-langkah dalam algoritma harus dan hanya mempunyai tafsiran tunggal. b. Algoritma harus tepat (precise) Algoritma harus menyatakan urutan-urutan langkahnya. c. Algoritma harus pasti (definite) Setiap instruksi jelas maksudnya dan tidak meragukan, sehingga jika serangkaian langkah yang sama dilakukan dua kali maka hasilnya harus selalu sama. d. Algoritma harus berhingga (finite) Algoritma baik secara keseluruhan maupun sub algoritma bila ditelusuri harus ada titik berhentinya.

Algoritma & Struktur Data 1 - STMIK Atma Luhur Okkita Rizan - Hamida

1

e. Algoritma tidak harus ada data masukan yang dimasukkan dari luar f. Algoritma paling tidak ada satu buah keluaran 3. Cara Penulisan Algoritma Penulisan algoritma setidaknya ada 3 cara untuk menguraikannya, yaitu : a. Uraian Deskriptif Adalah uraian yang menggunakan bahasa yang biasa digunakan sehari-hari. Pengurutan bilangan genap pada kasus diatas merupakan contoh penulisan algoritma menggunakan uraian deskriptif. b. Pseudocode Yang dimaksud dengan pseudocode adalah kode atau tanda atau ceritera yang menyerupai atau merupakan (pseudo) penjelasan cara menyelesaikan persoalan. Kode atau tanda atau ceritera tersebut ditulis dalam suatu bahasa yang dimengerti oleh manusia. Pseudocode dapat dikembangkan sendiri, asalkan arti dari setiap kode disepakati bersama. Algoritma dalam contoh kasus diatas jika dituliskan kedalam bentuk pseudocode menjadi : input (b) i 0 j 0 while (i <= b) do ii+j jj+1 if i mod 2 = 0 then output (i) end

c.

Flowchart (Bagan Alir) Adalah penulisan algoritma dengan menggunakan notasi grafik atau gambar. Terdapat lima macam bentuk gambar atau notasi dasar yang dianggap baku dalam penggambaran flowchart. Terminal / Notasi kapsul, untuk menggambarkan START (Mulai) dan END (Selesai). Terminal hanya sebagai tanda, tidak melakukan suatu pekerjaan khusus. I/O, Input/Output Operation atau Notasi jajaran genjang, untuk menggambarkan pembacaan data (input/read) dan untuk menampilkan data atau proses tulis (output/write). Process atau notasi empat persegi panjang, menggambarkan proses dalam bagan alir.

Decision atau notasi belah ketupat menggambarkan keputusan sesuai dengan suatu kondisi. Notasi ini mempunyai dua panah keluar (dua nilai keluaran) yang bernilai true (ya, benar) dan false (tidak, salah). Garis, untuk menyatakan urutan pelaksanaan atau alur proses.


2

Dari contoh kasus diatas, flowchartnya dapat digambarkan sebagai berikut : START

input (b)

i0 j0

i
true

ii+j jj+1

false

i mod 2 = 0

true

false output (i)

END

4. Struktur Alur Algoritma Algoritma mempunyai 3 macam struktur alur, yaitu : a. Struktur Sequential Pada struktur ini, perintah-perintah atau instruksi dilaksanakan secara berurutan sesuai dengan urutan penulisannya. Contoh : A0 B0 N5 for I  1 to n do AA+2 BA+3 end output (A) output (B)

Atau : A  0 ; B  0 ; N  5; for I  1 to n do AA+2;BA+3; end output (A); output (B);

Pada contoh diatas, perintah atau instruksi yang dilingkari termasuk kedalam struktur sequential pada algoritma.


3

b. Struktur Conditional Branch / Selection Pada struktur ini memungkinkan beberapa perintah/instruksi tidak dikerjakan, karena struktur ini alur algoritma akan menjadi bercabang, sehingga hanya alur perintah yang terseleksi/terpenuhi saja yang akan dikerjakan. Ada dua macam struktur Conditional Branch yaitu : 1) Simple Conditional Branch (menggunakan if statement) 2) Multiway Conditional Branch (menggunakan case statement) Mengenai kedua macam struktur ini, akan dibahas lebih lanjut pada bab berikutnya. Contoh : 1) 2) 3) 4) 5) 6) 7)

input (a) if (a <= 5) then a  a + 100 else a  a – 100 end output(a)

Pada contoh diatas, jika a diinput dengan nilai 5 maka instruksi yang akan dikerjakan yaitu 1, 2, 3, 6, 7. Tetapi jika a diinput dengan nilai 6, maka instruksi yang akan dikerjakan yaitu 1, 2, 4, 5, 6, 7. Berikut flowchart dari contoh diatas : START

input (a)

false

a<5

a  a - 100

true

a  a + 100

output (a)

END


4

c.

Struktur Loop Struktur ini memungkinkan beberapa perintah atau instruksi akan dikerjakan berulangulang. Ada dua macam struktur loop yaitu : 1) Unconditional Loop 2) Conditional Loop Untuk dua macam struktur loop ini akan dibahas lebih lanjut pada bab berikutnya. Contoh : 1) 2) 3) 4) 5) 6) 7) 8) 9)

T0 I1 WHILE I <= 100 DO READ(A) TT+A II+1 ENDDO WRITE(T)

Pada contoh diatas perintah-perintah yang termasuk kedalam struktur loop adalah 3, 4, 5, 6, 7, 8. Perintah-perintah tersebut akan dikerjakan berulang sesuai dengan kondisi yang diberikan. 5. Bahasa Pemrograman C++ Cikal bakal dari Bahasa Pemrograman C++ adalah bahasa C yang dikembangkan mulai awal tahun 1980 oleh Bjarne Stroustrup dari AT&T Bell Laboratories. Bahasa Pemrograman C++ merupakan pengembangan dari bahasa C dan pengembangannya diresmikan pada tahun 1985. Tahun 1989, dunia pemrograman C mengalami peristiwa penting dengan dikeluarkannya standar bahasa C oleh American National Standars Institute (ANSI), yang kemudian dikenal dengan nama ANSI C. Sebenarnya bahasa C++ mengalami dua tahap evolusi. Bahasa C++ yang pertama, dirilis oleh AT&T Laboratories dan dinamai dengan cfront. Bahasa C++ versi pertama ini hanya berupa kompiler yang menterjemahkan C++ menjadi bahasa C. Pada evolusi selanjutnya, Borland International Inc. mengembangkan kompiler C++ menjadi sebuah kompiler yang mampu mengubah C++ langsung menjadi bahasa mesin (assembly). Sejak evolusi ini, mulai tahun 1990 C++ menjadi bahasa berorientasi obyek yang digunakan oleh sebagian besar pemrogram professional (sumber : wikipedia.org).


5

6. Struktur Program C++ Setiap bahasa pemrograman mempunyai ciri dan struktur program tersendiri. Struktur program menjadi bagian dari program yang akan dibuat. Struktur dari program memberikan gambaran secara luas, bagaimana bentuk dari program secara umum. Adapun struktur utama dari bahasa pemrograman C++ adalah :

void main ( ) { statement ; statement ; statement ; }

Struktur dari program C++ dapat dilihat dan pada hakekatnya adalah tersusun dari sebuah atau lebih blok-blok fungsi. Fungsi pertama yang harus ada di program C++ adalah main(), fungsi yang sudah ditentukan. Fungsi ini lah yang menjadi titik awal dan titik akhir eksekusi dari program. C++ juga merupakan bahasa pemrograman yang bersifat case sensitive, yang berarti penulisan program menggunakan huruf kapital ataupun huruf kecil pada kode program dapat berarti lain. Pasangan kurung kurawal menandakan awal dan akhir kumpulan dari instruksiinstruksi yang akan dikerjakan di dalam fungsi. Setiap instruksi atau baris-baris perintah harus diakhiri dengan titik koma untuk menandakan akhir dari satu baris perintah. C++ menyediakan file judul (header file) yaitu file yang diantaranya berisi deklarasi fungsi dan definisi konstanta. File-file ini mempunyai ciri yaitu namanya diakhiri dengan ekstension .h. Apabila file judul tersebut akan digunakan pada suatu program, maka file judul tersebut harus diikut sertakan didalam program dengan menggunakan pengarah praprosesor. Pengarah praprosesor yang dipakai untuk membaca file judul adalah #include. Bentuk umum #include

#include atau #include “namafile”

Berikut adalah contoh program sederhana dari bahasa pemrograman C++ : Nama Program : contoh1.cpp


6

Materi II

Tipe Data, Variabel, Konstanta dan Operator Sasaran Perkuliahan : 1) Mahasiswa dapat memahami 2) Mahasiswa dapat memahami 3) Mahasiswa dapat memahami 4) Mahasiswa dapat memahami

mengenai mengenai mengenai mengenai

Tipe Data Variabel Konstanta Operator

1. Tipe Data Tipe data adalah pengelompokkan data berdasarkan isi dan sifatnya. Didalam pemrograman, sifat dari data adalah karakter, bilangan bulat, bilangan pecahan atau boolean. Tipe Data biasanya selalu berpasangan dengan variabel. Berikut Tabel Tipe Data Dasar (Basic Data Type) yang digunakan dalam Bahasa C++.

Sebutan Tipe Data

Character

Integer

Bentuk Penulisan Dalam Bahasa C

Jumlah Byte Yang Diperlukan

Jangkauan Nilai Numerik

char atau signed char

1

-128 s.d 127

unsigned char

1

0 s.d 255

2

- 32768 s.d 32767

2

0 s.d. 65535

4

- 2147483648 s.d 2147483647

4

0 s.d. 4294967295

4

3.4E-38 s.d 3.4E38 Positif atau negatip

int atau signed int atau signed unsigned int atau unsigned long atau long int atau signed long atau signed long int unsigned long atau unsigned long int

Floating point single precision

Float


7

Floating point double precision

double

8


long double

10


2. Variabel Secara umum variabel adalah suatu simbol atau lambang yang mempunyai nilai. Secara teknis dalam pemrograman yang dimaksud dengan variabel adalah area atau tempat didalam memory komputer yang isinya dapat diubah-ubah yang digunakan untuk menampung suatu nilai dan/atau mengambil nilai tersebut. Variabel didefinisikan/dideklarasikan menggunakan kombinasi antara identifier, type dan dapat juga sekaligus diinisialisasi (pemberian nilai awal). Nama dari variabel ditentukan atau dikarang sendiri oleh pembuat program. Ada beberapa aturan dalam pemberian nama variabel yaitu :  Tidak boleh sama dengan nama atau kata yang sudah disiapkan oleh komputer (reserved word) seperti keyword dan functions.  Maksimum 32 karakter, bila lebih dari 32 karakter, maka karakter selebihnya tidak diperhatikan oleh komputer.  Huruf besar (kapital) dan huruf kecil berbeda (case sensitive)  Karakter pertama harus huruf atau karakter garis bawah (under score), dan karakter berikutnya boleh huruf atau angka, atau karakter garis bawah.  Tidak boleh mengandung spasi atau blank. Bentuk Umum Pendeklarasian Variabel adalah : tipe_data nama_variabel ; atau tipe_data nama_variabel = nilai_variabel ;

Adapun contoh programnya sebagai berikut : Nama Program : variabel.cpp


8

Penjelasan Program : - int bulat, float pecah : adalah proses pendeklarasian variabel. Variabel yang dibuat sebanyak 2 buah yaitu variabel dengan nama bulat dan variabel dengan nama pecah. Variabel bulat digunakan untuk menampung bilangan bulat sedangkan variabel pecah digunakan untuk menampung bilangan pecahan. - bulat = 10, pecah = 2.5 : adalah perintah penugasan (Assignment Statement) mengisi nilai/angka kedalam masing-masing variabel. - /n : adalah perintah ganti baris. Berikut contoh program menggunakan variabel dengan angka yang akan diisi ke dalam variabel tersebut diinput terlebih dahulu : Nama Program : variabelinput.cpp

Penjelasan Program : - cin : adalah perintah untuk menginput data. Data yang diinput akan ditampung kedalam variabel yang sudah ditentukan. 3. Konstanta Pada dasarnya konstanta memiliki kesamaan dengan variabel yaitu sebuah tempat untuk menyimpan sebuah nilai sesuai dengan datanya, hanya saja nilai yang ada dalam konstanta tidak dapat diubah-ubah dan hanya dapat digunakan atau diakses. Konstanta biasanya digunakan untuk menyimpan sebuah nilai yang sering digunakan atau nilai yang sudah pasti. Contohnya jari-jari lingkaran. Dalam bahasa C++ konstanta dapat menggunakan preprocessor directive #define. Bentuk Umum Pendeklarasian Konstanta adalah : #define nama_konstanta nilai_konstanta

Contoh programnya sebagai berikut :


9

Nama Program : konstanta.cpp

4. Operator Operator yang digunakan didalam pemrograman antara lain : a. Operator Aritmatika Beberapa operator aritmatika yang dapat digunakan dalam pemrograman adalah : 1) Operator Perkalian Simbol operator perkalian adalah tanda bintang/asterik (*). Contoh : 5*2 2) Operator Penjumlahan Simbol operator penjumlahan adalah tanda tambah/plus (+). Contoh : 5+2 3) Operator Pengurangan Simbol operator pengurangan adalah tanda kurang/minus (-). Contoh : 5-2 4) Operator Pembagian Simbol operator pembagian adalah tanda garis miring (/). Contoh : 5/2 5) Operator Sisa Hasil Bagi Simbol Operator sisa hasil bagi adalah tanda persen (%). Contoh : 5%2 Contoh Programnya sebagai berikut : Nama Program : aritmatika.cpp


10

b. Operator Relasi Yaitu operator yang biasa digunakan untuk membandingkan dua buah nilai. Hasil dari operator ini adalah Benar (TRUE) atau Salah (FALSE). Operator-operator relasi yang dapat digunakan dalam pemrograman sebagai berikut :  Operator sama dengan Simbol operator yang digunakan adalah “ == ”, operator ini menyatakan bahwa nilai yang dibandingkan antara dua operan adalah sama. Contoh : a == b  Operator tidak sama dengan Simbol operator yang digunakan adalah “ !=”, operator ini menyatakan bahwa nilai yang dibandingkan antara dua operan tidak sama. Contoh : a != b  Operator lebih dari Simbol operator yang digunakan adalah “ > ”, operator ini menyatakan bahwa nilai operan pertama lebih besar dari nilai operan yang kedua. Contoh : a > b  Operator kurang dari Simbol operator yang digunakan adalah “ < ”, operator ini menyatakan bahwa nilai operan pertama lebih kecil dari nilai operan yang kedua. Contoh : a < b  Operator lebih dari sama dengan Simbol operator yang digunakan adalah “ >= ”, operator ini menyatakan bahwa nilai operan pertama lebih besar dari atau sama dengan nilai operan yang kedua. Contoh : a >= b  Operator kurang dari sama dengan Simbol operator yang digunakan adalah “ <= ”, operator ini menyatakan bahwa nilai operan pertama lebih kecil dari atau sama dengan nilai operan yang kedua. Contoh : a <= b Contoh programnya sebagai berikut : Nama Program : relasi.cpp


11

c.

Operator Logika Bolean Yaitu operator yang biasa digunakan untuk mengaitkan dua buah ungkapan kondisi menjadi sebuah kondisi. Operator-operator logika Boolean yang biasa digunakan dalam pemrograman adalah :  Operator dan (AND) Simbol operator yang digunakan adalah “ && ”. Ungkapan Kondisi 1 B B S S

Ungkapan Kondisi 2 B S B S

Hasil Operator Logika dan B S S S

B = Benar, S = Salah. Dari table diatas dapat disimpulkan bahwa hasil operator akan BENAR jika kedua ungkapan kondisi tersebut, kedua-duanya Benar. 

Operator atau (OR) Simbol operator yang digunakan adalah “ || ”. Ungkapan Kondisi 1 B B S S

Ungkapan Kondisi 2 B S B S

Hasil Operator Logika dan B B B S

B = Benar, S = Salah Dari table diatas dapat disimpulkan bahwa hasil operator akan BENAR jika kedua atau salah satu ungkapan kondisi tersebut Benar. 

Operator bukan / negasi (NOT) Simbol operator yang digunakan adalah “!”. Operator ini berfungsi pembalik nilai logika TRUE menjadi FALSE atau nilai logika FALSE menjadi TRUE. Ungkapan Kondisi 1 B S

Hasil Operator Logika bukan S B

Misalkan ada dua bilangan, x = 5 dan y = 6. Jika dibentuk menjadi satu kondisi sehingga menjadi (x==y), maka kondisi tersebut bernilai TRUE. Bila dikenai dengan operator bukan, kondisi tersebut menjadi !(x==y), nilai kondisi sebelumnya bernilai TRUE berubah menjadi FALSE.


12

Contoh programnya sebagai berikut : Nama Program : boolean.cpp


13

Materi III

Pencabangan atau Seleksi Sasaran Perkuliahan : 1) Mahasiswa dapat mengetahui beberapa struktur pencabangan 2) Mahasiswa dapat memahami alur/cara kerja struktur pencabangan 3) Mahasiswa dapat menyusun algoritma menggunakan struktur pencabangan 4) Mahasiswa dapat membuat program menggunakan struktur pencabangan Salah satu struktur alur algoritma adalah pencabangan. Pencabangan bermanfaat untuk menentukan satu dari sekian banyak pilihan yang telah disediakan. Didalam pemrograman, pencabangan akan mengakibatkan ada beberapa baris perintah yang tidak akan dikerjakan/dilewati sama sekali, karena pencabangan membentuk kelompok/blok tersendiri yang akan dikerjakan atau tidak ditentukan berdasarkan kondisinya. Dalam pencabangan, dikenal dengan istilah kondisi (condition). Kondisi ini yang menentukan blok/kelompok dari baris perintah dikerjakan atau tidak sama sekali. Kondisi bertugas untuk membandingkan dua atau lebih operan. Operator yang digunakan untuk membandingkan operan tersebut tentu saja menggunakan operator relasi. Hasil akhir dari kondisi adalah nilai BENAR (TRUE) atau SALAH (FALSE). Contohnya sebagai berikut : NO 1 2 3 4

KONDISI 5 5 5 5

>2 == 2 <= 7 != 2

NILAI TRUE FALSE TRUE TRUE

Pencabangan dibedakan menjadi dua macam, yaitu simple conditional branch dan multiway conditional branch. Berikut adalah penjelasan dari kedua macam bentuk pencabangan tersebut. 1. Simple Conditional Branch Control statement yang menjadi bagian simple conditional branch adalah control statement if. Control statement if terbagi menjadi 3 macam sesuai dengan keperluannya, yaitu IF-THEN, IF-THEN-ELSE dan NESTED IF. a) IF - THEN Ciri dari bentuk pencabangan ini hanya memiliki satu buah grup/kelompok baris perintah yang akan dikerjakan apabila kondisinya BENAR/TRUE. IF-THEN digunakan apabila hanya mempunyai satu pilihan/pilihan tunggal saja. Bentuk Umum Instruksi IF – THEN dan Flowchart adalah sebagai berikut :

if (cond) { statement true ; }

cond

false

true

Statements True

next instruction


next instruction

14

Urutan pelaksanaan perintah :  Periksa nilai kondisi pada pencabangan (cond = kondisi), apakah bernilai TRUE atau FALSE .  Bila kondisi bernilai TRUE maka blok perintah (grup/kelompok baris perintah) / statements true akan dikerjakan, setelah selesai maka langsung mengerjakan next instruction.  Bila kondisi bernilai FALSE, maka langsung meloncat mengerjakan next instruction. Berikut contoh program menggunakan IF-THEN : Nama Program : ifthen.cpp

Output Program : - Kondisi bernilai BENAR/TRUE.

-

Kondisi bernilai SALAH/FALSE.


15

b) IF - THEN - ELSE Ciri dari bentuk pencabangan ini memiliki dua buah grup/kelompok baris perintah. Masingmasing grup mewakili hasil akhir dari kondisinya. Grup/kelompok baris perintah yang pertama akan dikerjakan apabila kondisi bernilai BENAR/TRUE, sedangkan grup/kelompok baris perintah yang kedua akan dikerjakan apabila kondisi bernilai SALAH/FALSE. IF-THEN-ELSE digunakan apabila mempunyai dua pilihan. Bentuk Umum Instruksi IF – THEN – ELSE dan Flowchart sebagai berikut : if (cond) { statement true ; } else { statement false ; }

false

cond

Statements True

Statements False

next instruction

true

next instruction

Urutan pelaksanaan perintah :  Periksa nilai kondisi pada pencabangan ( cond = kondisi), apakah bernilai TRUE atau FALSE .  Bila kondisi bernilai TRUE maka blok perintah (grup/kelompok baris perintah) / statements true akan dikerjakan, setelah selesai maka langsung mengerjakan next instruction.  Bila kondisi bernilai FALSE maka blok perintah (grup/kelompok baris perintah) / statements false akan dikerjakan, setelah selesai maka langsung mengerjakan next instruction. Berikut contoh program menggunakan IF-THEN-ELSE : Nama Program : ifthenelse.cpp


16

Output Program : - Kondisi bernilai BENAR/TRUE

-

Kondisi bernilai SALAH/FALSE

c) NESTED IF Disebut juga dengan if bersarang/pencabangan bersarang. NESTED IF digunakan apabila pilihan lebih dari dua. Bentuk pencabangan ini memiliki lebih dari dua grup/kelompok baris perintah dan kondisi lebih dari satu. Tidak ada bentuk yang baku dari NESTED IF, karena NESTED IF dibentuk menggunakan kombinasi antara IF-THEN dan IF-THEN-ELSE. Berikut adalah contoh dari bentuk-bentuk NESTED IF dan flowchartnya :





if (cond1) { if (cond2) { S1 } } else { S2 }

if (cond1) { if (cond2) { S1 } else { S2 } } else { S3 }

false

cond1

true

cond2

false

S2

false


S2

S1

true

cond1

false

S3

true

cond2

true

S1

17





if (cond1) { S1 if (cond2) { S2 } S3 } else { if (cond3) { S4 } else { S5 } } if (cond1) { S1 if (cond2) { S2 } else { S3 } } else { if (cond3) { S4 } else { S5 } S6 }

false

false

cond3

cond1

true

true

S5

S1

S4

cond2

true

false S2

S3

false

false

cond3

S5

cond1

true

true

S1

S4

false

true

cond2

S3

S2

S6


18



if (cond1) { if (cond2) { if (cond3) { if (cond4) { S1 } }

cond1

true

true

cond2

cond3

true

false cond4

false

true

false

S1

false

} }



if (cond1) { S1 } else { if (cond2) { S2 } else { false if (cond3) { S3 S5 } else { if (cond4) { S4 } else { S5 } } } }


false

false

false

cond4

cond3

true

cond2

true

cond1

true

true

S1

S2

S3

S4

19

Berikut contoh program menggunakan NESTED IF dengan 3 pilihan/blok perintah: Contoh Program : nestedif.cpp

Output Program : - Pilihan dengan grup/kelompok baris perintah yang pertama

-

Pilihan dengan grup/kelompok baris perintah yang kedua

-

Pilihan dengan grup/kelompok baris perintah yang ketiga


20

2. Multiway Conditional Branch Control statement yang menjadi bagian multiway conditional branch adalah control statement switch case. Switch case dapat digunakan untuk satu, dua atau lebih dari dua pilihan. Khusus untuk pilihan dari dua, switch case sama dengan nested if, tetapi ada beberapa perbedaan dari kedua control statement tersebut diantaranya : a. Pernyataan switch berbeda dengan pernyataan if dimana switch hanya dapat menguji kesamaan, sedangkan pernyataan if dapat melakukan evaluasi sembarang tipe ekspresi Boolean. Dengan demikian switch terlihat seperti hanya mencocokkan diantara nilai-nilai ekspresi dan konstanta-konstanta case. b. Tidak ada konstanta case di blok case yang sama dapat mempunyai nilai yang identik. c. Pernyataan switch biasanya lebih efisien dibanding if bersarang yang dalam. Bentuk Umum Control Statement Switch Case :

switch(nama_variabel) { case nilai_variabel_1 : statement_1 ; break ; case nilai_variabel_2 : statement_2 ; break ; …………………………….. case nilai_variabel_n : statement_n ; break ; default : statement_default ; break ; }

Perintah break berfungsi untuk keluar dari case. Jika break ditiadakan, maka akan dilanjutkan dengan pelaksanaan dibawahnya sampai selesai. Perintah break merupakan optional, tergantung kebutuhan program. Adakalanya diperlukan untuk menjalankan case sekaligus, hal ini berarti perintah break tidak digunakan. Contoh program menggunakan switch case sebagai berikut :


21

Nama Program : switchcase.cpp

Output Program :


22

Materi IV

Perulangan atau Iterasi Sasaran Perkuliahan : 1) Mahasiswa dapat mengetahui beberapa struktur perulangan 2) Mahasiswa dapat memahami alur/cara kerja struktur perulangan 3) Mahasiswa dapat menyusun algoritma menggunakan struktur perulangan 4) Mahasiswa dapat membuat program menggunakan struktur perulangan Salah satu struktur alur algoritma adalah perulangan. Persamaan perulangan dan pencabangan adalah sama-sama membentuk grup/kelompok baris perintah yang akan dikerjakan atau tidak berdasarkan hasil akhir kondisinya. Perbedaannya struktur perulangan akan mengerjakan grup/kelompok baris perintah secara berulang-ulang selama kondisi masih terpenuhi. Dalam bahasa pemrograman struktur alur algoritma ini biasa disebut dengan looping. Perulangan mempunyai beberapa bagian yang harus dipenuhi, antara lain : a. Inisialisasi Inisialisasi adalah tahap persiapan membuat kondisi awal sebelum melakukan perulangan, misalnya mengisi variabel dengan nilai awal. Tahap ini dilakukan sebelum memasuki bagian perulangan. b. Proses Tahap proses terjadi didalam bagian perulangan yaitu berisi semua proses yang perlu dilakukan secara berulang-ulang. c. Iterasi Iterasi terjadi di dalam perulangan yakni merupakan kondisi pertambahan agar perulangan dapat terus berjalan. d. Terminasi Terminasi adalah kondisi berhenti dari perulangan, kondisi berhenti sangat penting dalam perulangan agar perulangan dapat berhenti, tidak menjadi perulangan yang tanpa henti. Bentuk dasar dari struktur perulangan ada 3 macam yaitu : for, while dan do while. 1. For Bentuk Umum Perulangan For : for (init ; cond; chng cond) { Statements ; } Next instruction Prinsip Kerja Perulangan For : a. Perintah init merupakan memberi nilai awal kondisi (inisialisasi). Perlu mempersiapkan sebuah variabel untuk menampung nilai awal kondisi. b. Kemudian dilanjutkan dengan memeriksa kondisi pada cond, jika bernilai BENAR/TRUE maka Statements akan dikerjakan. Setelah selesai baris perintah melaksanakan chng cond, yang berfungsi untuk mengubah nilai variabel. Kemudian kembali ke point b memeriksa kondisi dan seterusnya. c. Jika kondisi sudah bernilai SALAH/FALSE, maka perulangan akan selesai dan melaksanakan baris perintah berikutnya (next instruction).


Initialization (init)

Condition (cond) true Statements

Change Condition (chng cond)

23 Next Instruction

false

Adapun contoh program menggunakan for adalah sebagai berikut : Nama Program : for.cpp

Penjelasan Program : - i=1, merupakan proses init(initialization), variabel dengan nama i diisi dengan angka 1. - i<=5, merupakan cond(condition), kondisi akan bernilai TRUE selama nilai variabel i kurang atau sama dengan 5. - i++, merupakan chng cond (change condition), i++ sama artinya dengan i=i+1. Dengan perintah tersebut nilai variabel i akan berubah secara berurutan dari 1 s.d 5. - Output program menunjukkan perulangan akan dilakukan selama 5 kali mengikuti status kondisi dan status change condition. 2. While Prinsip Kerja struktur While sama dengan struktur For. Perbedaannya pada bentuk strukturnya. Bentuk umum struktur while : init ; while (cond) { Statements ; } Contoh programnya sebagai berikut : Nama Program : while.cpp


24

3. Do..While Nama lain dari struktur do..while adalah repeat until. Perbedaan struktur ini dengan struktur looping sebelumnya terletak pada bentuk strukturnya dan cara kerjanya. Yang menjadi ciri utama dari do..while, grup/kelompok baris perintah perulangan paling tidak dikerjakan satu kali walaupun kondisi perulangan bernilai SALAH/FALSE. Grup/kelompok baris perintah dikerjakan terlebih dahulu sebelum memeriksa kondisinya. Bentuk umum struktur do..while sebagai berikut : Initialization

initialization do { Statements ; Change Condition ; } while (condition) ;

Statements

Change Condition

next Instruction true Prinsip Kerja Struktur Perulangan Do..While : a. Initialization bermaksud memberi nilai awal kondisi. Perlu mempersiapkan sebuah variabel untuk menampung nilai awal kondisi. b. Kemudian dilanjutkan dengan pengerjaan Statements perulangan dan diteruskan dengan melaksanakan perintah untuk mengubah nilai kondisi (Change Condition). c. Periksa kondisi perulangan (condition). Jika kondisi bernilai BENAR/TRUE, maka kembali mengerjakan langkah b. Jika kondisi bernilai SALAH/FALSE maka perulangan dihentikan dan melaksanakan perintah berikutnya (Next Instruction).

Condition

false Next Instruction

Contoh programnya sebagai berikut : Nama Program : dowhile.cpp


25

4. Nested Loop Disebut juga dengan perulangan bersarang. Struktur ini membentuk perulangan yang sangat dalam. Struktur ini kadang kala diperlukan untuk mengatasi persoalan pemrograman yang tidak bisa hanya mengandalkan perulangan tunggal saja. Struktur ini merupakan kombinasi dari struktur looping yang telah diuraikan diatas. Nested Loop mempunyai istilah Inner Loop (Perulangan bagian dalam) dan Outer Loop (Perulangan bagian luar).

#include #include void main ( ) { int I, J ; I = 1; while ( I <= 3 ) { J = 1; while ( J <= 5 ) { J++; } I++; } }

I=1

I <= 3

false

true

J=1

I <= 5

false

Inner Loop

I++

Inner Loop (Loop Bagian Dalam)

Outer Loop

true

J++

Outer Loop (Loop Bagian Luar)

Salah satu manfaat dari Nested Loop adalah dapat membentuk kombinasi angka seperti contoh program sebagai berikut :


26

Nama Program : nestedloop.cpp

Output Program :

Penjelasan Program : - Output program menunjukkan terbentuknya sebanyak 5 baris dengan 5 kolom. - 5 Baris terbentuk dari outer loop / perulangan bagian luar. - 5 Kolom terbentuk dari inner loop / perulangan bagian dalam. - Angka yang ditampilkan diambil dari perubahan angka pada variabel j.


27

Materi V

Function dan Procedure Sasaran Perkuliahan : 1) Mahasiswa dapat memahami dan membuat program mengenai function/fungsi 2) Mahasiswa dapat memahami dan membuat program mengenai procedure/prosedur

Function dan procedure disebut juga sebagai sub program. Sub program ini kadang kala diperlukan dalam pembuatan program untuk memenuhi kebutuhan pengguna. Sub program adalah pengelompokkan beberapa baris perintah tertentu diluar dari program utamanya. Disebut dengan sub program, karena sub program tidak bisa dipisahkan dari program utamanya walaupun letaknya terpisah dari program utamanya. Dalam bahasa C++, yang menjadi bagian program utama adalah seluruh perintah yang ada di dalam void main(). Adapun perbedaan antara function dengan procedure adalah fungsi menghasilkan sebuah nilai keluaran sedangkan prosedur tidak menghasilkan nilai keluaran. Cara menjalankan function dan procedure dengan menuliskan nama function atau procedure di program utamanya. Nama function atau procedure harus dideklarasikan terlebih dahulu diatas program utamanya. 1. Function Bentuk umum dari function adalah : tipe_data nama_fungsi (tipe_data nama_variabel_masukan) { statement ; return variabel_keluaran } Contoh programnya sebagai berikut : Nama Program : function.cpp

Perintah memanggil function

Sub Program / FUNCTION Algoritma & Struktur Data 1 - STMIK Atma Luhur Okkita Rizan - Hamida

28

2. Procedure Procedure memiliki dua bentuk, yaitu procedure tanpa parameter dan procedure dengan parameter. a) Procedure tanpa parameter Bentuk umumnya sebagai berikut : void nama_prosedur(void) { statement ; } Contoh programnya sebagai berikut : Nama program : procedure1.cpp

Perintah memanggil procedure

Sub Program / PROCEDURE

b) Procedure dengan parameter Bentuk umumnya sebagai berikut :

void nama_prosedur(tipe_data variabel_input, tipe_data variabel_inputn) { statement ; }

Contoh programnya sebagai berikut :


29

Nama Program : procedure2.cpp

Perintah memanggil procedure

Sub Program / PROCEDURE


30

Materi VI

Array Sasaran Perkuliahan : 1) Mahasiswa dapat memahami mengenai array 2) Mahasiswa dapat memahami perbedaan array 1 dimensi dan 2 dimensi 3) Mahasiswa dapat membuat program menggunakan array Array atau disebut juga dengan larik, dapat digambarkan hampir sama dengan tabel. Array dapat juga diartikan sebagai sesuatu yang berbaris-baris atau berderet-deret. Dalam bahasa pemrograman, array adalah variabel sejenis yang berderet-deret sedemikian rupa sehingga alamatnya saling bersambung atau bersebelahan/berdampingan (contiguous). Pada dasarnya, fungsi array sama dengan varabel yaitu untuk menampung nilai. Perbedaan array dengan variabel adalah variabel hanya dapat menampung satu nilai saja pada satu waktu, variabel ini disebut juga dengan variabel tunggal sedangkan array merupakan variabel yang dapat menampung banyak nilai / data dengan tipe data yang sejenis dalam satu waktu. Nilai pada array diakses berdasarkan indeks yang tersusun secara berurutan. Array dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi. 1. ARRAY SATU DIMENSI Array satu dimensi adalah array yang memiliki satu kolom dengan banyak baris, atau satu baris dengan banyak kolom, tergantung bagaimana cara mengilustrasikannya dalam pikiran. Untuk lebih jelasnya array satu dimensi dapat digambarkan sebagai berikut : Indeks : 0

Indeks : 0

N1

1

N2

2

N3

3

N4

4

N5

N1

1 N2

2

3 N3

4 N4

N5

Array satu dimensi disebut juga dengan vector karena hanya mempunyai satu arah saja. Bentuk Umum Deklarasi Array Satu Dimensi :

tipe_data nama_array [jumlah_indeks] ;


31

Aturan pemberian nama array sama halnya dengan aturan pemberian nama variabel. Lihat di bab terdahulu. Contoh program dengan array 1 dimensi sebagai berikut : Nama Program : array1d.cpp

2. ARRAY DUA DIMENSI Array dua dimensi adalah array yang memiliki dua atau lebih kolom dengan banyak baris, atau dua atau lebih baris dengan banyak kolom, bergantung bagaimana mengilustrasikannya didalam pikiran. Array dua dimensi juga dapat dipandang sebagai gabungan dari dua atau beberapa array satu dimensi. Array Dua Dimensi diilustrasikan sebagai berikut :

Indeks : 0

1

2

3

4

0

N[0,0]

N[0,1]

N[0,2]

N[0,3]

N[0,4]

1

N[1,0]

N[1,1]

N[1,2]

N[1,3]

N[1,4]

2

N[2,0]

N[2,1]

N[2,2]

N[2,3]

N[2,4]


32

Dari contoh ilustrasi diatas, Array Dua Dimensi tersebut mempunyai 3 baris dan 5 kolom. Setiap elemen mempunyai dua buah indeks berdasarkan perpotongan antara indeks baris dan indeks kolom. Karena mempunyai baris dan kolom Array Dua Dimensi disebut juga dengan matriks. Bentuk Umum Deklarasi Array Dua Dimensi :

tipe_data nama_array [jml_indeks_baris] [jml_indeks_kolom] ;

Aturan pemberian nama array sama halnya dengan aturan pemberian nama variabel. Lihat di bab terdahulu. Contoh Program dengan array 2 dimensi sebagai berikut : Nama Program : array2d.cpp


33

Materi VII

Pengantar Struktur Data Sasaran Perkuliahan : 1) Mahasiswa dapat memahami mengenai struktur data 2) Mahasiswa dapat memahami istilah-istilah yang digunakan pada struktur data 3) Mahasiswa dapat memahami macam-macam Struktur Data Dalam istilah komputer, struktur data diartikan sebagai cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien. Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolomkolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data. Struktur data dibedakan menjadi dua macam yaitu struktur data sederhana dan struktur data majemuk. Contoh dari struktur data sederhana adalah array dan record. Struktur data majemuk terdiri dari Linier dan Non Linier. Anggota dari Linier adalah Stack, Queue, List dan Multilist, sedangkan anggota dari Non Linier adalah Pohon Biner (tree) dan Graph. Dari beberapa macam bentuk struktur data tersebut akan diuraikan lebih lanjut pada materi-materi berikutnya.


34

Materi VIII

Struktur Data STACK Sasaran Perkuliahan : 1) Mahasiswa dapat memahami mengenai stack 2) Mahasiswa dapat memahami istilah-istilah yang digunakan pada stack 3) Mahasiswa dapat memahami macam-macam stack 4) Mahasiswa dapat membuat program menggunakan stack Stack terbagi kedalam dua macam, yaitu Single Stack dan Double Stack. 1. Single Stack Single Stack disebut juga dengan tumpukan. Struktur data single stack ini dapat diilustrasikan seperti menyusun buku diatas meja. Seperti gambar berikut :

Dalam struktur stack dikenal dengan istilah PUSH, dan POP. - PUSH adalah istilah yang digunakan untuk memasukkan, menyimpan, menulis atau menginsert data kedalam stack. - POP adalah istilah yang digunakan untuk mengambil, membaca, mengeluarkan atau mendelete data dari stack. - TOP adalah menunjukkan posisi elemen terakhir dari sebuah stack. Prinsip yang digunakan pada stack adalah L I F O atau kepanjangan dari Last in First Out. Artinya data yang terakhir masuk kedalam stack, maka data tersebut akan pertama kali dikeluarkan dari stack. Pada pemrograman, ilustrasi sebuah stack dapat dilihat dari gambar berikut yang menggunakan array 1 dimensi :


35

Dari gambar diatas dapat diketahui bahwa telah disiapkan sebuah array dengan nama S[]. Array tersebut mempunyai indeks sampai dengan 10. Artinya Array tersebut dapat menampung maksimal sampai dengan 10 data. Cara memasukkan dan mengambil data dari array tersebut menggunakan struktur Single Stack. Top menunjukkan posisi paling akhir dari elemen array yang mempunyai isi. Yang dimaksud dengan posisi terakhir adalah data yang dimasukkan terakhir kali, bukan yang pertama kali dimasukkan ke dalam array. Beberapa kondisi yang dipunyai oleh single stack adalah sebagai berikut : a) Stack Kosong (IsEmpty) Ciri stack dalam keadaan kosong adalah posisi Top kurang dari nol. Kondisi ini dapat dikatakan sebagai proses awal dari sebuah single stack. Dalam algoritma ciri stack kosong adalah : Top = - 1 Stack kosong diilustrasikan sebagai berikut :

b) Stack Penuh (IsFull) Ciri stack sudah dalam keadaan penuh adalah posisi Top berada pada indeks terakhir dari stack. Dalam algoritma ciri stack penuh adalah : Top = n - 1 Stack penuh diilustrasikan sebagai berikut :

c) Stack dapat diisi Ciri stack masih bisa diisi adalah posisi Top tidak berada pada indeks terakhir dari stack. Dalam Algoritma ciri stack masih bisa diisi adalah : Top < n - 1 Stack dapat diisi diilustrasikan sebagai berikut :


36

Atau :

d) Stack punya isi Ciri stack masih mempunyai isi adalah posisi TOP tidak kurang dari nol. Dalam algoritma ciri stack masih mempunyai isi adalah : Top > -1 Stack punya isi diilustrasikan sebagai berikut :

Atau :

Dari keempat kondisi pada stack tersebut mempengaruhi proses PUSH dan POP pada stack. - Pada proses PUSH, stack dapat disi apabila kondisi stack kosong dan bisa diisi. Algoritma untuk proses PUSH adalah : Top = Top + 1 ; S[Top] = X; Pada saat stack penuh, maka proses PUSH tidak dapat dilakukan. Algoritma lengkap untuk proses PUSH adalah : if ( Top < n-1 ) { Top = Top + 1; S[Top] = X; } else { cout << “Stack Penuh”; }


37

Atau : if ( Top == n-1 ) { cout << “Stack Penuh”; else { Top = Top + 1; S[Top] = X; }

-

Pada proses POP, stack dapat diambil isinya apabila kondisi stack penuh dan stack punya isi. Algoritma untuk proses POP adalah : X = S[Top] ; Top = Top - 1 ;

Pada saat stack kosong, maka proses POP tidak dapat dilakukan. Algoritma lengkap untuk proses POP adalah : if ( Top < -1 ) { X = S[Top]; Top = Top - 1; } else { cout << “Stack Kosong”; }

Atau :

if ( Top == -1 ) { cout << “Stack Kosong”; else { X = S[Top]; Top = Top - 1; }

Contoh program menggunakan single stack sebagai berikut :


38

Nama Program : singlestack.cpp

Penjelasan Program : - Int S[n], proses deklarasi sebuah array satu dimensi dengan nama S[] dan bertipe data integer. Untuk indeks array tersebut menggunakan variabel n yang sudah dijadikan konstanta pada bagian #define n 7. - Top = -1, merupakan proses inisialisasi awal pada stack. Perintah tersebut menandakan juga stack masih dalam keadaan kosong. Output Program :


39

2. Double Stack Double stack dapat diilustrasikan sebagai gabungan dua buah stack menggunakan array yang sama. Prinsip pada double stack sama dengan single stack yaitu LIFO (Last In First Out) baik untuk stack yang pertama maupun stack yang kedua pada double stack tersebut. Adapun ilustrasi dari double stack seperti gambar berikut ini :

Dari gambar tersebut dapat diketahui bahwa, stack mempunyai dua buah pointer TOP yaitu Top1 dan Top2. Top1 mewakili stack yang pertama. Arah pergerakannya dari kiri ke kanan (dari ilustrasi gambar diatas). Top2 mewakili stack yang kedua. Arah pergerakannya dari kanan ke kiri (dari ilustrasi gambar diatas). Beberapa kondisi yang dimiliki oleh double stack adalah sebagai berikut : a) Double stack kosong (IsEmpty) Ciri dari double stack kosong adalah posisi dari Top1 kurang dari nol dan Top2 berada di indeks trakhir dari stack. Kondisi ini dapat dikatakan sebagai proses awal (inisialisasi) dari sebuah double stack. Dalam Algoritma ciri double stack kosong adalah : Top1 = - 1 Top2 = n

Double stack kosong diilustrasikan sebagai berikut :

Top1

Top2

b) Stack Penuh (IsFull) Ciri double stack penuh apabila posisi Top1 dengan Top2 betul-betul bersebelahan atau dengan kata lain apabila Top2 dikurangi dengan Top1 hasilnya adalah 1. Dalam algoritma ciri double stack penuh adalah :

Top2 - Top1 = 1

Double stack penuh diilustrasikan sebagai berikut :


40

Top1 Top2

c) Stack dapat diisi Ciri stack masih dapat diisi apabila posisi Top1 dengan Top2 tidak bersebelahan, atau apabila Top2 dikurangi dengan Top1 hasilnya tidak sama dengan 1 (satu), tepatnya lebih besar dari 1 (satu). Dalam algoritma ciri stack masih bisa diisi adalah : Top2 - Top1 > 1

Double stack dapat diisi diilustrasikan sebagai berikut :

Top1

Top2 Atau :

Top1

Top2 Atau :

Top1

Top2 Atau :

Top1


Top2

41

d) Stack punya isi Ciri double stack masih mempunyai isi pada double stack memiliki beberapa ciri yaitu : - Top1 tidak kurang dari nol dan Top2 sama dengan indeks. - Top1 sama dengan nol dan Top2 tidak sama dengan indeks. - Top1 tidak kurang dari nol dan Top2 tidak sama dengan indeks. Dalam algoritma ciri stack masih mempunyai isi adalah : Top1 > -1 Top2 < n Double stack punya isi diilustrasikan sebagai berikut :

Top1

Top2

Atau :

Top1

Top2 Atau :

Top1

Top2 Atau :

Top1 Top2 Atau :

Top1 Top2 Atau :

Top1 Top2


42

Sama seperti single stack, kondisi tersebut juga mempengaruhi proses PUSH dan POP pada double stack. a) PUSH Proses PUSH dapat dilakukan selama stack dalam kondisi kosong atau masih dapat diisi. Algoritma dasar proses PUSH pada stack yang pertama adalah : Top1 = Top1 + 1 ; S[Top1] = X;

Algoritma dasar proses PUSH pada stack yang kedua adalah : Top2 = Top2 - 1 ; S[Top2] = X;

Proses PUSH tidak dapat dilakukan apabila stack dalam kondisi penuh. Algoritma lengkap untuk proses PUSH pada double stack adalah : - Algoritma lengkap proses PUSH untuk stack yang pertama adalah

if ( Top2 - Top1 >1 ) { Top1 = Top1 + 1; S[Top1] = X; } else { cout << “Stack1 Penuh”; }

Atau :

if ( Top2 - Top1 == 1 ) { cout << “Stack1 Penuh”; } else { Top1 = Top1 + 1; S[Top1] = X; }


43

-

Algoritma lengkap proses PUSH untuk stack yang kedua adalah

if ( Top2 - Top1 >1 ) { Top2 = Top2 - 1; S[Top2] = X; } else { cout << “Stack2 Penuh”; }

Atau :

if ( Top2 - Top1 == 1 ) { cout << “Stack2 Penuh”; } else { Top2 = Top2 - 1; S[Top2] = X; }

b) POP Proses POP dapat dilakukan selama stack dalam kondisi penuh atau masih mempunyai isi. Algoritma dasar proses POP pada stack yang pertama adalah :

X = S[Top1] ; Top1 = Top1 - 1 ;

Algoritma dasar proses POP pada stack yang kedua adalah :

X = S[Top2] ; Top2 = Top2 + 1 ;


44

Proses POP tidak dapat dilakukan apabila stack dalam kondisi kosong. Algoritma lengkap untuk proses POP pada double stack adalah : - Algoritma lengkap untuk proses POP stack yang pertama adalah : if ( Top1 < -1 ) { X = S[Top1]; Top1 = Top1 - 1; } else { cout << “Stack1 Kosong”; } Atau : if ( Top1 == -1 ) { cout << “Stack1 Kosong”; else { X = S[Top1]; Top1 = Top1 - 1; }

-

Algoritma lengkap proses POP stack yang kedua adalah : if ( Top2 < n ) { X = S[Top2]; Top2 = Top2 + 1; } else { cout << “Stack2 Kosong”; }

Atau :

if ( Top2 == n ) { cout << “Stack2 Kosong”; else { X = S[Top2]; Top2 = Top2 + 1; }


45

Contoh program double stack adalah sebagai berikut : Nama Program : doublestack.cpp


46

Penjelasan Program : - Double stack dibuat dengan nama S[] dengan elemen sebanyak 10. - Proses PUSH pada stack yang pertama hanya dibatasi sebanyak 5 kali. Pada program algoritmanya : Top2 - Top1 > 1 && Top1 < 4. - Proses PUSH pada stack yang kedua dilakukan selama stack belum penuh. Output Program :


47

Materi IX

Struktur Data QUEUE Sasaran Perkuliahan : 1) Mahasiswa dapat memahami mengenai queue 2) Mahasiswa dapat memahami istilah-istilah yang digunakan pada queue 3) Mahasiswa dapat memahami macam-macam queue 4) Mahasiswa dapat membuat program menggunakan prinsip queue Queue, apabila diartikan secara harfiah adalah antrian. Implementasi dalam queue dalam kehidupan sehari-hari seperti mengantri pembelian karcis pada loket penjualan karcis. Dari sebuah literatur pengertian queue adalah : “A Queue is an ordered collection of items into which new

items may be inserted at one end (called the rear of the queue) and from which items may be deleted at one end (called the front of the queue)”.( Yedidyah L, Moshe J. A., and Aaron M. Tenenbaum; Data Structures Using C and C++).

Prinsip kerja dari queue adalah FIFO (First In First Out) atau FIFS (First In First Serve). Secara harfiahnya, prinsip kerja queue ini seperti pada loket antrian, seseorang yang pertama kali mengantri, maka orang tersebut yang akan pertama kali keluar dari antrian. Beberapa istilah yang digunakan pada queue adalah : 1. FRONT Front menunjukkan posisi antrian pertama / depan. Untuk memudahkan penulisan materi ini Front selanjutnya akan ditulis menjadi F. 2. REAR Rear menunjukkan posisi antrian terakhir / belakang. Untuk memudahkan penulisan materi ini Rear selanjutnya akan ditulis menjadi R. 3. ENQUEUE EnQueue menunjukkan item yang masuk kedalam antrian. 4. DEQUEUE DeQueue menunjukkan item yang keluar dari antrian. Struktur queue terdiri dari 3 macam. Struktur ini akan diimplementasikan dengan array 1 dimensi. Adapun strukturnya adalah : -

Linear Queue Circular Queue Double End Queue (Deque).


48

1. LINEAR QUEUE Linear Queue disebut juga dengan antrian lurus. Struktur ini seakan-akan membentuk sebuah antrian lurus yang hanya memiliki satu pintu masuk dan satu pintu keluar. Ilustrasi dari struktur linear queue ini adalah sebagai berikut :

Seperti yang telah disebutkan diatas prinsip kerja dari queue adalah FIFO (First In First Out). Dari contoh gambar, F menunjukkan antran pertama dan R menunjukkan antrian terakhir. Apabila ada data yang akan masuk (insert), maka akan ditempatkan pada indeks ke-4 dan posisi R akan bergeser ke indeks ke-4, begitu seterusnya sampai pada indeks yang terakhir dan antrian penuh. Apabila ada data yang akan keluar (delete), maka antrian yang akan pertama kali keluar adalah A dan posisi F akan bergeser menunjuk B, begitu seterusnya sampai antrian kosong. Beberapa kondisi pada Linear Queue adalah : a) Queue Kosong Ciri dari Linear Queue kosong adalah posisi F (Front) persis berada di depan posisi R (Rear). Dalam algoritma ciri Linear Queue kosong adalah : F=R+1 Kondisi kosong juga merupakan salah satu ciri dari proses awal (inisialisasi) pada Linear Queue, walaupun kondisi kosong belum tentu merupakan proses awal dari Linear Queue. Algoritma proses awal (inisialisasi) dari Linear Queue adalah : F=0 R = -1

Linear Queue kosong diilustrasikan sebagai berikut :

Pada gambar ini merupakan kondisi awal (inisialisasi) dari Linear Queue.


49

Bentuk lain dari linear queue kosong adalah sebagai berikut :

Atau :

b) Queue Penuh Ciri dari Linear Queue penuh adalah posisi Rear (R) berada pada indeks terakhir dari antrian (queue). Dalam algoritma ciri Linear Queue penuh adalah : R=n-1 Linear queue penuh diilustrasikan sebagai berikut :

Atau :

c) Queue dapat diisi Ciri dari linear queue masih dapat diisi ke antrian adalah posisi Rear (R) tidak berada pada indeks terakhir dari antrian. Dalam algoritma ciri Linear Queue masih dapat diisi adalah : R
Linear queue masih dapat diisi diilustrasikan sebagai berikut :


50

Atau :

Atau :

Atau :

Atau :

d) Queue punya isi Ciri Linear Queue masih mempunyai isi pada antrian adalah posisi F (Front) berada dibelakang R (Rear). F
Atau :

Atau :


51

Atau :

Kondisi pada Linear Queue mempengaruhi proses PUSH dan POP pada Linear Queue tersebut. a) PUSH Proses PUSH dapat dilakukan selama Linear Queue dalam kondisi kosong atau masih dapat diisi. Algoritma dasar proses PUSH pada Linear Queue adalah : R=R+1 Q[R] = X

Proses PUSH tidak dapat dilakukan apabila Linear Queue dalam kondisi penuh. Algoritma lengkap proses PUSH pada Linear Queue adalah : if ( R < n-1 ) { R = R + 1; Q[R] = X; } else { cout << “Antrian Penuh”; }

Atau : if ( R == n-1 ) { cout << “Antrian Penuh”; } else { R = R + 1; Q[R] = X; }


52

b) POP Proses POP dapat dilakukan selama linear queue dalam kondisi penuh atau masih mempunyai isi pada antrian. Algoritma dasar proses POP pada Linear Queue adalah : X = Q[F] ; F = F + 1; if ( F == n ) { F = 0; R = -1; }

Proses POP tidak dapat dilakukan apabila Linear Queue dalam kondisi kosong. Algoritma lengkap untuk proses POP pada Linear Queue adalah : if ( F < R+1 ) { X = Q[F] ; F = F + 1; if ( F == n ) { F = 0; R = -1; } } else { cout << “Antrian Kosong”; } Atau :

if ( F == R+1 ) { cout << “Antrian Kosong”; } else { X = Q[F] ; F = F + 1; if ( F == n ) { F = 0; R = -1; } }


53

Contoh Program menggunakan prinsip Linear Queue adalah sebagai berikut : Nama Program : linearqueue.cpp

Output Program :


54

2. CIRCULAR QUEUE Circular Queue dapat diartikan sebagai antrian melingkar. Pada Linear Queue, apabila data yang sudah dimasukkan (PUSH) pada sebuah antrian dan datanya dikeluarkan (POP) pada indeks antrian tersebut, maka data baru tidak dapat dimasukkan (PUSH) kembali ke indeks antrian tersebut sebelum Linear Queue di reset atau dijadikan kedalam kondisi kosong/awal setelah antrian tidak mempunyai data lagi. Ilustrasinya sebagai berikut :

Dari contoh gambar tersebut, dapat diketahui bahwa kondisi queue sudah penuh karena posisi R (Rear) berada pada indeks terakhir dari antrian. Sehingga queue tidak dapat diisi lagi walaupun antrian dari indeks ke-0 sampai dengan ke-5 masih kosong. Untuk mengatasi hal tersebut dapat dilakukan dengan cara memindahkan posisi R (Rear) ke indeks ke-0, sehingga data dapat diisi kembali sampai antrian benar-benar penuh. Konsep seperti ini yang disebut dengan antrian melingkar atau circular queue. Ilustrasinya dari contoh gambar diatas menjadi sebagai berikut :

Posisi R dipindahkan seperti gambar berikut :


55

Maka ilustrasi Circular Queuenya seperti gambar berikut :

Atau :

Algoritma memindahkan posisi R (Rear) pada circular queue sebagai berikut :

if(R == n) { R = 0; } else { R = R + 1; }

atau

R = R + 1; if(R == n+1) { R = 0; }

Selain dengan cara diatas, algoritma untuk memindahkan posisi R (Rear) dapat dilakukan dengan memanfaatkan operator modulus (%) atau sisa hasil pembagian dan Library Function fmod().

R = (R+1) % n

atau

R = fmod(R+1, n)

Berbeda dengan linear queue, selain menggunakan F (Front) dan R (Rear) didalam antriannya, circular queue menggunakan Counter untuk menentukan jumlah antrian yang masuk dan keluar sekaligus menentukan kondisi circular queuenya. Adapun beberapa kondisi pada circular queue adalah : a) Queue Kosong Ciri dari Circular queue kosong adalah apabila Counter bernilai 0. Maka Algoritma circular queue kosong adalah :


56

Counter = 0;

Sama seperti Linear Queue, kondisi kosong juga merupakan salah satu ciri proses awal (inisialisasi) pada circular queue, walaupun kondisi kosong belum tentu merupakan proses awal dari circular queue. Algoritma proses awal (inisialisasi) dari Circular queue adalah : F = 0; R = -1; Counter = 0;

Ilustrasi Circular Queue dalam kondisi kosong adalah sebagai berikut :

Atau :

b) Queue Penuh Ciri dari Circular queue penuh pada antrian adalah apabila counter bernilai sama dengan indeks antrian. Maka algoritma circular queue penuh adalah : Counter = n;

Ilustrasi circular queue dalam kondisi penuh digambarkan sebagai berikut :


57

c) Queue dapat diisi Ciri dari circular queue masih dapat diisi pada antrian apabila Counter tidak bernilai sama dengan indeks antrian. Maka algoritma circular queue masih dapat diisi adalah :

Counter < n

Ilustrasi circular queue dalam kondisi dapat diisi dapat dilihat pada beberapa gambar sebagai berikut :

1)

2)

3)

4)

5)

6)


58

d) Queue punya isi Ciri dari circular queue masih mempunyai isi pada antrian apabila Counter tidak bernilai 0. Maka algoritma circular queue masih mempunyai isi pada antrian adalah : Counter > 0

Ilustrasi circular queue masih mempunyai isi pada antrian dapat dilihat pada beberapa gambar sebagai berikut :

1)

2)

3)

4)

5)

Kondisi pada Circular Queue mempengaruhi proses PUSH dan POP pada Circular Queue tersebut. a) PUSH Proses PUSH dapat dilakukan selama Circular Queue dalam kondisi kosong atau masih dapat diisi. Algoritma dasar proses PUSH pada Circular Queue adalah : R = (R+1) % n; Q[R] = X; Counter++; Counter++ sama artinya dengan Counter=Counter+1.


59

Proses PUSH tidak dapat dilakukan apabila Circular Queue dalam kondisi penuh. Algoritma lengkap proses PUSH pada Circular Queue adalah : if ( Counter < n) { R = (R+1) % n; Q[R] = X; Counter++; } else { cout << “Antrian Penuh”; }

Atau :

if ( Counter == n) { cout << “Antrian Penuh”; } else { R = (R+1) % n; Q[R] = X; Counter++; }

b) POP Proses POP dapat dilakukan selama circular queue dalam kondisi penuh atau masih mempunyai isi pada antrian. Algoritma dasar proses POP pada Circular Queue adalah :

X = Q[F]; F = (F+1) % n; Counter--;

Counter-- sama artinya dengan Counter=Counter-1.

Proses POP tidak dapat dilakukan apabila circular queue dalam kondisi kosong. Algoritma lengkap untuk proses POP pada Circular Queue adalah :


60

if ( Counter > 0) { X = Q[F]; F = (F+1) % n; Counter--; } else { cout << “Antrian Kosong”;} Atau : if ( Counter == 0) { cout << “Antrian Kosong”; } else { X = Q[F]; F = (F+1) % n; Counter--; } ontoh program menggunakan circular queue adalah sebagai berikut : Nama program : circularqueue.cpp


61

3. DOUBLE END QUEUE (DEQUEUE) Double End Queue atau biasa disebut sebagai dequeue dapat diartikan sebagai antrian yang mempunyai ujung ganda. Disebut dengan ujung ganda karena antrian dapat dimasukkan (insert) atau dikeluarkan (delete) dari kedua ujung antriannya. Dari sebuah literatur dequeue adalah “A deque (Double-ended queue) is a linear list in which insertion and deletions are made to or from either end of the structure (Jean-Paul Tremblay, An Introduction To Data Structures with Applications; McGraw-Hill, 1985)”. Ilustrasi Dequeue digambarkan seperti sebuah tabung sebagai berikut :

Ilustrasi Dequeue yang digambarkan dengan array 1 dimensi adalah sebagai berikut :

Dari gambar diatas dapat diketahui bahwa, ada dua buah pointer yang disebut dengan L (Left) dan R (Right). Kedua pointer tersebut berfungsi untuk menentukan posisi antrian yang terakhir, baik dari sebelah kiri dan di sebelah kanan. Pergerakan dari kedua pointer tersebut bisa ke arah kiri dan bisa ke arah kanan, tergantung proses pada antriannya. - Apabila antrian akan diinput (insert) dari sebelah kiri, maka posisi L akan bergerak ke kiri. - Apabila antrian akan diambil (delete) dari sebelah kiri, maka poisis L akan bergerak ke kanan. - Apabila antrian akan diinput (insert) dari sebelah kanan, maka posisi R akan bergerak ke kanan. - Apabila antrian akan diambil (delete) dari sebelah kanan, maka poisis R akan bergerak ke kiri. Beberapa kondisi pada Dequeue adalah : a) Dequeue Kosong Ciri dari dequeue kosong adalah apabila posisi L dan R betul-betul bersebelahan. Dalam algoritma, ciri dequeue kosong adalah :

L == R + 1

Atau

R == L - 1

Sama seperti Linear Queue dan Circular, kondisi kosong juga merupakan salah satu ciri proses awal (inisialisasi) pada dequeue, walaupun kondisi kosong belum tentu merupakan


62

proses awal dari dequeue. Algoritma proses awal (inisialisasi) dari Circular queue adalah : L=0; R = -1;

Ilustrasi Dequeue dalam kondisi kosong terlihat pada beberapa gambar berikut :

1)

2)

3)

b) Dequeue Penuh Apabila Dequeue penuh, maka Dequeue tidak bisa diinput (insert) lagi. Karena dequeue mempunyai dua buah sisi/pintu/jalan untuk insert antrian, maka ada 3 kondisi penuh yaitu : 1) Dequeue penuh dari sebelah kiri (Left/L) Kondisi ini mengakibatkan antrian tidak bisa diinput (insert) dari sebelah kiri tetapi kemungkinan masih bisa diinput dari sebelah kanan. Cirinya adalah posisi L berada pada indeks pertama dari antrian. Algoritmanya adalah : L == 0

Ilustrasinya dari beberapa gambar berikut :

(a)

(b)


63

(c)

2) Dequeue penuh dari sebelah kanan (Right/R) Kondisi ini mengakibatkan antrian tidak bisa diinput (insert) dari sebelah kanan tetapi kemungkinan masih bisa diinput dari sebelah kiri. Cirinya posisi R berada pada indeks terakhir dari antrian. Algoritmanya adalah :

R == n - 1

Ilustrasi Dequeue penuh sebelah kanan dapat dilihat dari beberapa gambar berikut :

(a)

(b)

(c)

3) Dequeue penuh dari kedua sisi Kondisi ini mengakibatkan antrian tidak bisa diinput dari sisi kiri ataupun dari sebelah kanan. Cirinya apabila posisi L berada di indeks pertama dari antrian dan R berada di indeks terakhir dari antrian. Algoritmanya adalah :

R == n-1 && L == 0

Ilustrasinya dapat dilihat pada gambar berikut :


64

c) Dequeue Dapat diisi Dequeue masih dapat diisi/diinput (insert) ke antrian dari dua sisi/jalan/pintu. 1) Antrian dapat diisi dari sisi sebelah kiri apabila posisi L tidak berada pada indeks pertama dari antrian. Algoritmanya adalah : L>0

Ilustrasinya dapat dilihat dari beberapa gambar sebagai berikut :

(a)

(b)

(c)

(d)

(e)

2) Antrian dapat diisi dari sisi sebelah kanan apabila posisi R tidak berada pada indeks terakhir dari antrian. Algoritmanya adalah : R
Ilustrasinya dapat dilihat dari beberapa gambar sebagai berikut :

(a)


65

(b)

(c)

(d)

(e)

d) Dequeue Punya isi Ciri dequeue masih mempunyai isi pada antrian apabila posisi R ataupun L tidak betulbetul bersebelahan. Algoritmanya adalah : L < R+1

atau

L <= R

atau

R > L-1

atau

R >= L

Ilustrasinya dapat dilihat pada beberapa gambar sebagai berikut :

(a)

(b)

(c)

(d)


66

(e)

Dari beberapa kondisi tersebut mempengaruhi proses PUSH dan POP pada Double End Queue. 1) PUSH Proses PUSH dapat dilakukan selama Dequeue dalam kondisi kosong atau masih dapat diisi. a) Algoritma dasar proses PUSH Dequeue dari sisi sebelah kiri adalah : L = L - 1; Q[L] = X; Proses PUSH dari sebelah kiri tidak dapat dilakukan apabila Dequeue penuh pada bagian kiri atau posisi L berada pada indeks pertama dari antrian. Maka algoritma lengkap proses PUSH Dequeue dari sebelah kiri adalah : if ( L > 0) { L = L - 1; Q[L] = X; } else { cout << “Antrian Penuh Kiri” }

b) Algoritma dasar proses PUSH Dequeue dari sisi sebelah kanan adalah : R = R + 1; Q[R] = X; Proses PUSH dari sebelah kanan tidak dapat dilakukan apabila Dequeue penuh pada bagian kanan atau posisi R berada pada indeks terakhir dari antrian. Maka algoritma lengkap proses PUSH Dequeue dari sebelah kanan adalah : if ( R < n - 1) { R = R + 1; Q[R] = X; } else { cout << “Antrian Penuh Kanan” }


67

2) POP Proses POP dapat dilakukan selama dequeue dalam kondisi penuh atau masih mempunyai isi pada antrian. a) Algoritma dasar proses POP Dequeue dari sebelah kiri adalah : Q[L] = X; L = L + 1;

Proses POP dari sebelah kiri tidak dapat dilakukan apabila Dequeue kosong atau posisi L dan R tidak betul-betul bersebelahan. Maka algoritma lengkap proses POP Dequeue dari sebelah kiri adalah : if ( L < R+1) { Q[L] = X; L = L + 1; } else { cout << “Antrian Kosong Kiri” }

b) Algoritma dasar proses POP Dequeue dari sebelah kanan adalah : Q[R] = X; R = R - 1;

Proses POP dari sebelah kanan tidak dapat dilakukan apabila Dequeue kosong atau posisi L dan R tidak betul-betul bersebelahan. Maka algoritma lengkap proses POP Dequeue dari sebelah kanan adalah : if ( L < R+1) { Q[R] = X; R = R - 1; } else { cout << “Antrian Kosong Kanan” }

Berikut adalah contoh program menggunakan dequeueu :


68

Nama Program : dequeue.cpp


69

Penjelasan Program : Pada saat program dijalankan proses PUSH akan dilakukan dari arah kanan, karena proses awal inisialisasi baik posisi L maupun R berada di sebelah kiri. Hal ini mengakibatkan proses PUSH tidak bisa dilakukan dari sebelah kiri karena dianggap dequeue penuh. Proses POP pertama kali dilakukan dari arah yang berlawanan. Hal ini dilakukan secara tidak langsung untuk memindahkan posisi L ke sebelah kanan. Sehingga proses PUSH bisa dilakukan dari sebelah kiri. Dan proses POP pada dequeue akan dilakukan dari arah kanan. Output Program :


70

Materi X

Struktur Data LINKED LIST Sasaran Perkuliahan : 1) Mahasiswa dapat memahami mengenai Linked List 2) Mahasiswa dapat memahami istilah-istilah yang digunakan pada Linked List 3) Mahasiswa dapat memahami macam-macam Linked List 4) Mahasiswa dapat membuat program menggunakan Linked List Linked list disebut juga dengan objek yang dihubungkan satu dengan yang lain. Objek yang dimaksud adalah sekumpulan elemen yang digabung menjadi satu kelompok yang disebut : structure, atau Vertex, atau Node, atau Titik, atau Record atau Simpul. Contoh dari sebuah list adalah array 1 dimensi. Nama lain Array 1 dimensi adalah vektor dan kadang disebut juga dengan list. Perhatikan contoh berikut ini :

Dari gambar diatas, dapat diketahui bahwa terdapat sebuah array 1 dimensi dengan nama A. Array tersebut mempunyai 5 elemen yang diwakili oleh indeks 0 sampai ke 4. Dari gambar tersebut dapat pula dikatakan terdapat sebuah list dengan 5 elemen. Tetapi list tersebut bukanlah sebuah Linked List. Karena List tersebut bukanlah List yang di-link satu dengan yang lainnya tapi List yang bersisian atau bergandengan atau berurutan (contiguous) satu dengan lainnya, sedemikian rupa sehingga alamat tiap elemen bersambung satu dengan yang lainnya (contiguous). Yang dimaksud dengan alamat adalah lokasi penempatan elemen didalam memori. Peran dari alamat ini lah yang nantinya akan menghubungkan satu list/simpul dengan list/simpul yang lain. Berikut contoh pembentukan sebuah simpul yang akan digunakan dalam konsep linked list.

Simpul adalah nama tipe sebagaimana nama tipe yang telah disediakan oleh Bahasa C seperti : int, long int, float, dan sebagainya. Bila int adalah nama tipe suatu variable, maka Simpul disini adalah nama tipe dari suatu structure atau record, dimana structure tersebut terdiri dari dua field, yaitu : INFO yang bertipe integer (int), dan LINK yang bertipe pointer (pakai *) untuk structure tersebut.


71

INFO berfungsi sebagai tempat menyimpan data sedangkan sebuah pointer pada simpul berfungsi untuk menunjukkan alamat data tersebut disimpan di memory sekaligus berperan untuk menghubungkan simpul tersebut ke simpul berikutnya. Konsep ini yang disebut dengan Linked List. Berikut adalah ilustrasi dari beberapa simpul yang telah membentuk Linked List :

Dari gambar tersebut dapat diketahui bahwa, terdapat 4 (empat) buah simpul yang diwakili oleh angka (1), (2), (3) dan (4). Masing-masing simpul tersebut sudah memiliki data yang terdapat didalam INFOnya. Keempat simpul tersebut akan dihubungkan (link) satu dengan yang lain. Maka, yang berperan untuk menghubungkan simpulnya adalah LINK pada masing-masing simpul akan menyimpan alamat dari INFO simpul yang akan dituju. Maka linked list dari gambar diatas adalah : - Simpul (1) akan dihubungkan ke simpul (2), karena LINK simpul (1) menyimpan alamat simpul (2). - Simpul (2) akan dihubungkan ke simpul (3), karena LINK simpul (2) menyimpan alamat simpul (3). - Simpul (3) akan dihubungkan ke simpul (4), karena LINK simpul (3) menyimpan alamat simpul (4).


72

Untuk memudahkan penggambaran linked list, selanjutnya hubungan antar simpul akan dibuat menggunakan panah, menggantikan penulisan alamatnya. Contoh perubahan ilustrasi dari gambar diatas sebagai berikut :

Linked list empat simpul tersebut dapat disederhanakan sebagai berikut :

Linked List terbagi kedalam 4 (empat) macam dengan cirinya masing-masing. Keempat linked tersebut adalah : 1. LINEAR SINGLY LINKED LIST Linear Singly Linked List disebut juga dengan Linked List Lurus dengan pointer tunggal. Ilustrasi dari Linear Singly Linked List dapat dilihat dari beberapa gambar berikut :

a)


73

b)

c)

d)

Untuk selanjutnya Linear Singly Linked List digambarkan sebagai berikut :

Dari gambar diatas dapat dijelaskan bahwa, Ada 4 simpul, simpul no (1) sampai dengan no (4). Setiap simpul (record) terdiri dari dua elemen (field) yaitu : Field INFO misal bertipe integer. Field LINK bertipe pointer yang diilustraskan dengan panah. Simpul pertama no (1) berada diujung paling kiri, dan ditunjuk oleh pointer FIRST. Simpul terakhir no (4) berada diujung paling kanan,dan ditunjuk oleh pointer LAST. LINK dari simpul terakhir diisi dengan NULL. Adapun beberapa proses dari Linear Singly Linked List adalah : a) Pembuatan Record Awal (inisialisasi) Beberapa langkah proses inisialisasi pada linear singly linked list adalah : 1) Proses deklarasi sebuah simpul baru :


74

Disiapkan 3 buah variabel pointer, yaitu : P, FIRST dan LAST yang kesemuanya berkaitan dengan simpul atau record atau node yang bertipe Simpul. 2) Menyimpan simpul baru ke sebuah alamat di memory melalui pointer P.

Ilustrasinya sebagai berikut :

Terbentuk sebuah simpul yang alamatnya disimpan dalam pointer P atau disebut : “simpul yang ditunjuk oleh pointer P” 3) Perintah/instruksi pokok yang diperlukan untuk membuat sebauh simpul baru : P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; FIRST = P; LAST = P; P->LINK = NULL;

Maksud setiap perintahnya sebagai berikut : a) P=(Simpul*)malloc(sizeof(Simpul)), terbentuk sebuah simpul yang alamatnya disimpan dalam pointer P atau disebut : “simpul yang ditunjuk oleh pointer P”. Malloc maksudnya adalah Memory Allocation yaitu mengalokasikan memory sebesar atau seukuran (sizeof) yang diperlukan untuk Simpul. b) P->INFO=X, memasukkan data melalui variabel X kedalam field INFO yang simpulnya sedang ditunjuk oleh pointer P. c) FIRST = P, pointer FIRST ikut menunjuk simpul yang ditunjuk oleh pointer P. d) LAST = P, pointer LAST ikut menunjuk simpul yang ditunjuk oleh pointer P. e) P->LINK = NULL, field LINK berisi NULL yang artinya field LINK tidak menunjuk ke alamat manapun. Ilustrasi gambar hasil perintah diatas adalah sebagai berikut :


75

b) Insert Kanan (Insert Akhir) Yang dimaksud dengan insert kanan adalah menambahkan simpul baru di bagian kanan linked list. Adapun proses insert simpul kanan diilustrasikan sebagai berikut : 1) Sudah ada sebuah simpul yang ditunjuk oleh pointer P, FIRST dan LAST. Sebut saja simpulnya bernama (1).

2) Dibuat sebuah simpul baru di sebelah kanan dari simpul yang sudah ada tetapi belum berhubungan (link). Sebut saja nama simpulnya adalah (2). Karena simpul (2) baru dibuat, otomatis pointer P akan menunjuk ke simpul (2).

3) Simpul yang pertama (1) sudah dihubungkan dengan simpul yang kedua (2). Otomatis pointer Last menunjuk ke simpul kedua (2), karena simpul kedua adalah simpul terakhir. Alamat LINK simpul pertama akan menunjuk alamat simpul kedua (2).

Perintah pokok yang diperlukan untuk menginsert simpul baru sebelah kanan linked list adalah :

P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; LAST->LINK = P; LAST = P; P->LINK = NULL;

Maksud setiap baris perintah dapat membandingkan dengan proses insert kanan pada gambar diatas.


76

c) Insert Kiri (Insert Awal) Yang dimaksud dengan insert kiri adalah menambah sebuah simpul baru pada bagian kiri linked list. Dapat juga diartikan membuat simpul baru yang akan menjadi simpul pertama dari linked list. Adapun proses insert simpul kiri diilustrasikan sebagai berikut : 1) Sudah ada sebuah simpul yang ditunjuk oleh pointer P, FIRST dan LAST. Sebut saja simpulnya bernama (1).

2) Dibuat sebuah simpul baru di sebelah kiri dari simpul yang sudah ada tetapi belum berhubungan (link). Sebut saja nama simpulnya adalah (2). Karena simpul (2) baru dibuat, otomatis pointer P akan menunjuk ke simpul (2).

3) Simpul yang baru akan dihubungkan ke simpul yang sudah ada (1). Pointer FIRST akan menunjuk simpul yang baru dibuat, karena simpul tersebut berada diawal linked list. Maka simpul yang baru akan menjadi simpul pertama (1) dan simpul yang sudah ada menjadi simpul kedua (2). Alamat LINK simpul pertama akan menunjuk alamat simpul kedua.

Perintah pokok yang diperlukan untuk menginsert simpul baru dibagian kiri dari linked list adalah : P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; P->LINK = FIRST; FIRST = P;

Maksud setiap baris perintah dapat membandingkan dengan proses insert kiri pada gambar diatas.


77

d) Insert Tengah Yang dimaksud dengan insert tengah adalah menyisipkan sebuah simpul baru diantara simpul yang sudah ada pada linked list. Adapun proses insert simpul tengah diilustrasikan sebagai berikut : 1) Dibuat sebuah simpul baru yang ditunjuk oleh pointer P.

2) Simpul baru tersebut akan disisipkan antara simpul ketujuh (7) dan kedelapan (8). Simpul ketujuh ditunjuk oleh sebuah pointer bernama Q. Simpul ketujuh tersebut tidak ditunjuk oleh pointer FIRST dan LAST, karena simpul tersebut bukan berada pada bagian pertama atau bagian terakhir dari rangkaian linked list tersebut. Berikut gambaran simpul akan disisipkan tetapi belum terhubung (link).

3) Semula alamat LINK simpul ketujuh (7) menyimpan alamat simpul kedelapan (8), pada saat dihubungkan (link) ke simpul yang baru, maka alamat LINK (yang ditunjuk oleh pointer Q) akan menyimpan alamat simpul yang baru, dan field LINK pada simpul yang baru akan menyimpan alamat simpul kedelapan (8).

Perintah pokok yang diperlukan untuk insert tengah simpul baru pada linked list adalah :

P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; P->LINK = Q->LINK; Q->LINK = P;

Maksud setiap baris perintah dapat membandingkan dengan proses insert tengah pada gambar diatas.


78

e) Delete Kanan Yang dimaksud dengan delete kanan adalah menghapus simpul yang ada pada linked list. Dapat juga diartikan dengan menghapus simpul terakhir dari linked list. Adapun proses delete simpul kanan diilustrasikan sebagai berikut : 1) Sudah terdapat 4 buah simpul yang membentuk linked list. Simpul yang terakhir akan dihapus, syaratnya simpul sebelah kiri (sebelum) simpul akhir, harus sudah ditunjuk sebuah pointer, misalnya pointer Q.

2) Simpul terakhir dihapus, maka pointer Last akan menunjuk simpul yang sama yang ditunjuk oleh pointer Q, sedangkan field LINK dari simpul yang ditunjuk Q akan berisi null, karena tidak menunjuk ke alamat apapun.

3) Algoritma dasar untuk menghapus simpul tengah dari linked list adalah : free(LAST); LAST = Q; LAST->LINK = NULL;

Maksud setiap baris perintah dapat membandingkan dengan proses insert tengah pada gambar diatas f)

Delete Kiri Yang dimaksud dengan delete kiri adalah menghapus simpul sebelah kiri dari rangkaian linked list. Dapat juga diartikan dengan menghapus simpul pertama pada Linked List. Adapun proses delete simpul kiri diilustrasikan sebagai berikut : 1) Sudah terdapat 4 buah simpul yang membentuk linked list. Simpul yang pertama akan dihapus, syaratnya simpul pertama ditambahkan sebuah pointer selain pointer FIRST, misalnya pointer Q.


79

2) Pointer FIRST dipindahkan ke simpul kedua. Perintah ini dilakukan karena kedua akan menjadi simpul pertama yang akan ditunjuk oleh pointer FIRST.

3) Simpul pertama dihapus melalui pointer Q. pertama.

simpul

Maka simpul kedua menjadi simpul

4) Algoritma dasar proses delete kiri sebuah simpul pada linked list adalah : Q = FIRST; FIRST = Q->LINK; free(Q);

Maksud setiap baris perintah dapat membandingkan dengan proses insert tengah pada gambar diatas

g) Delete Tengah Yang dimaksud dengan delete tengah adalah menghapus sebuah simpul diantara dua buah simpul pada linked list. Adapun proses delete tengah sebuah simpul diilustrasikan sebagai berikut : 1) Terdapat 3 buah simpul dari penggalan sebuah linked list, yaitu simpul tujuh (7), delapan (8) dan sembilan (9). Simpul yang akan dihapus adalah simpul delapan (8). Syaratnya harus membuat sebuah pointer baru setelah simpul yang akan dihapus. Dalam contoh ini, pointer baru diletakkan di simpul sembilan (9), misalnya dengan nama pointer R.

2) Setelah simpul delapan (8) dihapus, maka field LINK simpul tujuh (7) akan menyimpan alamat simpul sembilan (9).


80

3) Dari contoh ilustrasi diatas, algoritma proses menghapus (delete) tengah sebagai berikut : R = Q->LINK->LINK free(Q->LINK ) Q->LINK = R

2. LINEAR DOUBLY LINKED LIST Linear Doubly Linked List disebut juga dengan Linked List Lurus dengan pointer ganda. Ilustrasi Linear Doubly Linked List digambarkan sebagai berikut :

Adapun beberapa proses dari Linear Doubly Linked List adalah : a) Pembuatan simpul awal (inisialisasi) Algoritma untuk membuat simpul awal pada linear doubly linked list adalah : P = (Simpul *) malloc(sizeof(Simpul)); P->INFO = X; FIRST = P; LAST = P; P->LEFT = NULL; P->RIGHT = NULL;

Ilustrasi sebuah simpul baru sebagai berikut :


81

b) Insert Kanan Algoritma untuk membuat Insert Kanan pada linear doubly linked list adalah : P = (Simpul *) malloc(sizeof(Simpul)); P->INFO = X; LAST->RIGHT = P; P->LEFT = LAST; LAST = P; P->RIGHT = NULL; Ilustrasi penambahan simpul baru sebelah kanan pada linked list sebagai berikut :

c) Insert Kiri Algoritma untuk insert kiri pada linear doubly linked list adalah : p = (Simpul*) malloc(sizeof(Simpul)); P->INFO = X; P->RIGHT = LAST; LAST->LEFT = P; LAST = P; P->LEFT = NULL; Ilustrasi penambahan simpul baru sebelah kiri pada linked list sebagai berikut :

d) Insert Tengah Algoritma yang digunakan untuk memasukkan/insert tengah adalah : p = (Simpul *) malloc(sizeof(Simpul)); P->INFO = X; P->RIGHT = Q->RIGHT; P->LEFT = Q; Q->RIGHT->LEFT = P; Q->RIGHT = P;


82

Ilustrasi penambahan simpul baru di tengah linked list adalah sebagai berikut :

3. CIRCULAR SINGLY LINKED LIST Ilustrasi dari circular singly linked list adalah sebagai berikut :

4. CIRCULAR DOUBLY LINKED LIST Ilustrasi dari circular doubly linked list adalah sebagai berikut :


83

Pengenalan Algoritma dan Struktur Program

Recommend Documents