laporan resmi bab 5

22
LAPORAN PRAKTIKUM RESMI BAB V SEARCHING Disusun oleh : Analis Hasby Azizah 201301043 Dosen pengampu : Yosef Murya Kusuma Ardhana.S.T., M.Kom JURUSAN SISTEM INFORMASI SEKOLAH TINGGI ILMU KOMPUTER YOS SUDARSO PURWOKERTO 2014

Upload: arthur-bartlett

Post on 29-Dec-2015

11 views

Category:

Documents


1 download

DESCRIPTION

laporan

TRANSCRIPT

LAPORAN PRAKTIKUM RESMI

BAB V SEARCHING

Disusun oleh :

Analis Hasby Azizah

201301043

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

A. Pengantar

Menurut YM Kusuma Ardhana dalam bukunya Struktur Data Dalam Ilustrasi Eclipse Indigo

C++, pencarian (searching) adalah tindakan untuk mendapatkan suatu data dalam kumpulan

data. Metode pencarian data ada dua macam, pertama pencarian sekuensial (sequential search)

dan pencarian biner (binary search).

B. Pencarian Sekuensial (Sequential Search)

Pencarian sekuensial (sequential search) merupakan model pencarian paling sederhana yang

dilakukan terhadap suatu kumpulan data. Metode ini juga dikenal dengan nama pencarian lurus

(linear search).

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

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

Rumus : L[i] = k

i adalah bilangan indeks 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 ← indeks

Misalkan elmen yang dicari adalah 4 ( untuk posisi pertama ).

Dalam hal ini k = 4 dan k ditemukan di posisi indeks ke 3.

Perintah tersebut merupakan implementasi algoritma secara sekuensial yang menghasilkan

nilai berupa :

a. -1 jika data yang dicari tidak ada.

b. Bilangan antara 0 s/d n-1 (dengan n adalah jumlah elmen larik) jika data yang dicari telah

ditemukan.

3

C. Pencarian Biner (Binary Search)

Pencarian biner merupakan algoritma yang digunakan untuk kebutuhan pencarian data dengan

waktu yang tepat. Contohnya saat mencari arti kata dalam kamus bahasa inggiris.

Prinsip pencarian dengan metode biner atau membagi menjadi dua bagian mengilhami

algoritma pencarian bagi dua. Data yang tersimpan di dalam larik harus sudah dalam keadaan

terurut.

Misalkan indeks kiri adalah i dan indeks kanan adalah j. Awalnya inisialisasi i dengan 1 dan j

dengan n.

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

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

↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑

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

D. PENCARIAN PADA STRING

Pencarian pada string yaitu pencarian suatu huruf pada sebuah kalimat. Sebagai contoh

terdapat kalimat “ hallo stikom yos sudarso :, didalam kalimat tersebut yang dicari adalah

huruf “ y “. Maka yang akan ditampilkan posisi dari huruf “ y “ tersebut yaitu di posisi 13.

4

BAB II

PENJELASAN PROGRAM

A. Latihan Praktikum

Pada bab ini akan membahas tentang listing program pada bagian modul yang telah digunakan

untuk latihan pada pertemuan keempat.

Listing Program 5.1

/* * 5.1.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> using namespace std; int cari(int data [], int n, int k) /* Parameter fungsi cari */ { int posisi, i, ketemu; /* Pendeklarasian tipe data integer untuk fungsi cari */ if (n<=0) /* Jika n kurang dari sama dengan 0 maka posisi di – 1 */ posisi = -1; else { ketemu = 0; /* Jika tidak memenuhi maka data ada, ketemu = 0 */ i = 1; /* i bernilai 1 */ while ((i<n-1) && !ketemu) if (data [i] == k) { posisi = i; ketemu = i; } else i++; /* nilai i akan terus bertambah 1 jika pernyataan if belum terpenuhi */ if (!ketemu) posisi = -1; } return posisi; /*perulangan akan terus berjalan selama pernyataan while belum terpenuhi */ } int main()

5

{ /* Pendeklarasian variabel untuk main program */ int data[8]={10, 9, 6, 4, 7, 5, 4, 1}; int dicari; cout<<"Masukkan Angka : "; cin>>dicari; cout<<"posisi "<<dicari<<"ada dalam larik data ke :"<<cari(data,8,dicari)<<"\n"; /* pemanggilan fungsi cari dengan parameter aktualnya */ return 0; }

Output Program 5.1

Penjelasan Program 5.1

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. int data berupa bilangan bulat.

4. int main() untuk mengawali suatu program.

5. cout<< menampilkan data ke layar.

6. cin>>memasukkan data.

Listing Program 5.2

/* * 5.2.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> using namespace std; int caribiner(int data[], int n, int k) /*Parameter fungsi caribiner */ { int ada, atas, bawah, tengah, posisi; /* Deklarasi variabel untuk fungsi cari biner */ ada=0; bawah=0; atas=n-1;

6

while (atas>=bawah) { tengah=(atas+bawah)/2; /* nilai posisi tengah sama dengan (atas + bawah):2 */ if (k>data[tengah]) /* jika k>data[tengah] maka nilai posisi bawah sama dengan tengah + 1 */ bawah=tengah+1; else if (k<data[tengah]) /* jika tidak, k<data[tengah] maka atas sama dengan tengah – 1 */ atas=tengah-1; else { ada=1; /* ketemu datanya */ posisi=tengah; bawah=atas+1; /* akhir perulangan */ } } if (!ada) /* jika tidak ada posisi -1 */ posisi=-1; return posisi; } int main () { int data[]={10, 9, 7, 6, 5, 4, 3, 1}; int dicari; cout<<"Masukkan Angka : "; cin>>dicari; cout<<" Posisi "<<dicari<<"dalam larik data : " <<caribiner(data, 8, dicari)<<"\n"; /* pemanggilan fungsi cari biner dengan parameter aktualnya */ return 0; }

Output Program 5.2

Penjelasan Program 5.2

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. int data berupa bilangan bulat.

4. int main() untuk mengawali suatu program.

7

5. cout<< menampilkan data ke layar.

6. cin>>memasukkan data.

Listing Program 5.3

/* * 5.3.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> #include <cstring> using namespace std; int string_kar(char st[], char k) /* parameter fungsi string_kar */ { int i, posisi, panjang; /* deklarasi variabel untuk fungsi string_kar */ i=0; posisi =-1; panjang=strlen(st); while ((i<panjang-1) && posisi ==-1) { if (st[i] ==k) /* Jika (st[i] == k) maka posisi = i */ posisi=i; i++; /* i akan bertambah sampai pernyataan while terpenuhi */ } return posisi; } int main() { /* pendeklarasian untuk main program */ char kalimat[]= "Hallo stikom yos sudarso"; char dicari; cout<<" Masukkan Huruf : "; cin>>dicari; cout<<" Posisi "<< dicari <<" didalam string " << kalimat <<": "<<string_kar(kalimat, dicari)<<"\n"; /* pemanggilan fungsi string_kar untuk paramter aktualnya */ return 0; }

8

Output Program 5.3

Penjelasan Program 5.3

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. #include<cstring> untuk menampilkan deklarasi strlen.

3. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

4. int data berupa bilangan bulat.

5. char data berupa karakter.

6. int main() untuk mengawali suatu program.

7. cout<< menampilkan data ke layar.

8. cin>>memasukkan data.

B. Tugas Praktikum

Listing Program 5.1 Typedef

/* * typedf5.1.cpp * * Created on: Apr 20, 2014 * Author: My */ /* Pendeklarasian file header */ #include <iostream> using namespace std; /*pendeklarasian tipe data baru */ typedef int bil; bil cari(bil data [], bil n, bil k) /* parameter fungsi cari */ { bil posisi, i, ketemu; if (n<=0) posisi = -1; else {

9

ketemu = 0; i = 1; while ((i<n-1) && !ketemu) if (data [i] == k) { posisi = i; ketemu = i; } else i++; if (!ketemu) posisi = -1; } return posisi; } int main() { bil data[8]={10, 9, 6, 4, 7, 5, 4, 1}; bil dicari; cout<<"Masukan Angka : "; cin>>dicari; cout<<"posisi "<<dicari<<"ada dalam larik data ke :"<<cari(data,8,dicari)<<"\n"; return 0; }

Output Program 5.1 Typedef

Penjelasan Program 5.1 Typedef

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. typedef int bil merubah nama tipe data int menjadi bil.

4. int data berupa bilangan bulat.

5. int main() untuk mengawali suatu program.

6. cout<< menampilkan data ke layar.

7. cin>>memasukkan data.

10

Listing Program 5.1 Struct

/* * search1.cpp * * Created on: Apr 14, 2014 * Author: rama */ /* Pendeklarasian file header */ #include <iostream> using namespace std; /*langsung dianggap variabel tempat */ struct { int posisi; int i; int ketemu; } tempat; int cari(int data[], int n, int k) { if(n<=0) tempat.posisi=-1; else { tempat.ketemu=0; tempat.i=1; while((tempat.i<n-1) && !tempat.ketemu) if(data[tempat.i] == k) { tempat.posisi=tempat.i; tempat.ketemu=tempat.i; } else tempat.i++; if (!tempat.ketemu) tempat.posisi=-1; } return tempat.posisi; } int main() { int data[8]={10,9,6,4,7,5,4,1}; int dicari; cout<<"Masukkan data yang akan dicari : "; cin>>dicari; cout<<"posisi "<<dicari<<" ada dalam larik data ke : "<<cari(data,8,dicari)<<"\n"; return 0; }

11

Output Program 5.1 Struct

Penjelasan Program 5.1 Struct

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. struct digunakan untuk membuat tipe data agregate

4. int data berupa bilangan bulat.

5. int main() untuk mengawali suatu program.

6. cout<< menampilkan data ke layar.

7. cin>>memasukkan data.

Listing Program 5.1 Typedef Struct

/* * 5.1typedefstruct.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> using namespace std; /*pendeklarasian tipe data baru struct mencari */ typedef struct mencari { int posisi; int i; int ketemu; }; int cari(int data[], int n, int k) { mencari tempat; /* variabel tempat bertipe data mencari */ if(n<=0) tempat.posisi=-1; else { tempat.ketemu=0; tempat.i=1;

12

while((tempat.i<n-1) && !tempat.ketemu) if(data[tempat.i] == k) { tempat.posisi=tempat.i; tempat.ketemu=tempat.i; } else tempat.i++; if (!tempat.ketemu) tempat.posisi=-1; } return tempat.posisi; } int main() { int data[8]={10,9,6,4,7,5,4,1}; int dicari; cout<<" Masukkan Angka : "; cin>>dicari; cout<<"posisi "<<dicari<<" ada dalam larik data ke : "<<cari(data,8,dicari)<<"\n"; return 0; }

Output Program 5.1 Typedef Struct

Penjelasan Program 5.1 Typedef Struct

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. typedef struct mencari mendeklarasikan tipe data baru struct mencari.

4. mencari tempat; variabel tempat bertipe data mencari.

5. int data berupa bilangan bulat.

6. int main() untuk mengawali suatu program.

7. cout<< menampilkan data ke layar.

8. cin>>memasukkan data.

13

Listing Program 5.2 Typedef

/* * typedef5.2.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> using namespace std; /* pendeklarasian tipe data baru */ typedef int biner; biner caribiner(biner data[], biner n, biner k) { biner 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<data[tengah]) atas=tengah-1; else { ada=1; posisi=tengah; bawah=atas+1; } } if (!ada) posisi=-1; return posisi; } int main () { biner data[]={10, 9, 7, 6, 5, 4, 3, 1}; biner dicari; cout<<"Masukkan Angka : "; cin>>dicari; cout<<" Posisi "<<dicari<<"dalam larik data : " <<caribiner(data, 8, dicari)<<"\n"; return 0; }

14

Output Program 5.2 Typedef

Penjelasan Program 5.2 Typedef

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. typedef int biner; merubah nama tipe data int menjadi biner.

4. mencari tempat; variabel tempat bertipe data mencari.

5. int data berupa bilangan bulat.

6. int main() untuk mengawali suatu program.

7. cout<< menampilkan data ke layar.

8. cin>>memasukkan data.

Listing Program 5.2 Struct

/* * str5.2.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> using namespace std; /* langsung di anggap variabel biner */ struct { int ada; int atas; int bawah; int tengah; int posisi; } biner; int caribiner(int data[], int n, int k) { biner.ada=0; biner.bawah=0; biner.atas=n-1;

15

while (biner.atas>=biner.bawah) { biner.tengah=(biner.atas+biner.bawah)/2; if (k>data[biner.tengah]) biner.bawah=biner.tengah+1; else if (k<data[biner.tengah]) biner.atas=biner.tengah-1; else { biner.ada=1; biner.posisi=biner.tengah; biner.bawah=biner.atas+1; } } if (!biner.ada) biner.posisi=-1; return biner.posisi; } int main () { int data[]={10, 9, 7, 6, 5, 4, 3, 1}; int dicari; cout<<"Masukkan Angka : "; cin>>dicari; cout<<" Posisi "<<dicari<<"dalam larik data : " <<caribiner(data, 8, dicari)<<"\n"; return 0; }

Output Program 5.2 Struct

Penjelasan Program 5.2 Struct

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. struct digunakan untuk membuat tipe data agregate

4. int data berupa bilangan bulat.

5. int main() untuk mengawali suatu program.

6. cout<< menampilkan data ke layar.

7. cin>>memasukkan data.

16

Listing Program 5.2 Typedef Struct

/* * typdefstr5.2.cpp * * Created on: Apr 21, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> using namespace std; /* pendeklarasian tipe data baru struct mencari */ typedef struct mencari { int ada; int atas; int bawah; int tengah; int posisi; }; int caribiner(int data[], int n, int k) { mencari biner; /* variabel biner bertipe data mencari */ biner.ada=0; biner.bawah=0; biner.atas=n-1; while (biner.atas>=biner.bawah) { biner.tengah=(biner.atas+biner.bawah)/2; if (k>data[biner.tengah]) biner.bawah=biner.tengah+1; else if (k<data[biner.tengah]) biner.atas=biner.tengah-1; else { biner.ada=1; biner.posisi=biner.tengah; biner.bawah=biner.atas+1; } } if (!biner.ada) biner.posisi=-1; return biner.posisi; } int main () { int data[]={10, 9, 7, 6, 5, 4, 3, 1}; int dicari; cout<<"Masukkan data : "; cin>>dicari;

17

cout<<" Posisi "<<dicari<<"dalam larik data : " <<caribiner(data, 8, dicari)<<"\n"; return 0; }

Output 5.2 Typedef Struct

Penjelasan Program 5.2 Typedef Struct

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. typedef struct mencari mendeklarasikan tipe data baru struct mencari.

4. mencari biner; variabel biner bertipe data mencari.

5. int data berupa bilangan bulat.

6. int main() untuk mengawali suatu program.

7. cout<< menampilkan data ke layar.

8. cin>>memasukkan data.

Listing Program 5.3 Typedef

/* * typedef.5.3.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include <iostream> #include <cstring> using namespace std; /* Pendeklarasian tipe data baru */ typedef int banyak; typedef char huruf; banyak string_kar(huruf st[], huruf k) { banyak i, posisi, panjang; i=0; posisi =-1;

18

panjang=strlen(st); while ((i<panjang-1) && posisi ==-1) { if (st[i] ==k) posisi=i; i++; } return posisi; } int main() { huruf kalimat[]= "Hallo stikom yos sudarso"; huruf dicari; cout<<"Masukkan Huruf : "; cin>>dicari; cout<<" Posisi "<< dicari <<" didalam string " << kalimat <<": "<<string_kar(kalimat, dicari)<<"\n"; return 0; }

Output Program 5.3 Typedef

Penjelasan Program 5.3 Typedef

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. typedef int banyak; merubah nama tipe data int menjadi banyak.

4. typedef char huruf; merubah nama tipe data char menjadi huruf.

5. mencari tempat; variabel tempat bertipe data mencari.

6. int data berupa bilangan bulat.

7. int main() untuk mengawali suatu program.

8. cout<< menampilkan data ke layar.

9. cin>>memasukkan data.

Listing Program 5.3 Struct

/* * Citra5.3TypedefStruct.cpp * * Created on: Apr 22, 2014 * Author: Citra */

19

/* Pendeklarasian file header */ #include<iostream> #include<cstring> using namespace std; /* langsung dianggap variabel esa */ struct { int i, posisi, panjang; char kalimat[30], dicari; } esa; int string_kar(char st[], char k) { esa.i=0; esa.posisi=-1; esa.panjang=strlen(st); while((esa.i<esa.panjang-1) && esa.posisi==-1) { if(st[esa.i] == k) esa.posisi=esa.i; esa.i++; } return esa.posisi; } int main() { esa.kalimat[30]; esa.dicari; cout<<"Masukkan sebuah kalimat\nEx\t: Hello stikom yos sudarso\nIn\t: "; cin>>esa.kalimat; cout<<"Masukkan letak huruf yang akan dicari : "; cin>>esa.dicari; cout<<"Posisi "<<esa.dicari<<" didalam string "<<esa.kalimat<<" : "<<string_kar(esa.kalimat, esa.dicari)<<"\n"; return 0; }

Output Program 5.3 Struct

20

Penjelasan Program 5.3 Struct

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2 using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. struct digunakan untuk membuat tipe data agregate

4. int data berupa bilangan bulat.

5. char data berupa karakter.

6. int main() untuk mengawali suatu program.

7. cout<< menampilkan data ke layar.

8. cin>>memasukkan data.

Listing Program 5.3 Typedef Struct

/* * typedefstruct5.3.cpp * * Created on: Apr 20, 2014 * Author: Analis */ /* Pendeklarasian file header */ #include<iostream> #include<cstring> using namespace std; /*pendeklarasian tipe data baru struct sp */ typedef struct sp { int i; int posisi; int panjang; }; int string_kar(char st[], char k) { sp esa; /* variabel esa bertipe data sp */ esa.i=0; esa.posisi=-1; esa.panjang=strlen(st); while((esa.i<esa.panjang-1) && esa.posisi==-1) { if(st[esa.i] == k) esa.posisi=esa.i; esa.i++; } return esa.posisi; } int main() {

21

char kalimat[]="Hallo stikom yos sudarso"; char dicari; cout<<" => "<<kalimat<<endl; cout<<"Masukkan huruf yang akan dicari : "; cin>>dicari; cout<<"Posisi "<<dicari<<" didalam string "<<kalimat<<" : "<<string_kar(kalimat, dicari)<<"\n"; return 0; }

Output Program 5.3 Typedef Struct

Penjelasan Program 5.3 Typedef Struct

1. #include <iostream> untuk menampilkan deklarasi yang ada pada cout.

2. using namespace std; untuk mengakses perintah – perintah yang ada pada library standard.

3. typedef struct sp mendeklarasikan tipe data baru struct sp.

4. sp esa; variabel esa bertipe data sp.

5. int data berupa bilangan bulat.

6. char data berupa karakter.

7. int main() untuk mengawali suatu program.

8. cout<< menampilkan data ke layar.

9. cin>>memasukkan data.

22

BAB III

KESIMPULAN

Pencarian atau searching digunakan untuk mendapatkan suatu data dari kumpulan data.

Ada dua metode yang digunakan dalam searching yaitu metode pencarian sekuensial (sequential

search) atau yang bisa disebut juga pencarian lurus (linear seacrh) dan pencarian biner (binary

search). Pencarian data ini bisa digunakan untuk mencari data berupa angka atau huruf. Selain itu

dalam pencarian data juga dapat memanipulasi suatu data dengan menggunakan tipe data abstrak

berupa typedef, struct atau typedef struct.