algoritmadan strukturdata ii & kekurangan • kelebihan-struktur data paling mudah-memori...
TRANSCRIPT
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 yang tersusun secara logis 1. ditulis dengan notasi khusus2. notasi mudah dimengerti3. notasi dapat diterjemahkan menjadi
sintaks suatu bahasa pemrograman
Struktur Data …..
model logika/matematik
yang secara khusus
mengorganisasi data 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 …..
Array B dua dimensi (matriks) :
- jumlah baris 2, kolom 3- data 18, 03, 69, 24, 08, 70.
1 2 3
18 03 69
24 08 70
1
2
1 2 3
Contoh Struktur Data …..
List Berkait / Senarai
Contoh Struktur Data …..
Tumpukan dengan tiga data( 18, 03, dan 69 yang merupakan
posisi terakhir / TOP )
69
03
<< TOP
18
Contoh Struktur Data …..
A
Pohon dengan akar A
B C D
E F
Struktur Data …..
Tempat
Penyimpanan Data
Operasi
terhadap dataPenyimpanan Data terhadap data
• Traversal (Traversing) : mengunjungi setiap elemen SD• Pencarian (Searching) : menemukan elemen/lokasi padaSD
• Penyisipan (Inserting) : menambah elemen baru pada SD
• Penghapusan (Deleting) : menghapus elemen dari SD
Kita lanjutkan Kita lanjutkan
untuk yang satu ini …..untuk yang satu ini …..
Struktur Data :Struktur Data : Array / LarikArray / Larik
Tujuan
Membahas struktur data yang paling sederhana dan
mudah pengoperasiannya, yaitu array / larik.
DefinisiDefinisi
struktur data yang mengacu pada sekumpulan
elemen yang diakses melalui indeks
KELEBIHAN & KEKURANGAN
• KELEBIHAN- Struktur Data paling mudah
� - Memori ekonomis, bila semua elemen terisi
� - Waktu akses sama ke setiap elemen
Array / LarikArray / Larik
� KEKURANGAN- Boros memori jika banyak elemen yang tidak digunakan
� - Struktur Data Statis
CONTOH PROSES Array / LarikArray / Larik
ALGORITMA
For Indeks � 1 to N do
PROSES LARIK
Endfor
�Mengisi elemen larik dengan 0 (inisialisasi)
�Mengisi elemen larik dari pirantimasukan
�Mencetak elemen larik ke pirantikeluaran
Endfor
INISIALISASIArray / LarikArray / Larik
ALGORITMA
For Indeks � 1 to 8 do
A[Indeks]A[Indeks] == 00
EndforEndfor
0 0 0 0 0 0 0 0
INPUT ELEMENArray / LarikArray / Larik
ALGORITMA
For Indeks � 1 to 8 do
Input A[Indeks]A[Indeks]
Endfor
? 1
? 3
? 5Endfor
1 3 5 7 2 9 4 7
CETAK ELEMENArray / LarikArray / Larik
ALGORITMA
For Indeks � 1 to 8 do
Print A[Indeks]A[Indeks]
Endfor
13572947
Endfor
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)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
学籍番号名前生年月日
学籍番号名前学籍番号名前
struct NILAI {
char nama[100];
float math;
float biology;生年月日体重身長
名前生年月日体重身長
名前生年月日体重身長
nama
Nilai math
Nilai biology
Nilai geography
Nilai English
Nilai Bhs.Indonesia
Nilai rata-rata
float biology;
float geography;
float english;
float bi;
float ratarata;
};
struct NILAI p[10];
Deklarasi struct
Struct
Gabungan beberapa variable dengan tipe yang berbeda
学籍番号名前生年月日
学籍番号名前学籍番号名前学籍番号
struct NILAI {
char nama[100];
float math;
float biology;生年月日体重身長
名前生年月日体重身長
名前生年月日体重身長
学籍番号名前生年月日体重身長
学籍番号名前生年月日体重身長
nama
Nilai math
Nilai biology
Nilai geography
Nilai English
Nilai Bhs.Indonesia
Nilai rata-rata
float biology;
float geography;
float english;
float bi;
float ratarata;
} p[10];
Beberapa Jenis Struktur Data
1. Array 1. Linear List2. Stack3. Queue
1. Apa ?
2. Bagaimana cara implementasinya ?3. Queue
2. List1. Connected List2. Circular List3. Doubly-linked List4. Multi list structure
3. Tree Structure
2. Bagaimana cara implementasinya ?
Linear ListLinear List
Apakah Linear List itu ?
• Sekumpulan elemen yang diatur secara terurut
][,],1[],[],1[,],2[],1[ nxkxkxkxxx LL +−
• Linear List tidak sama dengan Connected-List
][,],1[],[],1[,],2[],1[ nxkxkxkxxx LL +−
Operasi pada Linear List
No. Operasi
1 Menambahkan sebuah elemen sebelum elemen ke-k
2 Menghapus elemen ke-k2 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 penghapusanelemen dapat dijalankan di sebarang posisi
• Pada sebuah Linear List, penyisipan dan penghapusanelemen dapat dijalankan di sebarang posisi
• Bentuk khusus linear list:Penambahan elemen dan penghapusannyadilakukan di posisi terdepan atauposisi terbelakang saja
Stack
Queue
Stack dan Queue juga merupakan salah satu jenis list
List, Stack & Queue
• Pada sebuah Linear List, penyisipan dan penghapusanelemen dapat dijalankan di sebarang posisi
• Penambahan dan penghapusan elemen pada stack/queue dilakukan di posisi terdepan atau posisi terbelakang saja
1 2 63 4 5
1 2 63 4 5
1 2 63 4 5
List
Stack
Queue
StackStack
Apakah Stack itu ?
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)
• Operasi PUSH : Menambahkan elemen pada sebuahstack
1PUSH 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
PUSH1
2 top
bottom
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkanditambahkan
• Nama lain: LIFO (Last In First Out)
• Operasi PUSH : Menambahkan elemen pada sebuahstack
PUSH 1
2
3
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)• Nama lain: LIFO (Last In First Out)
• Operasi PUSH : Menambahkan elemen pada sebuahstack
PUSH1
2
3
4
bottom
top
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 • Operasi PUSH : Menambahkan elemen pada sebuah stack
PUSH
1
2
3
4
5
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)
• Operasi PUSH : Menambahkan elemen pada sebuah• Operasi PUSH : Menambahkan elemen pada sebuahstack
PUSH
1
2
3
4
5
6
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)
• Operasi POP : Menghapus sebuah elemen dari sebuah• Operasi POP : Menghapus sebuah elemen dari sebuahstack
POP
1
2
3
4
5
6
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)
• Operasi POP : Menghapus sebuah elemen dari sebuah• Operasi POP : Menghapus sebuah elemen dari sebuahstack
POP
1
2
3
4
5
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)• Nama lain: LIFO (Last In First Out)
• Operasi POP : Menghapus sebuah elemen dari sebuahstack
POP
1
2
3
4
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)• Nama lain: LIFO (Last In First Out)
• Operasi POP : Menghapus sebuah elemen dari sebuahstack
POP
1
2
3
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)• Nama lain LIFO (Last In First Out)
• Operasi POP : Menghapus sebuah elemen dari sebuahstack
POP1
2
bottom
top
Apakah Stack itu ?
• Penambahan dan penghapusan elemen dilakukan padaelemen list yang terletak di paling depan
• Yang dihapus adalah elemen yang paling terakhirditambahkan
• Nama lain: LIFO (Last In First Out)
• Operasi POP : Menghapus sebuah elemen dari sebuah• Operasi POP : Menghapus sebuah elemen dari sebuahstack
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• Stack Underflow
Menghapus data dari sebuah stack yang sudah kosong
Apakah Queue itu ?
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)
• Operasi ENQUEUE: menambahkan data pada sebuahlist
1ENQUEUE
front==rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)• Nama lain: FIFO (First In First Out)
• Operasi ENQUEUE: menambahkan data pada sebuahlist
1ENQUEUE
front
2
rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)
• Operasi ENQUEUE: menambahkan data pada sebuahlist
1ENQUEUE
front
3
rear
2
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)
• Operasi ENQUEUE: menambahkan data pada sebuah• Operasi ENQUEUE: menambahkan data pada sebuahlistENQUEUE
1
front
32 4
rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)
• Operasi ENQUEUE: menambahkan data pada sebuahlistENQUEUE
1
front
32 5
rear
4
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)• Nama lain: FIFO (First In First Out)
• Operasi ENQUEUE: menambahkan data pada sebuahlist
ENQUEUE 1
front
32 54 6
rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)• Nama lain: FIFO (First In First Out)
• OperasiDEQUEUE: menghapus data pada sebuah listDEQUEUE
1
front
32 54 6
rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)• Nama lain: FIFO (First In First Out)
• OperasiDEQUEUE: menghapus data pada sebuah list
DEQUEUE
front
32 54 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)• Nama lain: FIFO (First In First Out)
• Operasi DEQUEUE: menghapus data pada sebuah list
DEQUEUE
front
3 54 6
rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)• Nama lain: FIFO (First In First Out)
• OperasiDEQUEUE: menghapus data pada sebuah list
DEQUEUE
front
54 6
rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)• Nama lain: FIFO (First In First Out)
• OperasiDEQUEUE: menghapus data pada sebuah list
DEQUEUE
front
5 6
rear
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuahlist, sedangkan penghapusan data dilakukan pada ujungyang lain
• Data yang dihapus adalah data yang paling awalditambahkan
• Nama lain: FIFO (First In First Out)• Nama lain: FIFO (First In First Out)
• OperasiDEQUEUE: menghapus data pada sebuah list
DEQUEUE6
front==rear
Animasi Queue
ENQUEUE dan DEQUEUE
push(10);
push(2);
Latihan 1
• Gambarkan kondisi stack setelah dilakukan operasiberikut:
10 10
2
push(2);
pop();
push(20);
pop();
push(15);
push(5);
10 10
enqueue(10);
enqueue(32);
enqueue(5);
10
Latihan 2
• Gambarkan kondisi queue setelah dilakukan operasi berikut:
enqueue(5);
dequeue();
enqueue(10);
dequeue();
dequeue();
10 32