Kadal Kebon

Pertemuan 1
Struktur Data adalah : suatu koleksi atau kelompok data
yang dapat dikarakteristikan oleh organisasi serta operasi
yang didefinisikan terhadapnya.
Pemakaian Struktur Data yang tepat didalam proses
STRUKTUR DATA
pemrograman, akan menghasilkan Algoritma yang lebih
jelas dan tepat sehingga menjadikan program secara
keseluruhan lebih sederhana.
Pada garis besarnya, Data dapat dikategorikan menjadi :
A. Type Data Sederhana / Data Sederhana
Terdiri dari :
1. Data Sederhana Tunggal
Misalnya : Integer, Real/Float, Boolean dan
Character
2. Data Sederhana Majemuk
Misalnya : String
B. Struktur Data
Terdiri dari :
1. Struktur Data Sederhana
Misalnya Array dan Record
2. Struktur Data Majemuk
Terdiri dari :
a. Linier
Misalnya : Stack, Queue dan Linear Linked List.
b. Non Linier
Misalnya : Pohon (Tree), Pohon Biner (Binary
Tree), Pohon Cari Biner (Binary Search Tree),
General Tree serta Graph.
1. INTEGER
Merupakan Bilangan Bulat dan tidak mengandung
pecahan. seperti : ...-3,-2,-1,0,1,2,3,....
Type data Integer
Type Range Ukuran
TYPE DATA SEDERHANA
(Dalam Program C++)
(Byte)
Integer - 32768..32767 2
Long - 2147483648..2147483647 4
2. FLOAT
Type data yang merupakan bilangan pecahan.
Jenis Data float ditulis dgn menggunakan
titik(koma) desimal.
Misalnya : 0.32 4,35 -131.128
Type Real dapat juga ditulis dengan Rumus :
M * Re = X
M = Pecahan, R = Radix,
e = Exponen, X = Hasil Bilangan,
Misalnya : 3.2 * 10-1 = 0.32
4.35 * 102 = 435
Type data FLOAT
Type Range Ukuran
(Byte)
Float 3.4 x 10 -38 s/d 3.4 x10 +38 4
Double 1.7 x 10 -308 s/d 1.7x10 +308 8
Long Double 3.4 x 10 -4932 s/d 1.1x10 + 4932 10
3. BOOL ATAU LOGICAL
Type data yang hanya mempunyai dua bentuk keluaran
yaitu nilai True dan False (Benar dan Salah) yang
dinyatakan dengan 1 dan 0, Sehingga satuan data yang
terpakai cukup satu bit saja. Operator yang digunakan
adalah : And, Or dan Not
Input NOT (!) AND (&&) OR (||)
A B C !A !B !C A&&B&&C A||B||C
0 0 0 1 1 1 0 0
0 0 1 1 1 0 0 1
0 1 0 1 0 1 0 1
0 1 1 1 0 0 0 1
1 0 0 0 1 1 0 1
1 0 1 0 1 0 0 1
1 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1
4. CHARACTER
Type data yang terdiri dari aksara (simbol) yang
meliputi digit numerik, character alfabetik dan spesial
character. Untuk menuliskan tipe char, karakter perlu
ditulis di dalam tanda petik tunggal ( ‘ )
Contoh :
‘A’ karakter berupa huruf A
‘1’ karakter berupa angka 1
‘*’ karakter simbol *
5. STRING
Merupakan type data majemuk yang terbentuk dari
kumpulan character sebanyak 256 (default) dengan
jangkauan niai 0 - 255. Kumpulan character yang
digunakan untuk membentuk String dinamakan alfabet.
Pemberian nilai String diapit dengan tanda petik ganda (“)
Bentuk umum penulisan tipe data ini adalah :
tipe_data pengenal [panjang] ;
pengenal = nama variabel
panjang = bilangan bulat yg menunjukan jumlah karakter
Contoh : char nama[15] ;
Fungsi pada Operasi STRING
1. Strcpy()
untuk menyalin nilai string.
2. Strcat()
untuk menggabungkan nilai string.
3. Strcmp()
untuk membandingkan 2 nilai string.
4. Strlen()
untuk mengetahui panjang nilai string.
5. Strchr ()
untuk mencari nilai karakter dalam string.
Operator
Aritmatika
Keterangan
pow Pangkat
sqrt Menghitung akar
Operator Dalam Bahasa C++
% Sisa hasil bagi (modulus)
* , / Perkalian, Pembagian
+ , - Penjumlahan, Pengurangan
Operator Pemberi
Nilai Aritmatika
Keterangan
* = Perkalian
/ = Pembagian
% = Sisa hasil bagi
Operator Dalam Bahasa C++
+ = Penjumlahan
- = Pengurangan
Operator Unary Keterangan
+ Tanda Plus
- Tanda Minus
Operator Dalam Bahasa C++
Operator
Penambah dan
Pengurang
Keterangan
++ Penambahan
-- Pengurangan
Operator
Relasi
Keterangan
= Sama dengan (assignment)
!= Tidak sama dengan
> Lebih besar
Operator Dalam Bahasa C++
< Lebih kecil
== Sama dengan (bukan assignment)
>= Lebih besar atau sama dengan
<= Lebih kecil atau sama dengan
Operator
Logika
Keterangan
&& Dan (AND)
|| Atau (OR)
! Bukan (NOT)
Operator Dalam Bahasa C++
Operator
Bitwise
Keterangan
~ NOT
<< Shift Left
>> Shift Right
Operator Dalam Bahasa C++
& AND
^ XOR
| OR
Bermanfaat untuk mengelompokkan sejumlah data
dengan tipe data yang berlainan.
Contoh :
struct data_pegawai
{
TYPE TERSTRUKTUR
(Dalam Program C++)
int nip;
char nama[25];
char alamat[40];
}
Operator
Aritmatika
Keterangan
pow Pangkat
sqrt Menghitung akar
Operator Dalam Bahasa C++
% Sisa hasil bagi (modulus)
* , / Perkalian, Pembagian
+ , - Penjumlahan, Pengurangan
Operator Pemberi
Nilai Aritmatika
Keterangan
* = Perkalian
Operator Dalam Bahasa C++
/ = Pembagian
% = Sisa hasil bagi
+ = Penjumlahan
- = Pengurangan
Operator Unary Keterangan
+ Tanda Plus
- Tanda Minus
Operator Dalam Bahasa C++
Operator
Penambah dan
Pengurang
Keterangan
++ Penambahan
-- Pengurangan
Operator
Relasi
Keterangan
= Sama dengan (assignment)
!= Tidak sama dengan
Operator Dalam Bahasa C++
> Lebih besar
< Lebih kecil
== Sama dengan (bukan assignment)
>= Lebih besar atau sama dengan
<= Lebih kecil atau sama dengan
Operator
Logika
Keterangan
&& Dan (AND)
Operator Dalam Bahasa C++
|| Atau (OR)
! Bukan (NOT)
Operator
Bitwise
Keterangan
~ NOT
<< Shift Left
Operator Dalam Bahasa C++
>> Shift Right
& AND
^ XOR
| OR
Bermanfaat untuk mengelompokkan sejumlah data
dengan tipe data yang berlainan.
Contoh :
struct data_pegawai
{
TYPE TERSTRUKTUR
(Dalam Program C++)
int nip;
char nama[25];
char alamat[40];
}
Pertemuan 2
ARRAY
DIMENSI 1 & 2
Array atau Larik merupakan Struktur Data Sederhana
yang dapat didefinisikan sebagai pemesanan alokasi
memory sementara pada komputer.
Array dapat didefinisikan sebagai suatu himpunan hingga
elemen yang terurut dan homogen.
Terurut : Dapat diartikan bahwa elemen tersebut dapat
diidentifikasi sebagai elemen pertama, elemen kedua dan
seterusnya sampai elemen ke-n.
Homogen : Adalah bahwa setiap elemen dari sebuah
Array tertentu haruslah mempunyai type data yang sama.
Sebuah Array dapat mempunyai elemen yang seluruhnya
berupa integer atau character atau String bahkan dapat
pula terjadi suatu Array mempunyai elemen berupa Array.
Karakteristik Array :
1. Mempunyai batasan dari pemesanan alokasi memory
(Bersifat Statis)
2. Mempunyai Type Data Sama (Bersifat Homogen)
3. Dapat Diakses Secara Acak
3 Hal yang harus diketahui dalam mendeklarasikan
array :
a. Type data array
b. Nama variabel array
c. Subskrip / index array
Jenis Array (yang akan dipelajari) adalah :
a. Array Dimensi Satu (One Dimensional Array)
b. Array Dimensi Dua (Two Dimensional Array)
c. Array Dimensi Tiga (Thee Dimensional Array)
1. ARRAY DIMENSI SATU (One Dimensional Array)
Dapat disebut juga dengan istilah vektor yang
menggambarkan data dalam suatu urutan
Deklarasi : Type_Data Nama_Variabel [index]
Misalnya : int A[5];
Penggambaran secara Logika :
A[1] A[2] A[3] A[4] A[5]
Elemen Array
0 1 2 3 4
Subscript / Index
• Contoh aplikasi untuk Array dimensi 1 adalah seperti
program input bilangan dibawah ini
input 5 bilangan genap : bilangan 1 = 45
bilangan 2 = 50
bilangan 3 = 100
bilangan 4 = 75
bilangan 5 = 30
Dengan hasil output sebagai berikut :
45 50 100 75 30
#include <iostream.h>
#include <conio.h>
void main()
{
float bil [5];
clrscr;
cout<<"Masukkan 5 bilangan genap : "<<endl;
for (int i = 0; i < 5; i++)
{
cout<< i + 1 <<" : ";
cin>> bil[i];
cout<<endl;
}
cout<<“5 bilangan genap yang dimasukkan : "<<endl;
for (int i = 0; i < 5; i++)
cout<<" "<<bil[i];
getch();
}
Rumus untuk menentukan jumlah elemen dalam Array :
np
(Elemen Array)
i=1
p = Perkalian dari elemen sebelumnya
(untuk array dimensi dua & tiga)
Contoh :
Suatu Array A dideklarasikan sbb :
int A[10]; maka jumlah elemen Array dimensi satu tersebut
adalah = 10
Rumus : @A[i] = B + (i – 1) * L
Dimana : @A[i] : Posisi Array yg dicari
B : Posisi awal index di memory komputer
i : Subkrip atau indeks array yg dicari
L : Ukuran / Besar memory suatu type data
PEMETAAN (MAPPING)
ARRAY DIMENSI SATU
KE STORAGE
Contoh :
Suatu Array A dideklarasikan sebagai berikut :
int A[5]; dengan alamat awal index berada di 0011 (H) dan
ukuran memory type data integer = 2
Tentukan berapa alamat array A[3] ?
Rumus : @A[i] = B + (i – 1) * L
Diketahui :
@A[i] = A[3]
B = 0011 (H)
i = 3
Penyelesaian :
A[3] = 0011(H) + (3 – 1) * 2
= 0011(H) + 4 (D)
= 0011(H) + 4 (H)
L = 2
= 0015(H) 4 Desimal = 4 Hexa
0011
A[1] A[2] A[3] A[4] A[5]
0013 0015 0017 0019
0 1 2 3 4
0 1 2 3 4 5 6 7
21d2 21d4 21d6 21d8 21da 21dc 21de 21e0
indeks
value
alamat
Contoh Penerapan
Array Dimensi 1 Pada Program C++
%x adalah hexadesimal
2. ARRAY DIMENSI DUA (Two Dimensional Array)
Deklarasi : Type_Data Nama_Variabel [Index1] [index2];
Misal : int A[3][2];
Sering digunakan dalam menterjemahkan matriks
pada pemrograman.
Penggambaran secara Logika : 0 1
0
1
2
• Contoh aplikasi untuk Array dimensi 2 adalah seperti
program input IPK mahasiswa dengan hasil output
seperti berikut :
Nama Mahasiswa IPK
Abdillah 3.50
Budiman 2.76
Indah 3.25
Khalilah 2.81
Nadya 2.93
Menentukan jumlah elemen dalam Array dimensi dua:
np
(Elemen array)
i=1
Contoh :
p = Perkalian dari elemen sebelumnya
(untuk array dimensi dua & tiga)
Suatu Array X dideklarasikan sbb :
int X[4][3];
maka jumlah elemen Array dimensi dua tersebut adalah :
(4) * (3) = 12
PEMETAAN (MAPPING)
ARRAY DIMENSI DUA
KE STORAGE
Terbagi Dua cara pandang (representasi) yang berbeda :
1. Secara Kolom Per Kolom (Coloumn Major Order/CMO)
@M[i][j] = M[0][0] + {(j - 1) * K + (i - 1)} * L
2. Secara Baris Per Baris (Row Major Order / RMO)
Keterangan :
@M[i][j] = Posisi Array yg dicari, M[0][0] = Posisi alamat awal index
array,i = Baris, j = kolom, L = Ukuran memory type data
K = Banyaknya elemen per kolom, N = Banyaknya elemen per baris
@M[i][j] = M[0][0] + {(i - 1) * N + (j - 1)} * L
Misal : int M[3][2];
(Array dengan 3 Baris & 2 Kolom)
Berdasarkan Cara pandang :
1. Kolom Per Baris (Row Major Order / RMO)
Penggambaran secara logika
0 1
0
1
2
M[0,0] M[0,1] M[1,0] M[1,1] M[2,0] M[2,1]
M[0,0] M[1,0] M[2,0] M[0,1] M[1,1] M[2,1]
2. Baris Per Kolom (Coloumn Major Order / CMO)
Jumlah elemen per baris = 2
Jumlah elemen per kolom = 3
Suatu Array X dideklarasikan sebagai berikut :
Float X[4][3], dengan alamat index X[0][0] berada di 0011(H)
dan ukuran type data float/real = 4
Tentukan berapa alamat array X[3][2] berdasarkan cara
pandang baris dan kolom ?
Contoh Pemetaan :
0 1 2
index
0011(H)
?
0
1
2
3
index
Penyelesaian :
Secara Baris Per Baris (Row Major Oder / RMO)
@M[i][j] = @M[0][0] + {(i - 1) * N + (j - 1)} * L
X[3][2] = 0011(H) + {(3 – 1) * 3 + (2 – 1)} * 4
= 0011(H) + 28 (D) 1C (H)
= 0011(H) + 1C (H)
Lanjutan Contoh Pemetaan :
= 002D(H)
Penyelesaian :
Secara Kolom Per Kolom (Coloumn Major Oder / CMO)
@M[i][j] = @M[0][0] + {(j - 1) * K + (i - 1)} * L
X[3][2] = 0011(H) + {(2 – 1) * 4 + (3 – 1)} * 4
= 0011(H) + 24 (D) 18 (H)
= 0011(H) + 18 (H)
Lanjutan Contoh Pemetaan :
= 0029(H)
Contoh Penerapan
Array Dimensi 2 Pada Program C++
Pertemuan 3
ARRAY
DIMENSI BANYAK
3. ARRAY DIMENSI TIGA (Three Dimensional Array)
Digunakan untuk mengelola data dalam bentuk 3 dimensi
atau tiga sisi.
Deklarasi :
Type_Data Nama_Variabel [index1] [ndex2] [index3];
Misal : int A [3][4][2];
Penggambaran secara Logika :
0
1
2
0 1 2 3 0
1
• Contoh aplikasi untuk Array dimensi 3 adalah seperti
program input data mahasiswa per kelas dan per
jurusan
0
1
2
0 1 2 3 0
1
Menentukan jumlah elemen dalam Array dimensi 3 :
np
(index array)
i=1
p = Perkalian dari statemen sebelumnya
Contoh :
Suatu Array X dideklarasikan sbb :
int A [3][4][2]; maka jumlah elemen Array dimensi tiga
tersebut adalah :
(3) * (4) * (2) = 24
PEMETAAN (MAPPING)
ARRAY DIMENSI TIGA
KE STORAGE
Rumus :
@M[n][m][p] = M[0][0][0] + {((n-1)*(index1)) + ((m-1)*(index2))
+ ((p-1)*(index3)}* L
Contoh :
Suatu Array A dideklarasikan sebagai berikut :
int A [2][4][3], dengan alamat awal index A[0][0][0] berada di
0011(H) dan ukuran type data int = 2 Tentukan berapa alamat
array di A[2][3][2] ?
Contoh Pemetaan :
Penyelesaian :
1. Tentukan jumlah elemen array A [2][4][3]
= (2) * (4) * (3)
= 24
2. @M[n][m][p] = M[0][0][0]+{((n-1)*(index1))+((m-1)*(index2))
+ ((p-1)*(index3)}* L
A[2][3][2] = 0011(H) + {((2–1) * 4 * 3) + ((3-1) * 3) + (2-1)} * 2
= 0011(H) + {12 + 6 + 1 } * 2
= 0011(H) + 38 (D) 26 (H)
= 0011(H) + 26 (H)
= 0037(H)
Tringular Array dapat merupakan Upper Tringular
(seluruh elemen di bawah diagonal utama = 0),
ataupun Lower Tringular (seluruh elemen di atas
diagonal utama = 0).
Dalam Array Lower Tringular dengan N baris, jumlah
TRINGULAR ARRAY
(ARRAY SEGITIGA)
maksimum elemen <> 0 pada baris ke-I adalah = I,
karenanya total elemen <> 0, tidak lebih dari
NS
I = N(N+1) / 2
I=1
Gambar (a) Upper Triangular Array
(b) Lower Triangular Array
Contoh :
Diketahui suatu array segitiga atas memiliki 3 baris dan
kolom, tentukan berapakah jumlah elemen yang bukan nol
pada array tersebut.
I = N(N+1) / 2
I = 3 (3+1) / 2
= 12 / 2
= 6
10 20 30
0 40 50
0 0 60
5 10 15
0 20 25
0 0 30
Contoh bentuk array nya adalah seperti dibawah ini :
Dan lain-lain
Suatu Array Upper Tringular dan Array Lower Tringular
dapat dengan order yang sama, dapat disimpan sebagai
suatu array dengan order yang berbeda, Contohnya :
Suatu Array yang sangat banyak elemen nol-nya,
contohnya adalah Array A pada Gambar berikut :
SPARSE ARRAY
(ARRAY JARANG)
Pertemuan 4
KONSEP POINTER DAN LINKED LIST
Untuk mengolah data yang banyaknya tidak bisa
ditentukan sebelumnya, maka disediakan satu fasilitas
yang memungkinan untuk menggunakan suatu perubah
yang disebut dengan perubah dinamis (Dinamic variable)
Perubah Dinamis (Dinamic variable)
Suatu perubah yang akan dialokasikan hanya pada saat
diperlukan, yaitu setelah program dieksekusi.
Perbedaan Perubah Statis & Dinamis
Pada perubah statis, isi Memory pada lokasi tertentu
(nilai perubah) adalah data sesungguhnya yang akan
diolah. Pada perubah dinamis, nilai perubah adalah
alamat lokasi lain yang menyimpan data sesungguhnya.
Dengan demikian data yang sesungguhnya dapat
dimasukkan secara langsung.
Dalam hal cara pemasukkan data dapat diilustrasikan
seperti dibawah ini.
DEKLARASI POINTER
Pointer digunakan sebagai penunjuk ke suatu alamat
memori
Dalam pemrograman C++, Type Data Pointer
dideklarasikan dengan bentuk umum :
Type Data *Nama Variabel;
Type Data dapat berupa sembarang type data, misalnya
char, int atau float. Sedangkan Nama veriabel merupakan
nama variabel pointer
Contoh penggunaan pointer dalam program C++:
Void main()
{
int x,y,*z;
x = 75; //nilai x = 75
y = x; //nilai y diambil dari nilai x
z = &x; //nilai z menunjuk kealamat pointer dari nilai
x
getch();
}
LINKED LIST (LINKED LIST)
Salah satu Struktur Data Dinamis yang paling
sederhana adalah Linked List atau Struktur Berkait
atau Senarai Berantai, yaitu suatu kumpulan komponen
yang disusun secara berurutan dengan bantuan
Pointer.
Linked List (Senarai Berantai) disebut juga dengan
Senarai Satu Arah (One-Way List). Masing-masing
komponen dinamakan dengan Simpul (Node).
Perbedaan Karakteristik
Array dan Linked List
Setiap simpul dalam suatu Linked List terbagi menjadi dua
bagian,yaitu :
1. Medan Informasi
Berisi informasi yang akan disimpan dan diolah.
2. Medan Penyambung (Link Field)
Berisi alamat berikutnya. Bernilai 0, Jika Link tersebut
tidak menunjuk ke Data (Simpul) lainnya. Penunjuk ini
disebut Penunjuk Nol.



Bentuk Node
Single Linked List non Circular
• Single : field pointer-nya hanya satu dan satu arah,pada
akhir node pointernya menunjuk NULL
• Linked List : node-node tersebut saling terhubung satu
sama lain.
Menempati alamat memori tertentu
• Setiap node pada linked list mempunyai field yang berisi
pointer ke node berikutnya, dan juga memiliki field yang
berisi data.
• Node terakhir akan menunjuk ke NULL yang akan
digunakan sebagai kondisi berhenti pada saat
pembacaan isi linked list.
Pembuatan
Single Linked List non Circular
Deklarasi Node :
typedef struct TNode{
int data;
TNode *next;
};
Keterangan:
• Pembuatan struct bernama TNode yang berisi 2 field,
yaitu field data bertipe integer dan field next yang
bertipe pointer dari TNode
• Setelah pembuatan struct, buat variabel head yang
bertipe pointer dari TNode yang berguna sebagai kepala
linked list.
• Digunakan perintah new untuk mempersiapkan sebuah
node baru berserta alokasi memorinya, kemudian node
tersebut diisi data dan pointer nextnya ditunjuk ke NULL.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
Single Linked List non Circular
Menggunakan Head
• Dibutuhkan satu buah variabel pointer : head yang akan
selalu menunjuk pada node pertama
Deklarasi Pointer Penunjuk Head Single Linked List
• Manipulasi linked list tidak dapat dilakukan langsung ke
node yang dituju, melainkan harus menggunakan suatu
pointer penunjuk ke node pertama (Head) dalam linked
list
• Deklarasinya sebagai berikut:
TNode *head;
Fungsi Inisialisasi Single Linked List
void init()
{
head = NULL;
}
Function untuk mengetahui kondisi Single Linked List
• Jika pointer head tidak menunjuk pada suatu node maka
kosong
int isEmpty()
{
if (head == NULL) return 1;
else return 0;
}
Menambah Node di Depan
• Penambahan node baru akan dikaitan di node paling
depan, namun pada saat pertama kali (data masih
kosong), maka penambahan data dilakukan dengan
cara: node head ditunjukkan ke node baru tersebut.
• Prinsipnya adalah mengkaitkan node baru dengan head,
kemudian head akan menunjuk pada data baru tersebut
sehingga head akan tetap selalu menjadi data terdepan.
void insertDepan(int databaru)
{
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1)
{
head=baru;
head->next = NULL;
}
else
{
baru->next = head;
head = baru;
}
printf(”Data masuk\n”);
}


Menambah Node di Belakang
• Penambahan data dilakukan di belakang, namun pada
saat pertama kali, node langsung ditunjuk oleh head.
• Penambahan di belakang membutuhkan pointer bantu
untuk mengetahui node terbelakang. Kemudian,
dikaitkan dengan node baru.
• Untuk mengetahui data terbelakang perlu digunakan
perulangan.
void insertBelakang (int databaru)
{
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1) {
head=baru;
head->next = NULL;
}
else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next = baru;
}
printf("Data masuk\n“);
}


Menghapus Node di Depan
• Penghapusan node tidak boleh dilakukan jika keadaan
node sedang ditunjuk oleh pointer, maka harus
dilakukan penggunakan suatu pointer lain (hapus) yang
digunakan untuk menunjuk node yang akan dihapus,
barulah kemudian menghapus pointer hapus dengan
menggunakan perintah delete.
• Sebelum data terdepan dihapus, terlebih dahulu head
harus menunjuk ke node berikutnya agar list tidak putus,
sehingga node setelah head lama akan menjadi head
baru
• Jika head masih NULL maka berarti data masih kosong!
void hapusDepan ()
{
TNode *hapus;
int d;
if (isEmpty()==0){
if(head->next != NULL){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%d terhapus\n“,d);
} else cout<<"Masih kosong\n";
}

Menghapus Node di Belakang
• Membutuhkan pointer bantu dan hapus. Pointer hapus
digunakan untuk menunjuk node yang akan dihapus,
pointer bantu untuk menunjuk node sebelum node yang
dihapus yang akan menjadi node terakhir.
• Pointer bantu digunakan untuk menunjuk ke nilai NULL.
Pointer bantu selalu bergerak sampai sebelum node
yang akan dihapus, kemudian pointer hapus diletakkan
setelah pointer bantu. Selanjutnya pointer hapus akan
dihapus, pointer bantu akan menunjuk ke NULL.
void hapusBelakang(){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != NULL){
bantu = head;
while(bantu->next->next!=NULL){
bantu = bantu->next;
}
hapus = bantu->next;
d = hapus->data;
bantu->next = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%d terhapus\n“,d);
} else printf(“Masih kosong\n“);
}

Function untuk menghapus semua elemen
Linked List
void clear()
{
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL)
{
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
}
Menampilkan / Membaca
Isi Linked List
• Linked list ditelusuri satu-persatu dari awal sampai akhir
node. Penelusuran dilakukan dengan menggunakan
pointer bantu, karena pointer head yang menjadi tanda
awal list tidak boleh berubah/berganti posisi.
• Penelusuran dilakukan terus sampai ditemukan node
terakhir yang menunjuk ke nilai NULL.
Jika tidak NULL, maka node bantu akan berpindah ke
node selanjutnya dan membaca isi datanya dengan
menggunakan field next sehingga dapat saling berkait.
• Jika head masih NULL berarti data masih kosong!
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<<bantu->data<<" ";
bantu=bantu->next;
}
printf(“\n”);
} else printf(“M Masih kosong\n“);
}
• Dibutuhkan dua variabel pointer : head dan tail
• Head selalu menunjuk pada node pertama, sedangkan
tail selalu menunjuk pada node terakhir.
• Kelebihan dari Single Linked List dengan Head & Tail
adalah pada penambahan data di belakang, hanya
Single Linked List non Circular
Menggunakan Head dan Tail
dibutuhkan tail yang mengikat node baru saja tanpa
harus menggunakan perulangan pointer bantu.
Inisialisasi Linked List
TNode *head, *tail;
Fungsi Inisialisasi Linked List
void init(){
head = NULL;
tail = NULL;
}
Function untuk mengetahui kondisi LinkedList kosong / tidak
int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}
void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=tail=baru;
Menambah Node di Depan
Dengan Head dan Tail
tail->next=NULL;
}
else {
baru->next = head;
head = baru;
}
printf(”Data masuk\n”);
}


void tambahBelakang(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
Menambah Node di Belakang
Dengan Head dan Tail
tail=baru;
tail->next = NULL;
}
else {
tail->next = baru;
tail=baru;
}
printf("Data masuk\n“);
}


• Penghapusan node tidak boleh dilakukan jika keadaan
node sedang ditunjuk oleh pointer, maka harus
dilakukan penunjukkan terlebih dahulu dengan pointer
hapus pada head, kemudian dilakukan pergeseran head
ke node berikutnya sehingga data setelah head menjadi
Menghapus Node di Depan
(Dengan Head dan Tail)
head baru, kemudian menghapus pointer hapus dengan
menggunakan perintah delete.
• Jika tail masih NULL maka berarti list masih kosong!
void hapusDepan(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head!=tail){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = tail->data;
head=tail=NULL;
}
printf(“%d terhapus\n“,d);
} else printf("Masih kosong\n“);
}

• Penghapusan node tidak boleh dilakukan jika keadaan
node sedang ditunjuk oleh pointer, maka harus
dilakukan penunjukkan terlebih dahulu dengan variabel
hapus pada tail. Jika tail masih NULL maka berarti list
masih kosong!
Menghapus Node di Belakang
(Dengan Head dan Tail)
• Dibutuhkan pointer bantu untuk membantu pergeseran
dari head ke node berikutnya sampai sebelum tail,
sehingga tail dapat ditunjukkan ke bantu, dan bantu
tersebut akan menjadi tail yang baru.
• Setelah itu hapus pointer hapus dengan menggunakan
perintah delete.
void hapusBelakang(){
TNode *bantu,*hapus;
int d;
if (isEmpty()==0){
bantu = head;
if(head!=tail){
while(bantu->next!=tail){
bantu = bantu->next;
}
hapus = tail;
tail=bantu;
d = hapus->data;
delete hapus;
tail->next = NULL;
}else {
d = tail->data;
head=tail=NULL;
}
cout<<d<<" terhapus\n";
} else cout<<"Masih kosong\n";
}
null
Function untuk menghapus semua elemen
LinkedList dengan HEAD & TAIL
void clear()
{
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL)
{
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
tail = NULL;
}
Pertemuan 5
STACK atau TUMPUKAN
Merupakan bentuk khusus dari Linier List yang pemasukan
dan penghapusan elemennya hanya dapat dilakukan pada
satu posisi, yaitu posisi akhir dari List (Top)
Prinsip Stack adalah LAST-IN-FIRST-OUT (LIFO).
STACK (TUMPUKAN)
Klik untuk
Ilustrasi Stack
• ISEMPTY
Untuk memeriksa apakah stack kosong
• ISFULL
Untuk memeriksa apakah stack sudah penuh
• PUSH
Untuk menambahkan item pada posisi paling atas
OPERASI STACK
(TOP)
• POP
Untuk menghapus item paling atas (TOP)
• CLEAR
Untuk mengosongkan stack
Deklarasi MAX_STACK
#define MAX_STACK 5
Deklarasi STACK dengan struct dan array data
typedef struct STACK{
STACK PADA ARRAY
int top;
int data[5];
};
Deklarasi variabel stack dari struct
STACK tumpuk;
• Pada mulanya isi top dengan
-1, karena array dalam
C/C++ dimulai dari 0, berarti
stack adalah KOSONG
• TOP adalah variabel
penanda dalam STACK yang
Inisialisasi
4 MAX_STACK
void inisialisasi ()
{
tumpuk.top = -1
}
menunjukkan elemen teratas
Stack.
• TOP of STACK akan selalu
bergerak hingga mencapai
MAX of STACK sehingga
menyebabkan stack PENUH TOP = -1
3
2
1
0
Fungsi IsEmpty
• Digunakan untuk
memeriksa apakah
stack masih dalam
kondisi kosong
• Dengan cara memeriksa
TOP of STACK.
int IsEmpty ()
{
if (tumpuk.top == -1
return 1;
else
return 0;
}
Jika TOP masih = -1
maka berarti stack
masih kosong
4
3
2
1
0
TOP = -1
MAX_STACK
Fungsi IsFull
• Digunakan untuk memeriksa apakah kondisi stack
sudah penuh
• Dengan cara memeriksa TOP of Stack.
Jika TOP of STACK = MAX_STACK-1 maka FULL
(Penuh).
Jika TOP of STACK < MAX_STACK-1 maka belum
penuh
int IsFull ()
{
if (tumpuk.top == MAX_STACK-1
return 1;
else
return 0;
}
E
D
C
B
A
4
3
2
1
0
TOP = 4
MAX_STACK
Fungsi PUSH
• Digunakan untuk memasukkan elemen ke dalam stack
dan selalu menjadi elemen teratas stack
• Dengan cara :
1. Menambah satu (increment) nilai TOP of
STACK setiap ada penambahan elemen
stack selama stack masih belum penuh
2. Isikan nilai baru ke stack berdasarkan indeks TOP
of STACK setelah ditambah satu (diincrement)
4 MAX_STACK
void push (char d[5])
{
tumpuk.top++
strcpy(tumpuk.data[tumpuk.top],d);
}
4 MAX_STACK
3
2
1
0
TOP = -1
A
3
2
1
0 TOP = TOP + 1
= -1 + 1
= 0
PUSH ELEMEN A
Fungsi POP
• Digunakan untuk menghapus elemen yang berada pada
posisi paling atas dari stack.
• Dengan cara :
1. Ambil dahulu nilai elemen teratas stack dengan
mengakses TOP of STACK.
2. Tampilkan nilai yang akan diambil.
3. Lakukan decrement nilai TOP of STACK
sehingga jumlah elemen stack berkurang 1
4
void pop ()
{
printf(“Data yg di POP = %s\n”, tumpuk.data[tumpuk.top]);
tumpuk.top--;
}
4
MAX_STACK Data yg di POP = C
B
A
3
2
1
0
C
B
A
3
2
1
0
TOP = 2
TOP = TOP - 1
= 2 - 1
= 1
Fungsi CLEAR
• Digunakan untuk mengosongkan stack / membuat stack
hampa sehingga Top pada Stack berada kembali di
posisi Top = -1
void clear ()
{
tumpuk.data=tumpuk.top=-1
printf(“Data clear”);
}
4
3
2
1
0
Pertemuan 6
QUEUE (ANTREAN)
Struktur Data Antrean (Queue) adalah suatu bentuk
khusus dari List Linier dengan operasi pemasukan data
hanya diperbolehkan pada salah satu sisi, yang disebut
sisi Belakang / ekor (Tail) dan operasi penghapusan
hanya diperbolehkan pada sisi lainnya yang disebut sisi
Depan / kepala (Head) dari LinkedList.
PENGERTIAN QUEUE
(ANTREAN)
Prinsip Antrean : FIFO (First In First Out)
FCFS (First Come First Serve)
“Yang Tiba lebih awal Maka akan dilayani Terlebih
Dahulu”
Deklarasi Queue
0 1 2 3 4 5 6 7 Max = 8
head = -1
tail = -1
• CREATE
Untuk menciptakan dan menginisialisasi Queue
Dengan cara membuat Head dan Tail = -1
• ISEMPTY
Untuk memeriksa apakah queue kosong
• ISFULL
Untuk memeriksa apakah queue sudah penuh
OPERASI QUEUE
• ENQUEUE
Untuk menambahkan item pada posisi paling belakang
• DEQUEUE
Untuk menghapus item dari posisi paling depan
• CLEAR
Untuk mengosongkan queue
• Digunakan untuk membentuk dan menunjukan awal
terbentuknya suatu Antrean / Queue
Fungsi Create
Void Create()
{
antrian.head = antrian.tail = -1
}
0 1 2 3 4 5 6 7 Max = 8
head = -1
tail = -1
Antrian pertama kali
Fungsi IsEmpty
• Untuk memeriksa apakah Antrian penuh atau kosong
• Dengan cara memeriksa nilai Tail, jika Tail = -1 maka
antrian kosong (empty)
• Head adalah tanda untuk kepala antrian (elemen
pertama dalam antrian) yang tidak akan berubah-ubah
• Pergerakan pada Antrian terjadi dengan penambahan
elemen Antrian kebelakang, yaitu menggunakan nilai
Tail
Int IsEmpty()
{
if (antrian.tail == -1)
return 1;
else
return 0;
}
0 1 2 3 4 5 6 7 Max = 8
head = -1
tail = -1
Antrian kosong
Karena tail = -1
Fungsi IsFull
• Untuk mengecek apakah Antrian sudah penuh
atau belum
• Dengan cara :
- Mengecek nilai Tail
- Jika tail = MAX-1 berarti antrian sudah penuh
(MAX-1 adalah batas elemen array dalam
program C++)
Int IsFull()
{
if (antrian.tail == Max-1)
return 1;
else
return 0;
}
5 10 35 20 15 30 40 25
0 1 2 3 4 5 6 7 Max = 8
head = 0
Antrian penuh karena
Head = 0
tail = max - 1
tail = 7
• Untuk menambahkan elemen ke dalam Antrian,
penambahan elemen selalu dilakukan pada
elemen paling belakang
• Penambahan elemen selalu menggerakan variabel
Tail dengan cara menambahkan Tail terlebih dahulu
Fungsi Enqueue

• Digunakan untuk menghapus elemen terdepan (head)
dari Antrian
• Dengan cara : menggeser semua elemen antrian
kedepan dan mengurangi Tail dgn 1. Penggeseran
dilakukan dengan menggunakan looping
Fungsi Dequeue

• Untuk menghapus elemen-elemen Antrian dengan
cara membuat Tail dan Head = -1
• Penghapusan elemen-elemen Antrian sebenarnya
tidak menghapus arraynya, namun hanya mengeset
Fungsi Clear
indeks pengaksesan-nya ke nilai -1 sehingga
elemen-elemen Antrian tidak lagi terbaca sehingga
mengembalikan antrian seperti keadaan semula
Antrian setelah di lakukan Clear
0 1 2 3 4 5 6 7 Max = 8
head = -1
tail = -1
Antrian kosong
Karena tail = -1
Pertemuan 9
STRUKTUR POHON (TREE)
Pohon atau Tree adalah salah satu bentuk Graph
terhubung yang tidak mengandung sirkuit.
Karena merupakan Graph terhubung, maka pada Pohon
(Tree) selalu terdapat Path atau Jalur yang
menghubungkan setiap simpul dalam dua pohon.
ISTILAH-ISTILAH DASAR
Pohon (Tree) dapat juga didefinisikan sebagai kumpulan
elemen yang salah satu elemennya disebut dengan Akar
(Root) dan sisa elemen lain (Simpul) yang terpecah
menjadi sejumlah himpunan yang saling tidak berhubungan
yang disebut dengan Subpohon (Subtree) atau cabang

1. Jika Pohon mempunyai Simpul sebanyak n, maka
banyaknya ruas atau edge adalah (n-1).
2. Mempunyai Simpul Khusus yang disebut Root, jika
Simpul tersebut memiliki derajat keluar >= 0, dan
derajat masuk = 0.
3. Mempunyai Simpul yang disebut sebagai Daun / Leaf,
Sifat utama Pohon Berakar
jika Simpul tersebut berderajat keluar = 0, dan
berderajat masuk = 1.
4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai
dari Root yang Levelnya = 1 sampai dengan Level ke - n
pada daun paling bawah. Simpul yang mempunyai Level
sama disebut Bersaudara atau Brother atau Stribling.
5. Pohon mempunyai Ketinggian atau Kedalaman atau
Height, yang merupakan Level tertinggi
6. Pohon mempunyai Weight atau Berat atau Bobot, yang
banyaknya daun (leaf) pada Pohon.
7. Banyaknya Simpul Maksimum sampai Level N adalah :
2 (N) - 1
8. Banyaknya Simpul untuk setiap Level I adalah :
N
Σ 2 ( I – 1)
I = 1
Hutan (Forest) adalah kumpulan Pohon yang tidak saling
berhubungan
Diketahui suatu bentuk Pohon Berakar T sebagai berikut :
Pohon Diatas Mempunyai :
a. Simpul sebanyak = 8 dan edge = n - 1 = 8 – 1 = 7
b. Root pada Pohon T diatas adalah Simpul P
c. Mempunyai daun (Leaf) = 4, yaitu = R, S, V dan W
d. Level (tingkatan) Pohon = 4 yaitu :
Level 1 = Simpul P
Level 2 = Simpul Q dan T
Level 3 = Simpul R, S dan U
Level 4 = Simpul V dan W
e. Ketinggian atau kedalaman = jumlah level = 4
f. Weight atau berat atau bobot = jumlah daun = 4
Dalam gambar Pohon T diatas dapat dibentuk 2 buah
hutan (forest), bila simpul P dihilangkan, yaitu :
Hutan 1 : Q,R,S
Hutan 2 : T,U,V,W
g. Banyaknya Simpul Maksimum yang dapat terbentuk
sampai Level 4 (bila simpul pada pohon dianggap
penuh) adalah : 2 (N) – 1
2 (4) – 1 = 16 – 1 = 15
h. Banyaknya Simpul maksimum untuk setiap Level I
(bila simpul pada pohon dianggap penuh) adalah :
Maksimum Simpul pada level 2 = 2 ( I – 1)
= 2 (2-1) = 2
Maksimum Simpul pada level 3 = 2 (3-1) = 4
Maksimum Simpul pada level 4 = 2 (4-1) = 2
Ada beberapa cara untuk menggambarkan bentuk pohon.
1. Cara Pertama
Merupakan cara yang paling banyak digunakan dan paling
mudah adalah dengan membuat gambar seperti pada
gambar diatas.
2. Cara Kedua
Dengan membuat Diagram Venn seperti dibawah ini
3. Cara Ketiga, Dengan menggunakan Notasi Kurung.
Berikut ini diberikan Notasi Kurung untuk Gambar pada
diagram Venn diatas.
Hasil : (P(Q(R,S)),T(U(V,W)))
4. Cara Keempat adalah menggunakan notasi Tingkat dan
Notasi Garis
Struktur ini biasanya digunakan untuk menyajikan data
yang mengandung hubungan hirarkial antara elemenelemennya.
Bentuk Pohon Berakar yang lebih mudah dikelola dalam
komputer adalah Pohon Biner (Binary Tree) yang lebih
dikenal sebagai Pohon Umum (General Tree) yang dapat
POHON BINAR (BINARY TREE)
didefinisikan sebagai kumpulan simpul yang mungkin
kosong atau mempunyai akar dan dua Subpohon yang
saling terpisah yang disebut dengan Subpohon Kiri /
cabang kiri (Left Subtree) dan Subpohon Kanan / cabang
kanan (Right Subtree).
Karakteristik Pohon Binar (Binary Tree) :
1. Setiap Simpul paling banyak hanya memiliki dua buah
anak
2. Derajat Tertinggi dari setiap Simpul adalah dua.
3. Dibedakan antara Cabang Kiri dan Cabang Kanan.
4. Dimungkinkan tidak mempunyai Simpul
Berikut ini diberikan contoh gambar Pohon Binar (Binary
Tree) dengan Cabang Kiri dan Cabang Kanan.
ISTILAH
PADA POHON BINER
• Pohon Biner Penuh
(Full Binary Tree)
Semua simpul (kecuali daun)
memiliki 2 anak dan tiap cabang
memiliki panjang ruas yang sama
A
B C
D E F G
• Pohon Biner Lengkap
(Complete Binary Tree)
Hampir sama dengan Pohon
Biner Penuh, semua simpul
(kecuali daun) memiliki 2 anak
tetapi tiap cabang memiliki
panjang ruas berbeda
A
B C
D E
• Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi
informasinya berbeda
A
B C
P
Q R
• Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang
sama
P
Q R
P
Q R
• Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu
anak / turunan kecuali daun
Deklarasi Pohon Biner
(Dengan Program C++)
Dalam setiap simpul selalu berisi dua buah Pointer untuk
menunjuk ke cabang Kiri dan cabang Kanan dan informasi
yang akan disimpan dalam simpul tersebut.

• Tree dapat dibuat dengan menggunakan linked list
secara rekursif.
• Linked list yang digunakan adalah double linked list non
circular
• Data yang pertama kali masuk akan menjadi node root.
Penyajian Pohon Binar
(Binary Tree)
• Data yang lebih kecil dari data node root akan masuk
dan menempati node kiri dari node root, sedangkan jika
lebih besar dari data node root, akan masuk dan
menempati node di sebelah kanan node root.
Bila diberikan untai HAKJCBL, maka proses untuk dapat
membentuk pohon biner dari untai diatas adalah :
1. Karakter pertama ‘H’ ditempatkan sebagai akar (root)
2. Karakter ‘A’,karena lebih kecil dari ‘H’, maka akan
menempati cabang kiri.
3. Karakter ‘K’, karena lebih besar dari ‘H’, maka akan
menempati cabang kanan.
4. Karakter ‘J’, lebih besar dari ‘H’ dan kecil dari ‘K’, maka
menempati cabang kiri ‘K’.
Dan begitu seterusnya sehingga terbentuk pohon
biner seperti berikut :
Pertemuan 10
KUNJUNGAN
PADA POHON BINER

3. Kunjungan secara Postorder, mempunyai urutan :
a. Kunjungi Cabang Kiri
b. Kunjungi Cabang Kanan
c. Cetak isi simpul yang dikunjungi (Simpul Akar)
Pada ketiga cara kunjungan diatas, kunjungan ke
Cabang Kiri dilakukan terlebih dahulu, baru kemudian
kunjungan ke Cabang Kanan. Dengan orientasi
semacam ini, Ketiga kunjungan diatas disebut dengan
Left To Right Oriented (LRO).
Jika kunjungan ke Cabang Kanan dilakukan lebih
dahulu baru kemudian kunjungan ke Cabang Kiri, maka
Orientasi semacam ini disebut Right To Left Oriented
(RLO).
A
B C
D E
A B D E C
Klik Animasi
Klik Animasi
Kunjungan PreOrder dalam Program C++
A
B C
D E
D B E A C
Klik Animasi
Klik Animasi
Kunjungan InOrder dalam Program C++
A
3. Kunjungan secara Postorder, mempunyai urutan :
a. Kunjungi Cabang Kiri
b. Kunjungi Cabang Kanan
c. Cetak isi simpul yang dikunjungi (Simpul Akar)
B C
D E
D E B C A
Klik Animasi
Klik Animasi
Kunjungan PostOrder dalam Program C++
Kunjungan LevelOrder
Selain kunjungan yang dijelaskan diatas, masih ada
satu macam kunjungan masih ada satu macam
kunjungan lagi yaitu kunjungan LevelOrder.
Kunjungan dimulai dari simpul yang ada pada tingkat
1 (Akar), diteruskan pada simpul di tingkat 2, tingkat 3
dan seterusnya.
Secara singkat kunjungan Level Order ini dapat dijelaskan
sebagai berikut.
1. Dimulai dengan memasukkan Akar kedalam antrean.
2. Kemudian mengeluarkan Akar tersebut keluar dari
antrean.
Pada saat Akar tersebut dikeluarkan dari antrean, cabang
kiri dan cabang kanan secara berturut-turut dimasukkan
dalam antrean.
Dengan kata lain jika suatu elemen dikeluarkan dari
antrean, maka cabang kiri dan kanan dari elemen yang
baru saja dikeluarkan dimasukkan kedalam antrean.
APLIKASI POHON BINER
NOTASI PREFIX, INFIX DAN POSTFIX
Pada bagian ini akan dibahas tentang bagaimana
menyusun sebuah Pohon Binar yang apabila dikunjungi
secara PreOrder akan menghasilkan Notasi Prefix,
kunjungan secara InOrder menghasilkan Notasi Infix, dan
kunjungan PostOrder menghasilkan Notasi Postfix.


Berdasarkan Gambar diatas, apabila dilakukan kunjungan
secara PreOrder, maka akan diperoleh Notasi Prefix dari
persamaan-persamaan yang digambarkan tersebut, yaitu :
+A*BC (Gambar.a)
*+AB-BC (Gambar.b)
^-*+ABC-DE+FG (Gambar.c)
Jika dilakukan kunjungan secara InOrder, akan diperoleh
Notasi Infixnya, yaitu :
(A+(B*C)) (Gambar.a)
((A+B) * (B-C)) (Gambar.b)
(((A+B) * C) – (D-E)^(F+G) (Gambar.c)
Jika dilakukan kunjungan secara PostOrder, akan
diperoleh Notasi Postfixnya, yaitu :
ABC*+ (Gambar.a)
AB+BC-* (Gambar.b)
AB+C*DE-FG+^ (Gambar.c)
Pertemuan 11
SORTING
SORTING
Operasi Pengurutan (Sorting) adalah operasi yang sangat
banyak dilakukan dalam ‘Bussiness Data Processing’.
Dalam hal ini pengurutan yang dilakukan adalah secara
Ascending (menaik dari kecil ke besar)
Macam-macam Sorting (Pengurutan) :
1. SELECTION SORT
2. BUBBLE SORT
3. MERGE SORT
4. QUICK SORT
5. INSERTION SORT
Metode pengurutan Selection Sort, Prosedur atau
Algoritmanya adalah sbb :
1. Pengecekan dimulai dari data ke –1 sampai dengan
data ke – n
2. Tentukan bilangan dengan index terkecil dari data
bilangan tersebut
1. SELECTION SORT
3. Tukar bilangan dengan index terkecil tersebut
dengan bilangan pertama (I = 1) dari data bilangan
tersebut
4. Lakukan langkah 2 dan 3 untuk bilangan berikut
(I = I+1) sampai didapatkan urutan yang optimal.
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
Langkah 2 : 22 10 15 3 8 2
Langkah 3 : 2 10 15 3 8 22
Langkah 4 : Ulangi langkah 2 dan 3
Iterasi 2
Langkah 1: 2 10 15 3 8 22
Langkah 2: 2 10 15 3 8 22
Langkah 3: 2 3 15 10 8 22
Langkah 4: Ulangi langkah 2 dan 3 .
Lakukan Iterasi selanjutnya sampai iterasi ke-6
Prosedur Program Selection Sort
(Dengan program C++)
2. BUBBLE SORT
Contoh : 22 10 15 3 8 2
terasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
Langkah 2 : 22 10 15 3 8 2
Langkah 3 : 22 10 15 3 2 8
Langkah 4 : Ulangi langkah 2 dan 3
Hasil iterasi 1 : 2 22 10 15 3 8
Iterasi 2
Langkah 1 : 2 22 10 15 3 8
Langkah 2 : 2 22 10 15 3 8
ket: 8>3, maka 8 tidak pindah, untuk selanjutnya
bandingkan data sebelunya yaitu 3.
Langkah 3 : 2 22 10 3 15 8
Langkah 4 : Ulangi langkah 2 dan 3
Hasil Iterasi 2 : 2 3 22 10 15 8
Lakukan Iterasi selanjutnya sampai iterasi ke- 6
Prosedur Program Bubble Sort
(Dengan program C++)
3. MERGE SORT
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
Langkah 2 : 10 22 3 15 2 8
Iterasi 2
Langkah 1 : 10 22 3 15 2 8
Langkah 2 : 3 10 15 22 2 8
Iterasi 3
Langkah 1 : 3 10 15 22 2 8
Langkah 2 : 2 3 8 10 15 22
Prosedur Program Merge Sort
(Dengan program C++)

4. QUICK SORT
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
LB UB
Langkah 2 :2 10 15 3 8 22
Iterasi 2
Langkah 1 : 2 10 15 3 8 22
LB/UB
Langkah 2 :2 10 15 3 8 22
LB UB
Iterasi 3
Langkah 1 :2 10 15 3 8 22
LB UB
Langkah 2 :2 8 15 3 10 22
Iterasi 4
Langkah 1 :2 8 15 3 10 22
LB UB
Langkah 2 :2 3 15 8 10 22
Lakukan Iterasi selanjutnya sampai iterasi ke- 6
Prosedur Program Quick Sort
(Dengan program C++)

5. INSERTION SORT
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1: 22 10 15 3 8 2
Langkah 2: 22 10 15 3 8 2
Langkah 3: 10 22 15 3 8 2
Langkah 4: Ulangi langkah 2 dan 3
Iterasi 2
Langkah 1: 10 22 15 3 8 2
Langkah 2: 10 22 15 3 8 2
Langkah 3: 10 15 22 3 8 2
Langkah 4: Ulangi langkah 2 dan 3
Lakukan Iterasi selanjutnya sampai iterasi ke- 6
Catatan : Setiap ada pemindahan, maka elemen. Yang
sudah ada akan di insert sehingga akan bergeser
kebelakang.
Prosedur Program Insertion Sort
(Dengan program C++)
Pertemuan 12
STRUKTUR
SEARCHING
Linier Searching
(Sequential Searching)
• Suatu teknik pencarian data dalam array dimensi 1 yang
akan menelusuri semua elemen array dari awal sampai
akhir, dimana data-data tidak perlu diurutkan terlebih
dahulu (acak).
• Kemungkinan terbaik (best case) adalah jika data yang
dicari terletak di indeks array terdepan sehingga waktu
yang dibutuhkan untuk pencarian data sangat singkat
(waktu minimal).
• Kemungkinan terburuk (worst case) adalah jika data
yang dicari terletak di indeks array terakhir sehingga
waktu yang dibutuhkan untuk pencarian data sangat
lama (waktu maksimal).
Misalnya terdapat array satu dimensi sebagai berikut:
8 10 6 -2 11 7 1 100
0 1 2 3 4 5 6 7
21da 21db 21dc 21dd 21de 21df 21e0 21e1
indeks
value
alamat
Kemudian program akan meminta data yang akan dicari,
misalnya 6.
Jika ada maka akan ditampilkan “Data ada”, jika tidak ada
maka akan ditampilkan “Data tidak ada”.
Linier Searching
(Sequential Searching)
Dengan Program C++
Merupakan metode terbaik dalam search (pencarian),
karena memulai pencarian dari lokasi tengah (m).
Kemudian berdasarkan posisi tengah tersebut terdapat 3
kemungkinan :
a. Jika cari < data[m], maka informasi yang dicari berada
disebelah kiri dari lokasi tengah (m)
Binary Searching
c. Jika cari > data[m], maka informasi yang dicari berada
disebelah kanan dari lokasi tengah (m)
b. Jika cari = data[m] maka data tengah tersebut adalah
data yang dicari
Binary Searching
Dengan Program C++
Pertemuan 13
GRAPH
Suatu Graph mengandung 2 himpunan, yaitu :
1. Himpunan V yang elemennya disebut simpul (Vertex
atau Point atau Node atau Titik)
2. Himpunan E yang merupakan pasangan tak urut dari
simpul. Anggotanya disebut Ruas (Edge atau rusuk
atau sisi)
GRAPH
Graph seperti dimaksud diatas, ditulis sebagai G(E,V).
Contoh :
Gambar berikut menanyakan Graph G(E,V) dengan :
1. V mengandung 4 simpul, yaitu simpul A,B,C,D.
2. E mengandung 5 ruas, yaitu :
e1 = (A,B) e4 = (C,D)
e2 = (B,C) e5 = (B,D)
e3 = (A,D)
Gambar dibawah ini menyatakan suatu Multigraph.
Disini, ruas e2 pada kedua titik ujungnya adalah simpul
yang sama, yaitu simpul A. Ruas semacam ini disebut
Gelung atau Self-Loop. Sedangkan ruas e5 dan e6
mempunyai titik ujung yang sama, yaitu simpul-simpul B
dan C. Kedua ruas ini disebut ruas berganda atau ruas
sejajar.
e3
e5
e4
e2
e1
e6
Suatu Graph yang tidak mengandung ruas sejajar maupun
self-loop, sering disebut juga sebagai Graph sederhana
atau simple Graph.
Suatu Graph G’(E’,V’) disebut Sub Graph dari G(E,V), bila E’
himpunan bagian dari E dan V’ himpunan bagian dari V.
Jika E’ mengandung semua ruas dari E yang titik ujungnya
di V’, maka G’ disebut Subgraph yang direntang oleh V’
(Spanning Subgraph).
Contoh Sub Graph:
Contoh Spanning Sub Graph :
Graph G disebut berlabel jika ruas dan atau simpulnya
dikaitkan dengan suatu besaran tertentu. Khususnya jika
setiap Ruas e dari G dikaitkan dengan suatu bilangan
non negatif d(e), maka d(e) disebut bobot atau panjang
GRAPH BERLABEL
dari ruas e.
Contoh :
Gambar berikut ini menyajikan hubungan antar kota.
Disini simpul menyatakan kota dan label d(e) menyatakan
jarak antara dua kota.
DERAJAT GRAPH
Derajat simpul V, ditulis d(v) adalah banyaknya ruas
yang menghubungi v. Karena setiap ruas dihitung dua
kali ketika menentukan derajat suatu Graph, maka :
Jumlah derajat semua simpul suatu Graph (derajat) =
dua kali banyaknya ruas Graph (Size) Atau dapat
dituliskan :
Derajat Graph = 2 x Size
Pada gambar diatas Jumlah Semua Simpul = 4, maka
Jumlah Derajat Semua Simpul = 8
Jika Derajat masing-masing simpul pada Graph berjumlah
Genap maka Graph tersebut disebut EULER Graph
Contoh :
D E
B
C
A F
Pada gambar diatas, banyak ruas/size = 7, sedangkan
derajat masing-masing simpul adalah :
d(A) = 2
d(B) = 5
d(C) = 3
d(D) = 3
d(E) = 1
d(F) = 0
maka, total jumlah derajat simpul adalah : 14
E disebut simpul bergantung/akhir, yaitu simpul yang
berderajat satu. Sedangkan F disebut simpul terpencil,
yaitu simpul yang berderajat Nol.
Walk atau perjalanan dalam Graph G adalah barisan simpul
dan ruas berganti-ganti : V1,e1,V2,e2,......., e n-1, Vn
Disini ruas ei menghubungkan simpul Vi dan Vi+1.
Banyaknya ruas disebut Panjang Walk. Walk dapat ditulis
lebih singkat dengan hanya menulis deretan ruas :
KETERHUBUNGAN
e1,e2, ...., en-1 atau deretan simpul : V1, V2,....., Vn-1, Vn
dimana : V1 = simpul awal
Vn = simpul akhir.
Walk disebut tertutup bila V1 = Vn

Graph diatas Bukan Walk tertutup tetapi merupakan
Walk Terbuka, karena tidak ada ruas yang
menghubungkan Simpul U dan T.
Merupakan suatu Path atau Trail terbuka dengan
derajat setiap simpulnya = 2, kecuali simpul awal V1
dan akhir Vn berderajat = 1.

· Barisan ruas a,b,c,d,b,f,g,h adalah Walk bukan Trail
(karena ruas b dua kali muncul).
· Barisan simpul A, B, E, F bukan Walk (karena tdk
ada ruas yang menghubungkan simpul B ke F).
· Barisan simpul A, B, C, D, E, C, F adalah Trail
bukan Jalur/Path (karena c dua kali muncul)
· Barisan ruas a, d, g, k adalah Jalur/Path karena
menghubungkan A dengan F
· Ruas a, b, h, g, e, a, adalah Cycle.
Graph yang tidak mengandung Cycle disebut Acyclic.
Contoh dari Graph Acyclic adalah pohon atau Tree.
Contoh dari acyclic

Pertemuan 14

MATRIKS

PENYAJIAN GRAPH

MATRIKS PENYAJIAN GRAPH

Misalnya disajikan Graph G dalam Matriks ruas B ukuran

(M x 2), maka setiap baris Matriks menyatakan ruas,

misalnya baris (4 7) menyatakan ada ruas

menghubungkan simpul 4 dan 7.

Matriks Adjacency dari Graph G, yaitu Matriks yang

menghubungkan Vertex dengan Vertex, tanpa ruas

sejajar adalah Matriks A berukuran (N x N) yang bersifat :

1 , bila ada ruas (Vi, Vj)

aij=

0, bila dalam hal lain.

Matriks Adjacency merupakan matriks simetri.

Untuk Graph dengan ruas sejajar, Matriks Adjacency

didefinisikan sebagai berikut :

P, bila ada p buah ruas menghubungkan

aij = (Vi, Vj)(p>0)

0, bila dalam hal lain.

Matriks Incidence dari Graph G, yaitu Matriks yang

menghubungkan Vertex dengan Edge, tanpa self-loop

didefinisikan sebagai Matriks M berukuran (NXM) sebagai

berikut :

1, bila ada ruas ej berujung di simpul Vi

mij =

0, dalam hal lain.

e1 e2 e3 e4 e5 e6 e7 e8

V1 1 1 0 1 1 0 0 0

V2 1 0 1 0 0 0 0 0

V3 0 1 1 0 0 1 1 0

V4 0 0 0 1 0 1 0 1

V5 0 0 0 0 0 1 0 1

GRAPH TERARAH (DIRECTED GRAPH / DIGRAPH)

Graph terarah adalah Graph yang dapat menghubungkan

V1 ke V2 saja (1 arah).

Maksimum jumlah busur dari n simpul adalah : n ( n - 1)

Suatu Graph Berarah (Directed Graph) D terdiri atas 2

himpunan :

1) Himpunan V, anggotanya disebut simpul.

2) Himpunan A, merupakan himpunan pasangan terurut,

yang disebut ruas berarah atau arkus.

Contoh, Gambar dibawah ini adalah sebuah Graph

Berarah D(V,A) dengan :

1. V mengandung 4 simpul, yaitu 1, 2, 3 dan 4

2. A mengandung 7 arkus, yaitu (1,4) ,(2,1), (2,1),

(4,2), (2,3), (4,3) dan (2)

Arkus (2,2) disebut gelung (self-loop), sedangkan

arkus (2,1) muncul lebih dari satu kali, disebut

arkus sejajar atau arkus berganda.

Bila arkus suatu Graph Berarah menyatakan suatu bobot,

maka Graph Berarah tersebut dinamakan jaringan /

Network. Biasanya digunakan untuk menggambarkan situasi

dinamis.

Bila V’ himpunan bagian dari V serta A’ himpunan bagian

dari A, dengan titik ujung anggota A’ terletak di dalam V’,

maka dikatakan bahwa D’(V’,A’) adalah Graph bagian

(Subgraph) dari D(V,A).

Bila A’ mengandung semua arkus anggota A yang titik

ujungnya anggota V’, maka dikatakan bahwa D’(V’,A’)

adalah Graph Bagian yang dibentuk atau direntang oleh V’.

CRITICAL PATH

1

2

3

4 5

Merupakan Spanning Tree yang mempunyai Bobot dan

tidak mempunyai arah dengan hasil penjumlahan

bobotnya adalah minimum.

Lihat gambar Graph G berikut :

MINIMUM SPANNING TREE

V2

V1

V4

V3

V5

Langkah yang dilakukan untuk membentuk minimum

spanning tree adalah :

Bentuk kembali semua simpul tetapi tanpa ruas.

Gambar dan telusuri ruas dengan bobot paling kecil,

seterusnya (secara ascending) hingga semua simpul

terhubung

Total Minimum

Spanning Tree = 22

(4)

V1

V2

V3

V4 V5

(5)

(6)

(7)

Karena V8 sudah dilewati setelah

penelusuran ke V4, maka penelusuran yang

berikutnya dianggap tidak dilewati lagi

Klik Animasi

2. Breadth First Search (BFS).

Berbeda dengan cara BFS, dengan BFS penelusuran

akan diawasi dari Node-1, kemudian melebar pada

Adjacent Node dari Node-1 dan diteruskan pada

Node-2, Node- 3 dan seterusnya.

Dari gambar di atas akan diperoleh urutan :

V1 , V2 ---> V3 , V4 ---> V5 ---> V6 ---> V7, V8

Klik Animasi