STRUKTUR DATA By : Sri Rezeki Candra Nursari
2 SKS
Literatur • Sjukani Moh., (2007), “Struktur Data (Algoritma & Struktur Data 2) dengan C, C++”, Mitra Wacana Media • Utami Ema. dkk, (2007),”Struktur Data (Konsep & Implementasinya Dalam Bahasa C & Free Pascal di GNU/Linux)”, Graha Ilmu • Hubbard Jhon, R., Ph.D, (2000), “Schaum’s Outline Of Theory and Problems of Data Structures With C++” McGraw-Hill • Bambangworawan Paulus., (2004), “Struktur Data Dengan C”, Andi Yogyakarta
Materi 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Data dan Struktur Data Array Struktur dan Record Pointer Linked List Stack (Tumpukan) Queue (Antrian) Tree (Pohon) AVL Tree Heap dan B-Tree Sorting Search Hashing Graph
SEARCH Pertemuan 14
2 SKS
SEARCHING Pencarian (searching) merupakan proses yang fundamental dalam pemrograman. Mencari data dengan menelusuri tempat penyimpanan data. Tempat penyimpanan data dalam memory dapat berupa array/linked list Beberapa metoda diantaranya adalah : – – – –
Sequential Search Binary Search Fibonacci Search Interpolation Search
Sequential Search Sequential Search/Pencarian Sekuential adalah proses membandingkan setiap elemen Larik satu persatu secara beruntun, dari elemen pertama sampai elemen yang dicari ditemukan Data yang ada pada suatu array dibandingkan satu persatu dengan data yang dicari Pencarian ini hanya melakukan pengulangan dari 1 s.d. dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan, tidak ada yang sama, berarti data tidak ada
Sequential Search
Sequential Search Algoritma Pencarian dengan metode Sequential Search / Pencarian Sekuensial adalah i1 Ketemu False Selama (not ketemu) dan ( i N) kerjakan baris 4 Jika (Data[i] = x) maka ketemu true, jika tidak i i + 1 5. IF (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan 1. 2. 3. 4.
Sequential Search Algoritma Pencarian dengan metode Sequential Search / Pencarian Sekuensial adalah 1. Tentukan dan simpan data dalam suatu array 2. Tentukan fungsi pencarian sekuensial 3. Fungsi pencarian sekuensial adalah sebagai berikut : int flag=-1; { for(int count=0; count < array_size; count++) { flag=count; break; } } 4. Masukkan data yang akan dicari 5. Kerjakan langkah 3, jika data ketemu kerjakan lang-kah 6. Jika data tidak ketemu lakukan langkah 6 6. Cetak data tersebut 7. Selesai
Sequential Search
Output Sequential Search
Binary Search Pencarian sebuah elemen dalam sebuah array satu dimensi dengan cara selalu membandingkan dengan nilai yang berada di tengah array tersebut Apabila tidak sama maka array akan dibagi dua dan pencarian diulang pada bagian dimana nilai yang dicari.
Binary Search Salah satu syarat pencarian bagi dua (binary search) adalah data sudah dalam keadaan terurut Apabila data belum keadaan terurut, pencarian biner tidak dapat dilakukan Data yang terurut merupakan syarat mutlak penerapan pencarian Algoritma pencarian Bagi Dua
Binary Search Prinsip dari pencarian Biner 1. Pertama diambil posisi awal =1 dan posisi akhir =N, kemudian dicari posisi data tengah dengan rumus (posisi awal+posisi akhir)/2 2. Kemudian data yang dicari dibandingkan dengan data tengah 3. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1 4. Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1 5. Demikian seterusnya sampai data tengah sama dengan yang dicari
Binary Search Array 1 dimensi dengan int A[10] = {4, 7, 10, 11, 16, 22, 24, 28, 63, 64}. Mencari titik tengah dari suatu bagian array, dan membandingkan nilainya dengan N. Langkahnya adalah sebagai berikut 1. Input N. Tentukan Lo=0; Hi=N-1; dan Flag=0 (untuk tanda tidak ditemukan yang dicari) Mid = (Lo + Hi)/2 2. Selama Lo <= Hi dan Flag==0 Hitung Mid=(Lo+Hi)/2 Bila N==A[Mid], isi Flag=1; (tanda ditemukan) Bila N
A[Mid], isi Hi=Mid+1, proses pencarian dibagian kanan
3. Proses pencarian selesai
Binary Search 16 Hitung Mid MID = (Lo + Hi)/2 = (6+10)/2 = 8 A[Mid] = A[8] = 28
7 28
4
64
22
10
11
24
63
Periksa nilai N N > A[Mid] Lo = Mid-1 = 8-1 =7 Hi tetap = 6
Binary Search 16
7
Hitung Mid MID = (Lo + Hi)/2 = (0+10)/2 = 5 A[Mid] = A[5] = 16
28
4
11
Periksa nilai N N < A[Mid] Lo = Mid-1 = 5+1 Hi tetap = 10
64
22
10
24
63
Binary Search
Binary Search
Binary Search
Binary Search
Fibonacci Search Merupakan pencarian sebuah elemen dalam sebuah array satu dimensi dengan menggunakan angka fibonacci sebagai titik-titik (index) elemen array yang isinya dibandingkan dengan nilai yang dicari (misal N) Salah satu syarat pencarian fibonacci adalah data sudah dalam keadaan terurut Prosesnya hanya menggunakan operasi tambah dan kurang yang memerlukan waktu yang lebih cepat dibandingkan dengan proses pembagian yang digunakan pada binary search
Fibonacci Search
Fibonacci Search
Interpolation Search Merupakan pencarian sebuah elemen dalam sebuah array satu dimensi dengan menggunakan rumus interpolasi atau perkiraan secara interpolasi Berlaku rumus interpolasi adalah b/a = q/p
Interpolation Search
