struktur data
TRANSCRIPT
http://catatanimam20.blogspot.com | Struktur Data semeter2 1
PERTEMUAN1
1.Type data dibawah ini, yang tidak termasuk dalam
tipe data sederhana tunggal, adalah:
a. Boolean d. Integer
b. String e. float
c.Char
2.==, <=, >=, !=, termasukdalamoperator …
a. Aritmatika d. Relasi
b. Unary e. Bitwise
c.Binary
3.Type data yang menghasilkanbentuk keluaran nilai
Truedan False(Benar dan Salah) , adalah :
a. Boolean d. Integer
b. String e. float
c. Char
4.void main()
{
....(a)....x,y,z;
clrscr();
cout<<“\ninputnilaiX=“;cin>>x;
cout<<“\ninputnilaiY=“;cin>>y;
z=x+y;
cout<<“\nhasilpenjumlahan=“<<z;
getch();
}
Tipe data yang tepat untuk (a)adalah ….
a. Boolean d. Integer
b. String e. Array
c. Char
5.void main()
{
intr=10;ints;
clrscr();
s=10+++r;
cout<<“r=“<<r<<‘\n’;
cout<<“s=“<<s<<‘\n’;getch();
}
Hasil eksekusi dari program diatas adalah ….
a. r = 11, s = 21 d. r = 10, s = 21
b. r = 11, s = 20 e. r = 10, s = 20
c. r = 12, s = 21
PERTEMUAN2
1.Setiap elemen dari sebuah Array haruslahmempunyai
type data yang sama, termasuk dalam karakteristik
array yaitu :
a. Statis d. Heterogen
b. Dinamis e. Homogen
c. Terurut
2.Array yang sering digunakan dalam menterjemahkan
matriks pada pemrograman, adalah array berdimensi :
a. Satu d. Satu dan Dua
b. Dua e. Satu dan Tiga
c. Tiga
3.Contoh aplikasi array dimensi dua adalah…..
a. Input data suhu
b. Input nama hari
c. Input nilai mahasiswa perkelas dan matakuliah
d. Input nilai ipk mahasiswa
e. Input nama bulan
4.Terdapat Array : A [5][4] maka jumlah elemen Array
tersebut adalah ……
a. 25 d. 15
b. 35 e. 20
c. 9
5.DiketahuifloatA[5]danlokasiawalterletakdialamat00F(
H),makalokasiA*3+adalah…..
a.00FC(H) d.01B(H)
b.017(H) e.111(H)
c.071(H)
PERTEMUAN3
1.Array yang sangat banyak elemen nol-nya,
dikenalsebagai :
a. Upper tringular Array d. One Dimensional Array
b. Lower tringular Array e. Multi Dimensional Array
c. Sparse Array
2Array yang seluruh elemen dibawah diagonal
utamanya = 0,dikenalsebagai :
a. Upper tringular Array d. One Dimensional Array
b. Lower tringular Array e. Multi Dimensional Array
c. Sparse Array
3.Terdapat Array : A [3][4][5] maka jumlah elemen
Array tersebut adalah ……
a. 25 b. 35 c. 12 d. 15 e. 60
http://catatanimam20.blogspot.com | Struktur Data semeter2 2
4. Diketahui suatu array segitiga memiliki 4 baris dan
kolom. Jumlah elemen yang bukan nol pada array
segitiga tersebut adalah …..
a. 10 d. 16
b. 8 e. 20
c. 4
5.Deklarasi Array X adalah int A [2][4][5], dengan
alamat awal index A[0][0][0] berada di 0021(H) dan
ukuran type data int = 2 Tentukan berapa alamat array
di A[2][2][2] ?
a. 0034(H) d. 0052(H)
b. 0022(H) e. 0034(H)
c. 0055(H)
PERTEMUAN4
1.Diketahui suatu deklarasi variabel int x,y,*z;
variabel yang merupakan penunjuk ke pointer adalah :
a. x d. x dan y
b. y e. x, y dan z
c. z
2.Perintah yang tepat untuk mempersiapkan sebuah
node baru berserta alokasi memorinya, adalah ….
a.Create d. New
b.Null e. Insert
c.Input
3.Jika Tail = Null, maka kondisi Linked List adalah :
a. Penuh d. Tidak dapat ditambah
b. Kosong e. Baru
c. Terisi
4.
Gambar diatas menunjukkan bentuk penghapusan
node pada posisi :
a.Belakang d. Tengah dan Depan
b.Depan e. Depan dan Belakang
c.Tengah
5.Perintah yang tepat untuk menyatakan Linked list
berada dalam kondisi kosong, adalah ….
a.head=tail d. bantu=head
b.head=tail=null e. bantu=tail
c. bantu=null
PERTEMUAN5
Diketahui suatu stack dgn max_stack = 6
1.Bila dilakukan PUSH 3 elemen kedalam stack,
kemudian di PUSH lagi 2 elemen dan di POP 3 elemen.
Maka dimana posisi Top of Stack ?
2.IsEmpty pada kondisi terakhir adalah ?
3.Dari kondisi diatas (no.3) Berapa elemen yg hrs di
PUSH unt mencapai kondisi penuh Top of Stack =
max_stack ?
4.Berapa elemen yg hrs di POP unt mencapai kondisi
IsEmpty = True
1.Operasi Stack yang digunakan untuk memeriksa
apakah stack sudah penuh, adalah …..
a. PUSH d. ISEMPTY
b. POP e. ISFULL
c. CLEAR
2.Menambah satu (increment) nilai TOP of STACK
setiap ada penambahan elemen stack selama stack
masih belum penuh, merupakan langkah awal pada
operasi STACK yaitu …..
a. PUSH d. ISEMPTY
b. POP e. ISFULL
c. CLEAR
3.Jika pada stack terdapat kondisi TOP of STACK =
MAX_STACK -1 maka stack berada dalam keadaan ...
a. ISEMPTY d. RETREIVE
b. CLEAR e. FULL
c. TOP
4.Pada saat awal, Top of Stack selalu bernilai :
a.Top = 0 d. Top = Max_Stack
b.Top = 1 e. Top = Max_Stack -1
c. Top = -1
5.Diberikan perintah/instruksi pada program C++, yaitu
tumpuk.top++;Maksud dari perintah/instruksi tersebut
adalah ….
a.Top = Top + 1 d. Top = -1
b.Top = Top -1 e. Top = 1
c. Top = 0
PERTEMUAN6
1.Operasi pada Antrian yang digunakan untuk
menambahkan item pada posisi paling belakang,
adalah …
a. Create d. Enqueue
http://catatanimam20.blogspot.com | Struktur Data semeter2 3
b. Clear e. Dequeue
c. Tail
2.Perintah IsFull pada antrian digunakan untuk :
a.Memeriksa apakah antrian sudah penuh
b.Memeriksa apakah Antrian penuh atau kosong
c.Menambahkan elemen ke dalam Antrian
d.Menghapus elemen dari dalam Antrian
e. Memeriksa apakah antrian sudah kosong
3.Yang tidak termasuk dalam operasi antrian, adalah ...
a.Clear d. Push
b.Enqueue e. Dequeue
c.IsFull
4.Menghapus elemen dari antrian dilakukan dari posisi
:
a.Tengah / Middle d. Belakang / Tail
b.Depan / Head e. Atas / Top
c. Bawah / bottom
5.Maksud dari perintah program
antrian.head=antrian.tail=-1; adalah untuk ......
a.Menambah elemen antrian
bMengecek kondisi antrian kosong atau tidak
c.Mengecek kondisi antrian penuh atau tidak
d. Membentuk atau menghapus semua elemen antrian
e. Menghapus elemen antrian
Berikan gambaran/ilustrasi dari kasus antrian berikut :
- Diketahui suatu Antrian/queue dgn max = 6.
- Lakukan Enqueue 4 elemen ke dalam antrian,
dimanakah posisi Head dan Tail ?
- Kemudian lakukan Dequeue 2 elemen dari
antrian. Maka dimana posisi Head dan Tail ?
- Dari keadaan diatas, bagaimanakah kondisi
IsFull dan IsEmpty nya ?
PERTEMUAN9
1.Simpul Khusus pada pohon yang memiliki derajat
keluar >= 0, dan derajat masuk = 0, adalah ….
a. Node / simpul d. edge / ruas
b. Root / akar e. level
c. Leaf / daun
2.Jika suatu pohon biner memiliki simpul sebanyak 5
maka banyaknya ruas adalah :
a.2 b.3 c. 4 d. 5 e. 6
3.Pohon biner yang memiliki ciri Semua simpul (kecuali
daun) memiliki 2 anak dan tiap cabang memiliki
panjang ruas yang sama, adalah pohon biner ….
a. Lengkap / complete
b. Similer
c. Miring / skewed
d. Penuh / full
e. ekivalen
4.Suatu pohon memiliki level = 4, maka banyaknya
Simpul Maksimum yang dapat terbentuk sampai Level
4adalah ….
a. 8 b. 15 c. 12 d. 4 e. 7
5.Pohon biner yang memiliki struktur dan informasinya
sama disebut :
a. Miring (Skewed)
c. Terstruktur
b. Ekivalent
d. Similer
e. Complete
PERTEMUAN10
1.Kunjungan dengan urutan : kunjungi simpul akar,
cabang kiri,cabang kanan, adalah kunjungan….
a. Preorder d. Postorder
b. Inorder e. Outorder
c. Symetric Order
2. Dengan kunjungan PREORDER maka untai yang
dihasilkan adalah :
a. A B D C
b. A B C D
c. B A D C
d. B D C A
e. B C D A
3. Dari gambar disamping, notasi POSTFIX yang
dihasilkan adalah …
http://catatanimam20.blogspot.com | Struktur Data semeter2 4
a. A B C -*
b. A -B * C
c. A B -C *
d. * -A B C
e. A B -* C
4.Dari gambar diatas,notasi PREFIX yang dihasilkan
adalah :
a. A B C -* d. A B -C *
b. A -B * C e. * -A B C
c. * -C A B
5.Berikut ini, yang tidak termasuk dalam kunjungan
pohon biner adalah :
a. Inorder d. Preorder
b. Outorder e. Postorder
c. Symetric Order
PERTEMUAN11
1.Tehnik pengurutan data yang paling tepat digunakan
untuk tabel data yang sangat besar adalah…
a. Selection Sort d. Quick Sort
b. Bubble Sort e. Insertion Sort
c. Merge Sort
2.Mengelompokan deret bilangan kedalam 2 bagian, 4
bagian, 8 bagian, … dst, merupakan salah satu iterasi
didalam metode:
a. Selection Sort d. Quick Sort
b. Bubble Sort e. Insertion Sort
c. Merge Sort
3.Jika urutan data pada langkah pertama adalah :
5 8 2 10 3 maka urutan data secara ascending pada
langkah berikutnya dengan metode Insertion sort
adalah …
a. 2 8 5 10 3 d. 2 3 5 8 10
b. 2 3 5 10 8 e. 2 5 8 10 3
c. 2 5 8 3 10
4.(1) Tentukan batas bawah (LB) dan batas atas (UB)
(2) Bila LB>UB, maka data ditukar
Pernyataan diatas adalah langkah pengurutan data
dengan metode :
a.Bubble d. Insertion
b. Merge e. Quick
c. Selection
5.Jika diketahui urutan data 26 18 21 6 12, bila urutan
data pada langkah berikutnya menjadi 18 26 6 21 12,
maka metode sorting yang digunakan adalah …
a. Quick d. Selection
b. Bubble e. Merge
c. Insertion
PERTEMUAN12
1.Kemungkinan terbaik (best case) untuk pencarian
data dengan sequential search adalah jika ….
a. Data yang dicari berada di indeks belakang
b. Data yang dicari berada di indeks terdepan
c. Data yang dicari berada di tengah indeks
d. Data yang dicari tidak ada pada indeks array
e. Tidak ada jawaban yang benar
2.Yang merupakan metode terbaik dalam searching
adalah
a. Linier Searching d. A, B dan C benar
b. Sequential Searching e. A, B dan C salah
c. Binary searching
3.Pencarian data dengan metode Binary search akan
berhenti bila data yang dicari sudah ditemukan, yaitu
pada kondisi…
a. cari < data[m] d. cari > data[m]
b. cari = data[m] e. cari = 0
c. cari <> data[m]
4.Suatu teknik pencarian data dalam array dimensi 1
yang akan menelusuri semua elemen array dari awal
sampai akhir, dimana data-data tidak perludiurutkan
terlebih dahulu (acak) adalah metode
a. Linier Searching d. A dan B benar
b. Sequential Searching e. B dan C benar
c. Binary searching
5.Bila diketahui urutan data sebagai berikut :
5 10 15 20 25
Pencarian data 10 dengan metode Binary dapat
diselesaikan pada langkah ke…
a. 1 b. 2 c. 3 d. 4 e. 5
http://catatanimam20.blogspot.com | Struktur Data semeter2 5
PERTEMUAN13
1.Graph yang memiliki ruas sejajar dan gelung disebut
…
a. Gelung/self loop d. Graph sederhana
b. Multigraph e. Euler graph
c. Simple Graph
2.Perjalanan (Walk) dalam suatu graph akan disebut
tertutup bila ….
a. V1 = Vn d. V1 = V(n-1)
b. Vn = V(n-1) e. V1 = 0
c. V1 <> Vn
3.Bila diketahui banyaknya ruas pada suatu graph = 7,
maka jumlah derajat Graph-nya adalah ….
a. 14 b. 49 c. 6 d. 21 e. 7
4.Bila diketahui jumlah derajat semua simpul pada
suatu graph adalah 20, maka banyaknya ruas pada
graph tersebut adalah ….
a. 19 b. 21 c. 40 d. 10 e. 15
5.
Dari gambar diatas, yang termasuk TRAIL adalah ….
a. a,b,c,h,g,d,a d. a,b,h,k,f,g,b
b. a,e,f,k,h,c,d e. a,d,g,k,f,d,b
c. a,b,c,g,h,c,d
PERTEMUAN14
1.Matriks penyajian graph yang menghubungkan
vertex dengan vertex, tanpa ruas sejajar, disebut
matriks…
a.Incidence d. Undirected Graph
b.Adjacency e. Semua jawaban salah
c. Directed Graph
2.Maksimum jumlah busur dari n simpul dalam
Directed Graph
a. n ( n -1) / 2 d. (n –1) / 2
b.n ( n -1) e. (n –1) + 2
c. n -1
3.Bila diketahui simpul dari suatu graph berarah
(Directed Graph) adalah 5, maka maksimum jumlah
busur dari graph tersebut adalah….
a. 25 b. 20 c. 10 d. 15 e. 2
4.Penelusuran graph yang diawali dari node-1
kemudian melebar pada node-2, node-3 dan
seterusnya, adalah penelusuran dengan cara ….
a. Breadth First Search d. Node First Search
b.Depth First Search e. Edge First Search
c. Width First Search
5.
Critical Path dari simpul A ke simpul D
pada graph disamping adalah …
a. 15 d. 33
b. 18 e. 38
c. 20
SILABUS PERKULIAHAN
JENJANG DIPLOMA III (tiga) AMIK BSI
Mata Kuliah : Struktur Data Kode/sks : 307 / 4 sks
Sumber Referensi :
1. Abdul Kadir. 2003. Pemrograman C++. Penerbit Andi. Yogyakarta.
2. Andri Kristanto. 2003. Struktur Data Dengan C++. Penerbit Graha Ilmu. Yogyakarta.
3. Frieyadie. 2006. Panduan Pemrograman C++. Penerbit Andi. Yogyakarta 4. Sjukani. Moh. 2009. Struktur Data (Algoritma & struktur Data 2) Dengan C, C++. Edisi 3 Mitra Wacana Media. Jakarta.
5. Teddy Markus Zakaria. 2006. Konsep dan Implementasi Struktur Data. Penerbit
Informatika. Bandung
Pertemuan ke-
Pokok Bahasan Keterangan
1 Data & Struktur Data
2 Array / Larik Dimensi 1 dan 2
3 Array / Larik Dimensi banyak
4 Single Linked List
5 Stack / Tumpukan
6 Queue / Antrian
7 Review Materi
8 UJIAN TENGAH SEMESTER
9 Struktur Pohon
10 Kunjungan Pada Pohon Biner
11 Graph & Matriks Penyajian Graph
12 Presentasi Project 1
13 Presentasi Project 2
14 Presentasi Project 3
15 Review Materi
16 UJIAN AKHIR SEMESTER
Capaian :
1. Mampu membuat program science berdasarkan materi yg telah dibahas pada tiap
pertemuan.
2. Mampu mengimplementasikan materi ke dalam project program.
Pertemuan 1
KONTRAK PERKULIAHAN • Struktur Data merupakan Mata Kuliah yang diambil oleh mahasiswa
di semester 2 (dua) dengan 4 (empat) sks dalam bentuk tatap muka
• Pertemuan 1-6 dilakukan seperti biasanya dimana dosen menyampaikan materi kepada mahasiswa
• Pertemuan 7 diadakan QUIZ / review materi
• Pertemuan 8 diadakan UTS dimana materi diambil dari pertemuan 1-6
• Pertemuan 9-11 yang diadakan setelah UTS dilakukan sama seperti Pertemuan 1-6 dimana dosen menyampaikan materi kepada mahasiswa.
• Pertemuan 12-14 mahasiswa secara berkelompok diwajibkan untuk membuat dan mempresntasikan Project program sebagai implementasi dari materi yang sudah diberikan.
• Pertemuan 15 diadakan QUIZ / review materi
• Pertemuan 16 diadakan UAS dimana materi diambil dari pertemuan 9-11 sebanyak 80% dan pertemuan 1-6 sebanyak 20%
• Sistem penilaian Struktur Data
10 % Absensi
20% Tugas & Quiz
Point nilai Quis 1 : 25
Point nilai Project : 50
Point nilai Quis 2 : 25
30% UTS
40% UAS
Bentuk tugas yang harus dilakukan adalah :
- Mahasiswa diharapkan mengerjakan tugas yang diberikan oleh dosen pada setiap pertemuan
- Quis dilakukan 2 kali< yaitu padaa pertemuan 7 dan 15.
- Pembuatan dan presentasi project dilakukan pada pertemuan 12-14.
Isi dari Makalah dan CD project tersebut antara lain:
A. Struktur Makalah ( nilai 20 %)
B. Struktur Program dan kesesuaian isi program dengan materi yang dipilih (nilai 50%)
C. Penyampaian presentasi project (nilai 30%)
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
pemrograman, akan menghasilkan Algoritma yang lebih
jelas dan tepat sehingga menjadikan program secara
keseluruhan lebih sederhana.
STRUKTUR DATA
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.
Type Range Ukuran
(Byte)
Integer - 32768..32767 2
Long - 2147483648..2147483647 4
1. INTEGER
Merupakan Bilangan Bulat dan tidak mengandung
pecahan. seperti : ...-3,-2,-1,0,1,2,3,....
Type data Integer
TYPE DATA SEDERHANA
(Dalam Program C++)
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.
Diharapkan dosen memberikan contoh
aplikasi programnya
Operator
Aritmatika
Keterangan
pow Pangkat
sqrt Menghitung akar
% Sisa hasil bagi (modulus)
* , / Perkalian, Pembagian
+ , - Penjumlahan, Pengurangan
Jenis-jenis Operator Dalam Bahasa C++
Diharapkan dosen memberikan latihan dan contoh
program serta memberikan tugas kelompok kepada
mahasiswa untuk membuat program yang
menggunakan salah satu operator dibawah ini
(dikumpulkan pada pertemuan berikutnya)
Operator Pemberi
Nilai Aritmatika
Keterangan
* = Perkalian
/ = Pembagian
% = Sisa hasil bagi
+ = Penjumlahan
- = Pengurangan
Operator
Logika
Keterangan
&& Dan (AND)
|| Atau (OR)
! Bukan (NOT)
Operator Unary Keterangan
+ Tanda Plus
- Tanda Minus
Operator Penambah
& Pengurang
Keterangan
++ Penambahan
-- Pengurangan
Operator
Relasi
Keterangan
= Sama dengan (assignment)
!= Tidak sama dengan
> Lebih besar
< Lebih kecil
== Sama dengan (bukan assignment)
>= Lebih besar atau sama dengan
<= Lebih kecil atau sama dengan
Operator
Bitwise
Keterangan
~ NOT
<< Shift Left
>> Shift Right
& AND
^ XOR
| OR
Bermanfaat untuk mengelompokkan sejumlah data dengan tipe data yang berlainan.
Contoh :
struct data_pegawai
{
int nip;
char nama[25];
char alamat[40];
}
TYPE TERSTRUKTUR
(Dalam Program C++)
Pertemuan 2
ARRAY
DIMENSI 1 & 2
Array / Larik : 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
void main()
{ int bil [5];
clrscr;
cout<<"Masukkan 5 bilangan genap : "<<endl;
for (int i = 0; i < 5; i++)
{ cout<<"Bilangan ";
cout<< i + 1 <<" : ";
cin>> bil[i];
cout<<endl;
}
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 :
n
(Elemen Array)
i=1
= 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
L = 2
Penyelesaian :
A[3] = 0011(H) + (3 – 1) * 2
= 0011(H) + 4 (D)
= 0011(H) + 4 (H)
= 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
Cara lain mengenal alamat elemen array
1. Terdapat array 1 dimensi dengan char A[10].
Diketahui &A[0] = 1000(H). Berapa alamat array
untuk posisi A[7]?
Jawab :
Tipe char = 1byte
0 1 2 3 4 5 6 7 8 9
&A[0]=1000(H) &A[7]=.....?
Perpindahan=7-0=7 elemen
7 elemen * 1 byte=7 Byte, jadi &A[7]=1000H + 0007H=1007H
2. Terdapat array 1 dimensi dengan int A[10]. Diketahui
&A[0] = 1000(H). Berapa alamat array untuk posisi
A[7]?
Jawab :
Tipe int = 2byte
0 1 2 3 4 5 6 7 8 9
&A[0]=1000(H) &A[7]=.....?
Perpindahan=7-0=7 elemen
7 elemen * 2 byte=14 Byte, jadi &A[7]=1000H + 000EH=100EH
0 1 2 3 4 5 6 7
21d2 21d4 21d6 21d8 21da 21dc 21de 21e0
indeks
value
alamat
%x adalah hexadesimal
Contoh Penerapan
Array Dimensi 1 Pada Program C++
2. ARRAY DIMENSI DUA (Two Dimensional Array)
Deklarasi : Type_Data Nama_Variabel [Index1] [index2];
Misal : int A[3][2];
Penggambaran secara Logika : 0 1
0
1
2
Sering digunakan dalam menterjemahkan matriks
pada pemrograman.
Menentukan jumlah elemen dalam Array dimensi dua:
n
(Elemen array)
i=1
Contoh :
Suatu Array X dideklarasikan sbb :
int X[4][3];
maka jumlah elemen Array dimensi dua tersebut adalah :
(4) * (3) = 12
= Perkalian dari elemen sebelumnya
(untuk array dimensi dua & tiga)
PEMETAAN (MAPPING)
ARRAY DIMENSI DUA KE STORAGE
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
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)
@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)
M[0,0] M[0,1]
Penggambaran secara logika
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
0 1
0
1
2
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 = 4
Tentukan berapa alamat array X[3][2] berdasarkan cara
pandang baris dan kolom ?
Contoh Pemetaan :
0011(H)
?
0 1 2
0
1
2
3
index
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)
= 002D(H)
Lanjutan Contoh Pemetaan :
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)
= 0029(H)
Lanjutan Contoh Pemetaan :
#include<stdio.h>
#include<conio.h>
main()
{
int a[3][5];
for (int i=0;i<3;i++)
{
for (int j=0;j<5;j++)
{
printf("%x ",&a[j][i]);
}
printf("\n");
}
getch();
}
Contoh program array dua dimensi
Cara lain Mengenal Alamat Elemen Array 2 Dimensi
Terdapat array 2 dimensi yang dibuat dengan int A[3][5].
Diketahui &A[0][0]=1000H. Tentukan &A[3][4]?
Jawab : tipe int satu elemen = 2byte
0 1 2 3 4
0
1
2
&A[0][0]=1000H
&A[3][4]=....?
&A[0][0]
Pindah baris =2-0=2 baris
2*5 kolom=10 elemen
Pindah elemen dalam baris terakhir :
=3-0=3elemen
Total perpindahan=10+3=13 elemen
=13*2byte=26 byte
26D=1AH
Jadi &A[2][3]=1000H+001AH=101AH
#include<stdio.h>
#include<conio.h>
main()
{
int a[3][5];
for (int i=0;i<3;i++)
{
for (int j=0;j<5;j++)
{
printf("%x ",&a[i][j]);
}
printf("\n");
}
getch();
}
Contoh program array dua dimensi
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
Menentukan jumlah elemen dalam Array dimensi 3 :
n
(index array)
i=1
= 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[m][n][p] = M[0][0][0] + {((m-1) *(jum.elemen2 *
jum.elemen3)) + ((n-1)*(jum.elemen 3)) +
((p-1)}* 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[m][n][p] = M[0][0][0] + {((m-1) *(jum.elemen2 *
jum.elemen3)) + ((n-1)*(jum.elemen
3)) + ((p-1)}* 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)
Contoh mengenal alamat array dimensi tiga
1. Terdapat array tiga dimensi dengan int A[3][5][2].
Diketahui &A[0][0][0]=1000H, Ditanya &A[2][3][1]=....?
Tipe int satu elemen=2byte
Untuk array [2][3][1]: 1 baris=5 elemen
: 1 grup=3 * 5=15 elemen
0 1 2 3 4
0
1
2
0
1
2
0 1 2 3 4
G
R
U
P
0
G
R
U
P
1
&A[0][0][0]=1000H
&A[2][3][1]=...?
&A[0][0][0]
Pindah grup=1-0=1 grup
=1*15=15 elemen
Pindah baris dalam grup terakhir
=2-0=2baris
=2*5=10 elemen
Pindah kolom dalam baris terakhir
=3-0=3 elemen
Total perpindahan=15+10+3=28 elemen
=28 elemen* 2 byte=56 byte, 56D=38H
Jadi,&A[1][2][3]=1000H+0038H=1038H
2. Terdapat array tiga dimensi dengan int A[3][5][2].
Diketahui &A[1][4][1]=12EFH, Ditanya &A[0][2][0]=....?
Tipe int satu elemen=2byte
Untuk array [3][5][2]: 1 baris=5 elemen
: 1 grup=3 * 5=15 elemen
0 1 2 3 4
0
1
2
0
1
2
0 1 2 3 4
G
R
U
P
0
G
R
U
P
1
&A[0][2][0]=...?
&A[1][4][1]=12EFH
&A[1][4][1]
Pindah grup=0-1=-1 grup
=-1*15=-15 elemen
(mundur)
Pindah baris dalam grup terakhir
=0-1=-1 baris
=-1 baris*5=-5 elemen
Pindah kolom dalam baris terakhir
=2-4=-2 elemen
Total perpindahan=-15+-5+-2=-22 elemen
=-22 elemen* 2 byte=-44 byte, -44D=-2CH
Jadi,&A[0]0][2]=12EFH-002CH=12C3H
Contoh Program array dimensi 3 /*
*Judul Program : Array dimensi 3
*Bahasa Program : Bahasa C
*Pembuat Program : Hendro Pramana
Sinaga
*Tanggal Pembuatan : 5 Mei 2012
*/
#include <stdio.h>
#include <conio.h>
main()
{
char h=64, nama[5][4][22] = {
"AC
Milan","Barcelona","Porto","Monaco",
"Liverpool","Real Madrid","CSK
Moskow","PSG",
"Inter
Milan","Arsenal","Atletico
Madrid","Ajax",
"AS Roma","Manchester
United","Dortmund","Valencia",
"Manchester City","Bayern
Munich","Napoli","Vilareal"
};
printf("Liga Champions : \n\n");
for(i=0; i<5; i++)
{
++h;
printf("Grup %c \n", h);
for(s=0; s<4; s++)
{
printf(" %d. %s \n",
s+1, nama[i][s]);
}
printf("\n");
}
getch();
}
Tampilan Program
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
maksimum elemen <> 0 pada baris ke-I adalah = I,
karenanya total elemen <> 0, tidak lebih dari
N
S I = N(N+1) / 2
I=1
TRINGULAR ARRAY
(ARRAY SEGITIGA)
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(“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 dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.
Single Linked List non Circular
Menggunakan Head dan Tail
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;
tail->next=NULL;
}
else {
baru->next = head;
head = baru;
}
printf(”Data masuk\n”);
}
Menambah Node di Depan
Dengan Head dan Tail
void tambahBelakang(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
tail=baru;
tail->next = NULL;
}
else {
tail->next = baru;
tail=baru;
}
printf("Data masuk\n“);
}
Menambah Node di Belakang
Dengan Head dan Tail
• 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
head baru, kemudian menghapus pointer hapus dengan
menggunakan perintah delete.
• Jika tail masih NULL maka berarti list masih kosong!
Menghapus Node di Depan
(Dengan Head dan Tail)
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!
• 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.
Menghapus Node di Belakang
(Dengan Head dan Tail)
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;
}
Latihan II Soal Struktur Data
(Review Materi Pertemuan 4)
Dikumpulkan pada pertemuan selanjutnya
Buatlah Ilustrasi / Penggambaran untuk
menambah dan menghapus node di posisi tengah
pada :
1. Single Linked List dengan Head
2. Single Linked List dengan Head & Trail
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
(TOP)
• POP
Untuk menghapus item paling atas (TOP)
• CLEAR
Untuk mengosongkan stack
OPERASI STACK
Deklarasi MAX_STACK
#define MAX_STACK 5
Deklarasi STACK dengan struct dan array data
typedef struct STACK{
int top;
int data[5];
};
Deklarasi variabel stack dari struct
STACK tumpuk;
STACK PADA ARRAY
• 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
menunjukkan elemen teratas
Stack.
• TOP of STACK akan selalu
bergerak hingga mencapai
MAX of STACK sehingga
menyebabkan stack PENUH
Inisialisasi
TOP = -1
MAX_STACK 4
3
2
1
0
void inisialisasi ()
{
tumpuk.top = -1
}
Fungsi IsEmpty
• Digunakan untuk memeriksa apakah stack masih dalam kondisi kosong
• Dengan cara memeriksa
TOP of STACK. Jika TOP masih = -1
maka berarti stack masih kosong
int IsEmpty ()
{
if (tumpuk.top == -1
return 1;
else
return 0;
}
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
E
D
C
B
A
4
3
2
1
0
TOP = 4
MAX_STACK
int IsFull ()
{
if (tumpuk.top == MAX_STACK-
1
return 1;
else
return 0;
}
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
3
2
1
0
TOP = -1
MAX_STACK
void push (char d[5])
{
tumpuk.top++
strcpy(tumpuk.data[tumpuk.top],d);
}
A
4
3
2
1
0 TOP = TOP + 1
= -1 + 1
= 0
MAX_STACK
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
B
A
4
3
2
1
0
void pop ()
{
printf(“Data yg di POP = %s\n”, tumpuk.data[tumpuk.top]);
tumpuk.top--;
}
C
B
A
4
3
2
1
0
TOP = 2
MAX_STACK Data yg di POP = C
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
Diketahui suatu stack dgn max_stack = 6
1. Bila dilakukan PUSH 3 elemen kedalam stack, kemudian di PUSH lagi 2 elemen dan di POP 3 elemen. Maka dimana posisi Top of Stack ?
2. IsEmpty pada kondisi terakhir adalah ?
3. Dari kondisi diatas, Berapa elemen yg hrs di PUSH unt mencapai kondisi penuh Top of Stack = max_stack ?
4. Berapa elemen yg hrs di POP unt mencapai kondisi IsEmpty = True
Latihan I Struktur Data
(Pertemuan 5)
Jawaban dibahas dgn
menggunakan contoh program
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.
Prinsip Antrean : FIFO (First In First Out)
FCFS (First Come First Serve)
“Yang Tiba lebih awal Maka akan dilayani Terlebih
Dahulu”
PENGERTIAN QUEUE
(ANTREAN)
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
• ENQUEUE
Untuk menambahkan item pada posisi paling belakang
• DEQUEUE
Untuk menghapus item dari posisi paling depan
• CLEAR
Untuk mengosongkan queue
OPERASI QUEUE
• Digunakan untuk membentuk dan menunjukan awal
terbentuknya suatu Antrean / Queue
Fungsi Create
0 1 2 3 4 5 6 7 Max = 8
head = -1
tail = -1
Antrian pertama kali
Void Create()
{
antrian.head = antrian.tail = -1
}
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
0 1 2 3 4 5 6 7 Max = 8
head = -1
tail = -1
Antrian kosong
Karena tail = -1
Int IsEmpty()
{
if (antrian.tail == -1)
return 1;
else
return 0;
}
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++)
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
Int IsFull()
{
if (antrian.tail == Max-1)
return 1;
else
return 0;
}
• 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 indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca sehingga mengembalikan antrian seperti keadaan semula
Fungsi Clear
Antrian setelah di lakukan Clear
0 1 2 3 4 5 6 7 Max = 8
head = -1
tail = -1
Antrian kosong
Karena tail = -1
Berikan gambaran/ilustrasi dari kasus antrian berikut :
a) Diketahui suatu Antrian/queue dgn max = 6.
b) Lakukan Enqueue 4 elemen ke dalam antrian, dimanakah posisi Head dan Tail ?
c) Kemudian lakukan Dequeue 2 elemen dari antrian. Maka dimana posisi Head dan Tail ?
d) Dari keadaan diatas, bagaimanakah kondisi IsFull dan IsEmpty nya ?
Latihan I Struktur Data
(Pertemuan 6)
Jawaban dibahas dgn
menggunakan contoh program
PERTEMUAN 7
Pertemuan 9
STRUKTUR POHON &
KUNJUNGAN POHON BINER
Pohon (Tree) termasuk struktur non linear yang
didefinisikan sebagai data yang terorganisir dari suatu
item informasi cabang yang saling terkait
Root
E
B C
F
A
G
D
H
Level
DEFINISI POHON (TREE)
---------------------------------- 1
----------------------- 2
------------------ 3
Height = 3
1. Predesesor
Node yang berada diatas node tertentu.
(contoh : B predesesor dari E dan F)
2. Succesor
Node yang berada dibawah node tertentu.
(contoh : E dan F merupakan succesor dari B)
3. Ancestor
Seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.
(contoh : A dan B merupakan ancestor dari F)
Istilah – istilah Dalam Pohon
4. Descendant
Seluruh node yang terletak sesudah node tertentu
dan terletak pada jalur yang sama.
(contoh : F dan B merupakan ancestor dari A)
5. Parent
Predesesor satu level diatas satu node
(contoh : B merupakan parent dari F)
6. Child
Succesor satu level dibawah satu node
(contoh : F merupakan child dari B)
7. Sibling
Node yang memiliki parent yang sama dengan satu
node (contoh : E dan F adalah sibling)
8. Subtree
Bagian dari tree yang berupa suatu node beserta
descendant-nya (contoh : Subtree B, E, F dan
Subtree D, G, H)
9. Size
Banyaknya node dalam suatu tree (contoh : gambar
tree diatas memiliki size = 8)
10. Height
Banyaknya tingkat/level dalam suatu tree (contoh :
gambar tree diatas memiliki height = 3)
11. Root (Akar)
Node khusus dalam tree yang tidak memiliki
predesesor (Contoh : A)
12. Leaf (Daun)
Node-node dalam tree yang tidak memiliki daun
(contoh : Node E,F,C,G,H)
13. Degree (Derajat)
Banyaknya child yang dimiliki oleh suatu node
(contoh : Node A memiliki derajat 3, node B memiliki
derajat 2)
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.
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
ISTILAH-ISTILAH DASAR
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,
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.
Sifat utama Pohon Berakar
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
Struktur ini biasanya digunakan untuk menyajikan data
yang mengandung hubungan hirarkial antara elemen-
elemennya.
Bentuk Pohon Berakar yang lebih mudah dikelola dalam
komputer adalah Pohon Biner (Binary Tree) yang lebih
dikenal sebagai Pohon Umum (General Tree) yang dapat
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).
POHON BINAR (BINARY TREE)
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
• Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang
sama
P
Q R
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.
• 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.
Penyajian Pohon Binar
(Binary Tree)
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
A B D E C
Klik Animasi
Klik Animasi
Kunjungan InOrder dalam Program C++
A
B C
D E
A B D E C
3. Kunjungan secara Postorder, mempunyai urutan :
a. Kunjungi Cabang Kiri
b. Kunjungi Cabang Kanan
c. Cetak isi simpul yang dikunjungi (Simpul Akar)
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
GRAPH dan
MATRIK PENYAJIAN 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 seperti dimaksud diatas, ditulis sebagai G(E,V).
GRAPH
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.
e5
e4
e3 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
dari ruas e.
GRAPH BERLABEL
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
E D
B
C
A F
Contoh :
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 :
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
KETERHUBUNGAN
Graph 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 U dan
simpul akhir T berderajat = 1.
Barisan ruas a,b,c,d,b,c,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
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
4
3
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
V1
V2
V4
V3
V5
Total Minimum
Spanning Tree = 22
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
(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
Pertemuan 12-14
PRESENTASI
PROJECT
PERTEMUAN 15