Algoritma Dan Struktur Data II
Array dan Matriks
Apa itu Struktur Data ?
PROGRAM
ALGORITMA
STRUKTUR DATA
Algoritma …..
deskripsi langkah-langkah penyelesaian masalah yang tersusun secara logis 1. ditulis dengan notasi khusus 2. notasi mudah dimengerti 3. notasi dapat diterjemahkan menjadi sintaks suatu bahasa pemrograman
Struktur Data …..
model logika/matematik yang secara khusus mengorganisasi data
Contoh Struktur Data …..
Array A satu dimensi : 8 indeks (1 s/d 8) dan data 1, 7, 18 dst. 1
7
18
03
69
24
08
70
1
2
3
4
5
6
7
8
Contoh Struktur Data ….. Ar ray B dua di mensi (matr iks) : - j uml ah bari s 2, kol om 3 - d ata 18, 03, 69, 24, 08, 70.
1
2
3
1
18
03
69
2
24
08
70
Contoh Struktur Data …..
List Berkait / Senarai
Contoh Struktur Data ….. Tumpukan dengan tiga data ( 18, 03, dan 69 yang mer upakan posisi terakhir / TOP )
69
03
18
<< TOP
Contoh Struktur Data ….. Pohon dengan akar A
A
B
C
D
E
F
Struktur Data …..
Tempat Penyimpanan Data
Operasi terhadap data
• •
Traversal (Traversing) : mengunjungi setiap elemen SD Pencarian (Searching) : menemukan elemen/lokasi pada SD • Penyisipan (Inserting) : menambah elemen baru pada SD •
Penghapusan (Deleting) : menghapus elemen dari SD
Kita lanjutkan untuk yang satu ini …..
Struktur Data :
Array / Larik
Tujuan Membahas struktur data yang paling sederhana dan mudah pengoperasiannya, yaitu array / larik. Definisi struktur data yang mengacu pada sekumpulan elemen yang diakses melalui indeks
KELEBIHAN & KEKURANGAN Array / Larik
• KELEBIHAN
- Struktur Data paling mudah - Memori ekonomis, bila semua elemen terisi - Waktu akses sama ke setiap elemen
KEKURANGAN - Boros memori jika banyak elemen yang tidak
digunakan - Struktur Data Statis
CONTOH PROSES Array / Larik
ALGORITMA For Indeks 1 to N do PROSES LARIK Endfor Mengisi
elemen larik dengan 0 (inisialisasi) Mengisi
elemen larik dari piranti
masukan Mencetak
keluaran
elemen larik ke piranti
INISIALISASI Array / Larik
ALGORITMA For Indeks 1 to 8 do A[Indeks] = 0 Endfor
0
0
0
0
0
0
0
0
INPUT ELEMEN Array / Larik
ALGORITMA For Indeks 1 to 8 do Input A[Indeks] Endfor
1
3
5
7
2
9
?1 ?3 ?5
4
7
CETAK ELEMEN Array / Larik
ALGORITMA For Indeks 1 to 8 do Print A[Indeks] Endfor
2 7 4 9 7 5 13
1
3
5
7
2
9
4
7
Array vs Struct •
•
Array : penampung sejumlah data sejenis (yang memiliki type data yang sama) dengan menggunakan satu identifier Elemen array dapat diakses dengan menggunakan index, dari nol sampai n-1 (n: jumlah elemen array) Contoh : int x[5]; printf(“%d”,x[3]);
Array vs Struct •
•
Struct: struktur data yang menggabungkan beberapa data dengan tipe yang berbeda, tetapi berkaitan Elemen struct dapat diakses dengan menggunakan dot operator dan arrow operator.
Struct Gabungan beberapa variable dengan tipe yang berbeda 学籍番号 学籍番号 名前学籍番号 名前 生年月日 名前 生年月日 nama 体重生年月日 体重 Nilai math 身長体重 Nilai biology 身長 身長 Nilai geography Nilai English Nilai Bhs.Indonesia Nilai rata-rata
struct NILAI { char nama[100]; float math; float biology; float geography; float english; float bi; float ratarata; }; struct NILAI p[10]; Deklarasi struct
Gabungan beberapa variable dengan tipe yang berbeda Struct 学籍番号 学籍番号 名前学籍番号 名前学籍番号 生年月日 名前学籍番号 生年月日 名前nama 体重生年月日 名前 体重生年月日 Nilai math 身長体重 Nilai biology 生年月日 身長体重 Nilai geography 身長体重 身長Nilai English 身長 Nilai Bhs.Indonesia Nilai rata-rata
struct NILAI { char nama[100]; float math; float biology; float geography; float english; float bi; float ratarata; } p[10];
Beberapa Jenis Struktur Data 1.
Array 1. Linear List 2. Stack 3. Queue
2. List 1. Connected List 2. Circular List 3. Doubly-linked List 4. Multi list structure 3. Tree Structure
1. Apa ? 2. Bagaimana cara implementasinya ?
Linear List
Apakah Linear List itu ?
• Sekumpulan elemen yang diatur secara terurut x[1], x[2],L , x[k − 1], x[k ], x[k + 1], L , x[n]
• Linear List tidak sama dengan Connected-List
Operasi pada Linear List No.
Operasi 1
Menambahkan sebuah elemen sebelum elemen ke-k
2
Menghapus elemen ke-k
3
Membaca/menulis isi elemen ke-k
4
Mencari elemen dengan key tertentu
5
Menggabungkan beberapa list menjadi satu
6
Memecah sebuah list ke beberapa buah
7
Mengcopy sebuah list
8
Menghitung banyaknya elemen dalam sebuah list
List, Stack & Queue • Tidak semua operasi list diperlukan pada setiap program ▫ Penentuan struktur data didasarkan pada operasi yang diperlukan saja agar bisa berjalan dengan efisien • Pada sebuah Linear List, penyisipan dan penghapusan elemen dapat dijalankan di sebarang posisi • Bentuk khusus linear list: Penambahan elemen dan penghapusannya dilakukan di posisi terdepan atau posisi terbelakang saja Stack dan Queue juga merupakan salah satu jenis list
Stack Queue
List, Stack & Queue • Pada sebuah Linear List, penyisipan dan penghapusan elemen dapat dijalankan di sebarang posisi • Penambahan dan penghapusan elemen pada stack/queue dilakukan di posisi terdepan atau posisi terbelakang saja
List
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
Stack
Queue
Stack
Apakah Stack itu ?
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi PUSH : Menambahkan elemen pada sebuah stack PUSH
1
top== bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi PUSH : Menambahkan elemen pada sebuah stack PUSH
2 1
top bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi PUSH : Menambahkan elemen pada sebuah stack 3
top
2 PUSH
1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi PUSH : Menambahkan elemen pada sebuah stack 4
top
3 PUSH
2 1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi PUSH : Menambahkan elemen pada sebuah stack top 5
PUSH
4 3 2 1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi PUSH : Menambahkan elemen pada sebuah stack top 6 5 PUSH
4 3 2 1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi POP : Menghapus sebuah elemen dari sebuah stack top 6 5 POP
4 3 2 1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi POP : Menghapus sebuah elemen dari sebuah stack top 5
POP
4 3 2 1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi POP : Menghapus sebuah elemen dari sebuah stack POP
4
top
3 2 1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi POP : Menghapus sebuah elemen dari sebuah stack 3 POP
top
2 1
bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain lain： LIFO (Last In First Out) • Operasi POP : Menghapus sebuah elemen dari sebuah stack
POP
2 1
top bottom
Apakah Stack itu ? • Penambahan dan penghapusan elemen dilakukan pada elemen list yang terletak di paling depan • Yang dihapus adalah elemen yang paling terakhir ditambahkan • Nama lain： LIFO (Last In First Out) • Operasi POP : Menghapus sebuah elemen dari sebuah stack
POP 1
top==bottom
Apakah Stack itu ?
PUSH
dan
POP
Stack Overflow & Stack Underflow • Stack Overflow Menambahkan data pada sebuah stack yang telah penuh • Stack Underflow Menghapus data dari sebuah stack yang sudah kosong
Apakah Queue itu ?
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front==rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list 1 2 ENQUEUE front
rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front
2
3 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front
2
3
4 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front
2
3
4
5 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front
2
3
4
5
6 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE
1 front
2
3
4
5
6 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE
2 front
3
4
5
6 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE
3 front
4
5
6 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE
4 front
5
6 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE
5 front
6 rear
Apakah Queue itu ? • Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE
6 front==rear
Animasi Queue
ENQUEUE dan DEQUEUE
• Gambarkan kondisi stack setelah dilakukan operasi berikut:
Latihan 1
push(10); push(2); pop(); push(20); pop(); push(15); push(5);
2 10
10
• Gambarkan kondisi queue setelah dilakukan operasi berikut:
Latihan 2
enqueue(10); enqueue(32);
10
enqueue(5); dequeue(); enqueue(10); dequeue(); dequeue();
10
32
