modul struktur data 2013

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

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


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 <iostream>

using namespace std;

main()

{

int *alamat_x,*y;

int x=20;

int *z=0; //null pointer

alamat_x=&x;


cout<<"Nilai dari x = "<<x<<" disimpan pada

alamat "<<alamat_x<<endl;

cout<<"Nilai dari y = "<<*y<<" --> ini

disebut dangling pointer"<<endl;

cout<<"Nilai dari z = "<<*z<<" --> ini dsebut

null pointer"<<endl;

}

Tampilan Hasil

20 alamatny

a

0x0012ff50

x

0 /null

*z

Null (Kosong)

alamatnya

*z -2081649835 alamatnya


1.2 Pointer dengan Variabel Biasa

1.3 Operator Pointer


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


Source Code

#include <iostream>


main()

{

float a,*x1,*x2;

y=12.34;

x1=&a;

x2=x1; //operasi pemberian nilai

cout<<"Nilai yang di tunjuk x1 = "<<a<<"

disimpan pada alamat "<<&a<<endl;

cout<<"Nilai yang di tunjuk x2 = "<<*x2<<"

disimpan pada alamat "<<x2<<endl;

}


Tampilan Hasil

Contoh 2: Mengisi variabel dengan nilai yang ditunjuk oleh

sebuah variabel pointer

Source Code

#include <iostream>


main()

{

int *p, a=25,b;

p=&a;

b=*p;

cout<<"Nilai a = "<<a<<" di alamat

"<<p<<endl;

cout<<"Nilai b = "<<b<<" di alamat

"<<p<<endl;

}


Tampilan Hasil

Contoh 3: Mengoperasikan isi variable dengan menyebut

alamatnya dengan pointer

Source Code

#include <iostream>


main()

{

int a=25, b=12;

int *p,*q;

p=&a;

q=&b;

cout<<"Nilai yg ditunjuk p = "<<*p<<" di

alamat "<<p<<endl;

cout<<"Nilai yg ditunjuk q = "<<*q<<" di


alamat "<<q<<endl;

*q=*p;

cout<<"Nilai yg ditunjuk p = "<<*p<<" di

alamat "<<p<<endl;

cout<<"Nilai yg ditunjuk q = "<<*q<<" di

alamat "<<q<<endl;

}

Tampilan Hasil


Contoh 4: Mengisi dan mengganti variabel yang ditunjuk oleh

pointer.

#include <iostream>


main()

{

int a,*p;

p=&a;

*p=25;

cout<<"Nilai a = "<<a;

}

Tampilan Hasil

1.6 Pointer pada Array

Pada array, pointer hanya perlu menunjuk pada alamat elemen

pertama saja karena letak alamat array sudah berurutan pada

memori.


Variabel pointer hanya perlu increment Lihat contoh-contoh!

Source Code

#include <iostream>


main()

{

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

int *p;

p=a;

cout<<"P Pertama : "<<*p<<endl;

p=a+1;

cout<<"P Berikutnya : "<<*p<<endl;

cout<<"P Keseluruhan = ";

for(int x=1;x<=5;x++)

{

p=&a[x];

cout<<x<<", ";

}

}


Tampilan Hasil


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 <nama_var>;

tipe_data <nama_var>;

} ;


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;

};


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<<mahasiswa.nim;

Jika x adalah pointer bertipe mahasiswa* maka field dari x

dapat diakses dengan mengganti tanda titik dengan tanda panah

(“ ->“).

cout<<mahasiswa->nim;


Contoh: Program Struktur


Latihan:

1. Buat program menghitung durasi rental warnet

menggunakan struct, dengan ketentuan perhitungannya:

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

2. Buat program menghitung jumlah nilai akhir mahasiswa

menggunakan struct 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 <=40 : E


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


NB : 0! = 1

Tabel Peningkatan Nilai Faktorial

Contoh: Imlementasi rekursif dari fungsi faktorial

#include <iostream>


long faktorial(int nilai)

{

if(nilai<2)

{

return 1; // basis

}

else

{

return nilai*faktorial(nilai-1);

//faktorial

}

}

main()

{

for(int x=0; x<=5; x++)

{

cout<<"faktorial("<<x<<")=

"<<faktorial(x)<<endl;

}

}


TAMPILAN HASIL

Tugas

Buat faktorial dengan ketentuan

Banyak faktorial diinputkan dari keyboard

Dapat diulang kembali

Untuk script kreasikan sendiri tidak boleh

sama dengan modul


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<2, kita dapat sederhanakan dengan

pernyataan If.


Contoh: Program Rekursif dari fungsi Fibonacci

#include <iostream>


long fibo(int n)

{

if(n<2)

{

return n; //basis

}

else

{

return fibo(n-1)+fibo(n-2); //fibonacci

}

}

main()

{

for(int n=0;n<=5;n++)

{

cout<<"fibonacci("<<n<<") =

"<<fibo(n)<<endl;

}

}


TAMPILAN HASIL

Tugas

Buat fibonacci dengan ketentuan

Banyak fibonacci diinputkan dari keyboard



sama dengan modul


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.


Contoh: Program Rekursif dari Menara Hanoi

#include <iostream>


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

{

if(n==1)

{

cout<<"Pindah cakra atas dari "<<x<<"

ke "<<z<<endl;

}

else

{

hanoi(n-1,x,z,y);

hanoi(1,x,y,z);

hanoi(n-1,y,x,z);

}

}

main()

{

cout<<"Game tower menara hanoi dengan 3

cakra"<<endl;

hanoi(3,'A','B','C');

}


TAMPILAN HASIL

Tugas

Buat program menara hanoi dengan ketentuan

Banyak cakram ditentukan user & inputan dari

keyboard



sama dengan modul

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 =


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


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


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

};


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:


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.


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


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.


Gambar 6.10. Ilustrasi fungsi POP

Sintaks program fungsi POP


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


Sintaks program fungsi Print:

void TampilStack()

{

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

{

cout<<”Data : “<<tumpuk.data[i]);

}

}

6.12 STUDI KASUS

Pembuatan Kalkulator SCIENTIFIC, misalkan operasi: 3 + 2

* 5 Operasi di atas disebut notasi infiks, notasi infiks tersebut harus

diubah lebih dahulu menjadi notas postfix 3 + 2 * 5 notasi

postfiksnya adalah 2 5 * 3 +. Kemudian diimplementasikan stack

sebagai berikut: Stack Soal (dalam bentuk postfiks) dan Stack Hasil

(masih kosong) seperti pada 6.12:

Gambar 6.12 Ilustrasi kalkulator SCIENTIFIC


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 <operator> a. Jadi b * a, yaitu 2

* 5 kemudian hasilnya disimpan lagi ke dalam StackHasil seperti

pada gambar 6.14.


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 <operator> 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 +


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


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)


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


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


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)).


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


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 <= derajat operator top of

stack

Pop top of stack dan masukkan ke dalam posfix

Setelah semua dilakukan, push operator soal ke

stack

Jika sudah semua soal dibaca, pop semua isi stack dan

push ke postfix sesuai dengan urutannya.

Penyelesaian


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: +


• 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


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

postfix dengan menggunakan algoritma Dijkstra


Contoh Stack

#include <stdio.h>

#include <iostream>

#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<<" Maaf data sudah

penuh"<<endl;

cout<<"--------------------------------

------------------"<<endl;

}

else


{

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

++(s->jml);

}

}

void ambil(Stack *s, itemType *x)

{

if(kosong(s))

{

cout<<" Maaf data masih

kosong"<<endl;

cout<<"----------------------------------

----------------"<<endl;

}

else

{

--(s->jml);

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

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

cout<<" Data "<<*x<<" berhasil

diambil"<<endl;

cout<<"-----------------------------------

---------------"<<endl;

}

}

void tampil(Stack *s)

{

if(kosong(s))

{

cout<<" Maaf data masih

kosong"<<endl;

cout<<"---------------------------------

-----------------"<<endl;

}

else

cout<<endl;

for(int i=s->jml-1;i>=0;i--)

{


cout<<"Data "<<s->item[i]<<endl;

}

}

void hapus(Stack *s)

{

s->jml=0;

cout<<" Semua data berhasil

dihapus"<<endl;

cout<<"--------------------------------------

------------"<<endl;

}

int main()

{

int pil;

Stack tumpukan;

itemType data;

init(&tumpukan);

do

{

cout<<"Selamat datang di Aplikasi

stack"<<endl;

cout<<"1. PUSH(Memasukan)"<<endl;

cout<<"2.

POP(Mengangkat/Memanggil)"<<endl;

cout<<"3. Display(Menampilkan)"<<endl;

cout<<"4. Delete(Hapus)"<<endl;

cout<<"5. Exit"<<endl;

cout<<"Masukkan pilihan : ";cin>>pil;

cout<<"----------------------------------

----------------"<<endl;

switch(pil)

{

case 1:

cout<<"Masukkan data : ";cin>>data;

cout<<"----------------------------

----------------------"<<endl;

isi(data,&tumpukan);

break;


case 2:

ambil(&tumpukan,&data);

break;

case 3:

tampil(&tumpukan);

break;

case 4:

hapus(&tumpukan);

break;

}

}

while(pil!=5);

cout<<" Terima Kasih"<<endl;

cout<<"--------------------------------------

------------"<<endl;

return 0;

}

Tampilan Hasil Stack

TUGAS :

Buatlah Program Menara Hanoi dengan menggunakan Stack!


BAB 7

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


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 elemen‐elemen 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.


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


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


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


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


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.


Contoh Queue dengan Linear Array

#include <iostream>

#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

{


return 0; //data berisi

}

}

void masuk()

{

int data;

cout <<"Masukkan bilangan "; cin >>data;

if(penuh()==0)

{

antrian.tail++;

antrian.data[antrian.tail]=data;

cout <<antrian.data[antrian.tail] <<"

masuk";

}

else

{

cout <<"Data penuh";

}

}

int keluar()

{

int i;

int x=antrian.data[antrian.head+1];

for(i=antrian.head;i<antrian.tail;i++)

{

antrian.data[i]=antrian.data[i+1];

}

antrian.tail--;

cout <<x <<" berhasil dikeluarkan";

return x;

}

void clear()

{

init();

cout <<"Data telah dikosongkan";

}


void tampil()

{

if(kosong()==0)

{

for(int

i=antrian.head+1;i<=antrian.tail;i++)

{

cout <<antrian.data[i]<<" ";

}

}

else

{

cout <<"Data masih kosong";

}

}

main()

{

int pil;

cout<<"*-------------------------------

*"<<endl;

cout<<"* Q u e u e ( A N T R I A N )

*"<<endl;

cout<<"*-------------------------------

*"<<endl;

do

{

cout<<"\n";

cout<<"\n********************************";

cout<<"\n1. Masukkan Data";

cout<<"\n2. Keluarkan Data";

cout<<"\n3. Kosong Data";

cout<<"\n4. Cetak Data";

cout<<"\n\nSilahkan Masukan Pilihan

Anda :";cin>>pil;

cout<<"\n";

switch (pil)

{

case 1:

{


masuk();

break;

}

case 2:

{

keluar();

break;

}

case 3:

{

clear();

break;

}

case 4:

{

tampil();

break;

}

default :

{

cout<<"\n Maaf, Tidak ada dalam

pilihan";

}

}

}

while(pil>=1 && pil<= 4);

}


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 seakan‐akan 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


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. Operasi‐operasi yang terdapat pada circular

array tidak jauh berbeda dengan operasi pada linear

array.

Atau lebih jelasnya seperti gambar di bawah ini :


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


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.


6.4.1 Pendeklarasian Queue


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


-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 :


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.


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),


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 <iostream>


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)

{

cout<<"Antrian Penuh";

}

else

{

cout<<"Data yang akan di

Push = ";cin>>variabel.baru;


antri.tail++;

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

}

}

void out()

{

if(antri.tail== -1)

{

cout<<"Antrian Kosong";

}

else

{

for(int

i=antri.head;i<=antri.tail;i++)

{

antri.data[i]=antri.data[i+1

];

antri.tail--;

}

cout<<"Data yang akan di

keluar = "<<antri.data[antri.tail];

}

}

void cetak()

{

if(antri.tail==-1)

{

cout<<"Antrian Kosong";

}

else

{

cout<<endl;

cout<<"Data dalam antrian


adalah : "<<endl<<endl;

for(int i=0; i<=antri.tail;i++)

{

cout<<antri.data[i]<<" ";

}

}

}

int main()

{

int pil, baru, i;

antri.head=-1;

antri.tail=-1;

cout<<"=================================

===="<<endl;

cout<<"= Q u e u e ( A N T R I A

N ) ="<<endl;

cout<<"=================================

===="<<endl;

do

{

cout<<endl;

cout<<"******************************

*******"<<endl;

cout<<"1. Masukkan

Data"<<endl;

cout<<"2. Keluarkan

Data"<<endl;

cout<<"3. Cetak Data"<<endl;

cout<<"Silahkan Masukan

Pilihan Anda : ";cin>>pil;

cout<<endl;


switch (pil)

{

case 1:

{

input();

break;

}

case 2:

{

out();

break;

}

case 3:

{

cetak();

break;

}

default :

{

cout<<"----------------------

--------------------"<<endl;

cout<<" Maaf, Tidak ada

dalam pilihan "<<endl;

cout<<"----------------------

--------------------"<<endl;

}

}

}

while(pil>=1 && pil<= 3);

}


TAMPILAN HASIL


BAB 8

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:


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.


- 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


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.


Proses 3


Dengan prosedur diatas, data terurut naik (ascending),

untuk urut turun (descending)

silahkan ubah bagian:


Contoh Source code

#include <iostream>


int data[10],data2[10];

int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{

cout<<"Masukkan jumlah data = ";cin>>n;

cout<<"--------------------------------------

"<<endl;

for(int i=0;i<n;i++)

{

cout<<"Masukkan data ke-"<<(i+1)<<" =

";cin>>data[i];

data2[i] = data[i];

}

cout<<endl;

}

void Tampil()

{


{

cout<<data[i]<<" ";

}

cout<<endl;

}


void bubble_sort()

{


{

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

{

if(data[j]<data[j-1]) tukar(j,j-1);

}

Tampil();

}

cout<<endl;

}

main()

{

cout<<"*-------------------------------------

*"<<endl;

cout<<"* Selamat datang di aplikasi

*"<<endl;

cout<<"* Bubble Sort

*"<<endl;

cout<<"*-------------------------------------

*"<<endl;

Input();

cout<<"Proses Bubble Sort,,,,,,,"<<endl;

cout<<"-------------------------------------

"<<endl;

Tampil();

bubble_sort();

cout<<"-------------------------------------

"<<endl;


cout<<" TERIMA KASIH

"<<endl;

cout<<"-------------------------------------

"<<endl;

}

Tampilan Hasil

Animasi Bubble Sort

Buka animasinya di home/animasi sorting


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.


Contoh source code Exchange Sort

#include <iostream>



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{


cout<<"--------------------------------------

"<<endl;


{


";cin>>data[i];

data2[i] = data[i];

}

cout<<endl;

}

void Tampil()

{


{

cout<<data[i]<<" ";


}

cout<<endl;

}

void exchange_sort()

{

for (int i=0; i<n-1; i++)

{

for(int j = (i+1); j<n; j++)

{

if (data [i] > data[j]) tukar(i,j);

}

Tampil();

}

cout<<endl;

}

main()

{

cout<<"*-------------------------------------

*"<<endl;


*"<<endl;

cout<<"* Exchange Sort

*"<<endl;

cout<<"*-------------------------------------

*"<<endl;

Input();

cout<<"Proses Exchange Sort,,,,,,,"<<endl;

cout<<"-------------------------------------

"<<endl;

Tampil();

exchange_sort();

cout<<"-------------------------------------

"<<endl;



"<<endl;

cout<<"-------------------------------------

"<<endl;

}

Tampilan Hasil


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]).


-


Contoh Source Code Selection Sort

#include <iostream>



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{


cout<<"--------------------------------------

"<<endl;


{


";cin>>data[i];

data2[i] = data[i];

}

cout<<endl;

}


void Tampil()

{


{

cout<<data[i]<<" ";

}

cout<<endl;

}

void selection_sort()

{

int pos,i,j;

for(i=0;i<n-1;i++)

{

pos = i;

for(j = i+1;j<n;j++)

{

if(data[j] < data[pos]) pos = j;

}

if(pos != i) tukar(pos,i);

Tampil();

}

cout<<endl;

}

main()

{

cout<<"*-------------------------------------

*"<<endl;


*"<<endl;

cout<<"* Selection Sort

*"<<endl;

cout<<"*-------------------------------------


*"<<endl;

Input();

cout<<"Proses Selection Sort,,,,,,,"<<endl;

cout<<"-------------------------------------

"<<endl;

Tampil();

selection_sort();

cout<<"-------------------------------------

"<<endl;


"<<endl;

cout<<"-------------------------------------

"<<endl;

}

Tampilan Hasil


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.


Contoh Source Code Insertion Sort

#include <iostream>



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{


cout<<"--------------------------------------


"<<endl;


{


";cin>>data[i];

data2[i] = data[i];

}

cout<<endl;

}

void Tampil()

{


{

cout<<data[i]<<" ";

}

cout<<endl;

}

void insertion_sort()

{

int temp,i,j;

for(i=1;i<n;i++)

{

temp = data[i];

j = i -1;

while(data[j]>temp && j>=0)

{

data[j+1] = data[j];

j--;

}

data[j+1] = temp;

Tampil();

}

cout<<endl;

}


main()

{

cout<<"*-------------------------------------

*"<<endl;


*"<<endl;

cout<<"* Insertion Sort

*"<<endl;

cout<<"*-------------------------------------

*"<<endl;

Input();

cout<<"Proses Insertion Sort,,,,,,,"<<endl;

cout<<"-------------------------------------

"<<endl;

Tampil();

insertion_sort();

cout<<"-------------------------------------

"<<endl;


"<<endl;

cout<<"-------------------------------------

"<<endl;

}


Tampilan Hasil


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.


Contoh source code

#include <iostream>



int n;


{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void Input()

{


cout<<"--------------------------------------

"<<endl;


{


";cin>>data[i];

data2[i] = data[i];

}

cout<<endl;

}

void Tampil()

{


{

cout<<data[i]<<" ";

}


cout<<endl;

}

void QuickSort(int L, int R) //the best sort

i've ever had :)

{

int i, j;

int mid;

i = L;

j = R;

mid = data[(L+R) / 2];

do

{

while (data[i] < mid) i++;

while (data[j] > mid) j--;

if (i <= j)

{

tukar(i,j);

i++;

j--;

};

Tampil();

} while (i < j);

if (L < j) QuickSort(L, j);

if (i < R) QuickSort(i, R);

}

main()

{

cout<<"*-------------------------------------

*"<<endl;


*"<<endl;

cout<<"* Quick Sort

*"<<endl;


cout<<"*-------------------------------------

*"<<endl;

Input();

cout<<"Proses Quick Sort,,,,,,,"<<endl;

cout<<"-------------------------------------

"<<endl;

Tampil();

QuickSort(0,n-1);

cout<<"-------------------------------------

"<<endl;


"<<endl;

cout<<"-------------------------------------

"<<endl;

}

Tampilan Hasil


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


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 !


BAB 9

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).


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).


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 <= N)

kerjakan baris 4


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.


Contoh (1):

#include <iostream>


main()

{

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

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

int cari;

int tanda=0;

cout<<"masukkan data yang ingin dicari =

";cin>>cari;

cout<<endl<<endl;

for(int i=0;i<8;i++)\

{

if(data[i] == cari) tanda=1;

}

if(tanda==1)

{

cout<<"--------------------------------

------"<<endl;

cout<<" Data Ditemukan!

"<<endl;

cout<<"--------------------------------

------"<<endl;

}


Tampilan Hasil

else

{

cout<<"---------------------------------

-----"<<endl;

cout<<" Data Tidak Ditemukan!

"<<endl;

cout<<"---------------------------------

-----"<<endl;

}

}


Contoh (2):

#include <iostream>


main()

{

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

x, posisi;

cout<<"Data : "<<endl;

for(int z=0;z<9;z++)

{

cout<<"\t"<<data[z]<<endl;

}

cout<<"--------------------------------

"<<endl;

cout<<"Data yang ingin dicari =

";cin>>x;

cout<<endl<<endl;

i=0;

posisi=0;

while(i<8 && data[i]!=x)

{

i++;

}

if (data[i]!=x)

{

cout<<"-----------------------------

---------"<<endl;

cout<<" Maaf data yang dicari

tidak ada "<<endl;


Tampilan Hasil

cout<<"--------------------------------------

"<<endl;

}

else if (data[i]==x)

{

posisi=i+1;

cout<<"Ditemukan pada urutan ke

"<<posisi;

}

}


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:


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


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 <= R) dan (tidak ditemukan) kerjakan baris 5

sampai dengan 8

5. m ← (L + R) / 2

6. Jika (Data[m] = x) maka ditemukan ← true

7. Jika (x < Data[m]) maka R ← m – 1

8. Jika (x > Data[m]) maka L ← m + 1

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


dicari, jika tidak data tidak ditemukan.

Di bawah ini merupakan contoh mencari data

menggunakan pencarian biner.

#include <iostream>


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<<"Masukan data yang di cari=

";cin>>cari;

cout<<endl<<"=========================

======="<<endl;

while((kiri<=kanan)&&(tanda==0))

{

tengah=(kiri+kanan)/2;

cout<<endl<<"Data tengah =>>

"<<tengah<<endl;

if(data[tengah]==cari) tanda=1;

else if(cari < data[tengah])

{

cout<<endl<<"cari di

kiri"<<endl;

kanan=tengah-1;

}


Tampilan Hasil

else

{

kiri=tengah+1;

cout<<endl<<"cari di

kanan"<<endl;

}

if(tanda==1)

{

cout<<"::: Data ada :::"<<endl;

}

else

{

cout<<"::: Data tidak ada

:::"<<endl;

}

}

}


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


Contoh Interpolation Search

#include <iostream>

#include <math.h>


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<<" Datanya yaitu : "<<endl;

for(int z=0; z<=6; z++)

{

cout<<"\t"<<data[z]<<endl;

}

cout<<"================================="<

<endl;

cout<<"Masukan data yang di cari =

";cin>>cari;


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]<cari)

{

low=posisi+1;

}

}

while

(cari>=data[low]&&cari<=data[high]);

if(tanda==1)

{

cout<<endl<<" ::>Data ditemukan

<::"<<endl;

}

else

{

cout<<endl<<" ::>Data tidak ada

<::"<<endl;

}

}


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.


BAB 10

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


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


9.4 Single 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


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 Single 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



9.6 Deklarasi Single 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;


Penjelasan :

keyword new gunanya untuk mempersiapkan

sebuah node baru beserta alokasi memorinya,

kemudian node tersebut diisi data dan pointer

nextnya ditunjuk ke NULL.

Single Linked List Menggunakan Head

Head Akan Selalu menunjukkan pada node pertama.

Ilustrasi Penambahan dari depan

1. List Masih Kosong (head==NULL)

NULL

head

head



2. Masukkan Data baru, missal 28

3. Masukkan data lagi dari depan, missal 21

28

head


Contoh Penambahan dari depan

#include <iostream>


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)


{

head=baru;

head->next=NULL;

}

else

{

baru->next=head;

head=baru;

}

cout<<"Penambahan Data Berhasil"<<endl;

}

main()

{

int pil, databaru;

do

{

cout<<"Menu Pilihan Single Linked

List dengan Head"<<endl;

cout<<"1. Insert Data dari

Depan"<<endl;


cout<<"Masukkan Pilihan Anda = ";

cin>>pil;

switch (pil)

{

case 1:

{

cout<<"Masukkan Data = ";

cin>>databaru;

isidepan(databaru);

break;

}

}

}

while(pil!=2);

}


Tampilan Hasil

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

2. Masukkan Data baru, missal 28

NULL

head

28

head


3. Masukkan data lagi dari belakang, missal 21

4. Masukkan data lagi dari belakang, missal 15


Contoh Penambahan dari depan

#include <iostream>


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;


if(cekkosong()==0)

{

head=baru;

head->next=NULL;

}

else

{

bantu=head;

while (bantu->next!=NULL)

{

bantu=bantu->next;

}

bantu->next=baru;

}

cout<<"Penambahan Data Berhasil"<<endl;

}

main()

{

int pil, databaru;

do

{

cout<<"Menu Pilihan Single Linked List

dengan Head "<<endl;


Belakang"<<endl;



cin>>pil;

switch (pil)

{

case 1:

{


cin>>databaru;

isibelakang(databaru);

break;


}

}

}

while(pil!=2);

}

Tampilan Hasil

Menampilkan isi linked List


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<<"Data Masih Kosong";

}

else if(bantu==NULL)

{

cout<<"Data Masih Kosong"<<endl;

}

else

{

while (bantu!=NULL)

{

cout<<bantu->data<<endl;

bantu=bantu->next;

}

}

}


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


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<<d<<" terhapus\n";

} else cout<<"Masih kosong\n";

}


jika head masih NULL maka berarti data

masih kosong.

Menghapus data dari belakang


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;

}


}

else

cout<<"Masih kosong\n";

}


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.


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;

}

}


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


Script penambahan dari depan dengan head dan tail

#include <iostream>


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;


if(cekkosong()==0)

{

head=tail=baru;

tail->next=NULL;

}

else

{

baru->next = head;

head = baru;

}

cout<<"Data masuk"<<endl;

}

main()

{

int pil, databaru;

do

{


List dengan Head dan Tail "<<endl;


Depan"<<endl;



cin>>pil;

switch (pil)

{

case 1:

{


cin>>databaru;

insertDepan(databaru);

break;

}

}

}

while(pil!=2);

}


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


3. Masukkan data baru lagi dari belakang, misal 21

Script penambahan dari belakang dengan head dan tail

#include <iostream>


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 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<<"Data masuk\n";

}

main()

{

int pil, databaru;

do

{


List dengan Head dan Tail "<<endl;



Belakang"<<endl;



cin>>pil;

switch (pil)

{

case 1:

{


cin>>databaru;

tambahBelakang(databaru);

break;

}

}

}

while(pil!=2);

}

Catatan : Pada penambahan data di belakang, data akan

selalu dikaitkan dengan tail, karena tail terletak

di node paling belakang.


Function untuk menampilkan isi LinkedList dengan head dan tail

void tampil(){

TNode *bantu;

bantu = head;

if(cekkosong()==0){

while(bantu!=NULL){

cout<<bantu->data<<" ";

bantu=bantu->next;

}

cout<<endl;


}

Menghaspus data dari depan

Ilustrasi


Function penghapusan dari depan void hapusDepan(){

TNode *hapus;

int d;


if(head!=tail){

hapus = head;

d = hapus->data;

head = head->next;

delete hapus;

} else {

d = tail->data;

head=tail=NULL;

}



}

Penjelasan :

1. Function di atas akan menghapus data

terdepan (pertama) yang ditunjuk oleh head

pada linked list.

2. Penghapusan node tidak boleh dilakukan


pointer, maka harus dilakukan penunjukkan

terlebih dahulu dengan pointer hapus pada

head, kemudian dilakukan pergeseran head


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


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;

}


}

else cout<<"Masih kosong\n";

}

Penjelasan :

1. Function di atas akan menghapus data paling

belakang (terakhir) yang ditunjuk oleh tail


pada linked list.

2. Penghapusan node tidak boleh dilakukan


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.


- 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


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.


- 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;

}

}


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


3. Masukkan data lagi dari depan, misal 21

Script Penambahan Double linkedlist dengan head

dari depan

#include <iostream>


struct TNode

{

int data;

TNode *next;

TNode *prev;

};

TNode *head;


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<<"Data masuk"<<endl;


}

main()

{

int pil, databaru;

do

{

cout<<"Menu Pilihan Double Linked

List Dengan Head"<<endl;


Depan"<<endl;



cin>>pil;

switch (pil)

{

case 1:

{


cin>>databaru;


break;

}

}

}

while(pil!=2);

}


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


2. Masukkan data baru, misal 25

3. Masukkan data baru lagi dari belakang,

missal 15

25

Head


- Script Penambahan data dari belakang pada

double linked list dengan head

#include <iostream>


struct TNode

{

int data;

TNode *next;

TNode *prev;

};

TNode *head;

void init(){

head = NULL;

}

int cekkosong(){

if(head == NULL){

return 0;

}

else{

return 1;

}

}


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;

}


}

main()

{

int pil, databaru;

do

{

cout<<"Menu Pilihan Double Linked List


Dengan Head"<<endl;

cout<<"1. Insert Data dari Belakang"<<endl;


cout<<"Masukkan Pilihan Anda = "; cin>>pil;

switch (pil)

{

case 1:

{


cin>>databaru;

insertBelakang(databaru);

break;

}

}

}

while(pil!=2);

}

Tampilan Hasil


Function untuk Menampilkan isi Double Linked

List

- Ilustrasi

- Contoh Script

void tampil(){

TNode *bantu;

bantu = head;

if(cekkosong()==0){

while(bantu!=NULL){

cout<<bantu->data<<"

";

bantu=bantu->next;

}

cout<<endl;


}


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){


hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {


d = head->data;

head = NULL;

}


} else { cout<<"Masih kosong\n";

}

}

Hapus data dari Belakang pada Double Linked List

dengan Head

- Ilustrasi Penghapusan nilai 10 dari Belakang


- 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;

}


}

else

{

cout<<"Masih kosong\n";

}

}


Penjelasan :

1. Tidak diperlukan pointer bantu yang

mengikuti pointer hapus yang berguna

untuk menunjuk ke NULL.

2. Karena pointer hapus sudah bisa

menunjuk ke pointer sebelumnya dengan

menggunakan elemen prev ke node

sebelumnya, yang akan diset agar

menunjuk ke NULL setelah

penghapusan dilakukan.

Double Linked List Menggunakan HEAD dan Tail

- Dibutuhkan dua buah variabel pointer: head dan

tail

- Head akan selalu menunjuk pada node pertama,

sedangkan tail akan selalu menunjuk pada node

terakhir.

Tail


- Inisialisasi Double Linked List Non Cingular

TNode *head, *tail;

- Fungsi Inisialisasi Double Linked List Non

Cingular

void init()

{

head = NULL;

tail = NULL;

}

- Fungsi Untuk Mengetahui Kosong Tidaknya

Double Linked List Non Cingular

int cekkosong(){

if(tail == NULL)

{

return 0;

}

else

{

return 1;

}

}


Penambahan data dari depan pada double Linked

List dengan Head dan Tail

- Ilustrasi

1. List Masih Kosong (Head=Tail=Null)


3. Masukkan Data Baru Lagi dari Depan, Misal 15

Tail

Head

10

Head

Tail


- Source Penambahan data dari depan dengan

Head dan Tail

#include <iostream>


struct TNode

{

int data;

TNode *next;

TNode *prev;

};

TNode *head, *tail;

void init(){

head = NULL;

tail = 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;

tail=head;

head->next = NULL;

head->prev = NULL;

tail->prev = NULL;

tail->next = NULL;

}

else {

baru->next = head;

head->prev = baru;

head = baru;

}



}

main()

{

int pil, databaru;

do

{


Dengan Head dan Tail"<<endl;

cout<<"1. Insert Data dari Depan"<<endl;



cin>>pil;

switch (pil)

{

case 1:

{


cin>>databaru;


break;

}

}

}

while(pil!=2);

}


Tampilan Hasil

Penambahan data dari belakang pada double

Linked List dengan Head dan Tail

- Ilustrasi

1. List Masih Kosong (Head=Tail=Null)


Head

Tail


3. Masukkan Data Baru lagi dari belakang,

Misal 15

10

Head

Tail


- Source Penambahan data dari Belakang dengan

Head dan Tail

#include <iostream.h>

#include <conio.h>

struct TNode

{

int data;

TNode *next;

TNode *prev;

};

TNode *head, *tail;

void init(){

head = NULL;

tail = NULL;

}

int cekkosong(){

if(head == NULL){

return 0;

}

else{

return 1;

}

}


void insertBelakang(int databaru){

TNode *baru;

baru = new TNode;


baru->next = NULL;

baru->prev = NULL;

if(cekkosong()==1){

head=baru;

tail=head;

head->next = NULL;

head->prev = NULL;

tail->prev = NULL;

tail->next = NULL;

}

else {

tail->next = baru;

baru->prev = tail;

tail = baru;

tail->next = NULL;

}


}

main()

{

int pil, databaru;

do

{



Dengan Head dan Tail"<<endl;

cout<<"1. Insert Data dari Belakang"<<endl;


cout<<"Masukkan Pilihan Anda = "; cin>>pil;

switch (pil)

{

case 1:

{


cin>>databaru;

insertBelakang(databaru);

break;

}

}

}

while(pil!=2);

}

Tampilan Hasil


Catatan : Penambahan node di belakang akan

selalu dikaitkan dengan tail dan

kemudian node baru tersebut akan

menjadi tail.

Function Untuk Menampilkan isi Linked List

- Ilustrasi

- Contoh Script

void tampil(){

TNode *bantu;

bantu = head;

if(isEmpty()==0){

while(bantu!=tail->next){

cout<<bantu->data<<" ";

bantu=bantu->next;

}

cout<<endl;


}

Tail


Hapus Data dari Depan pada Double Linked List

dengan Head dan Tail

- Ilustrasi

- Script Penghapusan Data dari Depan

void hapusDepan(){

TNode *hapus;

int d;



hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

} else {


d = head->data;

head = NULL;

tail = NULL;

}



}

Hapus Data dari Belakang pada Double Linked List

dengan Head dan Tail

- Ilustrasi


- Script Penghapusan Data dari Belakang

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){


hapus = tail;

d = tail->data;

tail = tail->prev;

tail->next = NULL;

delete hapus;

} else {

d = head->data;

head = NULL;

tail = NULL;

}



}

Penjelasan :

Pointer hapus tidak perlu di loop

untuk mencari node terakhir. Pointer

hapus hanya perlu menunjuk pada

pointer tail saja.

Karena pointer hapus sudah bisa


menunjuk ke pointer sebelumnya

dengan menggunakan elemen prev,

maka pointer prev hanya perlu diset

agar menunjuk ke NULL. Lalu

pointer hapus didelete.


BAB 11

TREE

Pengertian Tree

Kumpulan node yang saling terhubung satu

sama lain dalam suatu kesatuan yang

membentuk layaknya struktur sebuah pohon.

Struktur pohon adalah suatu cara

merepresentasikan suatu struktur hirarki (one-

to-many). Secara grafis mirip sebuah pohon,

walaupun pohon tersebut hanya tampak sebagai

kumpulan node-node dari atas ke bawah.

Suatu struktur data yang tidak linier yang

menggambarkan hubungan yang hirarkis (one-

tomany) dan tidak linier antara elemen-

elemennya.

Implementasi Tree

Contoh penggunaan struktur pohon :

Silsilah Keluarga

Struktur Organisasi

Pertandingan

Parse Tree (Pada Compiler)


Contoh Tree

Pohon Keluarga

Parse Tree

(a*(b+c))-(d+e)

Amir

Anis Komar Santoso

Agnes Zulkarn

ain

Firdaus Nur

-

* +

e d + a

b c


Representasi Tree

Tingkat 1

Tingkat 2

Tingkat 3

Tingkat 4


Diagram Venn

Notasi Tingkat

Notasi Kurung

(A(B(D,E(I,J)),C(F,G,H))


Terminologi Tree


BinaryTree

Binary Tree adalah tree dengan syarat bahwa

tiap node hanya boleh memiliki maksimal dua subtree

dan kedua subtree tersebut harus terpisah. Sesuai

dengan definisi tersebut tiap node dalam binary tree

hanya boleh memiliki paling banyak dua child.

Sebuah tree yang kosong juga merupakan

sebuah binary tree

Binary tree harus memenuhi salah satu syarat

berikut :

1. Tidak Memiliki anak

2. Memiliki subtree di sebelah kiri (left

subtree)

3. Memiliki subtree di sebelah kanan (right

subtree)

4. Memiliki baik left subtree maupun right

subtree


Jenis Binary Tree

- Full Binary Tree : Semua node (kecuali leaf)

pasti memiliki 2 anak dan tiap subtree memiliki

panjang path yang sama.


- Complete Binary Tree : Mirip dengan full

binary tree, tapi tiap subtree boleh memiliki

panjang path yang berbeda dan tiap node

(kecuali leaf) memiliki 2 anak.

- skewed binary tree : Binary tree yang semua

nodenya hanya memiliki satu anak (kecuali leaf)


Node Binary Tree

Jumlah maksimum node pada setiap tingkat

adalah

Node pada binary tree maksimum berjumlah

Implementasi Program

Tree dapat dibuat dengan menggunakan linked

list secara rekursif.

Linked list yang digunakan adalah double linked

list non circular.

Data yang pertama kali masuk akan menjadi

node root.

Data yang lebih kecil dari data node root akan

masuk dan menempati node kiri dari node root,

sedangkan jika lebih besar dari data node root,


akan masuk dan menempati node di sebelah

kanan node root.

Deklarasi Struct

struct tree {

int data;

tree *left;

tree *right;

}

Ilustrasi

Deklarasi Variabel

Tree *pohon;


Operasi-Operasi Tree

Create: membentuk sebuah tree baru yang

kosong.

pohon = NULL;

Clear: menghapus semua elemen tree.

pohon = NULL;

Empty: mengetahui apakah tree kosong atau

tidak.

int isEmpty(Tree *pohon){

if(pohon == NULL) { return 1 };

else { return 0 };

}

Insert : menambah node ke dalam Tree secara

rekursif. Jika data yang akan dimasukkan lebih

besar daripada elemen root, maka akan

diletakkan di node sebelah kanan, sebaliknya


jika lebih kecil maka akan diletakkan di node

sebelah kiri. Untuk data pertama akan menjadi

elemen root.

Find : mencari node di dalam Tree secara

rekursif sampai node tersebut ditemukan dengan

menggunakan variable bantuan ketemu.

Syaratnya adalah tree tidak boleh kosong.

Traverse: yaitu operasi kunjungan terhadap

node-node dalam pohon dimana masing-masing

node akan dikunjungi sekali.

Count : menghitung jumlah node dalam Tree.

Height : mengetahui kedalaman sebuah Tree.

Find Min dan Find Max : mencari nilai

terkecil dan terbesar pada Tree.

Child : mengetahui anak dari sebuah node (jika

punya).


Ilustrasi Insert

4. Insert (Left Tree)


Pembuatan Binary Tree

Pembuatan binary tree lebih mudah

menggunakan binary search tree (binary sorted tree)

dengan cara : “ Jika nilai dari simpul yang akan

disisipkan lebih besar dari simpul parent, maka simpul

tersebut ditempatkan sebagai subtree kanan. Jika lebih

kecil maka simpul baru tersebut disimpan sebagai

subtree kiri”.

Ilustrasi


Contoh Program Binary Tree

#include <iostream>

#include <stdlib.h> //fungsi random()

#include <ctype.h>


struct Node *createnode(long value);

struct Node *addnode(long value, struct Node*

pNode);

void listnodes(struct Node *pNode);

void freenodes(struct Node *pNode);

struct Node

{

long item;

int count;

struct Node *pLeft;

struct Node *pRight;

};


int main(void)

{

long newvalue = 0;

struct Node *pRoot = NULL;

char answer = 'n';

cout<<"-------------------------------------

"<<endl;

cout<<"---- Program Sorting Binary Tree-----

"<<endl;

cout<<"-------------------------------------

"<<endl;

do

{

cout<<"Inputkan Nilai Node:

";cin>>newvalue;

if(pRoot == NULL)

{

pRoot = createnode(newvalue);

}

else

{

addnode(newvalue, pRoot);

cout<<endl<<"Apakah anda mau

inputkan nilai lagi (y or n)? ";cin>>answer;

}

}

while(tolower(answer) == 'y');

cout<<endl<<"Hasil nilai binary

tree:"<<endl;

listnodes(pRoot);

freenodes(pRoot);

cout <<endl<< endl;

return 0;

}

struct Node *createnode(long value)

{

struct Node *pNode = (struct

Node*)malloc(sizeof(struct Node));

pNode->item = value;

pNode->count = 1;


pNode->pLeft = pNode->pRight = NULL;

return pNode;

}

struct Node *addnode(long value, struct Node*

pNode)

{

if(pNode == NULL)

{

return createnode(value);

}

if(value ==pNode->item)

{

++pNode->count;

return pNode;

}

if(value < pNode->item)

{

if(pNode->pLeft == NULL)

{

pNode->pLeft = createnode(value);

return pNode->pLeft;

}

else

{

return addnode(value, pNode->pLeft);

}

}

else

{

if(pNode->pRight == NULL)

{

pNode-> pRight = createnode(value);

return pNode-> pRight;

}

else

{

return addnode(value, pNode->

pRight);

}

}


}

void listnodes(struct Node *pNode)

{

int i;

if(pNode->pLeft != NULL)

{

listnodes(pNode->pLeft);

}

for(i = 0; i<pNode->count ; i++)

{

cout<<endl<<pNode->item<<endl;

}

if(pNode->pRight != NULL)

{

listnodes(pNode->pRight);

}

}

void freenodes(struct Node * pNode)

{

if(pNode == NULL)

{

return;

}

if(pNode->pLeft != NULL)

{

freenodes(pNode->pLeft);

}

if(pNode->pRight != NULL)

{

freenodes(pNode->pRight);

}

free(pNode);

}


Tampilan Hasil

Latihan

1. Buatlah program untuk memasukkan node baru ke

dalam pohon dengan menggunakan prosedur, preorder,

inorder dan postorder dengan contoh data Sebagai

berikut :

-Tampilan secara PreOrder : R A S I T E

-Tampilan secara InOrder : I S T A R E

-Tampilan secara PostOrder : I T S A E R?

2. Buatlah insert dan searching data pada binary tree

beserta tampilkan history nilai yang telah dilewati?

modul struktur data 2013

Documents