algoritmadan strukturdata ii & kekurangan • kelebihan-struktur data paling mudah-memori...

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