laporan praktikum resmi - searching

LAPORAN PRAKTIKUM RESMI

ALGORITMA & STRUKTUR DATA 1

SEARCHING

Disusun oleh :

Cintia Yosfin Samalle

201301041

Dosen pengampu :

Yosef Murya Kusuma Ardhana.S.T., M.Kom

JURUSAN SISTEM INFORMASI SEKOLAH TINGGI ILMU KOMPUTER YOS SUDARSO

PURWOKERTO 2014

2

BAB I

TEORI DASAR

1. PENGERTIAN Pencarian (searching) adalah tindakan untuk mendapatkan suatu data dalam

kumpulan data. Untuk keperluan pencarian data, terdapat beragam algoritma pencaraian

(search algorithm).

Menurut Tenenbaum dan Augenstein, algoritma pencaraian yaitu algoritma yang

menerima sebuah argumen X dan mencoba untuk menemukan sebuah rekaman yang

memiliki kunci X. Sebagai contoh pencarian data mahasiswa dengan NIM 201301041, maka

hasilnya adalah record yang berisi data mahasiswa tersebut yang didalamnya kemungkinan

berisi nama, alamat, tempat tanggal lahir, dan program studi.

Pencarian dibagi menjadi beberpa bagian, yaitu :

Pencarian internal adalah pencarian data yang berada di dalam memory komputer.

Pencarian eksternal adalah pencarian data yang berada di dalam server lain yang

berasal dari luar komputer.

Contoh kasus pencarian dalam kehidupan sehari-hari :

Mencari istilah dalam kamus

Mencari nomor teman yang berada dalam phonebook

Mencari data mahasiswa, dll

2. PENCARIAN SEKUENSIAL (SEQUENTIAL SEARCH) Pencarian sekuensial (sequential search) adalah model pencarian yang sederhana

yang dilakukan terhadap suatu kumpulan data. Nama lain dari metode pencarian sekuensial

adalah pencarian lurus (linear search).

Terdapat L yang merupakan larik (array) yang berisi n buah data

(L[0],L[1],..,L[n-1]) dan k adalah data yang dicari.

Rumus : L[i]=k

3

i adalah bilangan index terkecil yang memenuhi kondisi 0 < k < n-1

Contoh kasus :

L [10, 9, 6, 4, 7, 5, 4, 1]

0 1 2 3 4 5 6 7 index

Misalkan elemen data yang dicari adalah 4 (untuk posisi pertama).

Dalam hal ini k=4 dan k ditemukan diposisi di index ke 3.

Subrutin (perintah) tersebut merupakan implementasi algoritma secara sekuensial, dalam hal

ini menghasilkan nilai balik berupa :

a. -1 jika data yang dicari tidak ditemukan

b. Bilangan antara 0 sampai dengan n-1 (dengan n adalah jumlah elemen larik) jika data

yang dicari telah ditemukan.

3. PENCARIAN BINER (BINARY SEARCH) Pencarian biner merupakan algoritma yang digunakan untuk kebutuhan pencarian

data dengan waktu yang cepat. Contoh pencarian data yang dengan algoritma biner dalam

kehidupan sehari-hari yaitu ketika melakukan pencarian arti kata tertentu didalam kamus

bahasa inggris. Kita tidak akna membuka kamus dari halam awal sampaia akhir satu pesatu

saat mencari arti kata tertentu, namun kita akan mencarinya dengan cara membelah atau

membagi halaman kamus tersebut. Jika kata yang dicari tidak terletak di halaman

pertengahan itu, maka kita dapat mencari dibagian belahan sebelah kiri atau belhan sebelah

kanan dengan cara membagi dua belhan yang dimaksud. Begitu seterusnya sampai akhir

kata yang dicari ditemukan.

Prinsip pencarian dengan menggunakan metode biner atau membagi menjadi dua

bagian mengilhami algoritma pencarian bagi dua. Data yang tersimpan di dalam larik harus

sudah dlam keadaan terurut.

4

Misalkan index kiri adlah I dan index kanan adalah j. pada mulanya diinisialisasi I dengan 1

dan j dengan n.

Misalkan diberikan larik L dengan delapan buah elemen yang sudah terurut :

L [10, 9, 7, 6, 5, 4, 3, 1]

i=1 2 3 4 5 6 7 j=8

4. PENCARIAN PADA STRING Pencarian pada string yaitu pencarian suatu huruf pada sebuah kalimat. Sebagai contoh

terdapat kalimat selamat datang di stikom yos sudarso, didalam kalimat yang

dicariadalah huruf y. Maka yang akan ditampilkan posisi huruf y tersebut yaitu

diposisi ke 26.

5

BAB II

PENJELASAN PROGRAM

Pada penjelasan program bab ini akan dijelaskan mengenai bagaimana melakukan pemrograman C++ secara sederhana sesuai dengan modul praktikum Searching.

Listing Program 5.1

/* * Praktikum5.1.cpp * * Created on: Apr 14, 2014 * Author: STIKOM32 */ #include using namespace std; int cari(int data[], int n , int k) { int posisi,i,ketemu; if (n

6

Output Program 5.1

Hasil output dari Program 5.1 adalah sebagai berikut :

Pembahasan Program

1. Tanda yang diawali dengan /* dan diakhiri tanda */ merupakan script untuk membuat sebuah komentar pada pemrograman C++ yang jika didalamnya terdapat sebuah perintah atau teks maka ketika program dirunning atau dijalankan tidak akan dibaca oleh compiler.

2. #include atau disebut sebagai pengarah preprocessor #include berfungsi untuk menginstruksikan compiler untuk menyertakan berkas C++ sumber yang lain sebelum kompilasi dimulai.

3. untuk memanggil fungsi cout dan cin dalam C++. 4. using namespace std; adalah standar deviasi dalam sebuah program dalam bahasa

pemrograman C++. 5. Tanda kurung kurawal {} dimaksudkan untuk mengawali dan mengakhiri bagian main. 6. int cari dimaksudkan bahwa variable cari bertipe data integer. 7. int data[] maksudnya adalah variable data bertipe data integer dan yang dengan

penggunaan kurung siku disini maksudnya adalah untukmendeklarasikan array, dan karena kita belum mengetahui berapa elemen ndalam array tersebut maka cukup diberi tanda kurung saja tanpa isi apapun.

8. int n , int k maksudnya adalah variable n dan k bertipe data integer. 9. int posisi,i,ketemu maksudnya adalah variable posisi, i, ketemu bertipe data integer. 10. Tanda ; digunakan untuk mengakhiri sebuah pernyataan. 11. if (n

7

ketemu=i; } else i++; if(!ketemu) posisi=-1; Ini adalah rumus dalam program searching ini yang maksudnya adalah jika nilai n kurang dari atau sama dengan 0, maka posisi=-1, jika tidak maka nilai ketemu=0. i=1; maksudnya adalah sebuah penugasan yang maksudnya nilai i=1. while((i

8

tengah=(atas+bawah)/2; if(k>data[tengah]) bawah=tengah+1;

else if(k

9

7. int data[] maksudnya adalah variable data bertipe data integer dan yang dengan penggunaan kurung siku disini maksudnya adalah untukmendeklarasikan array, dan karena kita belum mengetahui berapa elemen ndalam array tersebut maka cukup diberi tanda kurung saja tanpa isi apapun.

8. int n , int k maksudnya adalah variable n dan k bertipe data integer. 9. int ada, atas, bawah, tengah, posisi maksudnya adalah variable ada, atas, bawah,

tengah, posisi bertipe data integer. 10. Tanda ; digunakan untuk mengakhiri sebuah pernyataan.

ada=0; bawah=0; atas=n-1; while (atas>=bawah) { tengah=(atas+bawah)/2; if(k>data[tengah]) bawah=tengah+1; else if(k

10

Listing Program 5.3

/* * program_praktikum5.3.cpp * * Created on: Apr 1, 2014 * Author: STIKOM32 */ #include #include "cstring" using namespace std; int string_kar(char st[], char k) { int i, posisi, panjang;

i=0; posisi=-1; panjang=strlen(st); while ((i

11

Pembahasan Program




pemrograman C++. 5. Tanda kurung kurawal {} dimaksudkan untuk mengawali dan mengakhiri bagian main. 6. int string_kar dimaksudkan bahwa variable tersebut bertipe data integer. 7. Char st[] maksudnya adalah variable st bertipe data integer dan yang dengan penggunaan

kurung siku disini maksudnya adalah untuk mendeklarasikan array, dan karena kita belum mengetahui berapa elemen ndalam array tersebut maka cukup diberi tanda kurung saja tanpa isi apapun.

8. char k maksudnya adalah variable n dan k bertipe data integer. 9. int i, posisi, panjang maksudnya adalah variable i, posisi, panjang bertipe data

integer. 10. Tanda ; digunakan untuk mengakhiri sebuah pernyataan. 11. int i, posisi, panjang;


12

17. return 0 dimaksudkan untuk menyatakan nilai balik main. 18. Tanda

13

cout

14

i=1; while((i

15

int caribiner(int data[], int n, int k) { int ada, atas, bawah, tengah, posisi; ada=0; bawah=0; atas=n-1; while (atas>=bawah) { tengah=(atas+bawah)/2; if (k>data[tengah]) bawah=tengah+1; else if (k

16

Pembahasan Program




pemrograman C++. 5. Tanda kurung kurawal {} dimaksudkan untuk mengawali dan mengakhiri bagian main. 6. int caribiner dimaksudkan bahwa variable cari bertipe data integer. 7. int data[] maksudnya adalah variable data bertipe data integer dan yang dengan



tengah, posisi bertipe data integer. 10. Tanda ; digunakan untuk mengakhiri sebuah pernyataan. 11. ada=0;

bawah=0; atas=n-1; while (atas>=bawah) { tengah=(atas+bawah)/2; if(k>data[tengah]) bawah=tengah+1; else if(k

17

14. int data[ ], maksudnya adalah variable data bertipe data integer mempunyai baris array, namun array tersebut balum diketahui jumlah elemennya.

15. cout

18

coutdicari; cout

19

panjang=strlen(st); while ((i

20

int posisi, i, ketemu; if (n

21

Pembahasan Program




pemrograman C++. 5. Tanda kurung kurawal {} dimaksudkan untuk mengawali dan mengakhiri bagian main. 6. int cari dimaksudkan bahwa variable cari bertipe data integer. 7. int data[] maksudnya adalah variable data bertipe data integer dan yang dengan



22

int dicari; }; struct bilangan angka Bilangan merupakan member atau anggota dari struct, variable dicari merupakan variable yang bertipe data integer, angka merupakan bagian dalam member bilangan dalam struct.

14. int main(),menyatakan tipe nilai balik fungsi main. 15. int data[8]={10,9,6,4,7,5,4,1}, maksudnya adalah variable data bertipe data integer

mempunyai elemen array sebanyak 8. 16. cout

23

} else i++; if (!ketemu) posisi=-1; } return posisi; } typedef int data; typedef int dicari; int main() { data angka[8]={10, 9, 6, 4, 7, 5, 4, 1}; dicari cari; coutcari; cout

24

7. int data[] maksudnya adalah variable data bertipe data integer dan yang dengan penggunaan kurung siku disini maksudnya adalah untukmendeklarasikan array, dan karena kita belum mengetahui berapa elemen ndalam array tersebut maka cukup diberi tanda kurung saja tanpa isi apapun.


25

19. return 0 dimaksudkan untuk menyatakan nilai balik main. 20. Tanda

26

coutangka.dicari; cout

27

i=1; while((i

28

Program 5.2 dengan menggunakan struct /* * Program2.cpp * * Created on: Apr 14, 2014 * Author: STIKOM32 */ #include using namespace std; int caribiner(int data[], int n, int k) { int ada, atas, bawah, tengah, posisi; ada=0; bawah=0; atas=n-1; while (atas>=bawah) { tengah=(atas+bawah)/2; if (k>data[tengah]) bawah=tengah+1; else if (k

29

return 0; } Output Program

Pembahasan Program






8. int n , int k maksudnya adalah variable n dan k bertipe data integer. 9. int ada, atas, bawah, tengah, posisi maksudnya adalah variable ada, atas,

bawah, tengah, posisi bertipe data integer. 10. Tanda ; digunakan untuk mengakhiri sebuah pernyataan. 11. ada=0;

bawah=0; atas=n-1; while (atas>=bawah) { tengah=(atas+bawah)/2; if(k>data[tengah]) bawah=tengah+1;

30

else if(k

31

* Author: STIKOM32 */ #include using namespace std; int caribiner(int data[], int n, int k) { int ada, atas, bawah, tengah, posisi; ada=0; bawah=0; atas=n-1; while (atas>=bawah) { tengah=(atas+bawah)/2; if (k>data[tengah]) bawah=tengah+1; else if (k

32

Ouput Program

Pembahasan Program









33

} } if (!ada) posisi=-1; Ini adalah rumus dalam program searching ini yang maksudnya adalah nilai ada dan nilai bawah adalah 0 dan nilai atas adalah n-1. While maksudnya adalah sebuah perulangan.

12. return posisi, membalikan nilai fungsi dari posisi. 13. typedef int data;

typedef int dicari; Typedef biasanya digunakan untuk memberikan nama alias untuk suatu tipe data.

14. data angka[]={10,9,7,6,5,4,3,1}; dicari cari;

15. Maksudnya adalah variable data bertipe data integer mempunyai baris array, namun array tersebut balum diketahui jumlah elemennya. Dan karena program ini menggunakan typedef yang berfungsi untuk memberi nama alias kepada suatu tipe data maka data diubah menjadi angka dan dicari diubah menajdi cari.

16. int main(),menyatakan tipe nilai balik fungsi main. 17. cout

34

ada=0; bawah=0; atas=n-1; while (atas>=bawah) { tengah=(atas+bawah)/2; if (k>data[tengah]) bawah=tengah+1; else if (k

35









36

int dicari; }; struct bilangan angka Typedef biasanya digunakan untuk memberikan nama alias untuk suatu tipe data. Bilangan merupakan member atau anggota dari struct, variable dicari merupakan variable yang bertipe data integer, angka merupakan bagian dalam member bilangan dalam struct.

14. data angka[]={10,9,7,6,5,4,3,1}; angka.dicari; Maksudnya adalah variable data bertipe data integer mempunyai baris array, namun array tersebut balum diketahui jumlah elemennya. Dan karena program ini menggunakan typedef yang berfungsi untuk memberi nama alias kepada suatu tipe data maka data diubah menjadi angka dan dicari diubah menajdi cari.


37

while ((i

38

4. using namespace std; adalah standar deviasi dalam sebuah program dalam bahasa pemrograman C++.

5. Tanda kurung kurawal {} dimaksudkan untuk mengawali dan mengakhiri bagian main. 6. int string_kar dimaksudkan bahwa variable tersebut bertipe data integer. 7. Char st[] maksudnya adalah variable st bertipe data integer dan yang dengan penggunaan





39

20. Tanda

40

Output Program

Pembahasan Program




pemrograman C++. 5. Tanda kurung kurawal {} dimaksudkan untuk mengawali dan mengakhiri bagian main. 6. int string_kar dimaksudkan bahwa variable tersebut bertipe data integer. 7. Char st[] maksudnya adalah variable st bertipe data integer dan yang dengan penggunaan





41

13. typedef int kalimat; typedef int dicari; Typedef biasanya digunakan untuk memberikan nama alias untuk suatu tipe data.

14. kalimat kata[]="Hallo stikom yos sudarso"; dicari cari; Maksudnya adalah variable kalimat bertipe data character mempunyai baris array, namun array tersebut balum diketahui jumlah elemennya. Dan karena program ini menggunakan typedef yang berfungsi untuk memberi nama alias kepada suatu tipe data maka data diubah menjadi angka dan dicari diubah menajdi cari.


42

} return posisi; } typedef struct kalimat { char dicari; }; struct kalimat kata; int main() { char kalimat[]="Hallo stikom yos sudarso"; kata.dicari; coutkata.dicari; cout

43

7. Char st[] maksudnya adalah variable st bertipe data integer dan yang dengan penggunaan kurung siku disini maksudnya adalah untuk mendeklarasikan array, dan karena kita belum mengetahui berapa elemen ndalam array tersebut maka cukup diberi tanda kurung saja tanpa isi apapun.




44

20. Tanda

45

BAB III

KESIMPULAN

Pencarian adalah tindakan untuk mendapatkan suatu data dalam kumpulan data tertentu, atau biasa disebut juga Searching.

Dan untuk keperluan pencarian data tersebut, terdapat beragam algoritma pencarian. Menurut Tenenbaum dan Augenstein algoritma pencarian yaitu algoritma yang menerima

argument X dan mencoba untuk menemukan sebuah rekeman yang memiliki kunci X. Pencarian Sekuensial (Sequential Search) adalah model pencarian yang paling

sedrhana yang dilakukan terhadap suatu kumpulan data. Pencarian Biner (Binary Search) adalah algoritma yang digunakn untuk kebutuhan

pencarian data dengan waktu yang cepat. Pencarian Pada String adalah pencarian suatu huruf pada sebuah kalimat.

46

BAB IV

DAFTAR PUSTAKA

1. Ardhana, YM Kusuma. 2013. Struktur Data dalam Ilustrasi Eclups Indigo C ++. Yogyakarta: CAPS (Center of Academic Publishing Service).

2. Kadir, Abdul. 2012. Buku Pintar C++ Untuk Pemula. Yogyakarta: MediaKom.

3. Modul praktikum algoritma dan struktur data 1 (bab 5 searching).

laporan praktikum resmi - searching

Documents