modul struktur data 2012 (software engineering laboratory

L A B P E M R O G R A M D A N R P L

Page 1

BAB 1

POINTER

1.1 PENGERTIAN

Pointer adalah suatu variabel penunjuk, berisi nilai

yang menunjuk alamat suatu lokasi memori tertentu.

Jadi pointer tidak berisi nilai data, melainkan berisi

suatu alamat memori atau null jika pointer tidak berisi data

disebut null pointer. Pointer yang tidak diinisialisasi disebut dangling pointer Lokasi memori tersebut bisa diwakili sebuah variabel

atau dapat juga berupa nilai alamat memori secara langsung.

Ilustrasi Pointer


Page 2

Kita memiliki variabel X yang berisi nilai karakter a maka Oleh kompiler C++, nilai a ini akan disimpan di suatu alamat

tertentu di memori. Sehingga lamat variabel X dapat diakses dengan menggunakan statemen &X.

Jika kita ingin menyimpan alamat dari variabel X ini,

kita dapat menggunakan suatu variabel misalnya int alamat_x

= &X; Maka alamat_x adalah suatu variabel yang berisi alamat dimana nilai X, yaitu 20 disimpan. Variabel alamat_x disebut variabel pointer atau sering disebut

pointer saja.

Contoh pointer beserta penjelasannya

Source Code

#include

using namespace std;

main()

{

int *alamat_x,*y;

int x=20;

int *z=0; //null pointer

alamat_x=&x;


Page 3

cout


Page 4

1.2 Pointer dengan Variabel Biasa

1.3 Operator Pointer


Page 5

1.4 Aturan

Variabel pointer dapat dideklarasikan dengan tipe data

apapun.

Pendeklarasian variabel pointer dengan tipe data

tertentu digunakan untuk menyimpan alamat memori yang

berisi data sesuai dengan tipe data yang dideklarasikan, bukan

untuk berisi nilai bertipe data tertentu. Tipe data digunakan sebagai lebar data untuk alokasi

memori (misal char berarti lebar datanya 1 byte, dst). Jika suatu variabel pointer dideklarasikan bertipe float,

berarti variabel pointer tersebut hanya bisa digunakan untuk

menunjuk alamat memori yang berisi nilai bertipe float juga.

1.5 Operasi pada Pointer

1.5.1 Operasi assignment Antar variabel pointer dapat dilakukan operasi assignment.

Contoh 1: Assignment dan sebuah alamat dapat ditunjuk oleh

lebih dari satu pointer


Page 6

Source Code

#include


main()

{

float a,*x1,*x2;

y=12.34;

x1=&a;

x2=x1; //operasi pemberian nilai

cout


Page 7

Tampilan Hasil

Contoh 2: Mengisi variabel dengan nilai yang ditunjuk oleh

sebuah variabel pointer

Source Code

#include


main()

{

int *p, a=25,b; p=&a;

b=*p;

cout


Page 8

Tampilan Hasil

Contoh 3: Mengoperasikan isi variable dengan menyebut

alamatnya dengan pointer

Source Code

#include


main()

{ int a=25, b=12;

int *p,*q;

p=&a;

q=&b;

cout


Page 9

alamat "


Page 10

Contoh 4: Mengisi dan mengganti variabel yang ditunjuk oleh

pointer.

#include


main()

{

int a,*p;

p=&a;

*p=25;

cout


Page 11

Variabel pointer hanya perlu increment Lihat contoh-contoh!

Source Code

#include


main()

{

int a[5]={1,2,3,4,5};

int *p;

p=a;

cout


Page 12

Tampilan Hasil


Page 13

BAB 2

STRUCTURE

2.1 Pengertian

Structure (struktur) adalah kumpulan elemen-elemen data

yang digabungkan menjadi

satu kesatuan. Masing-masing elemen data tersebut dikenal dengan

sebutan field. Field data tersebut dapat memiliki tipe data yang sama

ataupun berbeda. Walaupun fieldfield tersebut berada dalam satu

kesatuan, masing-masing field tersebut tetap dapat diakses secara

individual.

Field-field tersebut digabungkan menjadi satu dengan tujuan

untuk kemudahan dalam

operasinya. Misalnya Anda ingin mencatat data-data mahasiswa dan

pelajar dalam sebuah program, Untuk membedakannya Anda dapat

membuat sebuah record mahasiswa yang terdiri dari field nim, nama,

alamat dan ipk serta sebuah record pelajar yang terdiri dari field-field

nama, nonurut, alamat dan jumnilai. Dengan demikian akan lebih

mudah untuk membedakan keduanya.

Bentuk umum:

1. Menggunakan typedef

typedef struct nama_struct

{

tipe_data ;

tipe_data ;

} ;


Page 14

contoh :

typedef struct Mahasiswa

{

char NIM[8];

char nama[50];

float ipk;

};

2. Tanpa Menggunakan typedef

struct nama_struct

{

tipe_data field1; Atau

tipe_data field2;

tipe_data fieldn;

};

contoh :

struct mahasiswa

{

char nim[11];

char nama[30]; Atau

char alamat[50];

float ipk;

};


Page 15

2.2. Penggunaan dan pengaksesan Elemen terstruktur

Untuk menggunakan struktur, tulis nama struktur

beserta dengan fieldnya yang dipisahkan dengan tanda titik ( .

). Misalnya Anda ingin menulis nim seorang mahasiswa ke

layar maka penulisan yang benar adalah sebagai berikut:

mahasiswa.nim = 0818107;

cout


Page 16

Contoh: Program Struktur


Page 17

Latihan:

1. Buat program menghitung durasi rental warnet, dengan

ketentuan perhitungannya:

30 detik = Rp. 130,- Satuan waktu : jam : menit : detik

2. Buat program menghitung jumlah nilai akhir mahasiswa

dengan

ketentuan:

Nilai akhir = 10%*tugas + 20%*kuis + 30%*mid +

40%*uas

Nilai Huruf:

Nilai akhir >85 : A

85 >= nilai akhir > 70 : B

70 >= nilai akhir > 55 : C

55 >= nilai akhir > 40 :D

Nilai akhir


Page 18

BAB 3

REKURSIF 3.1 Pengertian

Rekursif adalah salah satu metode dalam dunia

matematika dimana definisi sebuah fungsi mengandung fungsi

itu sendiri. Dalam dunia pemrograman, rekursi

diimplementasikan dalam sebuah fungsi yang memanggil

dirinya sendiri dan prosesnya terjadi secara berulangulang.

3.2 Faktorial Rekursif

n! = 1 if n=0 anchor

n! = n*(n-1)! if n>0 inductive step

0! = 1 2! = 2*(2-1)! 3! = 3*(3-1)!

= 2*1! = 3*2!

1! = 1*(1-1)! = 2*1 = 3*2

= 1*0! = 2 = 6

= 1*1

= 1


Page 19

NB : 0! = 1

Tabel Peningkatan Nilai Faktorial

Contoh: Imlementasi rekursif dari fungsi faktorial

#include


long faktorial(int nilai)

{

if(nilai


Page 20

TAMPILAN HASIL

Tugas

Buat faktorial dengan ketentuan

Banyak faktorial diinputkan dari keyboard

Dapat diulang kembali

Untuk script kreasikan sendiri tidak boleh

sama dengan modul


Page 21

BAB 4

Fibonacci 4.1 Pengertian

Fibonacci adalah 1,1,2,3,5,8,13,21,34,55 . . . . . Setiap

bilangan setelah bilangan kedua merupakan jumlah dari dua

bilangan sebelumnya. Dengan demikian 2 dari 1+1, 3 dari 2+1,

5 dari 3+2 demikian seterusnya yang merupakan definisi

rekursif dan secara sistematis dijabarkan sebagai berikut.

Jika n = 0, maka Fn= 0,

Jika n = 1, maka Fn =1,

Jika n > 1, maka Fn= F(n-1)+ F(n-2)

Implementasi dari fungsi Fibonocci secara logik

ekuivalent dengan translasi langsung dari definisi diatas.

Karena Fn = n untuk n


Page 22

Contoh: Program Rekursif dari fungsi Fibonacci

#include


long fibo(int n)

{

if(n


Page 23

TAMPILAN HASIL

Tugas

Buat fibonacci dengan ketentuan

Banyak fibonacci diinputkan dari keyboard



sama dengan modul


Page 24

BAB 5

Menara Hanoi

5.1 Pengertian

Permainan menara hanoi merupakan contoh klasik di mana

solusinya memerlukan rekursif. Permainan terdiri dari papan dengan

3 tiang yang diberi label A, B, dan C, dan tumpukan cakram yang

disusun besar ke kecil (dari bawah ke atas ) pada tiang A. Aturannya

adalah tidak boleh ada cakram yang lebih besar berada di atas

cakram kecil. Tujuan permainan adalah memindahkan seluruh

cakram dari tiang A ke tiang C, satu persatu dengan melalui menara

B sebagai menara tampungan.

Solusi umum permainan ini pada dasarnya adalah rekursif.

Bagian I : Pindahkan n-1 cakram yang lebih kecil dari A ke B

Bagian II : Pindahkan sisa cakram dari A ke C

Bagian III : Pindahkan n-1 cakram dari B ke C

Bagian I dan III adalah rekursif; Terapkan solusi lengkap n-1

cakram. Basis dari rekursif ini adalah kasus di mana n=0, pada kasus

ini tidak ada yang di kerjakan.


Page 25

Contoh: Program Rekursif dari Menara Hanoi

#include


void hanoi(int n,char x, char y, char z)

{

if(n==1)

{

cout


Page 26

TAMPILAN HASIL

Tugas

Buat program menara hanoi dengan ketentuan

Banyak cakram ditentukan user & inputan dari

keyboard



sama dengan modul


Page 27

TUGAS :

Menghitung X pangkat n secara rekursif Buatlah Program

untuk menghitung X pangkat n secara rekursif, di mana n adalah

bilangan integer positif.

Solusi: secara rekursif n=2:

n=0 X0 = 1

n=1 X1 = X

n=2 X2 = X*X

n=3 X3 = X*X*X

n=4 X4 = X*X*X*X

n=N Xn = X*X*......X

Dengan Output program :

Masukan harga x :

Masukan harga n :

x pangkat n =


Page 28

BAB 6

STACK (TUMPUKAN)

6.1. Tujuan Instruksional Umum

a. Mahasiswa mampu melakukan perancangan aplikasi

menggunakan Struktur Stact (tumpukan)

b. Mahasiswa mampu melakukan analisis pada algoritma Stack

yang dibuat

c. Mahasiswa mampu mengimplementasikan algoritma Stack

pada sebuah aplikasi secara tepat dan efisien

6.2. Tujuan Instruksional Khusus

a. Mahasiswa mampu menjelaskan mengenai algoritma Stack

b. Mahasiswa mampu membuat dan mendeklarasikan struktur

algoritma Stack

c. Mahasiswa mampu menerapkan dan mengimplementasikan

algoritma Stack

6.3 Pengertian Stack

Stack atau tumpukan adalah suatu stuktur data yang

penting dalam pemrograman, bersifat LIFO (Last In First Out)

dimana benda yang terakhir masuk ke dalam stack akan

menjadi benda pertama yang dikeluarkan dari stack.

Contohnya, karena kita menumpuk Compo di posisi terakhir, maka


Page 29

Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya,

karena kita menumpuk Televisi pada saat pertama kali, maka elemen

Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita

mengambil elemen dari tumpukan, maka secara otomatis akan

terambil elemen teratas, yaitu Compo juga, seperti pada gambar

6.3.

6.3 Stack

6.4 Operasi-operasi/fungsi Stack

Push : digunakan untuk menambah item pada stack pada

tumpukan paling atas

pop : digunakan untuk mengambil item pada stack pada

tumpukan paling atas

Clear : digunakan untuk mengosongkan stack

IsEmpty : fungsi yang digunakan untuk mengecek apakah stack


Page 30

sudah kosong

IsFull : fungsi yang digunakan untuk mengecek apakah

stack sudah penuh

6.5 Stack dengan struktur array

1. Mendefinisikan Stack dengan menggunakan struct

2. Mendefinisikan MAX_STACK untuk maksimum isi stack

3. Membuatlah variabel array data sebagai implementasi stack

secara nyata

4. Mendeklarasikan operasi-operasi/function di atas dan buat

implemetasinya

6.6 Deklarasi STACK dengan struct dan array data

typedef struct STACK

{

int top;

char data[10][10];

//misalkan : data adalah array of string

//berjumlah 10 data, masing-masing string

//menampung maksimal 10 karakter

};


Page 31

Deklarasi/buat variabel dari struct

STACK tumpuk;

Deklarasi MAX_STACK

#define MAX_STACK 10

//hati-hati mulai dari 0 jadi 0-9

6.7 Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C

dimulai dari 0, yang berarti stack adalah KOSONG! Top

adalah suatu variabel penanda dalam STACK yang

menunjukkan elemen teratas Stack sekarang. Top Of

Stack akan selalu bergerak hingga mencapai MAX of

STACK sehingga menyebabkan stack PENUH!

Ilustrasi stack pada saat inisialisasi seperti pada gambar 6.7:


Page 32

Gambar 6.7 Inisialisasi Stack

6.8 Fungsi IsFull

Untuk memeriksa apakah stack sudah penuh? Dengan

cara memeriksa top of stack, jika sudah sama dengan

MAX_STACK-1 maka full, jika belum (masih lebih kecil dari

MAX_STACK-1) maka belum full seperti pada gambar 5.8.


Page 33

Gambar 6.8 Ilustrasi Fungsi IsFull

6.9 Fungsi Push

Untuk memasukkan elemen ke stack, selalu menjadi

elemen teratas stack. Tambah satu (increment) nilai top of

stack terlebih dahulu setiap kali ada penambahan elemen stack,

asalkan stack masih belum penuh, kemudian isikan nilai baru

ke stack berdasarkan indeks top of stack setelah ditambah

satu (diincrement) seperti pada gambar 6.9


Page 34

Gambar 6.9 Ilustrasi dan sintaks fungsi Push

6.10 Fungsi Pop

Untuk mengambil elemen teratas dari stack.Ambil

dahulu nilai elemen teratas stack dengan mengakses top of

stack, tampilkan nilai yang akan diambil terlebih dahulu, baru

didecrement nilai top of stack sehingga jumlah elemen stack

berkurang seperti pada gambar 6.10.


Page 35

Gambar 6.10. Ilustrasi fungsi POP

Sintaks program fungsi POP


Page 36

6.11 Fungsi Print

Untuk menampilkan semua elemen-elemen stack. Dengan

cara looping semua nilai array secara terbalik, karena kita harus

mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks

yang kecil seperti pada gambar 6.11.

Gambar 611. Ilustrasi fungsi Print


Page 37

Sintaks program fungsi Print:

void TampilStack()

{

for(int i=tumpuk.top;i>=0;i--)

{

cout


Page 38

Algoritma Pop Stack Soal:

1. Jika berupa operand, maka masukkan ke Stack Hasil

2. Jika berupa operator, maka:

a. Pop nilai pertama dari Stack Hasil

b. Pop nilai kedua dari Stack Hasil

c. Lakukan operasi sesuai dengan operator yang didapat.

Misalnya untuk contoh di atas pada gambar 6.13:

Gambar 6.13 Ilustrasi algoritma pop 5 dan 2 pada stack

Operator * di pop dari Stack Soal, pop Stack Hasil dua

kali, yaitu 5 dan 2 kemudian, simpan 5 ke dalam variabel

misalnya a, dan 2 ke dalam variabel misalnya b. Lalu lakukan

operasi sesuai dengan operatornya, b a. Jadi b * a, yaitu 2

* 5 kemudian hasilnya disimpan lagi ke dalam StackHasil seperti

pada gambar 6.14.


Page 39

Gambar 6.14. Ilustrasialgoritma pop 3 dan 8 pada stack

Kemudian lakukan langkah yang sama, sampai selesai.

Pada contoh: operator + dipop dari Stack Soal, pop Stack

Hasil dua kali, yaitu 3, disimpan pada variabel a, dan 2, disimpan

pada variabel b. Kemudian lakukan operasi sesuai dengan

operatornya, b a. Jadi b + a, yaitu 8 + 3 = 11.

Contoh, cara lain:

Penghitungan: ((1 + 2) * 4) + 3 dapat ditulis berurut ke bawah secara

postfix dengan

keuntungan tanpa preseden pada aturan dan pokok masalahnya:

1 2 + 4 * 3 +


Page 40

Persamaan di masukan dari kiri ke kanan menggunakan stack:

1. push operand yang dihtung dan

2. pop two operand dan nilai hasil operasi penghitungan.

3. push hasil penghitungan

dengan langkah seperti diilustrasikan berikut ini

Hasil akhir, 15 dan tinggalkan pada top stack dan selesai

menghitung


Page 41

Contoh pemanfaatan stack

Notasi Infix Prefix

Notasi Infix Postfix

6.13 NOTASI ARITMETIK (INFIX, PREFIX, DAN

POSTFIX)

Notasi aritmetik biasa ditulis dalam notasi Infix, missal

A+B-C. Notasiinfix mudah dimengerti oleh manusia, hanya

saja dalam notasi infix perlu diperhatikan prioritas pengerjaan

karena berhubungan dengan hirarki operator pada computer.

Prioritas pengerjaannya adalah :

1. Tanda kurung : ( . )

2. Eksponensial atau pangkat : ^

3. Perkalian, pembagian : * , /

4. Penjumlahan, Pengurangan : +, -

Contoh : (A-B) * (C+D)

Prioritas pengerjaan soal diatas adalah sebagai berikut :

a. Dalam kurung yang paling kiri : (A-B)

b. Dalam kurung yang kedua : (C-D)


Page 42

c. Perkalian hasil pengurangan dengan hasil penjumlahan.

Notasi Prefix dan Notasi Postfix lebih mudah dikerjakan oleh

computer.

PREFIX adalah keadaan dimana symbol operator diletakan

sebelum dua operand.

POSTFIX adalah keadaan dimana symbol operator diletakan

sesudah dua operand.

Aturan notasi infix, prefix dan postfix :

- Notasi Infix : operand operator operand A + B

- Notasi Prefix : operator operand operand + A B (disebut juga

Poslish Notation PN)

- Notasi Postfix : Operand operand operator (disebut juga

Reveser Polish Notation RPN)

Contoh ke-1 : INFIX ke PREFIX (A+B) (C*D)

Cara pengerjaan :

a. Pengerjaan dalam kurung ke-1 : (A+B), prefixnya adalah

+AB

b. Pengerjaan dalam kurung ke-2 : (C*D), prefixnya adalah

*CD


Page 43

c. Terakhir adalah operator - , +AB - *CD, prefix nya adalah

-+AB * CD

Contoh ke-2 : INFIX ke POSTFIX (A+B) (C*D)

Cara pengerjaan :

a. Pengerjaan dalam kurung ke-1 : (A+B), postfixnya adalah

AB+

b. Pengerjaan dalam kurung ke-2 : (C*D), postfixnya adalah

CD*

c. Terakhir adalah operator - , AB+ - CD*, postfix nya adalah

AB+ CD*-

Contoh ke-3 : PREFIX ke INFIX: +/*ABCD

Cara pengerjaan : mencari operator dimulai dari operand

terkanan.

a. Cari operator ke-1 : *, ambil dua operand sebelumnya A dan

B, sehingga infixnya adalah (A*B)

b. Cari operator ke-2 : /, ambil dua operand sebelumnya (A*B)

dan C, sehingga infixnya adalah ((A*B)/C)

c. Cari operator ke-3 : +, ambil dua operand sebelumnya

((A*B)/C) dan D, sehingga infixnya adalah ((A*B)/C)+D


Page 44

Contoh ke-4 : PREFIX ke POSTFIX: +/*ABCD


terkanan.

a. Cari operator ke-1 : *, ambil dua operand sebelumnya A dan

B, sehingga postfixnya adalah AB*

b. Cari operator ke-2 : /, ambil dua operand sebelumnya AB*

dan C, sehingga postfixnya adalah AB* C/

c. Cari operator ke-3 : +, ambil dua operand sebelumnya AB*

C/ dan D, sehingga postfixnya adalah AB* C/ D+

Contoh ke-5 : POSTFIX ke INFIX : ABCD*/-


terkiri.

a. Cari operator ke-1 : *, ambil dua operand sebelumnya C dan

D, sehingga infixnya adalah (C*D)

b. Cari operator ke-2 : /, ambil dua operand sebelumnya B dan

(C*D), sehingga infixnya adalah (B/(C* D))

c. Cari operator ke-3 : -, ambil dua operand sebelumnya A dan

(B/(C* D)), sehingga infixnya adalah A- (B/(C* D)).


Page 45

Contoh ke-6 : POSTFIX ke PREFIX : ABCD*/-


terkiri.

a. Cari operator ke-1 : *, ambil dua operand sebelumnya C dan

D, sehingga prefixnya adalah *CD

b. Cari operator ke-2 : /, ambil dua operand sebelumnya B dan

*CD, sehingga prefixnya adalah /B *CD

c. Cari operator ke-3 : - , ambil dua operand sebelumnya A dan

/B *CD, sehingga prefixnya adalah A /B *C

Untuk lebih jelasnya.

Algoritma Infix ke Postfix

Contoh sederhana

3 + 2 * 5

stac

k

posftix

infix


Page 46

6.14 Aturan Pengerjaan

1. Baca soal dari depan ke belakang

2. Jika berupa operand, maka masukkan ke posftix

3. Jika berupa operator, maka:

Jika stack masih kosong, push ke stack

Jika derajat operator soal > derajat operator top of

stack

Push operator soal ke stack

Selama derajat operator soal


Page 47

Contoh lain

a+b*c-d

Stack (kosong) dan Postfik (kosong)

Scan a

Postfik: a

Scan +

Stack: +

Scan b

Postfik: ab

Scan *, karena ToS (+) < *, maka add ke Stack

Stack: +*

Scan c

Postfik: abc

Scan , karena * > -, maka pop Stack, dan add ke Postfik

Stack: +


Page 48

Postfik: abc*

Karena + >= -, maka pop Stack, dan add ke Postfik,

karena Stack kosong, maka push ke stack

Stack: -

Postfik: abc*+

Scan d

Postfik: abc*+d

Karena sudah habis, push ToS stack ke Posfix

Postfix: abc*+d-

Penggunaan notasi postfix dalam stack, misal :

2 14 + 5 * = 80

push 2 pop 14 push 5 pop 5 pop 80

push 14 pop 2 pop 16

push 2

+ 14

push 16

* 5

14 5

2 16 16 80


Page 49

Contoh : Ubah ekspresi A+B*C+(D+E)*F ke dalam notasi

postfix dengan menggunakan algoritma Dijkstra


Page 50

Contoh Stack

#include

#include

#define MAXSTACK 100


typedef int itemType;

typedef struct

{

int item[MAXSTACK];

int jml;

} Stack;

void init(Stack *s)

{

s->jml=0;

}

int kosong(Stack *s)

{

return (s->jml==0);

}

int penuh(Stack *s)

{

return (s->jml==MAXSTACK);

}

void isi(itemType x, Stack *s)

{

if(penuh(s))

{

cout


Page 51

{

s->item[s->jml]=x;

++(s->jml);

}

}

void ambil(Stack *s, itemType *x)

{

if(kosong(s))

{

coutjml]=0;

cout


Page 52

cout


Page 53

case 2:

ambil(&tumpukan,&data);

break;

case 3:

tampil(&tumpukan);

break;

case 4:

hapus(&tumpukan);

break;

}

}

while(pil!=5);

cout


Page 54

BAB 6

QUEUE

6.1 Pengertian

Secara harfiah queue dapat diartikan sebagai

antrian. Queue merupakan kumpulan data dengan

penambahan data hanya melalui satu sisi, yaitu belakang

(tail) dan penghapusan data hanya melalui sisi depan

(head). Berbeda dengan stack yang bersifat LIFO maka

queue bersifat FIFO(First In First Out), yaitu data yang

pertama masuk akan keluar terlebih dahulu dan data yang

terakhir masuk akan keluar terakhir. Berikut ini adalah

gambaran struktur data queue seperti pada gambar 6.1.

6.1 Gambaran Queue


Page 55

Elemen yang pertama kali masuk ke dalam queue

disebut elemen depan (front/head of queue), sedangkan

elemen yang terakhir kali masuk ke queue disebut elemen

belakang (rear/tail of queue).

Perbedaan antara stack dan queue terdapat pada

aturan penambahan dan penghapusan elemen. Pada stack,

operasi penambahan dan penghapusan elemen dilakukan

di satu ujung. Elemen yang terakhir kali dimasukkan akan

berada paling dekat dengan ujung atau dianggap paling

atas sehingga pada operasi penghapusan, elemen teratas

tersebut akan dihapus paling awal, sifat demikian dikenal

dengan LIFO. Pada queue, operasi tersebut dilakukan di

tempat yang berbeda. Penambahan elemen selalu

dilakukan melalui salah satu ujung, menempati posisi di

belakang elemenelemen yang sudah masuk sebelumnya

atau menjadi elemen paling belakang. Sedangkan

penghapusan elemen dilakukan di ujung yang berbeda,

yaitu pada posisi elemen yang masuk paling awal atau

elemen terdepan. Sifat yang demikian dikenal dengan

FIFO.


Page 56

Walaupun berbeda implementasi, struktur data queue

setidaknya harus memiliki operasi-operasi sebagai berikut

:

Inisialisasi Menginisialisasi antrian

EnQueue Memasukkan data ke dalam

antrian

DeQueue Mengeluarkan data terdepan

dari antrian

Clear Menghapus seluruh antrian

IsEmpty Memeriksa apakah antrian

kosong

IsFull Memeriksa apakah antrian

penuh


Page 57

Adapun pendeklarasian queue dapat dilakukan dengan 2 cara,

yaitu :

6.2 Implementasi Queue dengan Linear Array

Berikut ini diberikan deklarasi kelas Queue Linear

sebagai implementasi dari Queue

menggunakan linear array. Dalam prakteknya, anda

dapat menggantinya sesuai dengan kebutuhan Anda.

Data diakses dengan field data, sedangkan indeks item

pertama dan terakhir disimpan dalam field Head dan

Tail. Konstruktor akan menginisialisasikan nilai Head

dan Tail dengan -1 untuk menunjukkan bahwa antrian

masih kosong dan mengalokasikan data sebanyak

MAX_QUEUE yang ditunjuk oleh Data. Destruktor

akan mengosongkan antrian kembali dan

mendealokasikan memori yang digunakan oleh antrian.

6.3 Operasi-operasi Queue dengan Linear Array

6.3.1 Pendeklarasian sebuah queue

Setiap queue memiliki elemen-elemen (field)

berupa posisi depan, posisi belakang, elemen

antrian, dan maksimal elemennya.

6.3.2 Inisialisasi queue


Page 58

Inisialisasi queue adalah proses pemberian nilai 0

untuk field depan dan belakang dari queue dan

juga pemberian nilai maks ke maks_queue yang

menunjukan banyaknya maksimal data dalam

queue. Karena dalam bahasa C++ elemen sebuah

array dimulai dengan 0 maka proses inisialisasi

nilai depan dan belakang bukan 0 tetapi -1

sehingga ketika ada proses penambahan elemen

(enqueue) akan bernilai 0 sehingga elemen tersebut

akan disimpan dalam elemen antrian pada posisi 0.

6.3.3 Fungsi kosong

Fungsi kosong digunakan untuk memeriksa apakan

keadaan queue tidak memiliki elemen. Fungsi

kosong didapatkan dengan memeriksa field

belakang dari queue. Jika field belakang bernilai 0

maka berarti queue kosong dan jika tidak 0 maka

berarti queue mempunyai elemen. Implementasi

dalam bahasa C++ agak berbeda karena elemen

array dimulai dari 0 sehingga pemeriksaan nilai

belakang dilakukan dengan membandingkannya

dengan nilai -1. Jika nilai belakang bernilai -1


Page 59

maka queue kosong (true) dan jika lebih dari -1

berarti queue tidak kosong (false).

6.3.4 Fungsi penuh

Fungsi penuh berguna untuk memeriksa apakah

suatu queue telah penuh. Fungsi ini diperlukan

ketika proses enqueue. Fungsi ini akan bernilai

benar (true) jika field belakang sama dengan nilai

maks_queue jika tidak sama dengan berarti queue

belum penuh. Dalam bahasa C++ perbandingan

yang dilakukan adalah bukan dengan maks_queue

tetapi dengan nilai maks_queue-1 karena elemen

array dalam bahasa C++ dimulai dari posisi 0.

6.3.5 Operasi enqueue

Proses enqueue adalah proses untuk penambahan

di posisi belakang. Penambahan ini dilakukan jika

kondisi queue tidak penuh. Jika keadaan masih

kosong, maka field depan dan belakang bernilai 1

tetapi jika sudah mempunyai elemen maka yang

nilai belakang harus bertambah 1. Kemudian data

baru disimpan di array pada posisi

belakang.Implementasi dalam C++ harus


Page 60

melakukan penyesuaian karena elemen array C++

dimulai dari 0 sehingga ketika queue masih kosong

pemberian nilai depan dan belakang adalah 0

bukan 1.

6.3.7 Operasi dequeue

Operasi dequeue adalah proses pengambilan

elemen queue. Tentunya elemen yang diambil

selalu dari elemen pertama (1). Setelah elemen

pertama diambil, maka akan diperlukan proses

pergeseran elemen data setelah elemen data yang

diambil (dari posisi ke-2 sampai posisi paling

belakang), dan kemudian posisi belakang akan

dikurangi 1 karena ada data yang diambil.

Implementasi dalam bahasa C++ dilakukan dengan

pengambilan elemen pada posisi 0.


Page 61

Contoh Queue dengan Linear Array

#include

#define max 8


typedef struct

{

int data[max];

int head;

int tail;

}Queue;

Queue antrian;

void init()

{

antrian.head = antrian.tail = -1;

}

int kosong()

{

if(antrian.head==-1)

{

return 1; //data kosong

}

else

{

return 0; //data berisi

}

}

int penuh()

{

if(antrian.tail==max-1)

{

return 1; //data penuh

}

else

{


Page 62

return 0; //data berisi

}

}

void masuk()

{

int data;

cout data;

if(penuh()==0)

{

antrian.tail++;

antrian.data[antrian.tail]=data;

cout


Page 63

void tampil()

{

if(kosong()==0)

{

for(int

i=antrian.head+1;i


Page 64

masuk();

break;

}

case 2:

{

keluar();

break;

}

case 3:

{

clear();

break;

}

case 4:

{

tampil();

break;

}

default :

{

cout=1 && pil


Page 65

TAMPILAN HASIL

6.4 Implementasi Queue dengan Circular Array

Salah satu variasi array adalah array melingkar

(circular array), artinya array dapat diakses mulai dari

sembarang indeks (indeks awal) ke arah indeks terakhir

(maksimum array), lalu memutar ke indeks pertama

hingga kembali ke indeks awal. Circular array adalah

array yang dibuat seakanakan merupakan sebuah

lingkaran dengan titik awal dan titik akhir saling

bersebelahan jika array tersebut masih kosong. Jumlah

data yang dapat ditampung oleh array ini adalah

besarnya ukuran array dikurangi 1. Misalnya besar

array adalah 8, maka jumlah data yang dapat ditampung


Page 66

adalah 7.

Dengan circular array, meskipun posisi terakhir telah

terpakai, elemen baru tetap dapat ditambahkan pada

posisi pertama jika posisi pertama dalam keadaan

kosong. Jika akhir=MAX dan awal=1, nilai head dan

tail mencapai maksimum, maka akan dikembalikan ke

posisi awal. Operasioperasi yang terdapat pada circular

array tidak jauh berbeda dengan operasi pada linear

array.

Atau lebih jelasnya seperti gambar di bawah ini :


Page 67

Aturan-aturan dalam queue yang menggunakan circular

array adalah :

1. Proses penghapusan dilakukan dengan cara nilai

depan (front) ditambah 1:

depan=depan + 1.

2. Proses penambahan elemen sama dengan linear array

yaitu nilai belakang

ditambah 1 : belakang=belakang + 1.

3. Jika depan = maks dan ada elemen yang akan

dihapus, maka nilai depan = 1.

4. Jika belakang = maks dan depan tidak 1 maka jika


Page 68

ada elemen yang akan

ditambahkan, nilai belakang=1

5. Jika hanya tinggal 1 elemen di queue (depan =

belakang), dan akan dihapus maka

depan diisi 0 dan belakang diisi dengan 0 (queue

kosong).

Contoh :

Untuk mempermudah, elemen dari queue bertipe

karakter.


Page 69

6.4.1 Pendeklarasian Queue


Page 70

Setiap queue memiliki elemen-elemen (field)

berupa posisi depan, posisi belakang, elemen antrian,

dan maksimal elemennya.

6.4.2 Inisialisasi Queue

Inisialisasi queue adalah proses pemberian nilai 0

untuk field depan dan belakang dari queue dan juga

pemberian nilai maks ke maks_queue yang menunjukan

banyaknya maksimal data dalam queue. Karena dalam

bahasa C++ elemen sebuah array dimulai dengan 0

maka proses inisialisasi nilai depan dan belakang bukan

0 tetapi -1 sehingga ketika ada proses penambahan

elemen (enqueue) akan bernilai 0 sehingga elemen

tersebut akan disimpan dalam elemen antrian pada

posisi 0.

6.4.3 Fungsi Kosong

Suatu queue yang menggunakan circular array

dapat dikatakan kosong jika nilai yang menunjuk posisi

depan atau belakang mempunyai nilai 0. Implementasi

dalam bahasa C++, perbandingan posisi depan atau

belakang dilakukan bukan dengan angka 0 tetapi angka


Page 71

-1 karena angka 0 menunjukan elemen pertama dari

array.

6.4.5 Fungsi Penuh

Suatu queue akan disebut penuh jika terjadi 2

hal yaitu jika nilai depan mempunyai nilai 1 dan posisi

belakang sama dengan maks_queue atau jika posisi

depan sama dengan posisi belakang +1. Jika salah satu

dari 2 hal tersebut terjadi maka fungsi penuh

mempunyai nilai true dan jika tidak terjadi 2 hal

tersebut maka fungsi bernilai false. Implementasi dalam

bahasa C++ agar beda karena posisi awal array bukan 1

tapi 0 dan posisi terakhir data adalah maks_queue-1

bukan maks_queue.

6.4.6 Operasi Enqueue

Proses enqueue data hanya bisa dilakukan jika queue

tidak kosong. Ada

beberapa hal yang harus diperhatikan ketika akan

melakukan enqueue pada circular array, diantaranya

adalah :


Page 72

1. Kondisi ketika queue masih kosong. Jika ini terjadi,

maka posisi depan dan belakang bernilai 0.

2. Ketika ketika nilai belakang sama dengan

maks_queue, maka posisi belakang adalah 0. Ini terjadi

ketika posisi depan lebih besar dari 0 (pernah ada

dequeue).

3. Ketika nilai belakang masih lebih kecil dari

maks_queue maka posisi belakang ditambah 1 :

belakang=belakang+1;

Dari ketentuan-ketentuan di atas dapat

diimplementasikan dalam bahasa C++ dengaN

mengganti beberapa hal yaitu posisi

perbandingan/pengisian dengan nilai 0 diganti dengan

perbandingan/pengisian dengan nilai -1 dan

perbandingan dengan nilai maks_queue diganti dengan

maks_queue-1 Itu disebabkan karena dalam bahasa

C++ array dimulai dari 0.


Page 73

6.4.7 Operasi Dequeue

Proses dequeue hanya bisa dilakukan jika queue dalam

keadaan tidak kosong.

Ada beberapa kondisi yang harus diperhatikan ketika

dequeue elemen queue

yaitu :

1. Kondisi ketika posisi depan sama dengan posisi

belakang (queue hanya memiliki 1 elemen) maka nilai

depan dan belakang diisi dengan 0 (queue kosong).

2. Jika posisi depan sama dengan posisi maks_queue

maka posisi depan berpindah ke 1.

3. Selain itu, posisi depan ditambah dengan 1 :

depan=depan+1

Ketika kita mengimplementasikannya dalam bahasa

C++, maka ada beberapa hal yang harus diganti adalah

semua pengisian/perbandingan dengan angka 1 diganti

dengan 0 (karena elemen array dalam bahasa C++

adalah 0),


Page 74

serta ketika ada perbandingan/pengisian dengan nilai 0

diganti dengan -1 dan perbandingan/pengisian dengan

nilai maks_queue diganti dengan maks_queue-1.

Contoh: Program circular array

#include


typedef struct

{

int data[5];

int head;

int tail;

}Queue;

Queue antri;

typedef struct

{

int baru;

}struk;

struk variabel;

void input()

{

if(antri.tail== 5-1)

{

coutvariabel.baru;


Page 75

antri.tail++;

antri.data[antri.tail]=variabel.baru;

}

}

void out()

{

if(antri.tail== -1)

{

cout


Page 76

adalah : "


Page 77

switch (pil)

{

case 1:

{

input();

break;

}

case 2:

{

out();

break;

}

case 3:

{

cetak();

break;

}

default :

{

cout


Page 78

TAMPILAN HASIL


Page 79

BAB 7

Sorting

7.1 Pendahuluan

- Pengurutan data dalam struktur data sangat penting

terutama untuk data yang beripe data numerik ataupun

karakter.

- Pengurutan dapat dilakukan secara ascending (urut

naik) dan descending (urut turun)

- Pengurutan (Sorting) adalah proses pengurutan data

yang sebelumnya disusun secara acak sehingga

tersusun secara teratur menurut aturan tertentu

Contoh:

Data Acak : 5 6 8 1 3 25 10

Ascending : 1 3 5 6 8 10 25

Descending: 25 10 8 6 5 3 1

7.1 DEKLARASI ARRAY UNTUK SORTING

Deklarasikan secara global:

int data[100];

int n; //untuk jumlah data

Prosedur Tukar 2 Buah Data:


Page 80

void tukar(int a,int b)

{

int tmp;

tmp = data[a];

data[a] = data[b];

data[b] = tmp;

}

7.3 BUBBLE SORT

- Metode sorting termudah

- Diberi nama Bubble karena proses

pengurutan secara berangsur-angsur

bergerak/berpindah ke posisinya yang

tepat, seperti gelembung yang keluar

dari sebuah gelas bersoda.

- Bubble Sort mengurutkan data dengan

cara membandingkan elemen

sekarang dengan elemen berikutnya.

- Jika elemen sekarang lebih besar dari

elemen berikutnya maka kedua

elemen tersebut ditukar, jika

pengurutan ascending.


Page 81

- Jika elemen sekarang lebih kecil dari elemen

berikutnya, maka kedua elemen tersebut ditukar, jika

pengurutan descending

- Algoritma ini seolah-olah menggeser satu per satu

elemen dari kanan ke kiri atau kiri ke kanan,

tergantung jenis pengurutannya.

- Ketika satu proses telah selesai, maka bubble sort akan

mengulangi proses, demikian seterusnya.

- Kapan berhentinya? Bubble sort berhenti jika seluruh

array telah diperiksa dan tidak ada pertukaran lagi

yang bisa dilakukan, serta tercapai perurutan yang

telah diinginkan.

Proses 1 tedapat pada gambar 1.1

Gambar 1.1 Proses 1 Bubble Sort


Page 82

Pada gambar 1.1 diatas, pegecekan dimulai dari data

yang paling akhir, kemudian dibandingkan dengan data di

depannya, jika data di depannya lebih besar maka akan ditukar.

Proses 2 terdapat pada gambar 1.2

Gambar 1.2 Proses 2 Bubble Sort

Pada proses kedua, pengecekan dilakukan sampai

dengan data ke-2 karena data pertama

pasti sudah paling kecil.


Page 83

Proses 3


Page 84

Dengan prosedur diatas, data terurut naik (ascending),

untuk urut turun (descending)

silahkan ubah bagian:


Page 85

Contoh Source code

#include


int data[10],data2[10];

int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{

coutn;

cout


Page 86

void bubble_sort()

{

for(int i=1;i=i;j--)

{

if(data[j]


Page 87

cout


Page 88

7.4 EXCHANGE SORT

- Sangat mirip dengan Bubble Sort

- Banyak yang mengatakan Bubble Sort sama dengan

Exchange Sort

- Pebedaan : dalam hal bagaimana membandingkan

antar elemen-elemennya.

Pegurutan berhenti di sini!

- Exchange sort membandingkan suatu elemen dengan

elemen-elemen lainnya dalam array tersebut, dan

melakukan pertukaran elemen jika perlu. Jadi ada

elemen yang selalu menjadi elemen pusat (pivot).

- Sedangkan Bubble sort akan membandingkan elemen

pertama/terakhir dengan elemen

sebelumnya/sesudahnya, kemudian elemen

sebelum/sesudahnya itu akan menjadi pusat (pivot)

untuk dibandingkan dengan elemen

sebelumnya/sesudahnya lagi, begitu seterusnya.


Page 89


Page 90


Page 91

Contoh source code Exchange Sort

#include



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{

coutn;

cout


Page 92

}

cout


Page 93

cout


Page 94

7.5 SELECTION SORT

- Merupakan kombinasi antara sorting dan searching

- Untuk setiap proses, akan dicari elemen-elemen yang

belum diurutkan yang memiliki nilai terkecil atau

terbesar akan dipertukarkan ke posisi yang tepat di

dalam array.

- Misalnya untuk putaran pertama, akan dicari data

dengan nilai terkecil dan data ini akan ditempatkan di

indeks terkecil (data[0]), pada putaran kedua akan dicari

data kedua terkecil, dan akan ditempatkan di indeks

kedua (data[1]).


Page 95

-


Page 96


Page 97

Contoh Source Code Selection Sort

#include



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{

coutn;

cout


Page 98

void Tampil()

{

for(int i=0;i


Page 99

*"


Page 100

7.6 INSERTION SORT

- Mirip dengan cara orang mengurutkan kartu, selembar

demi selembar kartu diambil dan disisipkan (insert) ke

tempat yang seharusnya.

- Pengurutan dimulai dari data ke-2 sampai dengan data

terakhir, jika ditemukan data yang lebih kecil, maka

akan ditempatkan (diinsert) diposisi yang seharusnya.

- Pada penyisipan elemen, maka elemen-elemen lain

akan bergeser ke belakang.


Page 101


Page 102


Page 103

Contoh Source Code Insertion Sort

#include



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{

coutn;

cout


Page 104

"


Page 105

main()

{

cout


Page 106

Tampilan Hasil


Page 107

7.7 Quick sort

Metode sorting dengan quicksort cukup sulit dipahami,

namun metode ini merupakan metode sorting tercepat yang ada

saat ini. Metode ini menggunakan paradigma devide-conquer,

sehingga dalam prosesnya, metode ini membagi array menjadi

2 bagian untuk selanjutnya diproses kembali secara rekursif

dengan memanggil dirinya sendiri (prosedur quicksort itu

sendiri).

Di dalam metode ini dikenal beberapa istilah, yakni :

1. Pivot

Sembarang elemen array yang digunakan sebagai batas.

Pivot ini dapat dipilih secara random, atau dengan

memilih elemen yang berada di tengah array.

2. Partisi

Hasil pembagian array menjadi 2 sub-array melalui

proses pemartisian.

Berikut ini ilustrasi algoritma quicksort.


Page 108


Page 109

Contoh source code

#include



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{

coutn;

cout


Page 110

cout


Page 111

cout


Page 112

Latihan

1. Buatlah program pengurutan dengan metode bubble sort

sejumlah n data bilangan bulat yang

dimasukkan oleh user.

Input :

a. Banyaknya bilangan (n).

b. Data bilangan sebanyak n.

Output :

a. Urutan bilangan secara ascending.

b. Urutan bilangan secara descending.

2. Buatlah program pengurutan dengan metode quicksort

sejumlah n data bilangan bulat yang

dimasukkan oleh user.

Input :

c. Banyaknya bilangan (n).

d. Data bilangan sebanyak n.

Output :

c. Urutan bilangan secara ascending.

d. Urutan bilangan secara descending.

3. Buatlah program untuk mengurutkan data mahasiswa (NPM,

Nama, Alamat, Jenis Kelamin,

Tanggal lahir). Program harus bisa melayani pengurutan secara


Page 113

ascending atau descending dan

pengurutan bisa dipilih berdasarkan nama atau NPM.

4. Buatlah program sorting dengan metode insertion sort. User

akan diminta menginput 10

bilangan yang kemudian akan disort. Sediakan pula fungsi

untuk mencari posisi bilangan (bila

bilangan yang dicari ada pada daftar bilangan yang telah

diurutkan, beritahukan pada urutan

keberapa bilangan tersebut).

5. Buatlah algoritma untuk mengurutkan data-data berikut ini

dengan menggunakan metode quick

sort.

Data datanya : cat, car, cab, cap, can

6. Buatlah program yang akan menampilkan lima angka secara

acak lalu disort dengan metode

insertion sort. Tampilkan langkah-langkah sorting satu persatu

dalam sebuah tabel !


Page 114

BAB 8

SEARCHING

8.1 Pengertian

Dalam kehidupan sehari-hari sebenarnya kita sering

melakukan pencarian data. Sebagai contoh, jika kita

menggunakan Kamus untuk mencari kata-kata dalam

Bahasa Inggris yang belum diketahui terjemahannya dalam

Bahasa Indonesia. Contoh lain saat kita menggunakan buku

telepon untuk mencari nomor telepon teman atau kenalan

dan masih banyak contoh yang lain. Pencarian data sering

juga disebut table look-up atau storage and retrieval

information adalah suatu proses untuk mengumpulkan

sejumlah informasi di dalam pengingat komputer dan

kemudian mencari kembali informasi yang diperlukan

secepat mungkin.

Algoritma pencarian (searching algorithm) adalah

algoritma yang menerima sebuah argumen kunci dan

dengan langkah-langkah tertentu akan mencari rekaman

dengan kunci tersebut. Setelah proses pencarian

dilaksanakan, akan diperoleh salah satu dari dua

kemungkinan, yaitu data yang dicari ditemukan (successful)

atau tidak ditemukan (unsuccessful).


Page 115

Metode pencarian data dapat dilakukan dengan dua

cara yaitu pencarian internal (internal searching) dan

pencarian eksternal (external searching). Pada pencarian

internal, semua rekaman yang diketahui berada dalam

pengingat komputer sedangakan pada pencarian eksternal,

tidak semua rekaman yang diketahui berada dalam

pengingat komputer, tetapi ada sejumlah rekaman yang

tersimpan dalam penyimpan luar misalnya pita atau cakram

magnetis. Selain itu metode pencarian data juga dapat

dikelompokkan menjadi pencarian statis (static searching)

dan pencarian dinamis (dynamic searching). Pada pencarian

statis, banyaknya rekaman yang diketahui dianggap tetap,

pada pencarian dinamis, banyaknya rekaman yang

diketahui bisa berubah-ubah yang disebabkan oleh

penambahan atau penghapusan suatu rekaman.

Ada dua macam teknik pencarian yaitu pencarian

sekuensial dan pencarian biner. Perbedaan dari dua teknik

ini terletak pada keadaan data. Pencarian sekuensial

digunakan apabila data dalam keadaan acak atau tidak

terurut (contoh: sequential search). Sebaliknya, pencarian

biner digunakan pada data yang sudah dalam keadaan urut

(contoh: Binary serach dan interpolation search).


Page 116

8.2 Pencarian Berurutan (Sequential Searching)

Pencarian berurutan sering disebut pencarian linear

merupakan metode pencarian yang paling sederhana.

Pencarian berurutan menggunakan prinsip sebagai berikut :

data yang ada dibandingkan satu per satu secara berurutan

dengan yang dicari sampai data tersebut ditemukan atau

tidak ditemukan.

Pada dasarnya, pencarian ini hanya melakukan

pengulangan dari 1 sampai dengan jumlah data. Pada setiap

pengulangan, dibandingkan data ke-i dengan yang dicari.

Apabila sama, berarti data telah ditemukan. Sebaliknya

apabila sampai akhir pengulangan tidak ada data yang

sama, berarti data tidak ada. Pada kasus yang paling buruk,

untuk N elemen data harus dilakukan pencarian sebanyak N

kali pula.

Algoritma pencarian berurutan dapat dituliskan sebagai

berikut :

1. i 0

2. ditemukan false

3. Selama (tidak ditemukan) dan (i


Page 117

4. Jika (Data[i] = x) maka ditemukan true,

jika tidak i i + 1

5. Jika (ditemukan) maka i adalah indeks dari

data yang dicari, jika tidak data tidak

ditemukan

Konsep : membandingkan setiap setiap elemen larik satu

per satu secara urut (beruntun), mulai dari elemen

pertama sampai dengan elemen yang terakhir. Ada 2

macam pencarian beruntun,yaitu pencarian pada array

yang sudah terurut, dan pencarian pada array yang

belum terurut.


Page 118

Contoh (1):

#include


main()

{

int data[8] = {2,3,4,-

5,56,47,20,98};//datanya :)

int cari;

int tanda=0;

cout>cari;

cout


Page 119

Tampilan Hasil

else

{

cout


Page 120

Contoh (2):

#include


main()

{

int data[9]={1,12,3,4,10,6,7,11,9}, i,n,

x, posisi;

cout


Page 121

Tampilan Hasil

cout


Page 122

8.3 Pencarian Biner (Binary Search)

Salah satu syarat agar pencarian biner dapat dilakukan

adalah data sudah dalam keadaan urut. Dengan kata lain,

apabila data belum dalam keadaan urut, pencarian biner tidak

dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita

juga sering menggunakan pencarian biner. Misalnya saat ingin

mencari suatu kata dalam kamus Prinsip dari pencarian biner

dapat dijelaskan sebagai berikut :

1. Mula-mula diambil posisi awal 0 dan posisi akhir = N -

1, kemudian dicari posisi data tengah dengan rumus

(posisi awal + posisi akhir) / 2. Kemudian data yang

dicari dibandingkan dengan data tengah.

2. Jika lebih kecil, proses dilakukan kembali tetapi posisi

akhir dianggap sama dengan posisi tengah 1.

3. Jika lebih besar, porses dilakukan kembali tetapi posisi

awal dianggap sama dengan posisi tengah + 1.

Demikian seterusnya sampai data tengah sama dengan yang

dicari.Untuk lebih jelasnya perhatikan contoh berikut:


Page 123

Misalnya ingin mencari data 17 pada sekumpulan data

berikut :

Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 =

4. Berarti data tengah adalah data ke-4, yaitu 15. Data yang

dicari, yaitu 17, dibandingkan dengan data tengah ini. Karena

17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal

dianggap sama dengan posisi tengah + 1 atau 5.

Data tengah yang baru didapat dengan rumus (5 + 9) / 2

= 7. Berarti data tengah yang baru adalah data ke-7, yaitu 23.

Data yang dicari yaitu 17 dibandingkan dengan data tenah ini.

Karena 17 < 23, berarti proses dilanjukkan tetapi kali ini posisi

akhir dianggap sama dengan posisi tengah 1 atau 6.

Data tengah yang baru didapat dengan rumus (5 + 6) / 2

= 5. Berarti data tengah yang baru adalah data ke-5, yaitu 17.

data yang dicari dibandingkan dengan data tengah ini dan

ternyata sama. Jadi data ditemukan pada indeks ke-5. Pencarian

biner ini akan berakhir jika data ditemukan atau posisi awal


Page 124

lebih besar daripada posisi akhir. Jika posisi sudah lebih besar

daripada posisi akhir berarti data tidak ditemukan.

Untuk lebih jelasnya perhatikan contoh pencarian data 16

pada data diatas. Prosesnya hampir sama dengan pencarian

data 17. Tetapi setelah posisi awal 5 dan posisi akhir 6, data

tidak ditemukan dan 16 < 17, maka posisi akhir menjadi posisi

tengah 1 atau = 4 sedangkan posisi awal = 5.

Disini dapat dilihat bahwa posisi awal lebih besar

daripada posisi akhir, yang artinya data tidak ditemukan.

Algoritma pencarian biner dapat dituliskan sebagai berikut :

1. L 0

2. R N 1

3. ditemukan false

4. Selama (L Data[m]) maka L m + 1

9. Jika (ditemukan) maka m adalah indeks dari data yang


Page 125

dicari, jika tidak data tidak ditemukan.

Di bawah ini merupakan contoh mencari data

menggunakan pencarian biner.

#include


main()

{

int data[7] = {10,13,17,34,58,67,99};

int N = 7;

int kiri=0,kanan=N-1,tengah,cari;

int tanda=0;

cout>cari;

cout


Page 126

Tampilan Hasil

else

{

kiri=tengah+1;

cout


Page 127

8.4 Interpolation Search

Teknik ini dilakukan pada data yang sudah terurut

berdasarkan kunci tertentu. Teknik searching ini dilakukan

dengan perkiraan letak data. Contoh ilustrasi: jika kita hendak

mencari suatu kata di dalam kamus telepon, misal yang

berawalan dengan huruf J, maka kita tidak akan mencarinya

dari awal buku, tapi kita langsung membukanya pada 1/3 atau

1/4 dari tebal kamus.

Rumus posisi relatif kunci pencarian dihitung dengan rumus:

- Jika data[posisi] > data yg dicari, high = pos 1

- Jika data[posisi] < data yg dicari, low = pos + 1


Page 128

Contoh Interpolation Search

#include #include


main()

{

int data[7] = {10,13,17,34,58,67,99};

int low,high,cari,posisi;

float posisi1;

int N = 7,tanda=0;

low=0,high=N-1;

cout


Page 129

do

{

posisi1 = (cari-

data[low])/(data[high]-data[low])*(high-

low)+low;

posisi = floor(posisi1);

//pembulatan ke bawah

if(data[posisi]==cari)

{

tanda =1;

break;

}

if(data[posisi]>cari)

{

high=posisi-1;

}

else if (data[posisi]=data[low]&&cari


Page 130

Tampilan Hasil

TUGAS :

1. Buatlah program SEARCHING, dengan ketentuan :

Data yang tersedia adalah melalui inputan user.

Banyak data yang di inputkan, di tentukan juga

oleh user.

Setelah pencarian jika data di temukan harus

menyebutkan indeks keberapa data tersebut.

Menyebutkan nilai Maksimum dan Minimum

data.

2. Cari tau tentang Fibonacci search, dan Sequential

search, sertakan sumbernya.


Page 131

BAB 9

LINKED LIST

9.1 Definisi Linked List:

Linked List adalah salah satu bentuk struktur data,

berisi kumpulan data (node) yang tersusun secara

sekuensial, saling sambung-menyambung dan

dinamis.

Linked List sering disebut juga Senarai Berantai.

Linked List saling terhubung dengan bantuan

variabel pointer

Masing-masing data dalam Linked List disebut

dengan node (simpul) yang menempati alokasi

memori secara dinamis dan biasanya berupa struct

yang terdiri dari beberapa field.

9.2 Ilustrasi Linked List:

Singgle Linked List

1. Contoh ilustrasi pada Kehidupan Nyata Tentang

Hubungan pertemanan

And

i

02 Rud

i

03 Ani null

No Rumah

01

No Rumah

02

No Rumah

03


Page 132

2. Contoh ilustrasi di komputer

Doble Linked List

1.

9.3 Perbandingan Array dengan Linked List

Array Linked List

Statis Dinamis

Penambahan/penghapusan

data terbatas

Penambahan/penghapusan

data tidak terbatas

Penghapusan array tidak

mungkin

Penghapusan Linked List

mudah

Random Access Sequential Access

28 FFF2 15 FFF3 21 null

FFF1 FFF2 FFF3

28 28 28


Page 133

9.4 Singgle Linked List

Singgle : artinya field pointer-nya hanya satu buah saja

dan satu arah serta pada akhir node, pointernya

menunjuk NULL.

Linked List : artinya node-node tersebut saling terhubung

antara satu dengan yang lain.

28

dat

a

point

er

NULL

28 FFF2 15 FFF3 21 NULL

FFF1 FFF2 FFF3 NULL

NULL data

point

er


FFF1 FFF2 FFF3


Page 134

setiap node pada linked list mempunyai field yang

berisi pointer ke node berikutnya, dan juga memiliki

field yang berisi data.

node terakhir akan menunjuk ke NULL yang akan

digunakan sebagai kondisi berhenti pada saat

pembacaan isi linked list.

9.5 Jenis Singgle Linked List

Singgle Linked List dengan HEAD

Singgle Linked List dengan HEAD dan TAIL

NULL

NULL

head

28 FFF2 15 FFF3 21 NUL

L

tail head



Page 135

9.6 Deklarasi Singgle Linked List

Deklarasi NODE

struct TNode

{

int data;

TNode *next;

};

TNode *head;

Penjelasan :

Pembuatan struct bernama TNode yang berisi 2

field, yaitu field data bertipe integer dan field

next yang bertipe pointer dari TNode. Setelah

itu membuat variable yang bernama node yang

digunakan kunci untuk mengakses struct

TNode.

Setelah pembuatan struct, buat variabel head

yang bertipe pointer dari TNode yang berguna

sebagai kepala linked list.

Pembuatan NODE baru

TNode *baru;

baru=new TNode;

baru->data=databaru;

baru->next=null;


Page 136

Penjelasan :

keyword new gunanya untuk mempersiapkan

sebuah node baru beserta alokasi memorinya,

kemudian node tersebut diisi data dan pointer

nextnya ditunjuk ke NULL.

Singgle Linked List Menggunakan Head

Head Akan Selalu menunjukkan pada node pertama.

Ilustrasi Penambahan dari depan

1. List Masih Kosong (head==NULL)

NULL

head

head



Page 137

2. Masukkan Data baru, missal 28

3. Masukkan data lagi dari depan, missal 21

28

head


Page 138

Contoh Penambahan dari depan

#include


struct TNode

{

int data;

TNode *next;

};

TNode *head;

void init()

{

head=NULL;

}

int cekkosong()

{

if(head==NULL)

{

return 0;

}

else

{

return 1;

}

}

void isidepan(int databaru)

{

TNode *baru;

baru=new TNode;


baru->next=NULL;

if (cekkosong==0)


Page 139

{

head=baru;

head->next=NULL;

}

else

{

baru->next=head;

head=baru;

}

cout


Page 140

Tampilan Hasil

Ilustrasi Penambahan dari belakang 1. List Masih Kosong (head==NULL)

2. Masukkan Data baru, missal 28

NULL

head

28

head


Page 141

3. Masukkan data lagi dari belakang, missal 21

4. Masukkan data lagi dari belakang, missal 15


Page 142

Contoh Penambahan dari depan

#include


struct TNode

{

int data;

TNode *next;

};

TNode *head;

void init()

{

head=NULL;

}

int cekkosong()

{

if(head==NULL)

{

return 0;

}

else

{

return 1;

}

}

void isibelakang(int databaru)

{

TNode *baru;

TNode *bantu;

baru=new TNode;


baru->next=NULL;


Page 143

if(cekkosong()==0)

{

head=baru;

head->next=NULL;

}

else

{

bantu=head;

while (bantu->next!=NULL)

{

bantu=bantu->next;

}

bantu->next=baru;

}

cout


Page 144

}

}

}

while(pil!=2);

}

Tampilan Hasil

Menampilkan isi linked List


Page 145

Penjelasan :

function di atas digunakan untuk

menampilkan semua isi list, di mana linked

list ditelusuri satu-persatu dari awal node

sampai akhir node. Penelusuran ini

dilakukan dengan menggunakan suatu

pointer bantu, karena pada prinsipnya

pointer head yang menjadi tanda awal list

tidak boleh berubah atau berganti posisinya.

penelusuran dilakaukan terus sampai node

void tampil()

{

TNode *bantu;

bantu=head;

if (cekkosong==0)

{

cout


Page 146

terakhir ditemukan menunjuk ke nilai

NULL. jika tidak null, maka node bantu

akan berpindah ke node selanjutnya dan

membaca isi datanya dengan menggunakan

field next sehingga dapat saling berkait.

jika head masih null berarti data masih

kosong.

Menghapus data dari depan


Page 147

Penjelasan :

function di atas akan menghapus data

terdepan(pertama) yang ditunjuk oleh head

pada linked list.

penghapusan node tidak boleh dilakukan

jika keadaan node sedang ditunjuk oleh

pointer.

sebelum data terdepan dihapus, head harus

ditujukan ke node sesudahnya terlebih

dahulu agar list tidak putus, sehingga node

setelah head lama akan menjadi head

baru(data terdepan yang baru).

void hapusDepan (){

TNode *hapus;

int d;

if (cekkosong()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

delete hapus;

} else {

d = head->data;

head = NULL;

}

cout


Page 148

jika head masih NULL maka berarti data

masih kosong.

Menghapus data dari belakang


Page 149

Penjelasan :

membutuhkan pointer bantu dan hapus.

pointer hapus digunakan untuk menunjuk node

yang akan dihapus, dan pointer bantu digunakan

untuk menunjuk node sebelum node yang

dihapus yang kemudioan selanjutnya akan

void hapusBelakang()

{

TNode *hapus,*bantu;

int d;

if (cekkosong()==0)

{

if(head->next != NULL)

{

bantu = head;

while(bantu->next->next!=NULL)

{

bantu = bantu->next;

}

hapus = bantu->next;

d = hapus->data;

bantu->next = NULL;

delete hapus;

}

else

{

d = head->data;

head = NULL;

}

cout


Page 150

menjadi node terakhir.

pointer bantu akan digunakan untuk menunjuk

ke nilai NULL.

Pointer bantu akan selalu bergerak sampai

sebelum node yang akan dihapus, baru

kemudian pointer hapus diletakkan setelah

pointer bantu. Setelah itu pointer hapus akan

dihapus, pointe bantu akan menunjuk ke NULL.

Singgle Linked List Menggunakan Head dan Tail

Dibutuhkan dua buah variabel pointer yaitu head dan

tail.

Head akan selalu menunjuk pada node pertama,

sedangkan tail akan selalu menunjuk pada node terakhir.


Page 151

Inisialisasi Linked List

TNode *head, *tail;

Fungsi inisialisasi LinkedList void init() {

head=NULL;

tail=NULL;

}

Function untuk mengetahui kosong tidaknya LinkedList int cekkosong()

{

If(tail==null)

{

Return 0;

}

Else

{

Return 1;

}

}


Page 152

Penambahan Data Dari Depan Ilustrasi

1. List Masih Kosong (head=tail=null)

2. Masukkan Data Baru, Misal 28

3. Masukkan data lagi dari depan, missal 15

head tail

28 null

head tail


Page 153

Script penambahan dari depan dengan head dan tail

#include


struct TNode

{

int data;

TNode *next;

};

TNode *head, *tail;

void init()

{

head=NULL;

tail=NULL;

}

int cekkosong()

{

if(tail==NULL)

{

return 0;

}

else

{

return 1;

}

}

void insertDepan(int databaru)

{

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;


Page 154

if(cekkosong()==0)

{

head=tail=baru;

tail->next=NULL;

}

else

{

baru->next = head;

head = baru;

}

cout


Page 155

Tampilan Hasil

Penambahan Data Dari Belakang Ilustrasi

1. List masih kosong (head=tail=null)

2. Masukkan data baru, misal 14

14 null

head tail

head tail


Page 156

3. Masukkan data baru lagi dari belakang, misal 21

Script penambahan dari belakang dengan head dan tail

#include


struct TNode

{

int data;

TNode *next;

};

TNode *head, *tail;

void init()

{

head=NULL;

tail=NULL;

}


Page 157

int cekkosong()

{

if(tail==NULL)

{

return 0;

}

else

{

return 1;

}

}

void tambahBelakang(int databaru)

{

TNode *baru,*bantu;

baru = new TNode;

baru-> data = databaru;

baru-> next = NULL;

if(cekkosong()==0)

{

head=baru;

tail=baru;

tail->next = NULL;

}

else

{

tail->next = baru;

tail=baru;

}

cout


Page 158

cout


Page 159

Function untuk menampilkan isi LinkedList dengan head dan tail

void tampil(){

TNode *bantu;

bantu = head;

if(cekkosong()==0){

while(bantu!=NULL){

cout


Page 160

Function penghapusan dari depan void hapusDepan(){

TNode *hapus;

int d;

if (cekkosong()==0){

if(head!=tail){

hapus = head;

d = hapus->data;

head = head->next;

delete hapus;

} else {

d = tail->data;

head=tail=NULL;

}

cout


Page 161

ke node berikutnya sehingga data setelah

head menjadi head baru, kemudian

menghapus pointer hapus dengan

menggunakan perintah delete.

3. Jika tail masih NULL maka berarti list

masih kosong!

Penambahan Data Dari Depan Ilustrasi


Page 162

Function penghapusan dari depan


{

TNode *bantu,*hapus;

int d;

if (cekkosong()==0)

{

bantu = head;

if(head!=tail)

{

while(bantu->next!=tail)

{

bantu = bantu->next;

}

hapus = tail;

tail=bantu;

d = hapus->data;

delete hapus;

tail->next = NULL;

}

else

{

d = tail->data;

head=tail=NULL;

}

cout


Page 163

pada linked list.

2. Penghapusan node tidak boleh dilakukan

jika keadaan node sedang ditunjuk oleh

pointer, maka harus dilakukan penunjukkan

terlebih dahulu dengan variabel hapus pada

tail, kemudian dibutuhkan pointer bantu

untuk membantu pergeseran dari head ke

node berikutnya sampai sebelum tail,

sehingga tail dapat ditunjukkan ke bantu

tersebut, dan bantu tersebut akan menjadi

tail yang baru. Setelah itu hapus pointer

hapus dengan menggunakan perintah delete.

3. Jika tail masih NULL maka berarti list

masih kosong!

Double Linked List (Non Circular)

Double Linked List memiliki 2 buah pointer yaitu

pointer next dan prev. Pointer next menunjuk pada

node setelahnya dan pointer prev menunjuk pada

node sebelumnya.

Pengertian :

- Double : artinya field pointer-nya dua buah dan

dua arah, ke node sebelum dan sesudahnya.


Page 164

- Linked List : artinya node-node tersebut saling

terhubung satu sama lain.

- Non Circular : artinya pointer prev dan next-nya

akan menunjuk pada NULL.

Ilustrasi Double Linked List

- Setiap node pada linked list mempunyai field

yang berisi data dan pointer ke node berikutnya

& ke node sebelumnya.

- Untuk pembentukan node baru, mulanya pointer

next dan prev akan menunjuk ke nilai NULL.

- Selanjutnya pointer prev akan menunjuk ke

node sebelumnya, dan pointer next akan

menunjuk ke node selanjutnya pada list.

2 next pre

v


Page 165

Deklarasi dan Pembentukan Node Baru pada

Double Linked List

Deklarasi Node

Struct TNode

{

int data;

TNode *next;

TNode *prev;

}

Pembentukan Node Baru

TNode *baru;

baru=new TNode;


baru->next=NULL;

baru->prev=NULL;

Double Linked List Menggunakan HEAD

- Dibutuhkan satu buah variabel pointer yaitu

head.

- Head akan selalu menunjuk pada node pertama.


Page 166

- Deklarasi Pointer Double Linked List

menggunakan head.

-

TNode *head;

- Fungsi Inisialisasi Double LinkedList.

void init()

{

head = NULL;

}

- Function untuk mengetahui kosong tidaknya

Double LinkedList.

-

int cekkosong()

{

if(head == NULL)

{

return 0;

}

else{ return 1;

}

}


Page 167

Penambahan data dari depan pada Double Linked

List dengan HEAD

- Penambahan node baru akan diletakkan di node

paling depan, namun pada saat pertama

kali(data masih kosong), maka penambahan data

dilakukan pada head nya.

- Pada prinsipnya adalah mengkaitkan data baru

dengan head, kemudian head akan menunjuk

pada data baru tersebut sehingga head akan

tetap selalu menjadi data terdepan.

- Ilustrasi

1. List masih kosong (Head=NULL)

2. Masukkan data baru, Misal 15

Null

Head

15

Head


Page 168

3. Masukkan data lagi dari depan, misal 21

Script Penambahan Double linkedlist dengan head

dari depan

#include


struct TNode

{

int data;

TNode *next;

TNode *prev;

};

TNode *head;


Page 169

void init()

{

head = NULL;

}

int cekkosong()

{

if(head == NULL)

{

return 0;

}

else

{

return 1;

}

}

void insertDepan(int databaru)

{

TNode *baru;

baru = new TNode;


baru->next = NULL;

baru->prev = NULL;

if(cekkosong()==0)

{

head=baru;

head->next = NULL;

head->prev = NULL;

}

else

{

baru->next = head;

head->prev = baru;

head = baru;

}

cout


Page 170

}

main()

{

int pil, databaru;

do

{

cout


Page 171

Tampilan Hasil

Penambahan data dari belakang pada Double

Linked List dengan HEAD

- Penambahan di belakang lebih sulit karena kita

membutuhkan pointer bantu untuk mengetahui

data terbelakang, kemudian dikaitkan dengan

data baru. Untuk mengetahui data terbelakang

perlu digunakan perulangan.

- Ilustrasi

1. List masih kosong (head=null)

NULL

Head


Page 172

2. Masukkan data baru, misal 25

3. Masukkan data baru lagi dari belakang,

missal 15

25

Head


Page 173

- Script Penambahan data dari belakang pada

double linked list dengan head

#include


struct TNode

{

int data;

TNode *next;

TNode *prev;

};

TNode *head;

void init(){

head = NULL;

}

int cekkosong(){

if(head == NULL){

return 0;

}

else{

return 1;

}

}


Page 174

void insertBelakang (int databaru){

TNode *baru,*bantu;

baru = new TNode;


baru->next = NULL;

baru->prev = NULL;

if(cekkosong()==0){

head=baru;

head->next = NULL;

head->prev = NULL;

}

else {

bantu=head;

while(bantu->next!=NULL){

bantu=bantu->next;

}

bantu->next = baru;

baru->prev = bantu;

}

cout


Page 175

Dengan Head"


Page 176

Function untuk Menampilkan isi Double Linked

List

- Ilustrasi

- Contoh Script

void tampil(){

TNode *bantu;

bantu = head;

if(cekkosong()==0){

while(bantu!=NULL){

coutnext;

}

cout


Page 177

Hapus data dari Depan pada Double Linked List

dengan Head

- Ilustrasi Penghapusan nilai 21 dari Depan

- Contoh Script Penghapusan dari depan

void hapusDepan (){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {


Page 178

d = head->data;

head = NULL;

}

cout


Page 179

- Contoh Script Penghapusan dari Belakang


{

TNode *hapus;

int d;

if (cekkosong()==0)

{

if(head->next != NULL)

{

hapus = head;

while(hapus->next!=NULL)

{

hapus = hapus->next;

}

d = hapus->data;

hapus->prev->next = NULL;

delete hapus;

}

else

{

d = head->data;

head = NULL;

}

cout


Page 180

Penjelasan :

1. Tidak diperlukan pointer bantu yang

mengikuti pointer hapus yang berguna

untuk menunjuk ke NULL.

2. Ka

modul struktur data 2012 (software engineering laboratory

Documents