Algoritma & Struktur Data
Array Oleh : Nur Hayatin, M.Kom
Teknik Informatika Universitas Muhammadiyah Malang 2016
About.. [U’r Lecturer] • Nama : Nur Hayatin, M.Kom • Email :
[email protected] • Research Interest [not limited to] : Information Retrieval Search Engine Technology Social Media Analysis
Pendahuluan • Pemilihan algoritma dan struktur data yang tepat peningkatan performansi program • Performansi program : – Time complexity – Space complexity
Pendahuluan • Algoritma : – Pencarian (searching) – Pengurutan (sorting)
• Struktur Data : – Array – Linked list – Stack – Queue – Binary Tree – Graf
Referensi • Nana Ramadiyanti, Pemrograman Lanjut : Array, Pens-ITS • Sahni, Sartaj, “Data Structures, Algorithms, and Applications in Java”. McGraw-Hill International Editions. • L.N. Harnaningrum, Struktur Data menggunakan Java, Graha ilmu, 2010 • Siswanto, Algoritma & Struktur Data Linier, Graha Ilmu, 2010
Catatan • Semua source code yang digunakan sebagai contoh dan tugas dalam perkuliahan ini menggunakan JAVA. • Materi dasar JAVA yang dibutuhkan : – Abstraksi (class abstrak maupun interface) – Override method – Java Collection Framework (JCF)
Struktur Data • Struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien. (https://id.wikipedia.org/wiki/Struktur_data)
Jenis Struktur Data • Struktur Data Linier : – Array – Linked list – Stack – Queue
• Struktur Data Hirarki : – Tree – Graf
Struktur Data • Cara memilih struktur data yang tepat memahami karakteristik struktur data. • Karakteristik struktur data, meliputi : – mekanisme pengaturan data dalam media penyimpanan computer – programming effort (kompleksitas) – waktu yang dibutuhkan untuk menjalankan operasi” dasar
Struktur Data • Beberapa pertanyaan terkait dengan karakteristik struktur data, a.n : – Bagaimana mekanisme penambahan data (dari depan/belakang/tengah)? – Apakah data bisa dihapus? – Bagaimana mekanisme pemrosesan data (harus terurut atau dapat diakses secara random)? Setiap struktur data memiliki kelemahan dan kelebihan.
Istilah • Istilah-istilah yang digunakan dalam struktur data : – – – – – – – – –
Elemen = data item/obyek pada list Indeks Node Pointer List = elemen-elemen yang susunannya terurut. Empty = tidak ada elemen didalam list. Size = jumlah elemen yang ada pada list Head = awal dari list, elemen terdepan pada list. Tail = akhir dari list, elemen terakhir pada list.
Struktur Data
ARRAY
Outline • Definisi Array • Operasi dasar Array • Contoh Class ArrayLinearList
Definisi • Sebuah tipe data yang mampu meyimpan data/variabel dengan nama dan tipe yang sama. • Contoh : nilai grade dari 6 mahasiswa 0
1
2
3
4
5
Index Elemen
• Keterangan – Terdiri dari 6 elemen – Elemen pertama pada index ke-0 elemen terakhir pada index ke-5
• Array pada java selalu diawali dengan index ke-0!!!!!
Deklarasi • Contoh : int grade[] = new int[6]; atau int []grade = new int[6];
Inisialisasi • Contoh : int grade[] = {5,8,9,7,6,7}; atau : int grade[] = new int[6]; grade[0] = 5; grade[1] = 8; grade[2] = 9; grade[3] = 7; grade[4] = 6; grade[5] = 7; • Untuk mendapatkan panjang array : panggil method length()
Pengaksesan Elemen • x = grade[5]; mengakses elemen grade pada index ke-5 yang akan diisikan ke variabel x.
• System.out.print(grade[0]); mengakses sekaligus menampilkan elemen grade pada index ke-0.
• Elemen array yang dapat diakses dimulai dari index 0 sampai elemen.length()-1
Contoh Program public class ArraySample { public static void main( String[] args ){ int[] ages = new int[100]; for( int i=0; i
Contoh:
Create dua dimensional array
• int[] [] myArray = new int [3] [];
Contoh program
Hasil running • Length pada Indeks ke-0 =3 • Length pada Indeks ke-1 =5 • Finished executing
Program
Hasil running • • • •
Elemen pd Dimensi ke-1 = 2 Elemen pd Dimensi ke-2 = 3 Elemen pd Dimensi ke-3 = 4 Finished executing
Operasi Dasar Array • Meliputi : – Pengecekan array kosong (empty) – Pengecekan array terisi penuh (full) – Penambahan elemen – Penghapusan elemen – Pencarian elemen pada array – Pencarian index elemen pada array
Operasi Add add(0,23)
Hasil akhir
Operasi Remove size = 6 a
g
b
c
d
d
e
remove(1) size = 5 a
b
c
e
Operasi get 0 a
1
2 3 4
b
c
get(2)? get(5)?
d
e
Operasi indexOf 0 a
1
2 3 4
b
c
d
indexOf(e)? indexOf(b)? indexOf(s)?
e
Increasing Array Length Length of array element[] is 6. a
b
c
d
e
f
First create a new and larger array newArray = new Object[15];
Increasing Array Length Now copy elements from old array to new one. a
a
b
b
c
c
d
d
e
e
f
f
Increasing Array Length Finally, rename new array. element = newArray; element[0]
a
b
c
d
e
f
element.length = 15
Altogether Now // create a new array of proper length and data type Object [] newArray = new Object [newLength]; // copy all elements from old array into new one System.arraycopy(element, 0, newArray, 0, element.length); // rename array element = newArray;
Latihan Diketahui L=(a,b,c,d). L adalah sebuah array. Tentukan hasil yang didapatkan ketika dilakukan perintah berikut ini : a) b) c) d) e) f)
isEmpty() size() get(0), get(2),get(6),get(-3) indexOf(a), indexOf(c), indexOf(q) remove(0), remove(2), remove(3) add(0,e), add(2,f), add(3,g), add(4,h), add(6,h), add(-3,h)
Linear List Abstract Data Type AbstractDataType LinearList { instances ordered finite collections of zero or more elements operations isEmpty(): mengembalikan nilai true jika kosong dan sebaliknya. size(): mengembalikan jumlah elemen pada list get(index): mengembalikan elemen sesuai index yang dimasukkan indexOf(x): mengembalikan nilai index dari elemen x yang dimasukkan, -1 jika elemen tidak ditemukan remove(index): menghapus elemen sesuai index yang dimasukkan add(theIndex, x): menambah elemen x pada index yang ditentukan output(): menampilkan semua elemen pada list dari kiri ke kanan }
Linear List as Java Interface public interface LinearList { public boolean isEmpty(); public int size(); public Object get(int index); public int indexOf(Object elem); public Object remove(int index); public void add(int index, Object obj); public String toString(); }
Implementing An Interface public class ArrayLinearList implements LinearList { // code for all LinearList methods must be provided here }
Linear List As Java Abstract Class public abstract class LinearListAsAbstractClass { public abstract boolean isEmpty(); public abstract int size(); public abstract Object get(int index); public abstract int indexOf(Object theElement); public abstract Object remove(int index); public abstract void add(int index, Object theElement); public abstract String toString(); }
Extending A Java Class public class ArrayLinearList extends LinearListAsAbstractClass { // code for all abstract classes must come here }
Class ArrayLinearList
Class ArrayLinearList import java.util.*; import utilities.*; public class ArrayLinearList implements LinearList { protected Object [] element; // array of elements protected int size; // number of elements in array
Data Type Of Array element[] Data type of list elements is unknown. Define element[] to be of data type Object. Cannot put elements of primitive data types (int, float, double, char, etc.) into our linear lists.
Constructor public ArrayLinearList(int initialCapacity) { if (initialCapacity < 1) throw new IllegalArgumentException ("initialCapacity must be >= 1"); element = new Object [initialCapacity]; } public ArrayLinearList() { this(10); }
Method isEmpty() dan size() public boolean isEmpty() { return size == 0; } public int size() { return size; }
Method get() void checkIndex(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException ("index = " + index + " size = " + size); } public Object get(int index) { checkIndex(index); return element[index]; }
Method indexOf()
public int indexOf(Object theElement) { for (int i = 0; i < size; i++) if (element[i].equals(theElement)) return i; return -1; }
Method remove()
public Object remove(int index) { checkIndex(index); Object removedElement = element[index]; for (int i = index + 1; i < size; i++) element[i-1] = element[i]; element[--size] = null; return removedElement; }
Method add() public void add(int index, Object theElement) { checkIndex(index); if (size == element.length) element = ChangeArrayLength.changeLength1D(element, 2 * size); for (int i = size - 1; i >= index; i--) element[i + 1] = element[i]; element[index] = theElement; size++; }
Latihan 2.
Buatlah sebuah array yang memenuhi spesifikasi yang ada pada tabel disamping. Petunjuk : • Buatlah class Bank yang memiliki dua variabel array tsb. • Berikan inisialisasi pada variabel antrian dengan angka terurut mulai dari 1. sedangkan inisialisasi variabel nasabah dengan obyek yg mengacu pada class Customer. • Berikan nilai saldo pada tiap objek yang ada dengan memanggil method setSaldo() menggunakan nasabah[0]. • Lakukan pengaksesan untuk setiap elemen pada array antrian. • Lakukan pengaksesan method getSaldo().
Variabel Array
Tipe data
Besar Array
nasabah
Customer
3
antrian
int
3
Class Customer{ double saldo; void setSaldo(double dana) { saldo = saldo+dana; } double getSaldo() { return saldo; } }
Latihan 3. Buatlah sebuah array dua dimensi untuk menyimpan sebuah kata bahasa indonesia beserta kata padanan bahasa inggrisnya. petunjuk : – – – –
Kata yg disimpan diberikan 5 kata. Element 1 digunakan untuk menyimpan kata bahasa indonesia Element 2 digunakan untuk menyimpan kata bahasa inggris Cobalah mengakses kata bahasa inggris dari kata bahasa indonesia yang dipilih pleh user.
Latihan 4. Diketahui L=(a,b,c,d). L adalah sebuah array linier list. Tentukan hasil yang didapatkan ketika dilakukan perintah berikut ini : a) b) c) d) e) f)
isEmpty() size() get(0), get(2),get(6),get(-3) indexOf(a), indexOf(c), indexOf(q) remove(0), remove(2), remove(3) add(0,e), add(2,f), add(3,g), add(4,h), add(6,h), add(-3,h)
