struktur data (12) organisasi berkas (file)

35
STRUKTUR DATA (12) organisasi berkas (file)

Upload: mariko

Post on 19-Jan-2016

110 views

Category:

Documents


16 download

DESCRIPTION

STRUKTUR DATA (12) organisasi berkas (file). Organisasi Berkas (File). Sekuensial Record disimpan dalam file secara beruntun berdasarkan kedatangannya Record yang masuk pertama akan memiliki indeks atau alamat yang lebih kecil daripada record yang masuk kemudian Langsung Sekuensial Berindeks. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: STRUKTUR DATA (12) organisasi berkas (file)

STRUKTUR DATA (12)organisasi berkas (file)

Page 2: STRUKTUR DATA (12) organisasi berkas (file)

Organisasi Berkas (File)

• Sekuensial• Record disimpan dalam file secara

beruntun berdasarkan kedatangannya• Record yang masuk pertama akan

memiliki indeks atau alamat yang lebih kecil daripada record yang masuk kemudian

• Langsung• Sekuensial Berindeks

Page 3: STRUKTUR DATA (12) organisasi berkas (file)

File Langsung

• Dengan organisasi ini, untuk menemukan suatu record, maka tidak melalui proses pencarian, namun langsung menuju ke alamat yang ditempati record

• Contoh: record dengan key 100 akan disimpan pada alamat 100

• Kerugian: berarti harus ada ruang yang cukup besar untuk menampung semua kemungkinan key yang ada.

• Contoh: jika key berupa NIM (8 digit) berarti harus ada alamat 00000000 sampai 99999999

Page 4: STRUKTUR DATA (12) organisasi berkas (file)

File Sekuensial Berindeks

• Record disimpan secara berurutan (beruntun)

• Record yang masuk lebih dahulu disimpan pada alamat yang lebih kecil daripada record yang disimpan kemudian

• Untuk menemukan record, harus dilakukan pencarian lebih dahulu

• Cara ini fleksible karena ukuran file dapat disesuaikan dengan jumlah record yang ada.

Page 5: STRUKTUR DATA (12) organisasi berkas (file)

Metode Hashing

• Untuk mengatasi kerugian korespondensi satu-satu, digunakan hashing

• Untuk mengurangi banyaknya ruang alamat yang digunakan untuk pemetaan dari key yang memiliki cakupan yang luas ke nilai alamat yang memiliki cakupan yang dipersempit

• Untuk itu dibutuhkan fungsi HASH• Output fungsi HASH adalah home address dari

record yang keynya diproses• Fungsi : f(key) = address

Page 6: STRUKTUR DATA (12) organisasi berkas (file)

Macam-macam Fungsi HASH

• Fungsi modulo• Home address dicari dengan cara

mencari sisa hasil bagi nilai key dengan suatu nilai tertentu.

• Fungsi: f(key) = key mod n• Dengan n adalah:

• Banyaknya ruang alamat yang tersedia• Atau bilangan prima terdekat yang berada di

atas nilai banyak data, setelah itu banyaknya ruang alamat disesuaikan dengan n

Page 7: STRUKTUR DATA (12) organisasi berkas (file)

Macam-macam Fungsi HASH

• Fungsi Pemotongan• Home address dicari dengan memotong nilai key

ke jumlah digit tertentu yang lebih pendek.• Contoh: NIM yang tadinya 8 digit, dipotong hanya

menjadi 2 digit!• Fungsi Pelipatan

• Dilakukan pelipatan terhadap record key dengan bagian yang sama panjang, lalu setiap bagian dijumlahkan

• NIM 8 digit dibagi dua digit, hingga menjadi 4 buah.

• Misal: 22002521, dibagi 22 00 25 21 kemudian dijumlahkan: 68

Page 8: STRUKTUR DATA (12) organisasi berkas (file)

Macam-macam Fungsi HASH

• Fungsi Pengkuadratan• Home address dicari dengan mengkuadratkan

setiap digit pembentuk key, lalu semua hasilnya dijumlahkan

• Contoh: 22002211, semua digit dikuadratkan dan dijumlah

• Fungsi Penambahan Kode ASCII• Jika key bukan kode numerik, home address

dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk key

• ADE = 65 + 68 + 69 = 192

Page 9: STRUKTUR DATA (12) organisasi berkas (file)

Collision (Tabrakan)

• Dengan menggunakan hashing, maka hubungan korespondensi satu-satu antara record key dengan alamat record akan hilang

• Selalu ada kemungkinan dimana terdapat dua buah record dengan key yang berbeda namun memiliki home address yang sama = tabrakan

Page 10: STRUKTUR DATA (12) organisasi berkas (file)

Kriteria Fungsi HASH yang baik

• Dapat mendistribusikan setiap record secara merata, sehingga dapat meminimalkan terjadinya tabrakan

• Dapat dieksekusi secara efisien sehingga waktu tidak habis untuk menghitung home address nya saja

Page 11: STRUKTUR DATA (12) organisasi berkas (file)

Collision Resolution

• Karena collision dapat dipastikan akan dapat terjadi, maka output dari suatu fungsi hash tidak selalu unik, namun hanya berupa kemungkinan suatu alamat yang dapat ditempati

• Jika suatu home address sudah ditempati oleh record lain, maka harus dicarikan alamat lain

• Proses pencarian alamat lain tersebut disebut collision resolution

Page 12: STRUKTUR DATA (12) organisasi berkas (file)

Metode Collision Resolution

• Open Addressing• Chaining• Coalesced Hashing• Chained Progressive Overflow• Bucket

Page 13: STRUKTUR DATA (12) organisasi berkas (file)

Metode Open Addressing

• Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong

• Cara:• Linear Probing

• Pencarian dilakukan dengan jarak pencarian tetap• Quardratic Probing

• Pencarian dilakukan dengan jarak pencarian berubah dengan perubahan tetap

• Double Hashing• Pencarian dilakukan menggunakan fungsi hash kedua.

Pertama hash untuk mencari home address, kedua untuk pencarian jika terjadi collision. Fungsi hash kedua tidak boleh menghasilkan nilai 0

Page 14: STRUKTUR DATA (12) organisasi berkas (file)

Contoh Liniear Probing

• F(key) = key mod 10• Ruang memori tersedia 10

alamat• Probing jarak 3• Urutan kunci: 20, 31, 33, 40, 10,

12, 30, 15

Page 15: STRUKTUR DATA (12) organisasi berkas (file)

Jawaban Linier Probing

Key F Proses Addr

20 0 0 0

31 1 1 1

33 3 3 3

40 0 0,3,6 6

10 0 0,3,6,9 9

12 2 2 2

30 0 0,3,6,9,2,5 5

15 5 5,8 8

0 20

1 31

2 12

3 33

4

5 30

6 40

7

8 15

9 10

Page 16: STRUKTUR DATA (12) organisasi berkas (file)

Soal Quadratic Probing

Soal sama, hanya Quadratic Probing, perubahan jarak 1

Page 17: STRUKTUR DATA (12) organisasi berkas (file)

Studi Kasus Stack (4)

• Kemudian lakukan langkah yang sama, sampai selesai.

• Pada contoh: operator + dipop dari Stack Soal, pop Stack Hasil dua kali, yaitu 3, disimpan pada variabel a, dan 2, disimpan pada variabel b. Kemudian lakukan operasi sesuai dengan operatornya, b <operator> a

• Jadi b + a, yaitu 8 + 3 = 11.

Page 18: STRUKTUR DATA (12) organisasi berkas (file)

Infix to Postfix Algorithm

• Scan the Infix string from left to right. • Initialise an empty stack. • If the scannned character is an operand, add it to the Postfix

string. If the scanned character is an operator and if the stack is empty Push the character to stack.

• If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack).

• If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.

• Repeat this step till all the characters are scanned. • (After all characters are scanned, we have to add any character

that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.

• Return the Postfix string.

Page 19: STRUKTUR DATA (12) organisasi berkas (file)

Contoh

• a+b*c-d• Stack (kosong) dan Postfik (kosong)

• Scan a• Postfik: a

• Scan +• Stack: +

• Scan b• Postfik: ab

• Scan *, karena ToS (+) < *, maka add ke Stack• Stack: +*

Page 20: STRUKTUR DATA (12) organisasi berkas (file)

Contoh

• Scan c• Postfik: abc

• Scan –, karena * > -, maka pop Stack, dan add ke Postfik• Stack: +• Postfik: abc*• Karena + <= -, maka pop Stack, dan add ke Postfik, karena

Stack kosong, maka push – ke stack• Stack: -• Postfik: abc*+

• Scan d• Postfik: abc*+d

• Karena sudah habis, push ToS stack ke Posfix• Postfix: abc*+d-

Page 21: STRUKTUR DATA (12) organisasi berkas (file)

Queue Dengan Array

• Bersifat FIFO• Elemen yang pertama masuk ke antrian akan keluar

pertama kalinya• DEQUEUE adalah mengeluarkan satu elemen dari suatu

Antrian• Antrian dapat dibuat dengan menggunakan: Liniear Array

dan Circular Array

Page 22: STRUKTUR DATA (12) organisasi berkas (file)

Queue Linier Array

• Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya

• Sehingga membutuhkan 2 variabel: Head dan Tail

Page 23: STRUKTUR DATA (12) organisasi berkas (file)

Queue (2)

• Operasi-operasi:Create()

• Untuk menciptakan dan menginisialisasi Queue

• Dengan cara membuat Head dan Tail = -1

Page 24: STRUKTUR DATA (12) organisasi berkas (file)

Queue (3)

Page 25: STRUKTUR DATA (12) organisasi berkas (file)

Queue (4)

• IsEmpty()• Untuk memeriksa apakah Antrian sudah penuh

atau belum• Dengan cara memeriksa nilai Tail, jika Tail = -1

maka empty• Kita tidak memeriksa Head, karena Head adalah

tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah

• Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail

Page 26: STRUKTUR DATA (12) organisasi berkas (file)

Queue (5)

Page 27: STRUKTUR DATA (12) organisasi berkas (file)

Queue (6)

Fungis IsFull• Untuk mengecek apakah Antrian sudah penuh

atau belum• Dengan cara mengecek nilai Tail, jika Tail >=

MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh

Page 28: STRUKTUR DATA (12) organisasi berkas (file)

Queue (7)

Enqueue• Untuk menambahkan elemen ke dalam

Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang

• Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu

Page 29: STRUKTUR DATA (12) organisasi berkas (file)

Queue (8)

Page 30: STRUKTUR DATA (12) organisasi berkas (file)

Queue (9)

• Dequeue()• Digunakan untuk menghapus elemen

terdepan/pertama (head) dari Antrian• Dengan cara menggeser semua elemen

antrian kedepan dan mengurangi Tail dgn 1

• Penggeseran dilakukan dengan menggunakan looping

Page 31: STRUKTUR DATA (12) organisasi berkas (file)

Queue (10)

Page 32: STRUKTUR DATA (12) organisasi berkas (file)

Queue (11)

• Clear()• Untuk menghapus elemen-elemen Antrian

dengan cara membuat Tail dan Head = -1• Penghapusan elemen-elemen Antrian

sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca

Page 33: STRUKTUR DATA (12) organisasi berkas (file)

Queue (12)

Page 34: STRUKTUR DATA (12) organisasi berkas (file)

Queue (13)

• Tampil()• Untuk menampilkan nilai-nilai elemen

Antrian• Menggunakan looping dari head s/d tail

Page 35: STRUKTUR DATA (12) organisasi berkas (file)

Soal

• Tambahkanlah function untuk mencari suatu elemen dalam queue & stack

• Tambahkan function untuk mengedit suatu elemen dalam queue & stack

• Carilah nilai total, rata-rata, terbesar dan terkecil dari elemen-elemen queue dalam function tersendiri

NEXT : Pengenalan Pointer dan Function