fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/algoritma-dan... ·...

185
MODUL PERKULIAHAN Algoritma Pemrograman & Struktur Data Pertemuan 1 PENDAHULUAN Fakultas Program Studi Tatap Muka Kode MK Disusun Oleh Ilmu Komputer Teknik Informatika 01 87031 Tim Dosen Abstract Kompetensi Membahas tentang konsep dasar dari algoritma dan struktur data Mampu memahami konsep dasar dari algoritma dan struktur data

Upload: dangkien

Post on 06-Mar-2018

258 views

Category:

Documents


12 download

TRANSCRIPT

Page 1: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 1 PENDAHULUAN

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

01 87031  Tim Dosen 

   

 

 

Abstract  Kompetensi    

Membahas tentang konsep dasar dari algoritma dan struktur data

 

Mampu memahami konsep dasar dari algoritma dan struktur data 

 

   

Page 2: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Pendahuluan

Tipe dan Definisi Data

DEFINISI DATA :

ADALAH FAKTA ATAU KENYATAAN YANG TERCATAT MENGENAI SUATU OBYEK.

Pengertian data ini menyiratkan suatu nilai yang bisa dinyatakan dalam bentuk konstanta

atau variabel.

Konstanta menyatakan nilai yang tetap

Variabel digunakan dalam program untuk menyatakan nilai yang dapat diubah-ubah

selama eksekusi berlangsung.

ADA 4 ISTILAH TENTANG DATA YAITU :

1. Tipe Data : Macam / isi data di dalam suatu variable dalam bahasa program

2. Objek Data : Set dari elemen misal X set bilangan integer

3. Representasi Data : Suatu mapping dari struktur data d ke suatu set dari struktur data e

misalnya Boolean direpresantasikan dalam 0 dan 1

4. Struktur Data : Struktur adalah koleksi dari variabel yang dinyatakan dengan sebuah

nama, dengan sifat setiap variabel dapat memiliki tipe yang berlainan. Struktur data

biasa dipakai untuk mengelompokkan beberapa informasi yang berkaitan menjadi

sebuah kesatuan

HIRARKI DARI TIPE DATA :

Page 3: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

TIPE DATA SEDERHANA

Hanya dimungkinkan untuk meyimpan sebuah nilai data dalam sebuah variabel.

Ada 5 macam :

- Bil. Bulat ( integer )

- Bil. Real presisi-tunggal ( Float )

- Bil. Real presisi-ganda ( Double )

- Karakter

- Tak bertipe/void (Tipe data untuk Fungsi)

- Boolean ( Operator Logika )

TIPE TOTAL

BIT

KAWASAN KETERANGAN

Char  8 -128 s/d 127 Karakter

Int 16 -32768 s/d 32767 Bil Integer

Float 32 3.4E-38 s/d 3.4E+38 Bil real Presisi Tunggal

Double 64 1.7E-308 s/d 1.7E+308 Bil Real Presisi Ganda

Void 6 Tak bertipe

TIPE DATA BOOLEAN

Mempunyai 2 nilai : True dan False

OPERATOR Maksud

&& Dan ( And )

|| Atau ( OR )

! Tidak ( Not )

Operator Boolean biasa dipakai untuk menghubungkan ungkapan relasi

Operand 1 Operand 2 Hasil

|| &&

False False False False

False True True False

True False True False

True True True True

Page 4: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

TIPE DATA TERSTRUKTUR

Adalah tipe dimana suatu variabel bisa menyimpan lebih dari sebuah nilai data. Masing-

masing nilai data disebut komponen.

Ada 5 macam :

1. Tipe String

Data yang berisi sederetan karakater dimana banyaknya karakter bisa berubah-ubah

sesuai dengan kebutuhan.

Contoh Char Nama[30];

2. Larik (Array )

Variabel hanya menyimpan 1 tipe data saja.

Contoh

Int A[10];

Float C[3][4];

3. Record

Terdiri dari beberapa variabel yang terstruktur dan masing-masing variabel bisa

mempunyai tipe yang berbeda.

Contoh :

Struct Nama data_tanggal { int tanggal;

int bulan;

int tahun };

4. Set ( himpunan )

Union

Memungkinkan suatu lokasi memori ditempati oleh dua atau lebih variabel yang

tipenya bisa berlainan.

Contoh :

Union

{ unsigned int Angka;

unsigned char Huruf[12] } bil_X

Enumerasi

Merupakan himpunan dari konstanta integer yang diberi nama.

Contoh :

enum manusia {pria,wanita};

enum manusia jns_kelamin;

jika jns_kelamin diisi pria maka nilai jns_kelamin=0 dan sebaliknya jika

wanita nilai=1

Page 5: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

5. File

Merupakan organisasi dari sejumlah record sejenis. Masing-masing record dapat

terdiri dari satu atau beberapa field dan setiap field terdiri dari satu atau bebrapa

karakter.

TIPE DATA POINTER

Variabel pointer berisi alamat dari suatu obyek lain (yaitu obyek yang ditunjuk oleh pointer

tersebut).

Contoh int *pa;

pa = &x;

pointer pa menunjuk alamat x.

Algoritma

DEFINISI ALGORITMA :

Adalah himpunan langkah-langkah instruksi untuk melaksanakan suatu pekerjaan tertentu,

dengan beberapa kriteria :

1. Ada input

2. Ada output

3. Jelas dan tidak meragukan (definiteness)

4. Ada terminasi (finiteness)

5. Efektif dan dapat dilaksanakan.

Ada sedikit perbedaan antara algoritma dan program.

Program tidak harus memenuhi kriteria 4 contoh SO, karena harus selalu menunggu job.

Page 6: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Algoritma dan Metode Pemrograman

Penekanannya pada bagaimana memecahkan suatu masalah dengan algoritma yang tepat.

Dasar-dasar algoritma :

- Statement Elementer

- Statement Control

Statement Elementer

- Assignment

- Comparison

- Arithmetic Statement

- Operator Boolean

- Instruksi I/O

Statement Control :

- Alternatif

- Pengulangan

- Percabangan

STATEMENT ELEMENTER :

a. Assigment

Untuk memberikan nilai kevariabel yang telah dideklarasikan, bentuk pernyataan yang

digunakan :

Contoh Bil3 = 0;

b. Comparison

U/ keperluan pengambilan keputusan diperlukan operator relasi sebagai berikut :

Operator >, <, >=, <=, = =, !=

c. Arithmetic Statement

Operator Aritmatika : +, - , *, /, ^

Ada operator aritmatika khusus yaitu mod (%) sisa pembagian.

Contoh 7 % 2 hasilnya 1

d. Operator Boolean

Adalah operator logika dipakai untuk menghubungkan ungkapan relasi yang hasilnya

True atau False

Yaitu && (dan), || (Or), ! (not)

Page 7: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

e. Operasi Input/Output

U/ memasukkan data kekomputer dalam Bahasa C/C++ Sbb : printf(),cin(),scanf(),

getch(), getche()

U/ mengeluarkan data : printf(), puts(), putchar(),cout().

STATEMENT CONTROL

a. Alternatif

Terdiri dari pernyataan : - If , If - else , switch

Bentuk umum :

If ( kondisi )

{ pernyataan }

If ( kondisi )

{ pernyataan True }

else

{ pernyataan False }

switch ( ekspresi )

{ case –1 : pernyataan 1

break;

case – n : pernyataan n

break }

b. Pengulangan

Pernyataan pengulangan terdiri dari :

- do while

- while

- for

do

{

pernyataan

}

while (kondisi)

Page 8: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

while ( kondisi )

{

pernyataan

}

for (ungkapan1;ungkapan2;ungkapan3)

{

pernyataan

}

c. Percabangan

Memerlukan label sebagai identitas cabang.

label :

{

pernyataan

}

goto label

STRUKTUR DATA LINIER

Struktur data linier adalah struktur data yang menggambarkan hubungan tentang elemen-

elemen yang berdekatan :

Terdiri dari :

ARRAY : a. Dimensi satu (vector matriks)

b. Dimensi dua (matriks)

c. Multi dimensi

Aplikasi penggunaan array diantaranya :

a. Stack (tumpukkan)

b. Queue (antrian)

c. Deque (antrian dengan 2 pintu )

Page 9: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

LINKED LIST (LIST BERKAIT)

a. Linier Singly linked list

b. Linier Doubly linked list

c. Circular singly linked list

d. Circular doubley linked list

Aplikasi linked list pada struktur data linier diantaranya :

a. Linked stack

b. Linked Queue

Sedangkan multi linked list banyak digunakan pada struktur data non-linier yaitu

untuk representasi tree maupun graph .

PENGELOLAAN MEMORI

Dapat secara STATIS atau DINAMIS

Secara STATIS

Menempati lokasi memori yang tetap(fixed size), tidak dapat dikembangkan atau

diciutkan.

Misal : array

Alamat memori menjadi kunci array

Secara DINAMIS

Menempati lokasi memori dimana dapat dikembangkan atau diciutkan sesuai dengan

kebutuhan.

Pengelolaan memori secara dinamis(dynamic address) ditunjukkan oleh pointer.

Page 10: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Latihan Soal Buatlah algoritma sebagai berikut :

1. Menampilkan deret 1 3 5 7 9

2. Menampilkan deret 5 10 15 20 25 30

3. Menampilkan deret 100 ….. 0

4. Menampilkan deret bilangan prima 1 – 100

5. Menampilkan deret

1

2 3

4 5 6

7 8 9 10

DaftarPustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 11: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 2 ARRAY

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

02 87031  Tim Dosen 

   

 

 

Abstract  Kompetensi    

Membahas tentang konsep dari array satu dimensi hingga array multidimensi

 

Mampu memahami konsep dasar dari array satu dimensi hingga array multidimensi 

 

   

Page 12: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Array

Definisi Array

Array (larik) adalah tipe terstruktur yang terdiri dari sejumlah komponen-komponen dengan

type yang sama.

Banyaknya komponen dalam suatu larik adalah tetap dan lokasi dalam suatu larik

ditunjukkan oleh suatu INDEKS.

Yang penting dalam array adalah pengalamatan memori dan digunakan pengalamatan

secara static.

Karakteristik pemakaian Array :

- Jumlah elemen array terbatas

- Semua elemen array dapat diakses secara acak

- Panjang elemen sama

Dimensi

Dalam bentuknya array dapat kita tinjau dari segi pengaturan struktur datanya dalam

konteks dimensi sebagai berikut :

Array 1 – Dimensi

List

Vektor

Array 2 – Dimensi

Tables

Matriks (2 dimensi)

Array 3 – Dimensi

Matriks 3 Dimensi

Array Mulidimensi

Pada prinsipnya secara teori jumlah dimensi suatu matriks tidak terbatas, yang

membatasi adalah kemampuan hardware dan besarnya memori

Array Satu Dimensi

Suatu array dideklarasikan dengan : A[ -3 . . 8 ], setiap elemen terdiri dari 4 byte.

Jika alamat elemen pertama @A[ -3 ] = 1000 H ditanya :

Page 13: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

A. Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat A[7] atau ditulis @A[7]

Jawab :

Di ilustrasikan sebuah Array sebagai berikut:

1 2 3 4 5 6 7 8 9 10 11 12

-3

-2

-1

0

1

2

3

4

5

6

7

8

1

2

3

4

Setiap elemen 4 Byte

@A[-3] = 1000 H maka @A[-2] = 1004 H

A. Jumlah Elemen = (Index atas - Index Bawah ) + 1

= ( 8 - (-3) ) + 1

= 12 Elemen

B. Jumlah Byte = JumlahElemen * Jumlah Byte PerElemen

= 12 * 4

= 48 Byte

C. Alamat @A[ 7 ] =

Dari @A[-3] berpindah/bergerak ke @A[7]

= 7 - (-3)

= 10 Elemen

Setiap Elemen 4 Byte maka :

10 * 4 = 40 Byte

40 disini adalah dalam notasi 40 Decimal, dalam pengalamatan memori digunakan

notasi Hexa Decimal. Maka 40 Decimal dirubah menjadi Hexa Decimal.

40 Decimal = 28 Hexa Decimal atau 28 H

Jadi @A[7] = 1000 H + 28 H

= 1028 H

Page 14: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Pendeklarasian A[ - 3 . . 8 ] adalah deklarasi yang ada pada bahasa program Pascal.

Pada bahasa program C/C++ pendeklarasian sedikit berbeda tapi mempunyai maksud

yang sama.

Contoh

A[8]

Maka akan terbentuk Array 1 Dimensi sebanyak 8 tempat

0

1

2

3

4

5

6

7

Dimana nomor index pertama pada bahasa C dimulai dari 0 (nol)

Program C++ mengetahui alamat suatu data

#include<iostream.h> #include<conio.h> main() {

int i,j,ANGKA[5]; clrscr(); for(i=0; i<5; i++) {

cout <<"MASUKAN ANGKA ["<<i<<"]= "; cin>>ANGKA[i]; } for(i=0; i<5; i++) {

cout <<"ANGKA ["<<i<<"]= "<<ANGKA[i]<<" ADA DIALAMAT = "<<&ANGKA[i]<<endl;

} getch(); }

Array Dua Dimensi

Representasi matriks dalam bentuk array dua dimensi dapat berupa :

Ukuran baris perbaris ( Row Major Order)

Ukuran Kolom perkolom ( Column Major Order)

Matrik dalam pembahasan selanjutnya menggunakan M[Baris][Kolom]

Page 15: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Diketahui suatu Array dua dimensi yang dideklarasikan dengan A[ -1 .. 2 , 3 .. 8 ] Setiap

elemen terdiri dari 4 Byte.

Alamat elemen pertama @A[-1,3] = 1000 H atau @A[-1,3] = 1000 H

Ditanya :

A. Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat A[2,5] atau @A[2,5] ?

Jika penempatan memori menggunakan :

C1. Row Major Order

C2. Column Major Order

Jawab .

Di ilustrasikan sebuah Array sebagai berikut:

@A[-1,3] = 1000 H

3 4 5 6 7 8

-1

A

B

C

D

E

F

0

G

H

I

J

K L

1

M

N

O

P

Q R

2

S

T

U

V

W

X

@A[2,5] = ?.

Pada Array 2 Dimensi yang diilustrasikan diatas, urutan elemennya dalam memori jika

megikuti cara :

Page 16: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

ROW MAJOR ORDER

(URUTAN YANG MENGUTAMAKAN/MENDAHULUKAN BARIS)

1 2 3 4 5 6 7 8 9….. 19 20 21 22 23 24

-1,3 -1,4 -1,5 -1,6 -1,7 -1,8 0,3 0,4 2,3 2,4 2,5 2,6 2,7 2,8

A B C D E F G H … .. S T U V W X

Baris Ke-1 Baris Ke-2 Baris ke 4

Baris (-1) Baris (0) Baris (2)

@A[-1,3] = 1000 H

Setiap pindah Satu Baris pindah 6 Elemen

COLUMN MAJOR ORDER

( URUTAN YANG MENDAHULUKAN KOLOM)

-1,3

A G M S B H N T C …. … Q W F L R X

kolom Ke-1 Kolom Ke-2 Kolom Ke 3 Kolom ke6

Kolom (3) Kolom (4) Kolom 5 Kolom 8

@A[-1,3] = 1000 H

Setiap pindah Satu Kolom pindah 4 Elemen

1 2 3 4 5 6 7 8 9…………….. 19 20 21 22 23 24

Page 17: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

BILA DINYATAKAN DENGAN NOMOR URUT MAKA PENEMPATAN ELEMEN ARRAY :

CARA ROW MAJOR ORDER

3 4 5 6 7 8

-1 1 2 3 4 5 6

0 7 8 9 10 11 12

1 13 14 15 16 17 18

2 19 20 21 22 23 24

CARA COLUMN MAJOR ORDER

3 4 5 6 7 8

-1 1 5 9 13 17 21

0 2 6 10 14 18 22

1 3 7 11 15 19 23

2 4 8 12 16 20 24

Catatan : Angka- Angka Didalam Elemen Bukan Isi elemen tapi merupakan nomor Urut

elemen.

Jawaban Soal ARRAY DUA DIMENSI

A. Jumlah Elemen = Baris * Kolom A[ -1..2 , 3 .. 8 ]

= 4 * 6

= 24

2 - (-1)+1 (8-3)+1

= 4 Baris = 6 Kolom

B. Jumlah Byte = 24 * 4 = 96 Byte

Page 18: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

             3        4          5         6         7           8  

-1 A B C D E F

0 G H I J K L

1 M N O P Q R

              3         4          5         6         7           8  

-1 1 2 3 4 5 6

0 7 8 9 10 11 12

1 13 14 15 16 17 18

C1. Menentukan Alamat @A[2,5]

menggunakan ROW MAJOR ORDER

@A[-1,3] = 1000 H

@A[2,5] =……?

Dari Gambar Diatas terlihat bahwa bergerak dari elemen A[-1,3] ke elemen A[2,5] yaitu

elemen ke 21 menurut ROW MAJOR ORDER perpindahannya sebanyak :

21 – 1 = 20 Elemen

A T A U

Terlihat dari Baris –1 ke baris 2 sebanyak 3 Baris

Setiap Baris ada 6 Elemen , Jadi 3 * 6 = 18 Elemen

Dari Kolom 3 Ke kolom 5 sebanyak 2 Kolom

Jadi Total Perpindahan = 18 + 2 = 20 Elemen

Satu Elemen 4 Byte Pindah 20 * 4 = 80 Byte 80 Dec = 50 Hexa Dec.

Atau tanpa melihat Gambar : A [Baris, Kolom ]

Ditanya : @A[ 2 , 5 ]

Diketahui : @A[ -1 , 3 ] Dikurang

3 2

Pindah 3 Baris = 3 * Banyak Elemen Per baris = 3 * 6 = 18

Pindah 2 Kolom = 2 2

Total Perpindahan 18 + 2 = 20 Elemen

Page 19: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

            3       4          5         6         7           8  

-1 A B C D E F

0 G H I J K L

1 M N O P Q R

             3         4          5         6         7           8  

-1 1 5 9 13 17 21

0 2 6 10 14 18 22

1 3 7 11 15 19 23

Dimana 1 Elemen 4 Byte Jadi 20 * 4 = 80 Byte ( Decimal )

80 Decimal = 50 Hexa Decimal

Jadi Alamat @A[2,5] = 1000 H + 50 H = 1050 H

C2. Menentukan Alamat @A[2,5] menggunakan

COLUMN MAJOR ORDER

@A[-1,3] = 1000 H

@A[2,5] = ……?

Dari Gambar Diatas terlihat bahwa bergerak dari elemen A[-1,3] ke elemen A[2,5] yaitu

elemen ke 12 menurut COLUMN MAJOR ORDER perpindahannya sebanyak :

12 – 1 = 11 Elemen

A T A U

Terlihat dari kolom 3 ke kolom 5 sebanyak 2 Kolom

Setiap Kolom ada 4 Elemen , Jadi 2 * 4 = 8 Elemen

Dari baris -1 Ke baris 2 sebanyak 3 baris

Jadi Total Perpindahan = 8 + 3 = 11 Elemen

Satu Elemen 4 Byte Pindah 11 * 4 = 44 Byte= 44 Dec

44 Dec = 2C Hexa,

Page 20: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

3 4 5 6 7 8

-1

0

1

2

3 4 5 6 7 8

-1

0

1

2

 

Atau tanpa melihat Gambar : A [Baris, Kolom ]

Ditanya : @A[ 2 , 5 ]

Diketahui : @A[ -1 , 3 ] Dikurang

3 2

Pindah 2 Kolom = 2 * Banyak Elemen Per Kolom = 2 * 4 = 8

Pindah 3 Baris = 3 3

Total Perpindahan 8 + 3 = 11 Elemen

Dimana 1 Elemen 4 Byte Jadi ---- 11 * 4 = 44 Byte ( Decimal )

44 Dec. = 2C Hexa Dec.l

Jadi Alamat @A[2,5] = 1000 H + 2C H = 102C H

Array Tiga Dimensi

Suatu Array dideklarasikan A[ 2 ..4 , -1 .. 2 , 3 .. 8 ], setiap elemen terdiri 4 byte.

Alamat elemen pertama @A[2,-1,3]= 1000 H ditanya :

A. Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat @A[4,2,5]

C1. Menggunakan Row Major Order

C2. Menggunakan Column Major Order

JAWAB

ilustrasi : @A[2,-1,3] = 1000 H

3 4 5 6 7 8

-1

0

1

2

Blok 2 Blok 3 Blok 4

@A[4,2,5] =….?

Page 21: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

3 4 5 6 7 8

-1 1 2 3 4 5 6

0 7 8 9 10 11 12

1 13 14 15 16 17 18

2 19 20 21 22 23 24

 

3 4 5 6 7 8

-1 25 26 27 28 29 30

0 31 32 33 34 35 36

1 37 38 39 40 41 42

2 43 44 45 46 47 48

3 4 5 6 7 8

-1 49 50 51 52 53 54

0 55 56 57 58 59 60

1 61 62 63 64 65 66

2 67 68 69 70 71 72

Blok Baris Kolom

(4 – 2 )+1 (2-(-1))+1 (8-3) + 1

3 Blok 4 Baris 6 Kolom

A[ 2 .. 4 , -1 .. 2 , 3 . . 8 ]

A. Jumlah Elemen: Jumlah Blok = ( 4 - 2 ) + 1 = 3 Blok

Jumlah Baris = ( 2 – (-1) + 1 = 4 Baris

Jumlah Kolom = ( 8 – 3 ) + 1 = 6 Kolom

Jumlah Elemen = 3 * 4 * 6 = 72 Elemen.

B. Jumlah Byte : 72 * 4 Byte = 288 Byte.

C1. ROW MAJOR ORDER

@A[2,-1,3] = 1000 H

BLOK 2 BLOK 3 BLOK 4

@A[4,2,5] = ……?

Dari Gambar terlihat urutan perpindahan dari elemen no. 1 ke Elemen No. 69 perpindahan

sebanyak 68 Elemen.

68 * 4 Byte =272 Byte --- 272 Dec. = 110 Hexa Dec.

Jika tidak melihat gambar dapat dihitung dengan melihat perpindahan Blok, Baris dan

kolom.

Ditanya : @A[ 4 , 2 , 5 ]

Diketahui @A[ 2 , -1 , 3 ] Di kurang

Page 22: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

3 4 5 6 7 8

-1 1 5 9 13 17 21

0 2 6 10 14 18 22

1 3 7 11 15 19 23

2 4 8 12 16 20 24

3 4 5 6 7 8

-1 25 29 33 37 41 45

0 26 30 34 38 42 46

1 27 31 35 39 43 47

2 28 32 36 40 44 48

3 4 5 6 7 8

-1 49 53 57 61 65 69

0 50 54 58 62 66 70

1 51 55 59 63 67 71

2 52 56 60 64 68 72

2 3 2

Pindah 2 Blok ( Dari Blok 2 Ke Blok 4 )

Setiap Blok Ada 24 Elemen

Jadi Perpindahan 2 * 24 = 48 Elemen

Pindah 3 Baris ( Dari Baris -1 Ke baris 2 )

Setiap Baris ada 6 Elemen

Jadi Perpindahan 3 * 6 = 18 Elemen

Pindah 2 Kolom ( 2 Elemen ) = 2 Elemen

Jadi Jumlah Pepindahan 68 Elemen

Pindah = 68 Elemen

= 68 * 4 Byte

= 272 Byte (Decimal)

= 110 Hexa Dec

Jadi Alamat @A[4,2,5] = 1000 H + 110 H = 1110 H

C2. COLUMN MAJOR ORDER

@A[2,-1,3] = 1000 H

BLOK 2 BLOK 3 BLOK 4

@A[4,2,5] = ……?

Dari Gambar terlihat urutan perpindahan dari elemen no. 1 ke Elemen No. 60 perpindahan

sebanyak 59 Elemen.

59 * 4 Byte = 236 Byte 236 Dec. = EC Hexa Dec.

Page 23: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 13 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Jika tidak melihat gambar dapat dihitung dengan melihat perpindahan Blok, Baris dan

kolom.

Ditanya : @A[ 4 , 2 , 5 ]

Diketahui @A[ 2 , -1 , 3 ] Di kurang

2 3 2

Pindah 2 Blok ( Dari Blok 2 Ke Blok 4 )

Setiap Blok Ada 24 Elemen

Jadi Perpindahan 2 * 24 = 48 Elemen

Pindah 3 Baris ( Dari Baris -1 Ke baris 2 )

Pindah Sebanyak 3 Elemen = 3 Elemen

Pindah 2 Kolom ( Dari Kolom 3 Ke Kolom 5)

Setiap Kolom 4 Elemen

Jadi Perpindahan 2 * 4 = 8 Elemen

Jadi Jumlah Pepindahan 59 Elemen

Pindah = 59 Elemen

= 59 * 4 Byte

= 236 Byte (Decimal)

= EC Hexa Dec

Jadi Alamat @A[4,2,5] = 1000 H + EC H = 10EC H

Page 24: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 14 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Array Empat Dimensi (Multidimensi)

Diketahui suatu Array Multi Dimensi yang dideklarasikan dengan A[1..2, 2..4, -1..2, 3..8 ].

Setiap elemen terdiri dari 4 Byte. Alamat elemen pertama @A[1,2,-1,3] = 1000 H

Ditanya : A . Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat @A[2,4,2,5] ?

C1. Row Major Order

C2. Column Major Order

Jawab

Grup Blok Baris Kolom

(2 –1)+1 (4-2)+1 (2-(-1)+1 (8-3)+1

2 Grup 3 Blok 4 Baris 6 Kolom

A [ 1 . . 2 , 2 . . 4 , -1 . . 2 , 3 . . 8 ]

ILUSTRASI

GRUP 1

3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8

-1

0

1

2

Blok 2 Blok 3 Blok 4

GRUP 2

3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8

-1

0

1

2

Blok 2 Blok 3 Blok 4

A. Jumlah Elemen = 2 Grup * 3 Blok * 4 Baris * 6 Kolom

= 144 Elemen

B. Jumlah Byte = 144 * 4 = 576 Byte

Page 25: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 15 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

C1. ROW MAJOR ORDER

GRUP 1

3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8

-1

0

1

2

Blok 2 Blok 3 Blok 4

GRUP 2

3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8

-1

0

1

2 1

4

1

Blok 2 Blok 3 Blok 4

C2. COLUMN MAJOR ORDER

GRUP 1

3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8

-1

0

1

2

Blok 2 Blok 3 Blok 4

GRUP 2

3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8

-1

0

1

2

Blok 2 Blok 3 Blok 4

Page 26: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 16 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Latihan Soal

Latihan Array satu dimensi :

1. Suatu array dideklarasikan dengan : A[-2 .. 5 ], setiap elemen terdiri dari 6 byte.

Jika alamat elemen pertama FFBB H ditanya :

a. Jumlah Elemen

b. Jumlah Byte Seluruhnya

c. Alamat A[4] atau ditulis @A[4]

2. Suatu array dideklarasikan dengan : A[9] pada Bahasa C++, setiap elemen terdiri dari 8

byte. Jika alamat elemen pertama 16FF H ditanya :

a. Jumlah Elemen

b. Jumlah Byte Seluruhnya

c. Alamat A[5] atau ditulis @A[5]

3 Suatu array dideklarasikan pada bahasa C++ dengan :

float angka[12]; Jika alamat elemen pertama 2C3E H ditanya :

a. Jumlah Elemen

b. Jumlah Byte Seluruhnya

c. Alamat A[6] atau ditulis @A[6]

Latihan Array dua dimensi :

1. Diketahui suatu Array dua dimensi yang dideklarasikan dengan A[-2..3,3..6]. Setiap

elemen terdiri dari 2 Byte. Alamat elemen pertama FECA H

Ditanya : A . Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat A[2,5] atau @A[2,5] ?

Jika penempatan memori menggunakan :

C1. Row Major Order

C2. Column Major Order

2. Diketahui suatu Array dua dimensi yang dideklarasikan dengan A[5][6] Pada Bahasa

C++. Setiap elemen terdiri dari 10 Byte. Alamat elemen pertama @A[0][0]=FBCA H

Ditanya : A . Jumlah Elemen

Page 27: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 17 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

B. Jumlah Byte Seluruhnya

C. Alamat A[3,2] atau @A[3,2] ?

Jika penempatan memori menggunakan :

C1. Row Major Order

C2. Column Major Order

3. Diketahui suatu Array dua dimensi yang dideklarasikan dengan :

long A[6][7] Pada Bahasa C.

Alamat elemen pertama 10CC H

Ditanya : A . Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat A[2,5] atau @A[2,5] ?

Jika penempatan memori menggunakan :

C1. Row Major Order

C2. Column Major Order

Latihan Array tiga dimensi :

1. Diketahui suatu Array 3 dimensi yang dideklarasikan dengan A[-2..2,1..4,3..6]. Setiap

elemen terdiri dari 6 Byte. Alamat elemen pertama FC8B H

Ditanya : A . Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat A[1,3,5] atau @A[1,3,5] ?

C1. Row Major Order

C2. Column Major Order

2. Diketahui suatu Array 3 dimensi yang dideklarasikan dengan A[2][5][6] Pada Bahasa

C++.Setiap elemen terdiri dari 4 Byte. Alamat elemen pertama BC9A H

Ditanya : A . Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. Alamat A[1,3,5] ?

C1. Row Major Order

C2. Column Major Order

3. Diketahui suatu Array 3 dimensi yang dideklarasikan dengan :

longdouble A[4][3[7] Pada Bahasa C++.

Alamat elemen pertama CBBA H

Ditanya : A . Jumlah Elemen

Page 28: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 18 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

B. Jumlah Byte Seluruhnya

C. Alamat A[3,2,6] ?

C1. Row Major Order

C2. Column Major Order

Latihan Array empat dimensi (multidimensi) :

1. Diketahui Array Multi dimensi yang dideklarasikan dengan A[2..4,-1..4,3..6,1..6]. setiap

elemen 8 Byte. Alamat elemen Pertama F2BE H.

Ditanya A. Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. @A[2,4,4,5]

C1. Row Major Order

C2. Column Major Order

2. Diketahui Array Multi dimensi yang dideklarasikan dengan A[4][3][2][3] dengan Bhs. C.

setiap elemen 4 Byte. Alamat elemen Pertama 2BCE H.

Ditanya A. Jumlah Elemen

B. Jumlah Byte Seluruhnya

C. @A[1,2,1,2]

C1. Row Major Order

C2. Column Major Order

3. Diketahui Array Multi dimensi yang dideklarasikan

int A[5][2][6][8][3] dengan Bhs. C++. Alamat elemen Pertama 3CDE H.

Ditanya A. Jumlah Elemen

B. Jumlah Byte Seluruhnya

D. @A[3,0,3,6,2]

C1. Row Major Order

C2. Column Major Order

Page 29: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 19 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 30: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 3 LINKED LIST

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

03 87031  Tim Dosen 

   

 

 

Abstract  Kompetensi    

Membahas tentang konsep dari linked list dan penerapannya

 

Mampu memahami konsep dasar dari dari linked list dan penerapannya 

 

   

Page 31: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Linier Singly Linked List

Linier Singly Linked List

- Pengelolaan memory secara dinamis artinya tidak perlu mengalokasikan memori

lebih awal secara tetap (fixed).

- Satu elemen terdiri dari 2 elemen :

a. Elemen yang menyimpan data

b. Elemen yang menyimpan alamat record

ILLUSTRASI

FIRST LAST INFO LINK INFO LINK INFO LINK INFO LINK

25

12

17

10

( 1 ) ( 2) ( 3 ) ( 4 ) Keterangan dari ilustrasi Linked List :

- Ada 4 Simpul : simpul 1 s/d simpul 4

- Setiap simpul(record) terdiri 2 elemen yaitu :

Field INFO misal bertipe Integer

Field LINK bertipe Pointer

Contoh simpul no. 1

Field INFO berisi nilai 25

Field LINK berisi alamat record no. 2

Simpul No. 3

Field INFO berisi nilai 17

Field LINK berisi alamat record no. 4

FIRST dan LAST adalah pointer

Proses yang dapat dilakukan :

a. Pembuatan Simpul Awal

Page 32: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

b. Insert kanan (akhir)

c. Delete Kanan

d. Insert Tengah

e. Insert Kiri

f. Delete Kiri

g. Delete Tengah

ILUSTRASI SEBUAH SIMPUL (RECORD)

INFO LINK

Nama Field : LINK Tipe : Pointer Isi : akan diisi alamat

Record Berikutnya

Nama Field : INFO Tipe : Integer Isi : akan diisi data

Dalam bahasa C/C++ untuk memberitahukan komputer bahwa kita memerlukan suatu

simpul atau record dengan tipe struktur diatas perlu ditulis instruksi-instruksi sebagai berikut:

Struct SIMPUL {

int INFO;

struct SIMPUL *LINK;

};

struct SIMPUL *P, *FIRST, *LAST;

disiapkan 3 buah pointer yaitu P, FIRST, LAST yang semuanya terkait dengan simpul atau

record .

Page 33: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

a. Pembuatan Simpul Awal

Instruksi untuk membuat sebuah simpul (record) baru adalah :

P=(struct SIMPUL*) malloc(sizeof(struct SIMPUL*));

Malloc : Maksudnya mengalokasikan memory Sebesar atau seukuran (sizeof) yang

diperlukan Untuk simpul.

Contoh sederhana (lengkap) program membuat Simpul Awal:

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <ctype.h>

struct SIMPUL { int INFO;

struct SIMPUL *LINK;

};

struct SIMPUL *P, *FIRST, *LAST;

main( )

{ int X;

clrscr();

cout<<"MASUKAN SIMPUL AWAL : ";

cin>>X;

P=(struct SIMPUL*)malloc(sizeof(struct SIMPUL));

P->INFO=X;

P->LINK=NULL;

cout<<" ANGKA YANG DIMASUKKAN = "<<P->INFO<<endl;

getch();

}

 

 

Page 34: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Perhatikan kembali Linier Singly Lingked List FIRST LAST INFO LINK INFO LINK INFO LINK INFO LINK

25

12

17

10

( 1 ) ( 2) ( 3 ) ( 4 ) Fungsi untuk membuat simpul(Record) AWAL

void AWAL(void)

{ int X;

cout<<”MASUKKAN SIMPUL AWAL : “;

cin>>X;

P=(struct SIMPUL*) malloc(sizeof(struct SIMPUL*));

P->INFO=X;

FIRST = P;

LAST=P;

P->LINK=NULL;

}

b. INSERT KANAN (INSERT AKHIR)

sudah dibuat Simpul awal sebagai berikut :

FIRST LAST P INFO LINK

25

( 1 )

   

Page 35: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Akan diinsert disebelah kanan seperti berikut FIRST LAST INFO LINK INFO LINK

25

12

( 1 ) ( 2) Fungsi untuk Insert Kanan sebagai berikut :

void InsertKanan(void)

{ int X;

cout<<”MASUKKAN SIMPUL KANAN : “;

cin>>X;

P=(struct SIMPUL*) malloc(sizeof(struct SIMPUL*));

P->INFO=X;

LAST->LINK=P;

LAST=P;

P->LINK=NULL;

}

c. DELETE KANAN

Misal sudah ada Linked List sebagai berikut:

FIRST Q LAST INFO LINK INFO LINK INFO LINK INFO LINK

25

12

17

10

( 1 ) ( 2) ( 3 ) ( 4 )

Fungsi untuk Delete Kanan sebagai berikut :

Page 36: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

void DeleteKanan(void)

{ int X;

X=LAST->INFO;

cout<<”DATA YANG AKAN TERHAPUS”<<X;

free(LAST);

LAST=Q;

LAST->LINK=NULL;

}

Buat Fungsi :

a. Insert Tengah

b. Insert Kiri

c. Delete Kiri

d. Delete Tengah

Linier Doubly Linked List

- Pengelolaan memory secara dinamis artinya tidak perlu mengalokasikan memori

lebih awal secara tetap (fixed).

- Satu elemen terdiri dari 2 elemen :

a. Elemen yang menyimpan data

b. Elemen yang menyimpan alamat record sebelumnya

c. Elemen yang menyimpan alamat record sesudahnya

ILUSTRASI

FIRST LAST LEFT INFO RIGHT

25

12

17

10

1 2 3 4

Page 37: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

ILUSTRASI SEBUAH SIMPUL

Simpul dengan 3 Elemen

LEFT INFO RIGHT

Nama Field : LEFT Nama Field : INFO Nama Field : RIGHT Type : Pointer Type : integer Type : Pointer Isi : Akan diisi alamat Isi : akan diisi data Isi : akan diisi alamat Record sebelumnya Record sesudanya

Dalam Bahasa C++ untuk menyatakan suatu simpul dengan struktur demikian dapat ditulis

sebagai berikut :

Struct SIMPUL {

int INFO;

struct SIMPUL *LEFT, *RIGHT;

};

struct SIMPUL *P, *FIRST, *LAST;

Proses yang dapat dilakukan :

a. Pembuatan Simpul Awal

b. Insert kanan (akhir)

c. Delete Kanan

d. Insert Tengah

e. Insert Kiri

f. Delete Kiri

g. Delete Tengah

a. Pembuatan Simpul Awal

Contoh sederhana (lengkap) program membuat Simpul awal:

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <ctype.h>

Page 38: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

struct SIMPUL { int INFO;

struct SIMPUL *LEFT,*RIGHT;

};

struct SIMPUL *P, *FIRST, *LAST;

main( )

{ int X;

clrscr();

cout<<"MASUKAN SIMPUL AWAL : ";

cin>>X;

P=(struct SIMPUL*)malloc(sizeof(struct SIMPUL));

P->INFO=X;

FIRST=P;

LAST=P;

P->LEFT=NULL;

P->RIGHT=NULL;

cout<<" Isi P = "<<P->INFO;

}

Fungsi untuk membuat Simpul Awal

void AWAL(void)

{ int X;

cout<<”MASUKKAN SIMPUL AWAL :”

cin>>X;

P=(struct SIMPUL*) malloc(sizeof(struct SIMPUL*));

P->INFO=X;

FIRST=P;

LAST=P;

P->LEFT=NULL;

P->RIGHT=NULL;

}

Page 39: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Ilustrasi simpul yang dihasilkan oleh program misal X=25

LAST FIRST P LEFT INFO RIGHT

25

Ada 3 buah pointer yang LAST, FIRST dan P yang menunjuk data yang sama.

b. Insert Kanan

Dibuat Simpul Awal sebagai berikut :

LAST FIRST P LEFT INFO RIGHT

25

(1)

Akan dibuat simpul baru disebelah kanan sebagai berikut

FIRST LAST LEFT INFO RIGHT

25

12

(1) (2)

Page 40: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Fungsi untuk Insert Kanan Sebagai Berikut :

void InsertKanan(void)

{ int X;

cout<<”MASUKKAN SIMPUL KANAN”;

cin>>X;

P=(struct SIMPUL*) malloc(sizeof(struct SIMPUL*));

P->INFO=X;

LAST->RIGHT=P;

P->LEFT=LAST;

LAST=P;

P->RIGHT=NULL;

}

c. Delete Kanan (Akhir)

Sudah ada Double Linked List sebagai berikut :

FIRST LAST LEFT INFO RIGHT

25

12

17

10

1 2 3 4

Akan dihapus simpul yang paling kanan (4) menjadi sebagai berikut:

FIRST LAST LEFT INFO RIGHT

25

12

17

1 2 3

Pointer LAST akan menunjuk Ke Record Ke 3

Page 41: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Fungsi untuk Delete Kanan Sebagai Berikut :

void DeleteKanan(void)

{ int X;

X=LAST->INFO;

cout<<”DATA YANG TERHAPUS”<<X;

LAST=LAST->LEFT;

free(LAST->RIGHT)

LAST->RIGHT=NULL;

}

Buat Fungsi :

a. Insert Tengah

b. Insert Kiri

c. Delete Kiri

d. Delete Tengah

Praktikum

PRAKTEK DI LABORATORIUM

DISAJIKAN SEBUAH PROGRAM LINIER SINGLE LINKED LIST /*PROGRAM LINIER SINGLY LINKED LIST */ #include <iostream.h> #include <conio.h> #include <stdlib.h> #include <ctype.h> struct SIMPUL { int INFO; struct SIMPUL *LINK; }; struct SIMPUL *P, *FIRST, *LAST, *T, *Q; void AWAL(void); void TAMPIL(void); void INSERT_KANAN(void);

Page 42: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 13 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

void INSERT_KIRI(void); void INSERT_TENGAH(void); void DELETE_KIRI(void); void DELETE_KANAN(void); void DELETE_TENGAH(void); void COBA(void); int X,PIL; main( ) { do { clrscr(); cout<<"LINIER SINGLY LIST"<<endl; cout<<"======================"<<endl; cout<<"1. SIMPUL AWAL"<<endl; cout<<"2. INSERT KANAN"<<endl; cout<<"3. INSERT KIRI"<<endl; cout<<"4. INSERT TENGAH"<<endl; cout<<"5. DELETE KANAN"<<endl; cout<<"6. DELETE KIRI"<<endl; cout<<"7. DELETE TENGAH"<<endl; cout<<"8. TAMPIL "<<endl; cout<<"9. Exit"<<endl<<endl; cout<<"PILIHAN : "; cin>>PIL; switch (PIL) { case 1 : AWAL(); break; case 2 : INSERT_KANAN(); break; /* case 3 : INSERT_KIRI(); break; case 4 : INSERT_TENGAH(); break; */ case 5 : DELETE_KANAN(); break; /* case 6 : DELETE_KIRI(); break; case 7 : DELETE_TENGAH(); break; */ case 8 : TAMPIL(); break; case 9 : cout<<"TERIMA KASIH"; break; } getch(); } while (PIL<9); } void AWAL(void) {

Page 43: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 14 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

clrscr(); cout<<"MASUKAN SIMPUL AWAL : "; cin>>X; P=(struct SIMPUL*)malloc(sizeof(struct SIMPUL)); P->INFO=X; P->LINK=NULL; FIRST=P; LAST=P; cout<<"Isi P = "<<P->INFO<<endl; cout<<"Isi FIRST = "<<FIRST->INFO<<endl; cout<<"Isi LAST = "<<LAST->INFO<<endl; cout<<"Isi pointer P = "<<P->LINK<<endl; cout<<"Isi pointer FIRST = "<<FIRST->LINK<<endl; cout<<"Isi pointer LAST = "<<LAST->LINK<<endl; } void INSERT_KANAN(void) { clrscr(); cout<<"MASUKAN SIMPUL KANAN : "; cin>>X; P=(struct SIMPUL*)malloc(sizeof(struct SIMPUL)); P->INFO=X; LAST->LINK=P; LAST=P; P->LINK=NULL; cout<<" Isi P = "<<P->INFO; } void DELETE_KANAN(void) { clrscr(); if (FIRST!=NULL) { P=FIRST; while(P->LINK!=NULL) { Q=P; P=P->LINK; } X=P->INFO; cout<<"DATA YANG AKAN DIHAPUS : "<<X; free(P); Q->LINK=NULL; LAST=Q; } else cout<<" SIMPUL KOSONG";

Page 44: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 15 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

} void TAMPIL(void) { clrscr(); T=FIRST; while (T!=NULL) { X=T->INFO; cout<<X<<" "; T=T->LINK; } } Buat procedure/Fungsi untuk :

1. Insert Kiri 2. Insert Tengah 3. Delete Kiri 4. Delete Tengah

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 45: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 4 STACK (TUMPUKAN)

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

04 87031  Tim Dosen 

   

 

 

Abstract  Kompetensi    

Membahas tentang konsep dari queue (antrian) dan penerapannya

 

Mampu memahami konsep dasar dari queue (antrian) dan penerapannya

 

 

   

Page 46: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

STACK (TUMPUKAN)

Konsep Stack

Aplikasi penggunaan array berupa : Stack ( tumpukan ), Queue ( antrian ) dan Dequeue (

antrian 2 Arah )

Stack maksudnya tumpukan

Salah satu Ilustrasi Stack yang mudah dipahami

misalnya tumpukan buku diatas meja yang diilustrasikan sebagai berikut :

Nomor Nomor Urut Urut Masuk Keluar ( Push ) ( Pop )

4

Buku 4

1 Top

3

Buku 3

2

2

Buku 2

3

1

Meja

Buku 1

4 Dasar

Proses yang dapat dilakukan terhadap Stack

PUSH untuk : - Penempatan atau

- Masuk, atau

- Insert, atau

- Tulis

POP untuk : - Ambil atau

- Keluar, atau

- Delete, atau

- Baca/ Hapus

Page 47: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Mempunyai Prinsip :

LIFO (LAST IN FIRST OUT ) :

terakhir masuk, pertama keluar

Atau

Data masuk terakhir akan diambil pertama kali.

Stack I

Satu Stack dalam satu array. (array hanya digunakan oleh satu stack) Dasar Stack berada

pada sisi index terkecil.

Ilustrasi

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n S[ ]

25

12

17

10

Dasar Top

0

4

10

Dasar Top X

a. Stack menggunakan array S[ ] dengan 10 elemen ( n=10)

Isi Stack ada 4 Elemen.

S[1] yang paling bawah dan

S[4] yang paling atas

Ada dua index ( baca Pointer ) yang digunakan yaitu dasar dan Top

Dasar : Untuk menunjuk dasar atau alas dari stack, isinya dalam hal ini selalu 0

Top : untuk menunjuk nomor elemen array yang menampung isi stack yang paling

atas. Dalam ilustrasi diatas isinya adalah 4

Page 48: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

b. Beberapa Kondisi Stack.

Ditentukan oleh posisi Pointer Top

1. Stack kosong tak ada Isinya (awal)

0 1 2 3 4 5 n S[ ]

….

….

Dasar Top

STACK dalam kondisi :

Kosong Top = 0

Bisa Diisi Top<n

2. Stack penuh tak bisa diisi

0 1 2 3 4 5 6 7 8 S[ ]

X

X

X

X

X

X

X

X

Dasar Top STACK dalam kondisi :

Penuh Top = n

Ada isinya Top>0

3. Stack bisa diisi

0 1 2 3 4 5 n S[ ]

X

X

X

X

….

….

….

….

Dasar Top

STACK dalam kondisi :

Bisa diisi Top < n

Ada isinya Top > 0

Page 49: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

KONDISI STACK CIRI 1 KOSONG, tak ada isinya Top = 0 2 PENUH, tak bisa di isi Top = n 3 BISA DI ISI, (kebalikan penuh) Top < n 4 ADA ISINYA (kebalikan kosong) Top > 0

c. Proses

a. AWAL ( Inisialisasi)

b. PUSH ( Simpan, insert ,Tulis )

c. POP (Ambil, Delete, Baca )

Algoritma Proses Awal Stack (Bhs. C++)

Dimana semua pointer Dasar dan Top dimulai dari 0

void Awal(void)

{

dasar = 0;

Top = 0;

}

Algoritma dasar proses Push (simpan)

- Naikkan Top dengan 1

- Isikan data kedalam elemen yang ditunjuk Top

void Push(void)

{

Top = Top + 1;

S[Top] = X;

}

Algoritma Lengkap proses Push (simpan)

- Periksa dahulu apakah Top<n

- Naikkan Top dengan 1

- Isikan data kedalam elemen yang ditunjuk Top

- Jika Sudah penuh cetak “Stack Penuh Boy”

Page 50: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

void Push(void)

{

if ( Top<n )

{

Top = Top + 1;

S[Top] = X;

}

else

cout<<“Stack Penuh Boy”;

}

Algoritma dasar proses Pop (ambil)

- Copy data dari elemen yang ditunjuk Top kedalam suatu Variabel

- Turunkan Top

void Pop(void)

{

X = S[Top];

Top = Top –1 ;

}

Algoritma Lengkap proses Pop (Ambil)

- Periksa dahulu apakah Top………

- …………………………………………

- ………………………………………..

-

void Push(void)

{ if (…………)

{

……………

……………

}

else

………………

}

Page 51: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Stack II

Dua Stack dalam satu array.

Satu array digunakan oleh dua stack

Dimana Dasar Stack1 berada pada sisi index terkecil dan Dasar Stack2 berada Pada sisi

index terbesar .

Ilustrasi

n = 12

0 1 2 3 4 5 6 7 8 9 10 11 12 13 S[ ]

a

a

a

a

b

B

b

b

Dasar1 Top1 Top2 Dasar 2

0

4

13

9

Dasar1 Top1 Dasar2 Top2

Dasar1 selalu = 0

Dasar2 selalu = n+1

Untuk Ilustrasi diatas Dasar2 selalu = 13

a. Beberapa Kondisi Stack.

1. Stack kosong tak ada Isinya (awal)

n 0 1 2 3 4 5 6 7 8 9 10 11

S[ ]

Dasar1 Top1 Dasar2 Top2

Kondisi Awal :

- Stack 1 Kosong dan bisa di isi

- Stack 2 Kosong dan bisa di isi

Page 52: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Cirinya :

Dasar1 =0 , Top1=0

Dasar2 = n + 1 , Top2 = n + 1

2. Stack1 dan Stack2 ada Isinya

0 1 2 3 4 5 6 7 8 9 10 11

S[ ]

a a a a b b b

Dasar1 Top1 Top2 Dasar 2

Stack1 ada isinya dan bisa di isi

Stack2 ada isinya dan bisa di isi

Cirinya :

Dasar1 = 0 , Dasar2= n + 1

Masih bisa diisi Top2 – Top1 >1

3. Stack Penuh

0 1 2 3 4 5 6 7 8 9 10 11

S[ ] a a a a a a b b b b b

Dasar1 Top1 Top2 Dasar 2

Stack1 dan Stack2 Tak bisa di isi

Cirinya :

Top2 – Top1 = 1

4 Stack Penuh

n 0 1 2 3 4 5 6 7 8 9 10 11

S[ ]

a a a a a a a a a a a

Dasar1 Top1 Top2 Dasar 2

Page 53: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Stack1 ada isinya

Stack2 tak ada isinya

Cirinya :

Top1 = n

Dasar2= n + 1 , Top2 = n + 1

KONDISI STACK CIRI 1 STACK1 KOSONG

STACK2 KOSNG Top1= 0 Top2 = n +1

2 STACK1 DAN STACK 2 PENUH Top2 – Top1 =1 3 STACK1 DAN STACK2 BISA DIISI Top2 – Top1 > 1 4 STACK1 ADA ISINYA

STACK2 ADA ISINYA Top1 > 0 Top2 < n + 1

b. Proses

- Awal (Inisialisasi)

- Push1

- Pop1

- Push2

- Pop2

Algoritma Proses Awal Stack( Bhs. C )

void Awal(void)

{

Dasar1 = 0;

Top1 = 0;

Dasar2 = n + 1;

Top2 = n +1

}

Algoritma dasar proses Push1 (simpan)

- Naikkan Top dengan 1

- Isikan data kedalam elemen yang ditunjuk Top

void Push1(void)

{ Top1 = Top1 + 1;

S[Top1] = X;

}

Page 54: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Algoritma Lengkap proses Push1 (simpan)

- Periksa dahulu apakah Top2-Top1>1

- Naikkan Top dengan 1

- Isikan data kedalam elemen yang ditunjuk Top

- Jika Sudah penuh cetak “Stack Penuh Boy”

void Push1(void)

{ if ( Top2-Top1>1 )

{

Top1 = Top1 + 1;

S[Top1] = X;

}

else

printf(“Stack Penuh Boy”)

}

Algoritma dasar proses Pop1(ambil)

- Copy data dari elemen yang ditunjuk Top1 kedalam suatu Variabel

- Turunkan Top1

void Pop1(void)

{

X = S[Top1];

Top1 = Top1 –1 ;

}

Algoritma Lengkap proses Pop1 (Ambil)

- Periksa dahulu apakah Top………

- …………………………………………

- ………………………………………..

void Push1(void)

{ if (…………)

{

……………

……………

}

else

Page 55: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

………………

}

Buat Procedure untuk Push2 dan Pop2

Stack III

Dua Stack dalam satu array.

Satu array digunakan oleh dua stack

Dimana Dasar kedua Stack berada ditengah .

Ilustrasi

n = 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 S[ ]

a

a

a

a

B

b

b

b

Top1 Dasar2 Dasar 1 Top2

7

3

6

10

Dasar1 Top1 Dasar2 Top2

Dasar1 selalu = div(n,2) +1

Dasar2 selalu = div(n,2)

Contoh fungsi div :

div(15,3) -- hasilnya 5

div(16,3) -- hasilnya 5

div(17,3) -- hasilnya 5

Page 56: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

a. Beberapa kondisi Stack

1. Kondisi Awal

n = 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13

S[ ]

Top2 Dasar2 Dasar1 Top1

Ciri :

Dasar1 = div(n,2) + 1

Top1 = div(n,2) + 1

Dasar2 = div(n,2)

Top2 = div(n,2)

Stack1 masih bisa di isi Top1>1

Stack2 masih bis diisi Top2 < n

2. Stack ada isinya

n = 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 S[ ]

a

a

a

a

b

b

b

b

Top1 Dasar2 Dasar 1 Top2

Cirinya

Stack1 masih bisa di isi Top1>1

Stack2 masih bis diisi Top2 < n

Page 57: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 13 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

3. Stack penuh

n = 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 S[ ]

a

a

a

a

a

a

b

b

b

b

b

b

b

Top1 Dasar2 Dasar 1 Top2

Stack1 dan Stack2 penuh

Cirinya

Top1 = 1

Top2 = n

KONDISI STACK CIRI 1 STACK1 KOSONG

STACK2 KOSNG Top1= div(n,2) +1 Top2= div(n,2)

2 STACK1 PENUH STACK 2 PENUH

Top1 = 1 Top2 = n

3 STACK1 BISA DIISI STACK2 BISA DIISI

Top1 > 1 Top2 < n

4 STACK1 ADA ISINYA STACK2 ADA ISINYA

Top1< div(n,2) + 1 Top2 > div(n,2)

b. Proses

- Awal (Inisialisasi)

- Push1

- Pop1

- Push2

- Pop2

Buat Procedure dalam Bhs C++

- Awal (Inisialisasi)

- Push1

- Pop1

- Push2

- Pop2

Page 58: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 14 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Praktikum

Anda diminta untuk membuat suatu program animasi stack dengan 4 buah pilihan : push,

pop, cetak stack , quit

Jika dipilih push maka program akan meminta user untuk menginput sebuah character yang

akan dimasukkan kesebuah wadah.

Jika dipilih pop maka character teratas akan dikeluarkan dari wadah.

Jika dipilih cetak stack maka komputer akan menampilkan character yang ada pada wadah.

Jika dipilih quit maka program keluar.

LAYOUT

ANIMASI STACK

1. PUSH

2. POP

3. CETAK STACK

4. QUIT

PILIH 1 – 4 : 1

Masukkan sebuah huruf : B

M

E

R

C

U

Page 59: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 15 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 60: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 5 QUEUE (ANTRIAN)

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

05 87031  Tim Dosen 

   

 

 

Abstract  Kompetensi    

Membahas tentang konsep dari queue (antrian) dan penerapannya

 

Mampu memahami konsep dasar dari queue (antrian) dan penerapannya

 

 

   

Page 61: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

QUEUE (ANTRIAN)

Bentuk Antrian

Ada 3 Bentuk Queue yang akan dibahas :

1. Linier Queue

2. Circuler Queue

3. Double Ended Queue

Mengunakan array satu dimensi

Antrian Lurus (Linier Queue)

Prinsip :

FIFO ( FIRST IN FIRST OUT )

FCFS ( FIRST COME FIRST SERVE )

Yang lebih awal masuk akan dilayani terlebih dahulu

ILUSTRASI

misal n = 10

n 0 1 2 3 4 5 6 7 8 9 10 Q[ ]

X

X

X

F R

Menggunakan Pointer F dan R

F ( Front ) untuk awal antrian

R ( Rear ) untuk akhir antrian

Untuk pengambilan data (keluar data) menggunakan Pointer F

Untuk pemasukan data menggunakan pointer R

Syarat F <= R

Page 62: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Dari ilustrasi diatas :

R = 5, artinya pernah masuk 5 pengantri yang menempati 5 elemen dengan urutan

masuk mulai Q[1], Q[2],…….. Jadi yang terkahir masuk sekarang

berada di Q[5]

F = 2, artinya sudah keluar(sudah dilayani) sebanyak 2 pengantri dengan urutan

keluar atau dilayani mulai dari Q[1], Q[2] jadi yang terakhir keluar adalah

yang berada di Q[2]

a. Kondisi Antrian

1. Kondisi Awal (belum ada yang ngantri)

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

F = R = 0 Kondisi awal F = R antrian Kosong

F R R< n antrian bisa di isi

2. Masuk 4 Pengantri/Belum ada yang keluar

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

X X X X

F = 0 Belum ada yang keluar F < R antrian ada isinya

F R R< n antrian bisa di isi

3 Misal Keluar/dilayani 3 pengantri dan belum ada

yang masuk

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

X

F = 3 Sudak keluar 3 F < R antrian ada isinya

F R R< n antrian bisa di isi

Page 63: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

4. Misal masuk lagi 2 Pengantri

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

X X X

F R

F<R antrian ada isinya R< n antrian bisa di isi

5. Misal sesudah itu keluar 3 (semua) pengantri

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

F = R antrian KOSONG F R

R < n antrian bisa di isi

6. Misal masuk lagi 4 Pengantri

misal n = 10 0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

X X X X

F < R antrian ADA ISINYA

R = n antrian Penuh F R

7. Misal Keluar/dilayani 4 (Semua ) Pengantri

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

F = R antrian Kosong

R = n antrian Penuh F R

F = R = n Antrian kosong tidak ada isinya

Page 64: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Dapat juga disebut penuh karena tak bisa di isi

Untuk keadaan ini perlu dilakukan RESET yaitu :

Mengembalikan pointer keposisi awal F=0 dan R=0

8. Kondisi Penuh sesungguhnya

misal n = 10

0 1 2 3 4 5 6 7 8 9 10 n Q[ ]

X X X X X X X X X X

F R

F = 0 Belum ada yang dilayani

R = n antrian Penuh

KONDISI ANTRIAN CIRI1 KOSONG

F = R dimana saja

2 PENUH

R = n

3 BISA DI ISI

R < n

4 ADA ISINYA

F < n

5 PERLU DI RESET

F = R = n

b. Proses yang dapat dilakukan

a. AWAL (Inisialisasi)

b. INSERT ( Sisip, Masuk, Simpan, ngantri)

c. DELETE (Hapus, Keluar, Ambil, dilayani)

d. RESET ( Kembali Keadaan Awal)

Untuk Proses INSERT menggunakan Pointer R ( Rear )

Untuk Proses DELETE menggunakan Pointer F ( Front )

Page 65: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

ALGORITMA DASAR PROSES AWAL (INISIALISASI)

Dimana Pointer F dan R bernilai 0

void AWAL(void)

{

F = 0;

R = 0;

}

ALGORITMA DASAR PROSES INSERT (MASUK)

- Pointer R maju 1 langkah

- Kemudian Isikan data kedalam elemen yang ditunjuk oleh R

void INSERT(void)

{

R = R +1 ;

Q[R]=X;

}

ALGORITMA DASAR PROSES DELETE (HAPUS)

- Pointer F maju 1 langkah

- Kemudian Copy data dari Elemen yang ditunjuk oleh F ke suatu Variabel.

void DELETE(void)

{

F = F + 1 ;

X =Q[F];

}

A. BUAT PROC. LENGKAP UNTUK PROC. INSERT DAN DELETE

B. BUAT PROC. INSERT DAN DELETE YANG MENGGUNAKAN PROC. RESET.

Page 66: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

CIRCULAR QUEUE ( Antrian Melingkar )

ILUSTRASI

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

X

X

X

X

F R

F = Front (Depan)

R = Rear (Belakang)

Arah antrian tetap sama dengan antrian biasa, hanya saja setelah sampai ke elemen

ke-n akan kembali ke elemen 1 tanpa harus di RESET.

Karena melingkar maka F dan R dapat saling menyusul :

F TIDAK SELALU <= R

a. Proses yang dapat dilakukan :

a. AWAL (Inisialisasi)

b. INSERT (Masuk, Simpan, Tulis)

c. DELETE (Hapus, Keluar, ambil, Baca)

b. Beberapa Kondisi Antrian

1. Keadaan AWAL

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

Flag = 0

F R

Page 67: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

KONDISI ARTINYA1 F = R dan Flag = 0 Kosong, Bisa di isi2 Atau cukup Flag = 0 Kosong Bisa di isi

Flag 0 ---- artinya tidak ada data

Flag 1 ---- artinya ada datanya

2. Masuk 1 Pengantri

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

X

Flag = 1

R F

KONDISI ARTINYA1 F != R Ada isinya2 Flag = 1 Ada isinya3 F != R Bisa di isi

Catatan : != (Tidak sama dengan)

3. Masuk Lagi 3 Pengantri

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

X X X X

Flag = 1 R F

KONDISI ARTINYA1 F != R Ada isinya2 Flag = 1 Ada isinya3 F != R Bisa di isi

Page 68: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

4. Keluar 1 Pengantri

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

X X X

Flag = 1 F R

KONDISI ARTINYA1 F != R Ada isinya2 Flag = 1 Ada isinya3 F != R Bisa di isi

5. Keluar 3 ( Semua ) Pengantri

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

Flag = 0

F R

KONDISI ARTINYA1 F = R and Flag = 0 Kosong2 Flag = 0 Kosong3 Flag = 0 Bisa di isi

Jika yang didelete elemen yang ditunjuk oleh R maka Flag langsung dibuat = 0;

6. Kemudian masuk 8 Pengantri

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

X X X X X X X X

Flag = 1 R F

Terlihat R berada disebeleh kiri F

Page 69: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

KONDISI ARTINYA1 F != R Ada isinya2 Flag = 1 Ada isinya3 F != R Bisa di isi

7. Masuk Lagi 2 Pengantri

n 1 2 3 4 5 6 7 8 9 10

Q[ ]

X X X X X X X X X X

Flag = 1 R F

KONDISI ARTINYA1 F = R DAN Flag = 1 Penuh, Ada isinya2 Flag = 1 Ada isinya

KONDISI ANTRIAN CIRI1 KOSONG

F = R dan Flag = 0 Atau cukup dengan Flag = 0

2 PENUH

F = R dan Flag = 1

3 BISA DI ISI

F != R atau Flag = 0

4 ADA ISINYA

F!=R atau Flag = 1 Atau cukup Flag = 1

ALGORITMA PROSES AWAL

Pointer F dan R berada di n dan Flag=0 (tak ada isinya)

void AWAL(void)

{

F = n;

R = n;

Flag = 0;

}

Untuk Proses INSERT menggunakan Pointer R ( Rear )

Untuk Proses DELETE menggunakan Pointer F ( Front )

Page 70: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Algoritma Dasar Proses Insert

- R maju 1 Langkah

- Kemudian Isikan data kedalam elemen yang ditunjuk oleh R

- Isi Flag dengan 1

void INSERT(void)

{

R = fmod(R,n) + 1;

Q[R] = X;

Flag =1

}

R = fmod(R,n) + 1, maksudnya : R maju satu langkah, dengan ketentuan jika R

berada pada posisi di n maka setelah maju satu langkah akan menjadi

R = 1

Fungsi fmod( ) dalam bhs C. adalah untuk mencari nilai sisa dari pembagian.

Contoh :

fmod(10,3) ----- hasilnya 1

fmod(3,10) ----- hasilnya 3

fmod(10,10) ---- hasilnya 0

fmod(2,10) ----- hasilnya 2

Algoritma Dasar Proses Delete

- F maju 1 Langkah

- Kemudian Copy data dari Elemen yang ditunjuk oleh F ke suatu Variabel.

- Isi Flag dengan 0

void DELETE(void)

{

F = fmod(F,n) + 1;

X = Q[F];

If F=R

{ Flag =0; }

}

BUAT PROC. LENGKAP UNTUK PROC. INSERT DAN DELETE

Page 71: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

DOUBLE ENDED QUEUE ( DEQUE ) Antrian dengan ujung ganda

ILUSTRASI

n Insert Kiri 1 2 3 4 5 6 7 8 9 10 insert

Kanan D[ ]

10

15

23

Delete Kiri Delete Kanan

L R

- Pengantri dapat masuk dari pintu kanan atau kiri

- Yang masuk dari pintu kiri, dapat keluar dari pintu kiri atau keluar dari pintu kanan

tergantung kesempatan yang ada.

- Yang masuk dari pintu kanan dapat keluar dari pintu kanan atau keluar dari pintu

kiri tergantung dari kesempatan yang ada.

Pointer yang digunakan:

L = LEFT (Kiri) digunakan untuk insert dan delete kiri

R = Right(kanan) digunakan untuk insert dan delete kanan

PROSES YANG DAPAT DILAKUKAN

- Insert Kiri : Masuk dari pintu kiri

- Insert Kanan : Masuk dari pintu kanan

- Delete kiri : Keluar dari pintu kiri

- Delete kanan : Keluar dari pintu kanan

Syarat : L tidak boleh mendahului R

L <= R

Prinsip : Bukan FIFO bukan juga LIFO, tetapi keluar dan masuk dari kedua

ujungnya sesuai dengan kesempatan yang ada.

Page 72: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 13 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

a. Beberapa Kondisi Antrian

1. Keadaan AWAL (Inisial)

0 1 2 3 4 5 6 7 n

D[ ]

1 2 3 ……………………………..

L R Insert Kanan

L=R=0 Pada Kondisi ini hanya bisa insert kanan

2. Insert Kanan Sebanyak 3 elemen

0 1 2 3 4 5 6 7 n

D[ ]

X

X

X

L R Insert Kanan

Delete kiri delete kanan

Pada Kondisi ini :

L = 0 (dianggap penuh kiri)

R = 3 ,

- tidak bisa insert kiri,

- hanya bisa Delete kiri, insert kanan dan delete kanan

3. Delete Kiri 2 elemen

0 1 2 3 4 5 6 7 n

D[ ] 

X

L R Insert Kiri Insert kanan

Page 73: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 14 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Pada Kondisi ini :

L = 2

R = 3 :

- Bisa insert kiri dan insert kanan

- Bisa delete kiri dan delete kanan

4. Insert Kanan sebanyak n

0 1 2 3 4 5 6 7 n

D[ ]

X

X

X

X

X

X

X

X

L R

Pada Kondisi ini :

L = 2

R = n (Penuh Kanan) - tak bisa insert kanan

5. Insert Kiri sebanyak 2 elemen

0 1 2 3 4 5 6 7 n

D[ ]

X

X

X

X

X

X

X

X

X

X

L R

Pada Kondisi ini :

L = 0 (Penuh kiri)

R = n (Penuh Kanan) - tak bisa insert kiri dan kanan

6. Delete kanan sampai R = 4

0 1 2 3 4 5 6 7 n

D[ ]

X

X

X

X

L R

Pada Kondisi ini :

Page 74: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 15 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

L = 0 (Penuh kiri)

R = 4 (Penuh Kanan) - tak bisa insert kiri

7. Delete kiri 4 Elemen

0 1 2 3 4 5 6 7 n

D[ ]

L R

Pada Kondisi ini :

L = 4, R = 4

Pada posisi mana saja jika L = R maka antrian Kosong

KONDISI ANTRIAN CIRI1 AWAL L = R = 0

2 KOSONG

L = R dimana saja

3 PENUH KIRI PENUH KANAN PENUH SEBENARNYA

L = 0 R = n L = 0 dan R = n

4 ADA ISINYA

L <> R atau L < R

ALGORITMA PROSES AWAL (INISILISASI)

Pointer L dan R berada di 0

void AWAL(void)

{

L = 0;

R = 0;

}

ALGORITMA DASAR PROSES INSERT KANAN(MASUK KANAN)

- Pointer R maju 1 langkah

- Kemudian Isikan data kedalam elemen yang ditunjuk oleh R

Page 75: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 16 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

void INSERT_KANAN(void)

{

R = R +1 ;

D[R]=X;

}

ALGORITMA DASAR PROSES DELETE KANAN(HAPUS KANAN)

- Copy data dari Elemen yang ditunjuk oleh R ke suatu Variabel.

- Mundur R sebanyak 1

void DELETE_KANAN(void)

{

X = D[R];

R = R - 1 ;

}

1. Buat algoritma dasar Insert kiri dan delete kiri

2. Buat Proc. Lengkap Insert Kiri, Delete Kiri, Insert Kanan, Delete Kanan

Page 76: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 17 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Praktikum

Soal 1

Anda diminta untuk membuat suatu program animasi ANTRIAN LURUS dengan 4 buah

pilihan : MASUK, KELUAR, LIHAT ANTRIAN , QUIT.

Jika dipilih MASUK maka program akan meminta user untuk menginput sebuah character

yang akan dimasukkan kesebuah wadah.

Jika dipilih KELUAR maka character pertama masuk akan dikeluarkan dari wadah.

Jika dipilih LIHAT ANTRIAN maka komputer akan menampilkan character antrian yang ada

pada wadah.

Jika dipilih QUIT maka program keluar.

LAYOUT

ANIMASI ANTRIAN

1. MASUK

2. KELUAR

3. LIHAT ANTRIAN

4. QUIT

PILIH 1 – 4 : 1

Masukkan sebuah huruf : M

M

E

R

C

U

Page 77: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 18 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Soal 2

Anda diminta untuk membuat suatu program animasi ANTRIAN CIRCULAR dengan 4 buah

pilihan : MASUK, KELUAR, LIHAT ANTRIAN , QUIT.

Jika dipilih MASUK maka program akan meminta user untuk menginput sebuah character

yang akan dimasukkan.

Jika dipilih KELUAR maka character yang ditunjuk oleh pointer F akan dikeluarkan.

Jika dipilih LIHAT ANTRIAN maka komputer akan menampilkan character antrian yang ada.

Jika dipilih QUIT maka program keluar.

LAYOUT

ANIMASI ANTRIAN CIRCULAR

1. MASUK

2. KELUAR

3. LIHAT ANTRIAN

4. QUIT

PILIH 1 – 4 : 1

Masukkan sebuah huruf : I

0 1 2 3 4 5 6

M E R C U

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 78: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 6 SORTING (PENGURUTAN)

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

06 87031  Tim Dosen 

   

 

 

Abstract  Kompetensi    

Membahas tentang konsep dari sorting (pengurutan) dan penerapannya

 

Mampu memahami konsep dasar dari sorting (pengurutan) dan penerapannya

 

   

Page 79: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

SORT

Pengertian Sort

• 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

Para pengguna Komputer memang sudah banyak dimanjakan oleh fasilitas yang

diberikan oleh bahasa pemrograman atau software application yang digunakan, terutama

bahasa pemrograman yang telah dirancang untuk kebutuhan tertentu(paket program). Di

bahasa pemrograman dbase,foxpro untuk melakukan pengurutan data tinggal menulis

perintah SORT atau INDEX saja, maka urusan pengurutan data sudah selesai. Kita tidak

tahu bagaimana komputer bekerja(menggunakan teknik bagaimana) sortir terhadap data

yang dilakukannya.

Namun untuk bahasa pemrograman yang sifatnya “generik”, untuk mensortir data,

kita perlu membuat programnya sendiri dan sudah barang tentu harus memikirkan teknik

seperti apa untuk melakukan sortir tersebut.

Pada garis besarnya ada tiga teknik sortir yaitu :

a. Insertion Sort (Sort penyisipan)

b. Selection Sort (Sortir pemilihan)

c. Exchange Sort (Sortir Penukaran)

Deklarasi Array

• Deklarasikan secara global:

int data[100];

int n; //untuk jumlah data

Page 80: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

• Prosedur Tukar 2 Buah Data:

void tukar(int a,int b)

{

int tmp;

tmp = data[a];

data[a] = data[b];

data[b] = tmp;

}

a. Insertion Sort

Teknik ini adalah membandingkan elemen ke-n (n dimulai dari 2 hingga elemen terkahir)

dengan elemen-elemen sebelumnya. Bila elemen elemen yang dibandingkan bernilai lebih

kecil, maka tukar posisinya.

Contoh pengurutan Ascending

i 1 2 3 4

Data[ ] 8 3 7 4

Langkah pengurutan

1. Data ke 2 dibandingkan dengan data ke 1

i=1 Data[2] = 3 3 8 7 4

2. Data ke 3 dibandingkan dengan data ke 2 dan ke 1

i=2 Data[3]= 7 3 7 8 4

3. Data ke 4 dbandingkan dengan data ke 3 ,ke 2 dan ke 1

i=3 Data[4]= 4 3 4 7 8

Hasil akhir 3 4 7 8

Page 81: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

b. Selection Sort

Teknik ini adalah mencari nilai elemen terkecil kemudian letakkan dan tukar dengan posisi

ke-n

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

• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks

pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Algoritma :

1. Repeat Langkah 1. s/d 3. sebanyak n-1

2. Cari Index dari harga terkecil/terbesar

3. Tukarkan nilai index pertama dengan index terkecil/terbesar yang ada dalam elemen

loop

Page 82: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

J 1 2 3 4 5 6 7 8 9

1

42

11 11 11 11 11 11 11 11 11

2

23 23 23 23 23 23 23 23 23 23

3

74 74

74 36 36 36 36 36 36 36

4

11 42

42 42 42 42 42 42 42 42

5

65 65 65 65 65 58 58 58 58 58

6

58 58 58 58 58 65 65 65 65 65

7

94 94 94 94 94 94 94 74 74 74

8

36 36 36 74 74 74 74 94 87 87

9

99 99 99 99 99 99 99 99 99 94

10

87

87 87 87 87 87 87 87 94 99

Keterangan Kotak

Terjadi perpindahan data

Page 83: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

c. Exchange Sort (Buble 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.

Algoritma :

1. Repeat Langkah 2. s/d 4 sebanyak n-1 kali

2. Repeat Langkah 3. untuk elemen yang belum sort

3. Jika Current Elemen > Next Elemen, tukar

4. Jika tidak ada pertukaran, Return

J kj 1 2 3 4 5 6 1

42 23 23 11 11 11 11

2

23 42 11 23 23 23 23

3

74 11 42 42 42 36 36

4

11 65 58 58 36 42 42

5

65 58 65 36 58 58 58

Page 84: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

6

58 74 36 65 65 65 65

7

94 36 74 74 74 74 74

8

36 94 87 87 87 87 87

9

99 87 94 94 94 94 94

10

87 99 99 99 99 99 99

Exc=6 Exc=4 Exc=2 Exc=1 Exc=1 Exc=0

Kondisi terjelek adalah

- Jika data terkahir adalah yang terkecil untuk sort ascending, Jika data terakhir adalah

yang terbesar untuk sort descending

Page 85: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

SOAL

1. Buatlah pengurutan menggunakan metode Bubble Sort Secara Ascending dari data

dibawah ini : 5 2 21 4 9 16 13 3

2. Buatlah pengurutan menggunakan metode Selection Sort Secara Descending dari

data dibawah ini : 5 2 21 4 9 16 13 3

3. Buatlah pengurutan menggunakan metode Insertion Sort Secara Descending dari

data dibawah ini : 5 2 21 4 9 16 13 3

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 86: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 7 PENERAPAN APLIKASI LINKED LIST, STACK DAN QUEUE

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

07 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang penerapan aplikasi linked list, stack dan queue

 

Mampu memahami penerapan aplikasi linked list, stack dan queue  

   

Page 87: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Aplikasi Linked List untuk Stack & Queue

STACK I

Stack dengan menggunakan Simpul Head

Simpul Head tidak berisi data merupakan HEAD sebagai dummy

TOP DASAR INFO LINK INFO LINK INFO LINK INFO LINK INFO LINK

25

12

17

10

0

Push (4) (3) (2) (1) Pop (1) (2) (3) (4)

Fungsi untuk membuat simpul HEAD

Void HEAD(void)

{

P=(struct SIMPUL*) malloc(sizeof(struct SIMPUL*));

P->INFO=0;

DASAR = P;

TOP=P;

TOP->LINK=NULL;

}

INFO diisi nilai dummy misal=0

Soal : Buat Fungsi PUSH dan POP

Page 88: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Contoh Program STACK I

#include<iostream.h>

#include<conio.h>

void PUSH(void);

void POP(void);

void CETAKLAYAR(void);

int PIL,TOP,DASAR;

char WADAH[7];

void main( )

{

TOP=0;

DASAR=0;

do

{

clrscr();

cout<<" MENU UTAMA"<<endl;

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

cout<<"1. PUSH"<<endl;

cout<<"2. POP"<<endl;

cout<<"3. CETAK STACK"<<endl;

cout<<"4. QUIT"<<endl<<endl;

cout<<"PILIHAN : "; cin>>PIL;

switch (PIL)

{

case 1 :

PUSH( );

break;

case 2:

POP( ); break;

case 3:

CETAKLAYAR();

Page 89: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

break;

default:

cout<<"TERIMA KASIH"; break;

}

getch();

}

while (PIL<4);

}

void PUSH(void)

{ char HURUF;

clrscr();

cout<<endl<<"MASUKKAN 1 HURUF : "; cin>>HURUF;

TOP=TOP+1;

WADAH[TOP]=HURUF;

}

void CETAKLAYAR(void)

{ int i;

clrscr();

i=7;

for (i=7; i>0; i--)

{

cout<<i<<" "<<WADAH[i]<<endl;

}

}

Program diatas belum sempurna sebagian jawaban dari pertanyaan yang diatas.

Ditanya :

1. Lengapilah Procedure untuk PUSH

2. Buat Procedure lengakap untuk POP

Page 90: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

STACK II

Stack tanpa Simpul Head

TOP INFO LINK INFO LINK INFO LINK INFO LINK

25

12

17

10

Push (4) (3) (2) (1) Pop (1) (2) (3) (4)

Bila Isi Stack tinggal 1 kemudian di delete (POP) maka TOP dibuat = NULL

Soal : Buat Fungsi PUSH dan POP

Contoh Program STACK II

#include <iostream.h>

#include <stdlib.h>// untuk penggunaan system("cls");

#include <conio.h>// untuk getch();

int n=10,dasar1=0,dasar2=n+1,top1=0,top2=n+1,pil,j;

char wadah[10];

char huruf;

void push1(void)

{

system("cls");

if(top2-top1>1) // if(top2-top1>1)

{

cout<<"input 1 huruf : ";

cin>>huruf;

top1=top1+1;

wadah[top1]=huruf;

}

else

{

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

Page 91: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

cout<<"STACK PENUH !!!"<<endl;

cout<<"KURANGI STACK!!"<<endl;

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

}

}

void pop1(void)

{

system("cls");

if(top1>0)

{

huruf=wadah[top1];

cout<<"Huruf yang di hapus : "<<huruf<<endl;

top1=top1-1;

}

else

{

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

cout<<"STACK KOSONG !!!"<<endl;

cout<<"TAMBAH STACK !!"<<endl;

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

}

}

void push2(void)

{

system("cls");

if(top2-top1>1)

{

cout<<"input 1 huruf : ";

cin>>huruf;

top2=top2-1;

wadah[top2]=huruf;

}

else

{

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

cout<<"STACK PENUH !!!"<<endl;

cout<<"KURANGI STACK!!"<<endl;

Page 92: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

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

}

}

void pop2(void)

{

system("cls");

if(top2<n+1)

{

huruf=wadah[top2];

cout<<"Huruf yang di hapus : "<<huruf<<endl;

top2=top2+1;

}

else

{

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

cout<<"STACK KOSONG !!!"<<endl;

cout<<"TAMBAH STACK !!"<<endl;

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

}

}

void c_stack(void)// menampilkan array terakhir yang pernah terisi, jadi walaupun sudah

dikurangi akan tetap menampilkan huruf yang pernah mengisinya

{

system("cls");

int i;

cout<<"huruf yang mengisi : ";

for(j=0;j<11;j++)

{

cout<<wadah[j]<<" ";

}

cout<<endl<<endl;

for(i=0+1;i<11;i++)

{

cout<<i<<". "<<wadah[i]<<endl;

}

}

void main()// program

Page 93: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

{

x:// ke menu utama

{

for( ;pil<1000; )

{

system("cls");

cout<<endl<<"MENU UTAMA"<<endl;

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

cout<<"1.PUSH1"<<endl;

cout<<"2.POP1"<<endl;

cout<<"3.PUSH2"<<endl;

cout<<"4.POP2"<<endl;

cout<<"5.CETAK STACK"<<endl;

cout<<"6.QUIT"<<endl;

cout<<"Pilihan (1-6) : ";

cin>>pil;

switch(pil)

{

case 1:

push1(); // memanggil fungsi push

break;

case 2:

pop1(); // memanggil fungsi pop

break;

case 3:

push2();

break;

case 4: // mengakhiri program

pop2();

break;

case 5:

c_stack(); // memanggil fungsi c_stack

break;

case 6:

cout<<endl<<"TERIMA KASIH"<<endl;

goto y;

break;

Page 94: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

default:

cout<<endl<<"ANDA SALAH INPUT"<<endl;

getch();

goto x;// kembali ke menu utama bila salah

break;

}

getch();// untuk mempertahankan output sebelum menekan sebarang

tombol(menunggu input sebarang output)

}

}

y:// untuk mengakhiri program

{

}

}

Contoh Program STACK III

#include <iostream.h>

#include <stdlib.h>// system("cls");

#include <conio.h>// getch();

char wadah[11];

int p,i,j,n=10,d1=(n/2)+1,d2=n/2,t1=(n/2)+1,t2=n/2;

char huruf;

/*struct awal

{

int d1;

int d2;

int t1;

int t2;

};*/

void push1(void);

void pop1(void);

void push2(void);

void pop2(void);

void cetak(void);

void main()

Page 95: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

{

x:

{

for( ;i<1000; )

{

system("cls");

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

cout<<"= MENU UTAMA ANIMASI STACK 3 ="<<endl;

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

cout<<"= Pilihan : 1.Push1 "<<endl;

cout<<"= 2.Pop1 "<<endl;

cout<<"= 3.Push2 "<<endl;

cout<<"= 4.Pop2 "<<endl;

cout<<"= 5.Cetak Stack "<<endl;

cout<<"= 6.Quit "<<endl;

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

cout<<"Pilihan anda : ";

cin>>p;

switch(p)

{

case 1:

push1();

break;

case 2:

pop1();

break;

case 3:

push2();

break;

case 4:

pop2();

break;

case 5:

cetak();

break;

case 6:

cout<<"TERIMA KASIH"<<endl;

Page 96: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

goto y;

default:

cout<<"ANDA SALAH INPUT !!"<<endl;

cout<<"ULANGI Masukan angka (1-6)"<<endl;

getch();

goto x;

}

getch();

}

}

y:

{}

}

void push1(void)

{

system("cls");

if(t1>1)// nb: deklarasikan lebih dulu nilai t1,t2,d1,d2

{

cout<<"masukan 1 huruf : ";

cin>>huruf;

t1=t1-1;

wadah[t1]=huruf;

}

else

{

cout<<"Stack Penuh"<<endl;

cout<<"Kurangi stack"<<endl;

}

}

void pop1(void)

{

system("cls");

if(t1<d1)

{

huruf=wadah[t1];

cout<<"huruf yang di hapus : "<<huruf<<endl;

t1=t1+1;

Page 97: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

}

else

{

cout<<"Stack Kosong"<<endl;

cout<<"Tambah Stack"<<endl;

}

}

void push2(void)

{

system("cls");

if(t2<n)

{

cout<<"Masukan 1 huruf : ";

cin>>huruf;

t2=t2+1;

wadah[t2]=huruf;

}

else

{

cout<<"Stack Penuh"<<endl;

cout<<"Kurangi Stack"<<endl;

}

}

void pop2(void)

{

system("cls");

if(t2>d2)

{

huruf=wadah[t2];

cout<<"huruf yang di hapus : "<<huruf<<endl;

t2=t2-1;

}

else

{

cout<<"Stack Kosong"<<endl;

cout<<"Tambah Stack"<<endl;

}

Page 98: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 13 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

}

void cetak(void)

{

cout<<"huruf yang mengisi : ";

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

{

cout<<wadah[i]<<" ";

}

cout<<endl<<endl;

for(j=1;j<11;j++)

{

cout<<j<<"."<<wadah[j]<<endl;

}

}

QUEUE

Ilustrasi untuk QUEUE

FRONT REAR INFO LINK INFO LINK INFO LINK INFO LINK

25

12

17

10

INSERT (1) (2) (3) (4) DELETE (1) (2) (3) (4) Soal : Buat Fungsi INSERT dan DELETE

Page 99: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 14 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Contoh Program QUEUE

#include <iostream.h>

#include <stdlib.h>

#include <conio.h>

int r=0,f=0,pil,n=10,i,j;

char wadah[11];// ada 11 elemen 0-10 dan yang mengisi antrian 10 elemen 1-10

char huruf;

void masuk(void);

void keluar(void);

void cetak(void);

void main()

{

x:

{

for( ;pil<1000; )

{

system("cls");

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

cout<<"= MENU UTAMA ="<<endl;

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

cout<<"= Pilihan : 1.Input ="<<endl;

cout<<"= 2.Hapus ="<<endl;

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

cout<<"= 4.Quit ="<<endl;

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

cout<<"pilihan Anda : ";

cin>>pil;

switch(pil)

{

case 1:

masuk();

break;

case 2:

keluar();

break;

case 3:

Page 100: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 15 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

cetak();

break;

case 4:

cout<<"Terima Kasih"<<endl;

goto y;

break;

default:

cout<<"Anda SALAH input"<<endl;

cout<<"Masukan nilai 1-6"<<endl;

goto x;

}

getch();

}

}

y:

{}

}

void masuk(void)

{

system("cls");

if(r<n)

{

cout<<"Masukan 1 huruf : ";

cin>>huruf;

r=r+1;

wadah[r]=huruf;

}

else

{

cout<<"Antrian Penuh"<<endl;

/*if((r=n)&&(f=n)) enga boleh disini alasan enga tau

{

f=0;

r=0;

}*/

}

}

Page 101: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 16 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

void keluar(void)

{

system("cls");

if(f<r)

{

f=f+1;

huruf=wadah[f];

wadah[f]=NULL;

cout<<"Huruf yang keluar antrian : "<<huruf<<endl;

}

else

{

cout<<"Antrian Kosong"<<endl<<endl;

cout<<"Antrian di reset"<<endl;

if((r=n)&&(f=n))// reset

{

f=0;

r=0;

}

}

}

void cetak(void)

{

system("cls");

cout<<"huruf yang mengisi antrian : ";

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

{

cout<<wadah[i]<<" ";

}

cout<<endl;

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

{

cout<<j<<"."<<wadah[j]<<endl;

}

}

Page 102: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 17 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Contoh Program Double Linked List

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

struct simpul

{

char info;

struct simpul *r,*l;

};

struct simpul *first,*last,*p,*q,*t;

int pil;

char x,n,i,m;

void awal();

void in_kanan();

void in_kiri();

void in_tengah();

void de_kanan();

void de_kiri();

void de_tengah();

void tampil();

void main()

{

system("cls");

do

{

system("cls");

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

cout<<"DOUBLE LINK LIST"<<endl;

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

cout<<"1.buat simpul awal"<<endl;

cout<<"2.insert kanan"<<endl;

cout<<"3.insert kiri"<<endl;

cout<<"4.insert tengah"<<endl;

cout<<"5.Delete kanan"<<endl;

cout<<"6.Delete kiri"<<endl;

cout<<"7.Delete tengah"<<endl;

Page 103: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 18 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

cout<<"8.tampilkan link"<<endl;

cout<<"9.Exit"<<endl;

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

cout<<"Pilihan (1-9) : ";

cin>>pil;

switch(pil)

{

case 1:

awal();

break;

case 2:

in_kanan();

break;

case 3:

in_kiri();

break;

case 4:

in_tengah();

break;

case 5:

de_kanan();

break;

case 6:

de_kiri();

break;

case 7:

de_tengah();

break;

case 8:

tampil();

break;

case 9:

cout<<"Thank You"<<endl;

getch();

break;

}

}

Page 104: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 19 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

while(pil<9);

}

void awal()

{

system("cls");

if((first==NULL)&&(last==NULL))// pada posisi awal *first & *last =NULL karena data

belum pernah di buat (p=(struc simpul*)malloc(sizeof(struct simpul));

{ // baru di deklarasi sebagai

struct simpul

p=(struct simpul*)malloc(sizeof(struct simpul));

cout<<"Masukan 1 huruf simpul awal : ";

cin>>x;

p->info=x;

p->r=NULL;

p->l=NULL;

first=p;

last=p;

cout<<"Isi simpul first : "<<first->info<<endl;

cout<<"Isi simpul last : "<<last->info<<endl;

}

else

{

cout<<"Simpul awal telah ada"<<endl;

}

getch();

}

void in_kanan()

{

system("cls");

cout<<"Masukan 1 huruf : ";

cin>>x;

p=(struct simpul*)malloc(sizeof(struct simpul));

p->info=x;

last->r=p;

p->l=last;

last=p;

last->r=NULL;

Page 105: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 20 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

getch();

}

void in_kiri()

{

system("cls");

cout<<"Masukan 1 huruf : ";

cin>>x;

p=(struct simpul*)malloc(sizeof(struct simpul));

p->info=x;

first->l=p;

p->r=first;

first=p;

first->l=NULL;

getch();

}

void in_tengah()

{

system("cls");

if((first==NULL)&&(last==NULL))

{

cout<<"Simpul awal belum ada!!!"<<endl;

cout<<"Masukan 2 simpul untuk insert tengah"<<endl;

}

else if(first==last)

{

cout<<"Belum bisa insert tengah"<<endl;

cout<<"baru ada satu simpul"<<endl;

cout<<"Harus ada 2 simpul untuk insert tengah"<<endl;

}

else

{

system("cls");

cout<<"Masukan 1 huruf : ";

cin>>x;

p=(struct simpul*)malloc(sizeof(struct simpul));

p->info=x;

first->r->l=NULL;// l->first di putus tapi tetap nyambung pada first->r

Page 106: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 21 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

first->r->l=p;

p->r=first->r;// line p->r=first->r posisi di samakan

first->r=NULL;// line menuju * setelah first di putus

p->l;first;// p di sambung ke first

first->r=p;// first di sambung ke p

}

getch();

}

void de_kanan()

{

system("cls");

if((last==NULL)&&(first==NULL))

{

cout<<"simpul kosong"<<endl<<endl;

}

else if(first==last)

{

x=first->info;

last=NULL;

first=NULL;

cout<<"Huruf yang di hapus : "<<x<<endl;

}

else

{

last=last->l;

x=last->r->info;

cout<<"Huruf yang di hapus : "<<x<<endl;

free(last->r);

last->r=NULL;

}

getch();

}

void de_kiri()

{

system("cls");

if((first==NULL)&&(last==NULL))

{

Page 107: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 22 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

cout<<"simpul kosong"<<endl<<endl;

}

else if(first==last)

{

x=first->info;

first=NULL;

last=NULL;

cout<<"Huruf yang di hapus"<<endl;

}

else

{

first=first->r;

x=first->l->info;

cout<<"Huruf yang terbuang : "<<x<<endl;

free(first->l);

first->l=NULL;

}

getch();

}

void de_tengah()

{

system("cls");

if((first==NULL)&&(last==NULL))

{

cout<<"Simpul kosong!!!"<<endl;

}

else if(first==last)

{

cout<<"hanya ada satu simpul"<<endl;

cout<<"Tidak bisa delete tengah"<<endl;

cout<<"harus ada tiga simpul"<<endl;

}

else if((first->r==last)&&(last->l==first))

{

cout<<"hanya ada dua simpul"<<endl;

cout<<"Tidak bisa delete tengah"<<endl;

cout<<"harus ada tiga simpul"<<endl;

Page 108: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 23 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

}

else

{

q=first->r->r;

x=first->r->info;

first->r=NULL;

first->r=q;

q->l=first;

cout<<"Huruf yang di hapus : "<<x<<endl;

}

getch();

}

void tampil()

{

system("cls");

cout<<"Isi data dalam link"<<endl;

p=first;

while(p!=NULL)

{

x=p->info;

cout<<" "<<x;

p=p->r;

}

cout<<endl;

getch();

}

Page 109: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 24 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 110: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 8 SORTING LANJUT

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

08 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang penerapan aplikasi sorting merge sort, heap sort dan radix sort

 

Mampu memahami penerapan aplikasi sorting merge sort, heap sort dan radix sort 

   

Page 111: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Sorting Lanjutan

Teknik Sorting Iainnya

1. Merge Sort

Sort ini digunakan untuk jumlah data yang besar, dengan membagi-bagi menjadi sub

bagian-sub bagian mulai dari sedikit elemen hingga keseluruhan elemen tersebut

menjadi data yang sudah urut. Sortir ini digunakan jika kapasitas memori tidak sanggup

untuk menampung seluruh data yang akan disortir.

Contoh 14 elemen berikut akan disortir:

66, 33, 40, 22, 55, 88, 60, 11, 80, 20, 50, 44, 77, 30.

Langkah 1 : data dibagi menjadi sub-sub yang tiap subnya berisi 2 elemen yang

kemudian disortir hasilnya :

33 , 66 22 , 40 55 , 88 11 , 60 20 , 80 44 , 50 30 , 70

Langkah 2 : gabungkan 2 sub bagian sebelumnya menjadi 1 sub bagian kemudian

disortir hasilnya :

22, 33, 40, 66 11, 55, 60, 88 22, 44, 50, 80 30, 70

Langkah 3 : Lakukan seperti langkah 2 hingga seluruh sub bagian menjadi 1 subbagian.

11, 22, 33, 40, 55, 60, 66, 88 20, 30, 44, 50, 77, 80

Hasil Akhir :

11, 20, 22, 30, 33, 40, 44, 50, 55, 60, 66, 77, 80, 88

Contoh Program Merge Sort

1. #include <iostream.h>   2. #include <conio.h>   3. int a[50];   4. void merge(int,int,int);   5. void merge_sort(int low,int high)   6. {   7.  int mid;   8.  if(low<high)   9.  {   

Page 112: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

10.   mid=(low+high)/2;   11.   merge_sort(low,mid);   12.   merge_sort(mid+1,high);   13.   merge(low,mid,high);   14.  }   15. }   16. void merge(int low,int mid,int high)   17. {   18.  int h,i,j,b[50],k;   19.  h=low;   20.  i=low;   21.  j=mid+1;   22.  while((h<=mid)&&(j<=high))   23.  {   24.   if(a[h]<=a[j])   25.   {   26.    b[i]=a[h]; h++;   27.   }   28.   else   29.   {   30.    b[i]=a[j]; j++;   31.   } i++;   32.  }   33.  if(h>mid)   34.  {   35.   for(k=j;k<=high;k++)   36.   {   37.    b[i]=a[k]; i++;   38.   }   39.  }   40.  else   41.  {   42.   for(k=h;k<=mid;k++)   43.   {   44.    b[i]=a[k]; i++;   45.   }   46.  }   47.  for(k=low;k<=high;k++)   48.   a[k]=b[k];   49. }   50. void main()   51. {   52.  int num,i; cout<<"*************************************************************

****** *************"<<endl;   53.  cout<<" MERGE SORT PROGRAM "<<endl;   54.  cout<<"******************************************************************* ****

*********"<<endl;   55.  cout<<endl<<endl;   56.  cout<<"Masukkan Banyak Bilangan: ";cin>>num;   57.    cout<<endl;   58.  cout<<"Sekarang masukkan "<< num <<" Bilangan yang ingin Diurutkan :"<<endl;   59.  for(i=1;i<=num;i++)   60.  {   61.   cout<<"Bilangan ke‐"<<i<<" ";cin>>a[i] ;   62.  }   63.  merge_sort(1,num);   64.  cout<<endl;   65.  cout<<"Hasil akhir pengurutan :"<<endl;   66.  cout<<endl;   67.  for(i=1;i<=num;i++)   68.   cout<<a[i]<<" ";   69.  cout<<endl<<endl<<endl<<endl;   70.    getch();   71. }   

Page 113: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

2. Heap Sort : Aplikasi dari Binary Tree

Heap sort merupakan teknik sortir yang memanfaatkan bentuk pohon binary. Maxheap

adalah penyortiran dari besar ke kecil (Desending). Minheap adalah penyortiran dari kecil ke

besar (ascending). Untuk melakukan penyortian ini maka langkah pertama yang dilakukan

adalah membentuk pohon heap.

Pembentukan pohon heap dilakukan dengan langkah-langkah :

1. Ikuti bentuk complete binary tree ( pohon biner lengkap)

2. Ayah harus memiliki nilai lebih besar atau sama dengan anak-anaknya (untuk

maxheap), ayah harus memiliki nilai lebih kecil atau sama dengan anak-

anaknya (unutk minheap)

Pada contoh ini akan dibuat pohon maxheap dengan elemen-elemen :

44 30 50 22 60 55 77 55

44 44 50

30 33 44

a. elemen 44 b. elemen 30 c. elemen 50

50 60 60

30 44 50 44 50 55

22 22 30 22 30 44

d. elemen 22 e. elemen 60 f. elemen 55

Page 114: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

77 77

50 60 55 60

22 30 44 55 50 30 44 55

22

g. elemen 77 h. elemen 55

Penulisan hasil sortir mengikuti langkah-langkah penghapusan elemen sebagai berikut :

1. Hapus akarnya (Root)

2. Letakkan elemen terakhir di posisi akarnya (root)

3. lakukan tindakan atas elemen tersebut seperti langkah-langkah pembuatan pohon

heap.

4. Lakukan Langkah 1 hingga pohon menjadi kosong (empty tree)

Perhatikan gambar dibawah ini bagaimana setelah elemen 77 (root) dihapus atau dijadikan

elemen awal dari hasil sortir

22

55 60

50 30 44 55

a. penghapusan elemen 77 , maka elemen 22 jadi root

Page 115: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

60

55 22

50 30 44 55

b. elemen 22 mengarah keanak kanan

60

55 55

50 30 44 22

c. elemen 22 mengarah keanak kanan

( fase 1 )

3 gambar diatas pembentukan pohon heap kembali setelah elemen 77 dihilangkan

untuk fase 2 elemen 60 sebagai akar akan dijadikan hasil, sehingga elemen elemen hasil

sortirnya menjadi 77, 66 dan seterusnya. Berikut gambar heap pada akhir fase 2 hingga fase

7 (akhir).

55

55 44

50 30 22

a. pohon heap pada akhir fase 2

Page 116: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

55

50 44

22 30

b. pohon heap pada akhir fase 3

50

30 44

22

c. pohon heap pada akhir fase 4

50

30 22

d. pohon heap pada akhir fase 5

30

22

e. pohon heap pada akhir fase 6

Page 117: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

22

f. pohon heap pada akhir fase 7

sehingga diperoleh urutan :

77 60 55 55 50 44 30 22

Contoh Aplikasi Heap Sort

#include <iostream.h> //mendeklarasikan header untuk fungsi I/O "cout & cin" #include <conio.h> //mendeklarasikan header untuk fungsi penahan layar "getch();"  void main() //inti dari program {   int a[10] = { 34, 15, 23, 9, 41, 26, 39, 11, 7, 28 }; //mendeklarasikan variabel a dengan jumlah data 10    cout<<"Program Heap Sort ..."<<endl;    cout<<"Mengurutkan Bilangan ..."<<endl;    cout<<"Bilangan sebelum diurutkan : "<<endl<<endl;    for(int h = 0; h <= 9; h++) //proses pengulangan untuk menampilkan data‐data di variabel a ke layar    {      cout<<"| "<<a[h]<<" ";    }    cout<<"|"<<endl<<endl;    for(int i = 0; i <= 9; i++)     //ini adalah bagian inti dari proses HEAP SORT.   {                               //inti dari program ini adalah membandingkan nilai pertama & kedua      for(int j = 0; j <= i; j++)  //kemudian mencari nilai mana yang paling besar.       {                            //kemudian ditempatkan di awal. dan seterusnya         if(a[i]>a[j])          {            int t = a[i];             a[i]  = a[j];             a[j]  = t;          } 

Page 118: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

      }    }     cout<<"‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐"<<endl<<endl;    cout<<"Bilangan Setelah diurutkan : "<<endl;    cout<<endl;    cout<<" ‐ Diurutkan dari yang Terkecil => Terbesar : "<<endl<<endl; //mengurutkan data dari yang terkecil ke terbesar    cout<<"   ";    for(int i = 9; i >= 0; i‐‐) //digunakan pengulangan.    {      cout<<"| "<<a[i]<<" ";    }    cout<<"|"<<endl<<endl;     cout<<" ‐ Diurutkan dari yang Terbesar => Terkecil : "<<endl<<endl; //mengurutkan data dari yang terbesar ke terkecil    cout<<"   ";    for(int i = 0; i <=9; i++)    {      cout<<"| "<<a[i]<<" ";    }    cout<<"|"<<endl<<endl;     cout<<"‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐"<<endl<<endl;    cout<<"TERIMA KASIH ..."<<endl<<endl;   getch(); } 

3. Radix Sort

Contoh penyelesaian sortir cara Radix sort adalah ketika kita diminta untuk mensortir

ratusan lembar jawaban ujian berdasarkan namanya. Maka langkah pertama yang kita

lakukan adalah dengan menumpuk lembar jawaban tersebut menjadi tumpukan-tumpukan

yang memiliki huruf depan yang sama dari nama peserta. Kemudian kita perhatikan huruf-

huruf kedua dan seterusnya(kita urutkan perabjad dahulu lalu tumpuk menjadi satu).

Sebenarnya masih banyak teknik-teknik sortir lainnya yang tidak dibahas dalam catatan ini,

dan anda juga dapat memikirkan untuk membuat teknik sendiri sebagai metode anda dalam

sort /search data.

Contoh Program

Page 119: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

1. /*

2. * C++ Program To Implement Radix Sort

3. */

4. #include <iostream>

5. #include <cstdlib>

6. using namespace std;

7. /*

8. * get maximum value in arr[]

9. */

10. int getMax(int arr[], int n)

11. {

12. int max = arr[0];

13. for (int i = 1; i < n; i++)

14. if (arr[i] > max)

15. max = arr[i];

16. return max;

17. }

18. /*

19. * count sort of arr[]

20. */

21. void countSort(int arr[], int n, int exp)

22. {

23. int output[n];

24. int i, count[10] = {0};

25. for (i = 0; i < n; i++)

26. count[(arr[i] / exp) % 10]++;

27. for (i = 1; i < 10; i++)

28. count[i] += count[i - 1];

29. for (i = n - 1; i >= 0; i--)

30. {

31. output[count[(arr[i] / exp) % 10] - 1] = arr[i];

32. count[(arr[i] / exp) % 10]--;

33. }

34. for (i = 0; i < n; i++)

35. arr[i] = output[i];

36. }

37. /*

38. * sorts arr[] of size n using Radix Sort

39. */

40. void radixsort(int arr[], int n)

41. {

42. int m = getMax(arr, n);

Page 120: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

43. for (int exp = 1; m / exp > 0; exp *= 10)

44. countSort(arr, n, exp);

45. }

46.

47. /*

48. * Main

49. */

50. int main()

51. {

52. int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

53. int n = sizeof(arr)/sizeof(arr[0]);

54. radixsort(arr, n);

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

56. cout << arr[i] << " ";

57. return 0;

58. }

Latihan

Buatlah pengurutan dari data dibawah ini

90 145 67 23 189 29 334 92 266 95

1. Insertion Sort

2. Selection Sort

3. Buble Sort

4. Merge Sort

5. Heap Sort

6. Radix Sort

Page 121: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 122: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 9 TREE

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

09 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang penerapan aplikasi TREE beserta jenis-jenisnya

 

Mampu memahami penerapan aplikasi tree beserta jenis-jenisnya 

   

Page 123: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

A

B  C D

E F  G H I J 

K  LM

Tree

Jenis-jenis Tree

Struktur Data Non Linier terdiri dari :

1. Struktur Pohon (Tree Structure)

2. Graph

Definisi Pohon adalah :

Susunan dari satu atau lebih simpul(node) yang terdiri dari satu simpul khusus yang

disebut akar(root) sedang sisanya membentuk subtree dari akar.

Akar dari struktur pohon ini adalah A

Satu simpul akan berisi :

- Informasi ( misal, A , B, dst)

- Cabang-cabang (Link) yang menghubungkan Kesimpul simpul yang lain.

Simpul A sebagai akar mempunyai 3 Link yang membentuk SUBTREE B,C, D.

Jumlah SUBTREE dari satu simpul disebut : DERAJAT (DEGREE).

Derajat Simpul : A = 3

B = 2

C = 1

G = 0

Level  1    2    3    4 

  

Page 124: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Simpul yang mempunyai derajat = 0 disebut :

SIMPUL TERMINAL atau DAUN (LEAF)

Contoh simpul daun gambar diatas adalah : K , L, F, G, M, I , J

Struktur Pohon yang terkenal adalah struktur geneologi (silsilah). Dalam struktur tersebut

adanya simpul anak (children) dan orangtua (parent)

Contoh anak D adalah H, I, J

Orangtua D adalah A

Anak dari orang tua yang sama (saudara sekandung) disebut sibling misal H,I,J.

DERAJAT (DEGREE) SUATU POHON:

Adalah derajat maksimum dari suatu simpul dalam pohon.

Contoh derajat pohon dalam gambar diatas adalah 3.

Nenek Moyang dari dari suatu simpul adalah seluruh simpul-simpul yang ada sepanjang

lintasan dari akar sampai simpul tersebut. Contoh nenek moyang dari M adalah A, D dan H.

KEDALAMAN (HEIGHT atau DEPTH)

Kedalaman suatu pohon ditentukan oleh level maksimum dari simpul dalam pohon.

Contoh kedalaman pohon dari gambar diatas adalah 4

HUTAN (FOREST)

Adalah susunan dari beberapa pohon. Bila akar A dihilangkan maka akan diperoleh hutan

dengan 3 pohon yaitu :

B(E(K,L),F)

C(G)

D(H(M),I,J)

Ada 2 cara untuk menyatakan struktur pohon yaitu :

1. Gambar

2. Daftar(List)

Pernyataan dengan Gambar adalah seperti terlihat pada Gambar diatas sedangkan kalau

dengan List adalah sebagai berikut :

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

Page 125: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

A

B  C D

E F  G H I J 

Proses dalam struktur data non linier, bentuk pohon akan lebih mudah digambarkan bila

diketahui :

n ( Jumlah Simpul atau Node )

k ( Derajat Pohon)

Dari data n dan k maka dapat dihitung :

JUMLAH LINK = n . k

JUMLAH NULL-LINK = n( k - 1)+1

JUMLAH NON ZERO LINK = n - 1

Link = Pointer yang digunakan untuk menunjukan simpul sub ordinat

Null Link = Link yang bernilai null, yaitu link yang tidak menunjuk simpul sub ordinat

Non Zero Link = Link yang menunjuk simpul atau link yang menghubungkan dua buah

simpul

STRUKTUR NODE K-ary

DATA

Child –1

……

Child-k

Pohon 3 - ary :

Dari gambar diatas diket : n = 10 , k = 3

Page 126: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

A

A

B  C

D E  F

G

Maka dapat dihitung :

JUMLAH LINK = n . k = 3. 10 = 30

JUMLAH NULL LINK = n ( k – 1 ) + 1

= 10 ( 3 – 1 ) + 1

= 21

JUMLAH NON ZERO LINK = n – 1 = 10 - 1 = 9

POHON BINER (BINARY TREE)

- Tipe yang sangat penting dari struktur data

- Dalam struktur pohon biner hanya dikenal SUBTREE KIRI DAN SUBTREE KANAN

saja

Simpul dalam pohon biner adalah :

Susunan dari simpul-simpul yang masing-masing bisa kosong atau terdiri dari akar

dan dua pohon biner yang terpisah dan disebut subtree kiri dan subtree kanan.

Pohon biner dengan subtree kanan kosong Pohon biner dengan subtree kiri kosong

Full Binary Tree

Page 127: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

A

B  C

D E 

Complette Binary Tree

Pohon Biner Penuh ( Full Binary Tree)

Adalah pohon biner yang mempunyai simpul atau node lengkap dari level 1 sampai level ke

I

Pohon Biner Lengkap ( Complette Binary Tree)

Adalah pohon biner yang mempunyai simpul dengannomor urut 1 sampai dengan n.

Page 128: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

LEVEL ANAK TERKIRI

ANAK TERKANAN

1 1 12 2 33 4 74 8 155 16 316 32 637 64 1278 128 2559 256 511

10 512 102311 1024 204712 . . . .

2048 . . . .

4095 . . . .

No anak kiri (Left Child) = No. Parent * 2

No anak kanan (Right Child) = (No. Parent *2) + 1

No Parent = No Child

2

Pertanyaan

1. Pohon dengan simpul jumlah simpul = 273 merupakan

lengkap atau penuh

2. Berapa kedalamannya ?

3. No berapa simpul terkiri dari level tersebut ?

4. berapa jumlah maxsimum simpul level 7

5. No berapa anak kanan dari simpul ke 180 ?…..ada dilevel berapa anak tersebut.

6. No. berapa orang tua dari simpul ke 83 ? … ada dilevel berapa orangtua tsb

Kedalaman minimal dari pohon biner adalah :

2 Log n + 1 dimana n = jumlah simpul

Contoh bila n = 15

Page 129: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Maka kedalamannya minimal = 2 Log 15 + 1

= Log 15 + 1

Log 2

= 1.17 / 0.3 + 1 = 3 + 1

= 4

SKEWED TREE

Adalah Pohon biner yang miring kekiri atau kekanan, atau dengan kata lain pohon biner

dengan subtree kiri kosong atau subtree kanan kosong.

Pohon Biner seperti ini dimpan dalam

REPRESENTASINYA sebagai berikut :

1 A 2 B 3 4 C 5 6 7 8 D 9

15

Page 130: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Kosong sebanyak 7 Elemen

Terlihat dari contoh diatas bahwa penyimpanan data dalam memori dari pohon biner hanya

menguntungkan kalau pohon binernya penuh sehingga tidak memboroskan tempat.

Untuk menanggulangi ini maka perlu menggunakan representasi Linked List, dimana

masing-masing simpul akan mempunyai 3 field yaitu :

LCHILD DATA RCHILD

ATAU

Contoh Representasi Link Pohon Biner Biasa

struct NAMA_SIMPUL { Tipe Data DATA; Struct NAMA_SIMPUL *RCHILD, *LCHILD; };

DATA 

LCHILD RCHILD 

0      D     0  0      E      0 

0      F      0  0      G      0 

Page 131: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Skewed Tree

CONTOH PROGRAM

               A            0 

               B           0 

               C           0 

Page 132: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Output Program :

Page 133: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 134: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 10 TREE 2 (PENELUSURAN POHON BINER)

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

10 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang penerapan aplikasi TREE dalam melakukan penelusuran pohon biner

 

Mampu memahami penerapan aplikasi tree dalam melakukan penelusuran pohon biner 

   

Page 135: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

*

+  C

A B 

PENELUSURAN POHON BINER

Macam – macam penelusuran

Ada 3 macam Traversal :

1. Inorder Traversal

2. Preorder Traversal

3. Postorder Traversal

1. Inorder Traversal

- Akan menghasilkan bentuk INFIX

- Bentuknya

Operand1 Operator Operand2

A + B

Contoh

Tulislah hasil penelusuran pohon biner berikut ini bila ditelusuri secara INORDER.

Langkah-langkahnya :

1. Telusuri Subtree(sub pohon) Kiri

2. Proses Simpul Akar

3. Telusuri Subtree(Sub pohon) Kanan

maka akan diperoleh persamaan INORDERnya adalah:

(A + B) * C

2. Preorder Traversal

- Akan menghasilkan bentuk PREFIX

- Bentuknya

Page 136: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

*

+  C

A B 

Operator Operand1 Operand2

+ A B

Contoh

Tulislah hasil penelusuran pohon biner berikut ini bila ditelusuri secara PREORDER.

Langkah-langkahnya :

1. Proses Simpul Akar

2. Telusuri Subtree(sub pohon) Kiri

3. Telusuri Subtree(Sub pohon) Kanan

maka akan diperoleh persamaan PREORDERnya adalah:

* + A B C

3. Postorder Traversal

- Akan menghasilkan bentuk POSTFIX

- Bentuknya

Operand1 Operand2 Operator

A B +

Page 137: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

*

+  C

A B 

Contoh

Tulislah hasil penelusuran pohon biner berikut ini bila ditelusuri secara POSTORDER.

Langkah-langkahnya :

1. Telusuri Subtree(sub pohon) Kiri

2. Telusuri Subtree(Sub pohon) Kanan

3. Proses Simpul akar

maka akan diperoleh persamaan POSTORDERnya adalah:

A B + C *

Representasi Dari Pohon K-Ary ke Binary.

Pohon 3 Ary

A

B  C D

E  F  G H I J

Page 138: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Kebinary 2 Ary

Pohon K-Ary

Jumlah NullLink = n (k – 1) +1

Pohon Binary

K=2 Jumlah NullLink = n (k – 1) +1

= n (2 - 1) +1

= n + 1

berapa besar penghematan memory bila dirubah ke binary…gambar diatas?.

Kalau ada 3 pohon kemudian disatukan menjadi 1 pohon.

E C 

DF  G 

I

J

E

C  DF

G

H I

Page 139: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

/

A +

D

‐ *

7 E F G 

*

Latihan

1. Buat Persamaan INORDER, PREORDER, DAN POST ORDER dari Tree Berikut :

2. Diket Persamaan POST ORDER :

A B / C * D E ** F 2 + –

Buat INORDER, PREORDER, dan buat Tree nya.

B  E

C

F  G

H

I

Page 140: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Contoh Program #include <stdio.h>

#include <conio.h>

typedef struct Node{

int data;

Node *kiri;

Node *kanan;

};

void tambah(Node **root,int databaru){

if((*root) == NULL){

Node *baru;

baru = new Node;

baru->data = databaru;

baru->kiri = NULL;

baru->kanan = NULL;

(*root) = baru;

(*root)->kiri = NULL;

(*root)->kanan = NULL;

printf("Data bertambah!");

}

else if(databaru < (*root)->data)

tambah(&(*root)->kiri,databaru);

else if(databaru > (*root)->data)

tambah(&(*root)->kanan,databaru);

else if(databaru == (*root)->data)

printf("Data sudah ada!");

}

void preOrder(Node *root){

if(root != NULL){

printf("%d ",root->data);

Page 141: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

preOrder(root->kiri);

preOrder(root->kanan);

}

}

void inOrder(Node *root){

if(root != NULL){

inOrder(root->kiri);

printf("%d ",root->data);

inOrder(root->kanan);

}

}

void postOrder(Node *root){

if(root != NULL){

postOrder(root->kiri);

postOrder(root->kanan);

printf("%d ",root->data);

}

}

void main(){

int pil,c;

Node *pohon,*t;

pohon = NULL;

do{

clrscr();

int data;

printf("MENU\n");

printf("1. Tambah\n");

printf("2. Lihat pre-order\n");

printf("3. Lihat in-order\n");

printf("4. Lihat post-order\n");

printf("5. Exit\n");

printf("Pilihan : "); scanf("%d",&pil);

Page 142: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

switch(pil){

case 1: printf ("Data baru : ");

scanf("%d",&data);

tambah(&pohon,data);

break;

case 2: if(pohon!=NULL) preOrder(pohon);

else printf("Masih kosong!");

break;

case 3: if(pohon!=NULL) inOrder(pohon);

else printf("Masih kosong!");

break;

case 4: if(pohon!=NULL) postOrder(pohon);

else printf("Masih kosong!");

break;

}

getch();

}while(pil!=5);

}

Output Program Tambah Data:

MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 1 Data baru : 5 Data Bertambah MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 1 Data baru : 2 Data Bertambah MENU 1. Tambah 2. Lihat pre-order

Page 143: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 1 Data baru : 3 Data Bertambah MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 1 Data baru : 8 Data Bertambah Output Program Pre -Order: MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 2 5 2 3 8 Output Program In-Order: MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 3 2 3 5 8 Output Program Post-Order: MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 4 3 2 8 5

Page 144: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 145: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 11 TEKNIK PENCARIAN DATA

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

11 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang penerapan aplikasi searching seperti linier search, binary search dan fibonaci search

 

Mampu memahami penerapan aplikasi searching seperti linier search, binary search dan fibonaci search 

   

Page 146: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

TEKNIK PENCARIAN DATA

Macam-macam searching

File adalah kumpulan record-record sejenis dimana masing masing record lebih dari satu

field. Field – field tersebut diperlukan untuk memberikan suatu identifikasi bagi masing-

masing record. Key (kunci) field untuk identifikasi record akan tergantung pada aplikasi

tertentu.

Misal : File Mahasiswa menggunkan field yang berisi NOMOR INDUK MAHASIWA (NIM)

Ada beberapa cara searching, yaitu :

a. Linier Search (Sequential Search)

b. Binary Search

c. Fibonaci Search

Dalam melakukan search ini diasumsikan file dalam keadaan sudah sort (urut).

a. Linier Search

Pencarian dimulai dari record ke –1, diteruskan ke record berikutnya yaitu record ke

2 , ke 3 ……..dst, sampai diperoleh isi record sama dengan informasi yang dicari.

Berikut ini Program sederhana Linier Search

Jika N = Jumlah Data

X = Data yang dicari

#include<iostream.h>

#include<conio.h>

#define N 8

main() {

int I,NILAI[N+1],X;

char GRADE[N+1];

clrscr();

Page 147: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

NILAI[1]=30;

NILAI[2]=40;

NILAI[3]=45;

NILAI[4]=60;

NILAI[5]=65;

NILAI[6]=70;

NILAI[7]=75;

NILAI[8]=80;

GRADE[1]='E';

GRADE[2]='D';

GRADE[3]='D';

GRADE[4]='C';

GRADE[5]='C';

GRADE[6]='B';

GRADE[7]='B';

GRADE[8]='A';

cout<<"MASUKAN NILAI YANG DICARI :";

cin>>X;

NILAI[N+1]=X;

I=1;

while (NILAI[I]!=X)

{

I=I+1;

}

if(I==N+1)

cout<<"PENCARIAN GAGAL";

else

{

cout<<"NILAI DICARI : "<<NILAI[I]<<endl;

cout<<"PADA LOKASI : "<<I<<endl;

cout<<"GRADE : "<<GRADE[I]; }

}

Page 148: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Cara ini sangat jelek karena memerlukan waktu yang lama. Kemungkinan terjelek adalah

memerlukan waktu N+1, sehingga waktu yang diperlukan untuk search adalah O(n).

Waktu yang diperlukan untuk search secara umum :

f(n) = O(g(n))

f(n) untuk menyatakan computing time dari beberapa algorithma

O(n) disebut waktu linier

O(log n) disebut waktu logarithmic, lebih cepat dari waktu linier.

b. Binary Search

- Merupakan metode terbaik dalam search

- Memulai search dari lokasi tengah(MIDDLE). Kemudian berdasarkan isi dari lokasi

ditengah tersebut dapat diberikan 3 kemungkinan :

X = Data yang dicari

1. jika X < K[M] : data yang dicari berada pada

bagian bawah dari lokasi middle

2. jika X = K[M] : data tengah adalah data yang

dicari.

3. jika X>K[M] : data yang dicari berada pada

bagian atas dari lokasi tengah (middle)

demikianlah seterusnya setiap sudah ditentukan lokasi tengah, sampai diperoleh

data yang dicari.

CONTOH : suatu urutan data dengan cacah data N=10;

Data tersebut mempunyai nilai sebagai berikut :

1 2 3 4 5 6 7 8 9 10

75 151 203 275 300 489 524 591 647 727

Logika pencarian : cari data yang bernilai 275

Page 149: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

X = 275

ITERASI LOW HIGH MIDDLE COMPARE

1 1 10 5 275 < 300

2 1 4 2 275 > 151

3 3 4 3 275 > 203

4 4 4 4 275 = 275

Pencarian dibutuhkan 4 Langkah (iterasi)

Misal lagi cari data yang bernilai 591

X = 591

ITERASI LOW HIGH MIDDLE COMPARE

1 1 10 5 591 > 300

2 6 10 8 591 = 591

Pencarian dibutuhkan 2 Langkah (iterasi)

Waktu yang diperlukan pada Binary Search adalah : O(Log n)

c. Fibonaci Search

- Menggunakan cara Search dengan memecah subfile menurut Fibonaci Sequence yaitu :

0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 ,………… dst

diperoleh harga awal Fo = 0 dan F1 = 1

Fibonaci Sequence : Fi = Fi - 1 + Fi - 2 ; i>=2

Keuntungannnya :

Dalam prosesnya hanya menggunakan operator pertambahan dan pengurangan saja.

Oleh karena itu waktu rata-rata search lebih cepat dari binary search yang menggunakan

pembagian dalam proses searchnya.

Page 150: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

CONTOH : Data yang sudah urut

Data ke - 1 2 3 4 5 6 7 8 9 10

11 23 36 42 58 65 74 87 94 99

Cari Data yang berharga 65 , X = 65

Diket : n = jumlah record

n = 10

Fk + m = n + 1 adalah rumus untuk mencari

increament (angka pertambahan)

Fk = angka Fibonaci

Fk + m = 10 +1

= 11

Fk + m = 11

m = 11 - Fk

= 11 - 8 Fk= 8 adalah angka

Fibonaci terdekat dengan 11

m = 3

Langkah-langkahnya :

Tentukan Fk-1 , F k-2, F k-3

Jika Fk = 8 ----------- i = Fk-1 = 5

p = Fk-2 = 3

q = Fk-3 = 2

Jika X > K[ i ] maka i = i + m

Lakukan While - DO bila i<>0 yang berisi

Case of : 1. Jika X < K[ i ] : Jika q = 0 maka i = 0

Jika q<>0 maka i = i – q; t=p; p=q ; q=t-q;

2. Jika X = K[ i ] : Data dicari di temukan ( Return)

Page 151: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

3. Jika X > K[ i ] : Jika p=1 maka i=0

Jika p<>0 maka i = i + q; p = p - q; q=q - p

Contoh :

Dicari data yang berharga 65 X = 65

i = 5 ; p = 3; q = 2; m = 3

Cek : Jika X > K[ i ] maka i = i + m

X > K[5]

X > 58 - “ya” maka i = 5 + 3 = 8

Masuk While – Do : case 65 … K[ i ]

65 < K[ 8 ]

65 < 87 - ‘ya’ maka Jika q<>0 : “ya” maka

i = i – q ; t=p ; p=q ; q = t -q

i = 8 – 2 t=3 p=2 q = 3-2

i = 6 q=1

case : 65 = k[ i ]

65 = k[ 6 ]

65 = 65

diperlukan 2 iterasi

Page 152: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Latihan

1. Suatu data dengan urutan

23 75 80 86 90 100 101 103 106 199 202 212 450

Dicari data 199

Berapa iterasi yang dibutuhkan untuk mendapatkan angka 199

2. Buat Algoritma dan Program C++ untuk kasus contoh diatas dengan Linier Search.

3. Suatu data dengan urutan

23 75 80 86 90 100 101 103 106 199 202 212 450

Dicari data 199

Berapa iterasi yang dibutuhkan untuk mendapatkan angka 199 dengan Fibonaci

Search

4. Buat Algoritma dan Program C++ untuk kasus contoh diatas dengan Fibonaci Search.

Contoh Program Binery Search #include <iostream.h> void main() { int data[20],n,x,posisi,e,temp,b,c,d,low,high,mid; bool ketemu; cout<<"Masukan jumlah data : "; cin>>n; for(b=0;b<n;b++) { cout<<"Masukan data ke-"<<b+1<<" = "; cin>>data[b]; } for(c=0;c<n;c++) { for(d=c+1;d<n;d++) { if(data[c]>data[d]) { temp=data[c]; data[c]=data[d]; data[d]=temp; } } } cout<<"data telah disorting"<<endl;

Page 153: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

for(b=0;b<n;b++) { cout<<data[b]<<" "; } cout<<endl; cout<<"Masukan huruf yang di cari : "; cin>>x; low=0,high=n; for(e=0;e<n;e++) { mid=(low+high)/2; if(x==data[mid]) { ketemu=true; posisi=mid+1 ; } else if(x>data[mid]) { low=mid+1; } else if(x<data[mid]) { high=mid-1; } } if(ketemu==true) { cout<<"data ditemukan pada posisi : "<<posisi<<endl; } else { cout<<"data tidak ditemukan"<<endl; } }

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 154: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 12 Macam-macam Graph dan Penerapannya

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

12 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang macam-macam graph dan penerapannya

 

Mampu memahami macam-macam graph dan penerapannya 

   

Page 155: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Graph dan Penerapannya

Pengertian Graph

Dinyatakan dalam suatu Fungsi G=(V,E) dimana :

V = Kumpulan Simpul /Vertex/Node

E = Kumpulan Busur/Edge/Arc

Tiap Busur pasti menghubungkan 2 Simpul (Vertex)

Ada 2 macam Graph :

1. Graph Tak Terarah (Undirect Graph)

2. Graph Terarah (Direct Graph)

1. Graph Tak Terarah ( Undirect Graph)

V1 – V2 = V2 – V1 V1 – V4 = V4 - V1

Graph Tak terarah adalah graph yang menghubungkan 2 simpul V1 ke V2 dan V2 ke V1 (2

arah). Bila simpul=n maka graph tak terarah komplit akan mempunyai busur sama dengan

n ( n - 1 ) / 2

2. Graph Terarah ( Directed Graph)

Hanya dapat menghubungkan 1 arah saja

V1 – V2 <> V2 – V1

V1 

V2 

V4 

V3 

V1 

V2 

V4 

V3 

Page 156: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Maksimum jumlah busur dari n simpul adalah :

n ( n – 1 )

3. MULTIGRAPH

Multigraph adalah 2 buah simpul V1 - V2 yang dihubungkan oleh busur yang jaraknya

berbeda-beda.

4. CYCLE

Suatu lintasan yang kembali kesimpul semula.

5. BOBOT PANJANG LINTASAN

8 7 6 5 10

Panjang dari V1 ke V4 adalah :

Busur 1 , 2 , 4 --------- 7 + 6 = 13

Busur 1 , 2 , 3, 4--------7 + 10 + 5 = 22 ( Lintasan Kritis )

Busur 1 , 4 ------------ 8

V1  V2 

V1 

V1 

V2 

V4 

V3 

Bobot Panjang Lintasan adalah jumlah busur yang menghubungkan simpul Vx ke simpul Vy

Page 157: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

5. GRAPH CONECTED

Jika untuk setiap pasangan simpul Vi dan Vj ada lintasan yang menghubungkannya.

6. GRAPH UNCONECTED

Suatu Graph non connected berisi paling sedikit 1 pasangan yang tidak terhubung.

7. GRAPH PLANAR

Adalah graph yang bila digambarkan bisa dengan tidak adanya garis yang berpotongan.

Gambar Graph Planar dapat digambarkan tanpa adanya garis berpotongan.

8. GRAPH NONPLANAR

Adalah kebalikan dari Graph Planar, jadi Graph nonplanar adalah Graph yang tidak

dapat digambarkan tanpa adanya garis yang saling berpotongan.

Gambar Graph Nonplanar

Page 158: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

REPRESENTASI GRAPH

Terdiri dari : 1. Adjency matrix

2. Adjency List

3. Adjency Array

4. Incidence Matrix

1. ADJENCY MATRIX

Orientasinya kesimpul dari Graph Ukuran : A [ n x n ]

Dimana A = Matrix , n = jumlah simpul

Definisi

ai = 1 : Jika ada busur yang menghubungkan simpul i dan j

0 : Jika tidak ada hubungan

UNDIRECTED

 

DIRECTED

 

A =       0    1     1     1 

             1    0     1     1 

             1    1     0     1 

             1    1     1     0 

A =        0    1    0                              1    0     1               

0    0     0  Kolom menyatakan IN ‐ DEGREE  Baris menyatakan OUT – DEGREE  

Page 159: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

2. ADJENCY LIST

Representasinya dalam bentuk List berangkai

Keuntungan : dapat dilakukan penambahan simpul dengan mudah,karena sifatnya dinamis

UNDIRECT

DIRECTED

Derajat dari tiap simpul dalam Undirected Graph bisa ditentukan dengan menghitung jumlah

simpul dalam adjency List.

Sedangkan dalam directed graph derajat keluaran (out degree) dapat ditentukan dari

jumlah node yang terhubung pada adjency listnya, tapi mengalami kesulitan dalam melihat

derajat masukan (indegree) dari tiap simpul.

Untuk itu disajikan INVERSE ADJENCY LIST ynag memperlihatkan jumlah derajat

masukan dari tiap simpul.

3 2 

 

 Vertex1 

   2   

   3 

     4 

 0 

 

 Vertex2 

   1   

   3 

     4 

 0 

 

 Vertex3 

   1   

   2 

     4 

 0 

 

 Vertex4 

   1   

   2 

     3 

 0 

 

 

 Vertex1 

   2 

 0  

 

 Vertex2 

   1   

   3 

 0 

 

 Vertex3 

   0   

 OUT DEGREE  

Page 160: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

INVERSE ADJENCY LIST

3. ADJENCY ARRAY

Lebih cocok untuk graph berarah untuk setiap ek mempunyai pasangan simpul asal

Vi dan simpul Tujuan Vj.

e3 e1 e4 e5 e7 e2 e6

Asal 1 4 2 2 3 5 3

Tujuan 2 1 3 5 4 4 5Gabungan dari kedua array tersebut adalah

3

5

3

2

2

4

1

X

2

1

3

5

4

4

5

Simpul Asal awal Simpul Tujuan

 

 Vertex1 

   2 

 0  

 

 Vertex2 

   1 

 0

 

 Vertex3 

   2 

 0

 IN DEGREE 

V2 

V3 

V5 V4 

V1 

  V asal  V Tujuan e1 1  2 

e2  4  1 

e3  2  3 

e4  2  5 

e5  3  4 

e6  5  4 

e7  3  5 

Page 161: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

4. INCEDENCE MATRIX

Menggambarkan hubungan antara simpul dan busur.

Ukuran : I [ n x m ] dimana n = jumlah simpul , m = jumlah busur

e3 e1 e4 e7 e2 e5 e6

e1 e2 e3 e4 e5 e6 e7

1 1 1 0 0 0 0 0I = 2 1 0 1 1 0 0 0

3 0 0 1 0 1 0 14 0 1 0 0 1 1 05 0 0 0 1 0 1 1

APLIKASI GRAPH

1. Critical Path (Lintasan Kritis)

Lintasan yang paling panjang dari simpul asal sampai simpul tujuan

2. Minimum Spaning Tree

Bagaimana mencapai semua simpul dengan total lintasan minimum.

1. Lintasan Kritis : menggunakan Graph berbobot

6 10 5 8 4 7 9

Graph G

V2 

V3 

V4 V5 

V1 

5 4 

Cari Lintasan Kritisnya :

Simpul Asal : 1

Page 162: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Lintasan Bobot

Alternatif : 1 2 5 15

1 2 3 5 24

1 2 3 4 5 29

1 4 5 16

1 4 3 5 19

1 4 3 2 5 22

Diperoleh : Lintasan Kritis = 29

Lintasan Terpendek = 15

2. Minimum Spanning Tree

6 10 5 G’ SubGraph dari G 9

6 4 8 G’’ SubGraph dari G 7

5 4 

G’ SubGraph dari G

Bobot : 10+6+5+9 =30

G’’ SubGraph dari G

Page 163: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

6 5 4 G’’’ SubGraph dari G 7 maka MST = 22

Latihan

 

 

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

G’’’ SubGraph dari G

Page 164: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 13 Macam-macam Graph dan Penerapannya

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

13 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang penerapan dan penelusuran Graph menggunakan DFS dan BFS

 

Mampu memahami penerapan dan penelusuran Graph menggunakan DFS dan BFS

 

   

Page 165: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Penelusuran Graph dan penerapannya

Penelusuran Graph

Penelusuran Graph maksudnya mengunjungi (visit) atau membaca Graph menurut arah

tertentu, simpul per simpul, mulai dari simpul tertentu sampai semua simpul dikunjungi

tanpa ada simpul yang dikunjungi atau dibaca lebih dari satu kali.

Ada 2 macam penelusuran :

1. Depth First Search (DFS), penelusuran dengan mendahulukan arah kedalaman

2. Breadth First Serch (BFS), penelusuran dengan mendahlukan arah melebar

1. Depth First Search

Depth First Search (DFS), penelusuran graph yang arah penelusurannya mendahulukan ke

arah kedalaman graph tersebut.

Pada setiap pencabangan, penelusuran verteks-verteks yang belum dikunjungi dilakukan

secara lengkap pada pencabangan pertama, kemudian selengkapnya pada pencabangan

kedua, dan seterusnya secara rekursif.

Algoritma DFS

• Traversal dimulai dari simpul v.

• Algoritma:

1. Kunjungi simpul v,

2. Kunjungi simpul w yang bertetangga dengan simpul v.

3. Ulangi DFS mulai dari simpul w.

4. Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga

dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul

terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum

dikunjungi.

5. Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat

dicapai dari simpul yang telah dikunjungi.

Page 166: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Urutan verteks hasil penelusuran :

Page 167: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Dalam proses penelusuran, akan terlihat nanti pada suatu titik, 'terpaksa' dilakukan langkah

kembali ke simpul sebelumnya. Dalam pemrograman, untuk dapat kembali ke posisi

sebelumnya, biasanya diperlukan stack. Pada penelusuran, kita menggunakan stack S,

dengan jumlah elemen tidak kurang dari jumlah simpul graph yang ditelusuri.

Page 168: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

2. Breadth First Search

Breadth First Search (BFS), penelusuran graph yang arah penelusurannya mendahulukan

ke arah 'lebar' graph tersebut.

Algoritma BFS

BFS diawali dengan vertex yang diberikan, yang mana di level 0. Dalam stage pertama, kita

kunjungi semua vertex di level 1. Stage kedua, kita kunjungi semua vertex di level 2. Disini

vertex baru, yang mana adjacent ke vertex level 1, dan seterusnya. Penelusuran BFS

berakhir ketika setiap vertex selesai ditemui.

• Traversal dimulai dari simpul v.

• Algoritma:

1. Kunjungi simpul v,

2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu.

3. Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul

yang tadi dikunjungi, demikian seterusnya.

Urutan verteks hasil penelusuran :

Page 169: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Page 170: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Proses penelusuran:

Diperlukan sebuah array untuk antrian (Queue) yang diberi nama Q yang jumlah elemenya

tidak kurang dari jumlah simpul.

Page 171: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Latihan

 

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4

Page 172: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

 

 

  MODUL PERKULIAHAN  

 

Algoritma

Pemrograman &

Struktur Data  

 

 

Pertemuan 14 Sorting, Searching, graph dan Tree dalam pemecahan masalah

 

 

             

  Fakultas  Program Studi  Tatap Muka  Kode MK  Disusun Oleh   

  Ilmu Komputer  Teknik Informatika 

13 87031  Tim Dosen 

   

 

Abstract  Kompetensi    

Membahas tentang penerapan dan penelusuran Graph menggunakan DFS dan BFS

 

Mampu memahami penerapan dan penelusuran Graph menggunakan DFS dan BFS

 

   

Page 173: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

Sort, Search, Tree dan Graph Quick Sort #include<iostream.h> #include<conio.h> #include<iomanip.h> #define MAX 20 void quick_sort(int darr[MAX], int lb, int ub) { int a; int up,down; int temp; if (lb>=ub) return; a=darr[lb]; up=ub; down=lb; while (down<up) { while (darr[down] <= a) down++; while (darr[up] > a) up--; if (down < up) { temp = darr[down]; darr[down]=darr[up]; darr[up]=temp; } } darr[lb] = darr[up]; darr[up] = a; quick_sort(darr, lb, up-1); quick_sort(darr,up+1, ub); } main() { int arr[MAX], n, ub ,lb=0; cout<<endl<<"============================================"; cout<<endl<<"| Pengurutan dengan metode quick sort |"; cout<<endl<<"============================================"; cout<<endl<<"Masukkan jumlah data yang ingin diurutkan :"; cin>>n; ub=n-1; cout<<endl<<"Masukkan data-datanya :"; for(int i=0;i<n;i++) { cout<<endl<<"Masukkan data ke "<<i+1<<" : "; cin>>arr[i]; }

Page 174: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 3 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

quick_sort(arr,lb,ub); cout<<endl<<"Hasil pengurutan :"; for(i=0;i<n;i++) cout<<endl<<setw(10)<<arr[i]; cout<<endl<<"Tekan sembarang tombol untuk keluar!!!"<<endl; getch(); return 0; } Sort dan Search #include<iostream.h> #include<conio.h> #include<iomanip.h> #include<stdlib.h> void menu(); void linear_search(); void binary_search(); void fibonacci_search(); void linear_sort(); void bubble_sort(); void fibonacci(); void swap(int &value1, int &value2); void tanya(); void salah(); int a,b,n,i,j,m,p,q,t,x,y,Fk,Fib[100],k,nilai[100],temp; char jawab; main() { cout<<setw(50)<<"\n\t========================="; cout<<setw(50)<<"\n\t| Searching And Sorting |"; cout<<setw(50)<<"\n\t|-----------------------|"; cout<<setw(50)<<"\n\t| Oleh : Tim Dosen |"; cout<<setw(50)<<"\n\t========================="; menu(); return 0; } void menu() { int nomor; system("cls"); cout<<"\n\n\tMENU SEARCHING AND SORTING"; cout<<"\n\t 1 :Linear Search"; cout<<"\n\t 2 :Binary Search"; cout<<"\n\t 3 :Fibonacci Search"; cout<<"\n\t 4 :Linear Sort"; cout<<"\n\t 5 :Exchange (Bubble) Sort"; cout<<"\n\t 6 :Keluar Program"; cout<<"\n\tPilihan Anda : "; cin>>nomor; switch(nomor)

Page 175: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 4 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

{ case 1: linear_search(); break; case 2: binary_search(); break; case 3: fibonacci_search(); break; case 4: linear_sort(); break; case 5: bubble_sort(); break; case 6: tanya(); break; default: salah(); menu(); break; } } void linear_search() { system("cls"); cout<<"\n\nMasukan jumlah nilai : "; cin>>n; for(i=1;i<=n;i++) { cout<<"Nilai ["<<i<<"] : "; cin>>nilai[i]; } cout<<"\nApakah data akan disortir? Y/N : "; cin>>jawab; if(jawab=='Y'||jawab=='y') { for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(nilai[i]>nilai[j]) { temp=nilai[i]; nilai[i]=nilai[j]; nilai[j]=temp; } } } cout<<"\n\nUrutan Ascending data :\n"; for(i=1;i<=n;i++) cout<<nilai[i]<<" ";

Page 176: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 5 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

cout<<"\nNilai yang dicari : "; cin>>b; i=1; while(nilai[i]!=b) i++; if(i==n+1) cout<<"\n\tPencarian gagal..."; else { cout<<"\n\tNilai yang dicari :"<<nilai[i]; cout<<"\n\tDi lokasi :"<<i; } } else if(jawab=='N'||jawab=='n') { cout<<"\nNilai yang dicari : "; cin>>b; i=1; while(nilai[i]!=b) i++; if(i==n+1) cout<<"\n\tPencarian gagal..."; else { cout<<"\n\tNilai yang dicari :"<<nilai[i]; cout<<"\n\tDi lokasi :"<<i; } } else { salah(); linear_search(); } tanya(); } void binary_search() { system("cls"); int low,mid,high,flag=0; cout<<"\n\nMasukan jumlah nilai : "; cin>>n; for(i=1;i<=n;i++) { cout<<"Nilai ["<<i<<"] : "; cin>>nilai[i]; } for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(nilai[i]>nilai[j]) { temp=nilai[i]; nilai[i]=nilai[j];

Page 177: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 6 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

nilai[j]=temp; } } } cout<<"\n\nUrutan Ascending data :\n"; for(i=1;i<=n;i++) cout<<nilai[i]<<" "; cout<<"\n\nNilai yang dicari : "; cin>>b; low=1;high=n; while(low<=high&&flag==0) { mid=(low+high)/2; if(nilai[mid]==b) flag=1; else if(nilai[mid]<b) low=mid+1; else high=mid-1; } if(flag==1) { cout<<"\n\n\tNilai yang dicari : "<<b; cout<<"\n\tDi lokasi : "<<mid; } else cout<<"Pencarian gagal..."; tanya(); } void fibonacci_search() { system("cls"); cout<<"\n\nFibonanci search ini mengunakan jumlah data sebanyak 10"<<endl<<endl; cin>>n; for(j=1;j<=n;j++) { cout<<"Masukan data ke "<<j<<"= "; cin>>nilai[j]; } for(j=1;j<=n;j++) { for(y=j+1;y<=n;y++) { if(nilai[j]>nilai[y]) { temp=nilai[j]; nilai[j]=nilai[y]; nilai[y]=temp; } } } cout<<"\n\nUrutan Ascending data :\n"; for(j=1;j<=n;j++) {

Page 178: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 7 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

cout<<nilai[j]<<" "; } cout<<endl; /* a=10+1; k=2; while(a<=n) { Fib[k]=Fib[k-2]+Fib[k-1]; if(Fib[k]==a) { Fib[k]=k-1; Fk=Fib[k]; } cout<<Fib[k]<<" "; k++; }*/ Fib[0]=0; Fib[1]=1; k=0; cout<<"Baris Fibonaci terdekat dengan data :"; while(Fib[k]<=n+1) { if(k>0) Fib[k+1]=Fib[k]+Fib[k-1]; cout<<Fib[k]<<" "; k++; } cout<<endl<<"Jumlah data fibonaci = "<<k--<<endl; Fk=Fib[k]; cout<<"Nilai Fk = "<<Fk<<endl; i=Fib[k-1]; p=Fib[k-2]; q=Fib[k-3]; m=n-Fk+1; cout<<"i="<<i<<endl<<"p="<<p<<endl<<"q="<<q<<endl<<"m="<<m<<endl; cout<<"\nMasukan data yang ingin dicari = "; cin>>x; if(x>nilai[i]) { i=i+m; } while(i!=0) { if(x<nilai[i]) { if(q==0) { i=0; cout<<"Data tidak ditemukan !!"; break; } i=i-q; t=p; p=q;

Page 179: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 8 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

q=t-q; } else if(x==nilai[i]||i==9||i==10) { cout<<"Data yang dicari ditemukan pada lokasi ke "<<i<<endl; break; } else if(x>nilai[i]) { if(p==1) { i=0; cout<<"Data tidak ditemukan !!"; break; } i=i+q; p-=q; q-=p; } } tanya(); } void linear_sort() { system("cls"); cout<<"\n\nMasukan jumlah data : "; cin>>n; for(i=1;i<=n;i++) { cout<<"Nilai ["<<i<<"] : "; cin>>nilai[i]; } cout<<"\n\nMetode sorting?"; cout<<"\n A :Ascending"; cout<<"\n D :Descending"; cout<<"\nPilihan Anda : "; cin>>jawab; if(jawab=='A'||jawab=='a') { for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(nilai[i]>nilai[j]) { temp=nilai[i]; nilai[i]=nilai[j]; nilai[j]=temp; } } } cout<<"\n\nUrutan Ascending data :\n";

Page 180: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 9 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

for(i=1;i<=n;i++) cout<<nilai[i]<<" "; } else if(jawab=='D'||jawab=='d') { for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(nilai[i]<nilai[j]) { temp=nilai[i]; nilai[i]=nilai[j]; nilai[j]=temp; } } } cout<<"\n\nUrutan Descending data :\n"; for(i=1;i<=n;i++) cout<<nilai[i]<<" "; } else { salah(); linear_sort(); } tanya(); } void bubble_sort() { int exc,loop,j=1; system("cls"); cout<<"\n\nMasukan jumlah data : "; cin>>n; for(i=1;i<=n;i++) { cout<<"Nilai ["<<i<<"] : "; cin>>nilai[i]; } cout<<"\n\nMetode sorting?"; cout<<"\n A :Ascending"; cout<<"\n D :Descending"; cout<<"\nPilihan Anda : "; cin>>jawab; cout<<endl<<endl; if(jawab=='A'||jawab=='a') { for(loop=1;loop<=n;loop++) { cout<<"Looping ke : "<<loop; cout<<endl; exc=0; for(j=1;j<n;j++)

Page 181: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 10 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

{ if(nilai[j]>nilai[j+1]) { swap(nilai[j],nilai[j+1]); exc++; for(i=1;i<=n;i++) cout<<nilai[i]<<" "; cout<<endl; } } if(exc==0) cout<<"Tidak ada eksekusi berlangsung...\n"; cout<<"Akhir looping ke : "<<loop; cout<<"\n----------------------------\n\n"; getch(); } cout<<"\n\nUrutan Ascending data :\n"; for(i=1;i<=n;i++) cout<<nilai[i]<<" "; } else if(jawab=='D'||jawab=='d') { for(loop=1;loop<=n;loop++) { cout<<"Looping ke : "<<loop; cout<<endl; exc=0; for(j=1;j<n;j++) { if(nilai[j]<nilai[j+1]) { swap(nilai[j],nilai[j+1]); exc++; for(i=1;i<=n;i++) cout<<nilai[i]<<" "; cout<<endl; } } if(exc==0) cout<<"\nTidak ada eksekusi berlangsung...\n"; cout<<"Akhir looping ke : "<<loop; cout<<"\n----------------------------\n\n"; getch(); } cout<<"\n\nUrutan Descending data :\n"; for(i=1;i<=n;i++) cout<<nilai[i]<<" "; } else { salah(); bubble_sort(); }

Page 182: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 11 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

tanya(); } void swap(int &value1,int &value2) { int holdValue=value1; value1=value2; value2=holdValue; } void tanya() { cout<<"\n\nProgram telah selesai"; cout<<"\nAnda ingin mengulang? Y/N : "; cin>>jawab; if(jawab=='Y'||jawab=='y') menu(); else if(jawab=='N'||jawab=='n') { cout<<setw(50)<<"\n\n\t========================="; cout<<setw(50)<<"\n\t| Searching And Sorting |"; cout<<setw(50)<<"\n\t|-----------------------|"; cout<<setw(50)<<"\n\t| Oleh : Tim Dosen |"; cout<<setw(50)<<"\n\t========================="; cout<<setw(50)<<"\n\t Universitas Mercubuana\n"; } else { salah(); tanya(); } } void salah() { cout<<"\n\n\tFatal Error"; cout<<"\n\tInput unrecognized"; cout<<"\n\tSystem back to the last action"; cout<<"\n\tPress any key to continue..."; getch(); } Tree #include <stdio.h> #include <conio.h> typedef struct Node{ int data; Node *kiri; Node *kanan; }; void tambah(Node **root,int databaru){ if((*root) == NULL){ Node *baru;

Page 183: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 12 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

baru = new Node; baru->data = databaru; baru->kiri = NULL; baru->kanan = NULL; (*root) = baru; (*root)->kiri = NULL; (*root)->kanan = NULL; printf("Data bertambah!"); } else if(databaru < (*root)->data) tambah(&(*root)->kiri,databaru); else if(databaru > (*root)->data) tambah(&(*root)->kanan,databaru); else if(databaru == (*root)->data) printf("Data sudah ada!"); } void preOrder(Node *root){ if(root != NULL){ printf("%d ",root->data); preOrder(root->kiri); preOrder(root->kanan); } } void inOrder(Node *root){ if(root != NULL){ inOrder(root->kiri); printf("%d ",root->data); inOrder(root->kanan); } } void postOrder(Node *root){ if(root != NULL){ postOrder(root->kiri); postOrder(root->kanan); printf("%d ",root->data); } } void main(){ int pil,c; Node *pohon,*t; pohon = NULL; do{ clrscr(); int data; printf("MENU\n"); printf("1. Tambah\n"); printf("2. Lihat pre-order\n"); printf("3. Lihat in-order\n"); printf("4. Lihat post-order\n"); printf("5. Exit\n");

Page 184: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 13 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

printf("Pilihan : "); scanf("%d",&pil); switch(pil){ case 1: printf ("Data baru : "); scanf("%d",&data); tambah(&pohon,data); break; case 2: if(pohon!=NULL) preOrder(pohon); else printf("Masih kosong!"); break; case 3: if(pohon!=NULL) inOrder(pohon); else printf("Masih kosong!"); break; case 4: if(pohon!=NULL) postOrder(pohon); else printf("Masih kosong!"); break; } getch(); }while(pil!=5); } Output Program Tambah Data: MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 1 Data baru : 5 Data Bertambah MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 1 Data baru : 2 Data Bertambah MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 1 Data baru : 3 Data Bertambah MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order

Page 185: fasilkom.mercubuana.ac.idfasilkom.mercubuana.ac.id/wp-content/uploads/2017/10/Algoritma-dan... · 2014 2 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning Tim Dosen Pendahuluan

2014 14 Algoritma Pemrog. & Strukdata PusatBahan Ajar dan eLearning   Tim Dosen http://www.mercubuana.ac.id

 

5. Exit Pilihan : 1 Data baru : 8 Data Bertambah Output Program Pre -Order: MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 2 5 2 3 8 Output Program In-Order: MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 3 2 3 5 8 Output Program Post-Order: MENU 1. Tambah 2. Lihat pre-order 3. Lihat in-order 4. Lihat post-order 5. Exit Pilihan : 4 3 2 8 5

 

Daftar Pustaka 1. Pengantar Struktur Data dan Algoritma, Bambang Wahyudi, Penerbit Andi Yogyakarta,

Edisi 1, 2004 2. Struktur Data dengan C, Paulus Bambangwirawan Dipl.Inf, Penerbit Andi Yogyakarta,

Edisi 1, 2004 3. Pengantar Algoritma dengan Bahasa C, Thompson Susabda Ngoen, Penerbit

Salemba Teknika, Edisi 1, 2004 4. Pemrograman C++, Abdul Kadir, Penerbit Andi Yogyakarta, Edisi 1, 2002 5. Struktur Data dengan C, C++, Moh. Sjukani, Mitra Wacana Media, Edisi 4